Teaching

Hands-on Tutorial on Optimization (engl./dt.)

Block course in Summer 2018
3 CP


A large number of problems arising in practical scenarios like communication, transportation, planning, logistics etc. can be formulated as discrete linear optimization problems. This course briefly introduces the theory of such problems.
We develop a toolkit to model real-world problems as (discrete) linear programs. Some examples of basic optimization problems that are part of this toolkit are scheduling, packing, matching, routing, and network-design. We also explore different ways to find integer solutions such as cutting planes, Branch & Bound, and column generation.
Based on this theoretical background, we focus on translating practical examples into mixed-integer linear programs. We learn how to use professional solvers (such as CPLEX, Gurobi, and FICO Xpress) and tailor the solution process to certain properties of the problem.
Throughout the course, we concentrate on modeling and solving practical problems with some theory parts in between.

Lecturers:


Franziska Eberle (Email)
Dr. Ruben Hoeksma (Email)
Prof. Dr. Nicole Megow (Email)
This course consists of two phases:
Phase 1: One week of lectures and practical labs during Mon Sept 24 – Fri Sept 29 from 9:30 to 12:30 and from 13:30 to 17:30.
Phase 2: One project has to be modeled, implemented, and solved individually or in a group of at most two students. The topic will be either developed with or provided by the lecturers. The project including the implementation has to be presented at the latest in the first week of the winter semester 2018/2019.
There are no prerequisites except some basic programming skills to participate.
Day Topic Slides
1 Introduction, Modeling, Using GAMS intro, modeling
2 Matrix and Polyhedral Representations Polyhedral Representation
3 GAMS guest lecture and Branch&Bound GAMS slides, Branch&Bound
4 LP Duality, Modeling Tricks Duality, Tricks, AIMMS Optimization modeling (book)
5 Column Generation, Non-Optimal Solutions, Using Other Environments Column Generation, Non-Optimal Solutions
Final Assignment Information
Day Exercises Data Solutions
1 Chips Factory,
Crude Oil Processing
Chips,
Oil
Chips,
Oil
2 Farm Planning,
Graph Coloring
Farm Farm,
Coloring
3 Cheese Coup Cheese Cheese,
Branch & Bound (Xpress)
4 Cheese Empire Empire Empire
5 Maintenance Scheduling Maintenance scheduling Maintenance,
Column Generation
Final Assignment* Time Tabling
* You can create simpler test-instances by removing some of the requirements (e.g., remove the assignment of teachers, only look at one semester, etc.)