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 ...