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