SluitenHelpPrint
Switch to English
Cursus: 191581420
191581420
Mixed-Integer Optimization
Cursus informatie
Cursus191581420
Studiepunten (ECTS)5
CursustypeCursus
VoertaalEngels
Contactpersoondr. M. Walter
E-mailm.walter@utwente.nl
Docenten
Docent
J. Hönen
Docent
R.P. van der Hulst
Examinator
dr. M. Walter
Contactpersoon van de cursus
dr. M. Walter
Collegejaar2022
Aanvangsblok
2A
AanmeldingsprocedureZelf aanmelden via OSIRIS Student
Inschrijven via OSIRISJa
Cursusdoelen
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.
Inhoud
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.
Voorkennis
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
M Educatie en Communicatie in de Bètawetenschappen
Verplicht materiaal
Course material
Lecture slides and videos. Will be provided as a PDF / link.
Aanbevolen materiaal
-
Werkvormen
Hoorcollege

Practicum

Toetsen
Oral Exam

SluitenHelpPrint
Switch to English