Single-Course English 5 ECTS

Integer Programming

Overall Course Objectives

Optimisation is one of the most important components of data science. Integer Programming lets you estabish optimal or near-optimal solutions for complex decision support problems within production, energy, transport etc. This courses gives the students a thorough introduction to formulating and solving integer programming problems. Participants will be able to formulate integer programming problems as well as applying it to a wide range of optimisationsproblem in order to utilise your data to its full capacity.

Learning Objectives

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

Course Content

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

Recommended prerequisites

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

Teaching Method

Lectures, exercises and project work.

See course in the course database.





13 weeks




DTU Lyngby Campus

Course code 42114
Course type Candidate
Semester start Week 35
Semester end Week 48
Days Tues 13-17

7.500,00 DKK