Integer Programming

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

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

Lectures, exercises and project work.