An application oriented tutorial on relaxations

Michael A. Trick
Carnegie Mellon University
Pittsburgh, PA 15213

February, 1996

• Contents
• Heuristics, Relaxations, and Branch and Bound
• Relaxations
  • Spanning Tree Relaxation
  • One-Tree Relaxation
  • Assignment Relaxation
• Branch and Bound
• Strengthening Relaxations
  • Lagrangian Relaxation
    • Application to the TSP
    • Application to Manpower Planning
• About this document ...