Integer Programming

• Define and describe what a mixed integer program, an integer program and a binary program is compared to a linear program
• Construct an integer programming model with objective function, constraints and variable definitions based on a simple textual description of the problem
• Define a formulation and show examples of how it is used in integer programming
• Apply bounds on an integer programming problem and evaluate its efficiency
• Define a relaxation and mention examples of relaxations from the course. Also define an LP relaxation and a Lagrangian relaxation
• Apply Lagrangian relaxation on a simpel IP problem
• Construct a branch-and-bound (B&B) algorithm for a standard IP problem
• Explain the meaning and contents of the central theorems within integer programming as selected in the course
• Demonstrate the use of valid inequalities and cuts in general and specifically with a given simple IP problem. Define Gomory cuts
• Describe the challenges when making the extension from valid inequality and cuts to a branch-and-cut algorithm (B&C)
• Describe on a high level the applications of B&B, B&C, upper and lower bounds when implementing an efficient solution method for simple IP problems (especially for TSP)
• Construct a dynamic programming algorithm for a simple problem based on “principle of optimality”, “stage” and “state”

Relaxation, duality, Branch & Bound, Cutting planes, Branch & Cut, Lagrange relaxation, Dynamic Programming, Strong Valid Inequalities. Application examples: project planning, vehicle routing, and production planning.

• 36 – 49 (Tues 13-17)

42101, The course requires the student to have taken an introductory course in Operations Research.

Lectures, exercises and project work.