Single-Course Engelsk 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.

See course description in Danish

Learning Objectives

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

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.

Faculty

See course in the course database.

## Registration

Language Engelsk 13 weeks Management DTU Lyngby Campus 42114 Candidate Week 36 Week 49 Tues 13-17
Price 9.250,00 DKK