Single-Course Engelsk 5 ECTS

Integer Programming

Overall Course Objectives

Optimization is one of the most important components of data science. Integer Programming enables one to obtain optimal, or near-optimal, solutions to complex decision-making problems within, e.g., production, energy, and transport. This courses gives students a thorough introduction to formulating and solving integer programming problems. Participants will be able to formulate integer programming problems and apply them to a wide range of optimization problems in order to utilize data to its full capacity.

See course description in Danish

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 their effectiveness
Define a relaxation and mention examples of relaxations from the course. Also define an LP relaxation and a Lagrangian relaxation
Apply Lagrangian relaxation to a simple IP problem
Describe how to construct the branch-and-bound (B&B) tree to 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
Devise dynamic programming algorithms for simple problems 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.