CloseHelpPrint
Kies de Nederlandse taal
Course module: 191581420
191581420
Mixed-Integer Optimization
Course info
Course module191581420
Credits (ECTS)5
Course typeCourse
Language of instructionEnglish
Contact persondr. M. Walter
E-mailm.walter@utwente.nl
Lecturer(s)
Lecturer
J. Hönen
Lecturer
R.P. van der Hulst
Contactperson for the course
dr. M. Walter
Examiner
dr. M. Walter
Academic year2022
Starting block
2A
Application procedureYou apply via OSIRIS Student
Registration using OSIRISYes
Aims
After following this course, the student:
  • can model discrete optimization problems as mixed-integer linear programming and prove model correctness;
  • is able to implement mixed-integer programming models by accessing solver software and critically interpret returned solutions;
  • can explain validity and algorithmic generation of general-purpose and problem-specific cutting planes;
  • is able to prove perfection of integer programming formulations using total unimodularity, geometry, and algorithmic knowledge;
  • can compare imperfect formulations by analyzing projections of relaxation polyhedra.
  • is able to construct new formulations by means of Benders' or Dantzig-Wolfe decomposition.
  • can explain the branch-and-bound algorithm as well as algorithms for separation- or pricing subproblems.
Content
In this course, we study mixed-integer programming (MIP) models and algorithmic techniques for solving these.
Throughout, problems from application areas such as transportation, network design, scheduling, production planning and location planning serve as motivating examples for different modeling techniques.
We will discuss several ways of characterizing when a model is perfect in a theoretical sense, and of comparing different (imperfect) models with each other.
These MIP models will be implemented in Python and solved using state-of-the-art solver software.
In order to solve certain types of MIPs in practice, standard models must be reformulated, and to this end, we analyze projections of polyhedra.
Finally, the addition of different sorts of cutting planes for improving the solution times of the solver will be discussed from a structural and algorithmic point of view.
On the way we will study algorithms, for solving MIPs in general, and for solving subproblems that arise during reformulation or model strengthening.
Assumed previous knowledge
Necessary: basic knowledge about linear optimization, linear algebra and computational complexity as well as basic programming skills
Participating study
Master Computer Science
Participating study
Master Applied Mathematics
Participating study
Master Industrial Engineering and Management
Participating study
Master Science Education and Communication
Required materials
Course material
Lecture slides and videos. Will be provided as a PDF / link.
Recommended materials
-
Instructional modes
Lecture

Practical

Tests
Exam

CloseHelpPrint
Kies de Nederlandse taal