• Get a broader knowledge in the area of mathematical optimization with focus on (mixed) integer linear programming (MIP)
• Be able to model both academic and real world problems as MIPs
• Be able to theoretically analyze and compare different mathematical programming formulations for a problem
• Have knowledge on common methodology for solving MIPs
• Be able to develop practical solution algorithms using state-of-the-art MIP frameworks

• Overview on mathematical optimization (focus on mixed integer models, but also including non-linear and non-deterministic models)
• Modeling (real world) problems as MIPs (basic techniques, modeling with exponentially many constraints and / or variables)
• Solution methods for MIPs
  - Cutting plane method, branch-and-cut
  - Decomposition approaches (Langrangian decomposition, Dantzig-Wolfe decomposition) and corresponding solution methods (subgradient method, column generation, branch-and-price)
• Theory of valid inequalities and further theoretical concepts
  - (Strong) valid inequalities (Chvatal-Gomory cuts, Gomory cuts, mixed integer cuts, cover cuts, theoretical concepts such as dominance, redundancy, facet defining cuts)
  - "Well-solved" problems (properties, total unimodularity, optimization = separation)
• Further issues in MIP computation and components of modern MIP solvers (presolving, primal heuristics, symmetry, frameworks)
• Overview on further methods and extensions (stochastic- and robust optimization, non-linear programming, multiobjective optimization)

Estimated effort:

Hours | Purpose
16       | Lecture
10       | Homework exercises 
30       | Programming exercise
19       | Exam preparation and exam
--------------------------------------
75       | Overall

In addition to the lectures, there will be homework assignments and a programming exercise.

Homework Assignments

Specifications will be made available for download in TISS.

Programming Exercise

You will have to design and implement different integer programming formulations for a specified optimization problem. Specifications and the framework will be available for download in TISS. You should join in groups of two for this programming exercise and send your results by mail to us (deadlines will be announced).

Final Exam

Dates for the final oral exam will be available in May and June and also in summer if required. Details will be announced here.

- Each team (w.r.t. the programming exercise) should choose a common date / timeslot for the exercise (unless there are good reasons not to do so).

- You should register for the exam by email (to both of us). In this email please specify who is going to take the exam (you and your partner), the date and constraints regarding the concrete time (as we will try to schedule the exams such that there are not too long breaks for us). For each group of two we will reserve 45 minutes and for a single student we will reserve 30 minutes.

- The concrete location of the exam will be announced to you by mail.

Grading

The mark you receive depends on the final exam (50%) and your accomplishments in the homework assignments (15%) and the programming exercise (35%).

• Basic knowledge of (integer) linear programming (modeling, LP based Branch-and-Bound) as e.g. taught in Algorithmics
• Knowledge of basic algorithms and data structures
• Programming skills in Java or C++
• Basic knowledge of linear algebra and graph theory