Integer Programming

• define what a mixed integer program, an integer program and a binary program is compared to a linear program.
• identify possible solution approaches for a integer programming (IP) problem.
• construct an integer programming model with objective function, constraints and variable definitions based on a simple textual description of the problem.
• Define a relaxation and mention examples of relaxations from the course.
• construct a branch-and-bound (B&B) algorithm for a standard IP problem.
• give the meaning and contents of the central theorems within integer programming as selected in the course.
• define and describe the use of valid inequalities and cuts in general and specifically with a given simple IP problem.
• 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” .
• define Lagrangian relaxation for an IP problem and be able to use Lagrangian relaxation on a simpel IP problem.

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.