A Tutorial on Integer Programming

The Operations Research Faculty of GSIA

Summer 1997

These notes are meant as an adjunct to Chapter 9 in Winston. You are responsible for what appears in these notes as well as the portions of 9.1-9.3, 9.5, 9.8 that we cover in class.

• Contents
• Introduction
• Modeling with Integer Variables
  • Capital Budgeting
    • Multiperiod Capital Budgeting
  • Knapsack
  • The Lockbox Problem
  • Set Covering
    • Set Packing and Partitioning
  • Traveling Salesperson Problem
• Solving Integer Programs
  • Relationship to Linear Programming
  • Branch and Bound
  • Cutting Plane Techniques
    • General Cutting Planes
    • Cuts for Special Structure
• Heuristics
• Solutions to Some Optional Problems
• About this document ...