Advanced Optimization PhD course

About the course

(Integer) linear programming as a modeling tool provides an effective solution and in-depth understanding of, e.g., graph theory / network research problems in many cases. In recent decades, a number of solution methods have been proposed in the literature, which can then be seen more and more often in scientific articles and applications. A significant part of these methods, due to lack of time, is usually left out from the curriculum of compulsory and specialized courses. The Advanced Optimization course thus fills this gap.

Course website

List of topics - for the PhD complex exam

1 Integer Linear Programming (ILP) basics

• Content:
  • Definition of ILP, binary integer program, linear mixed integer program.
  • Examples: assignment problem, 0-1 knapsack problem
  • Relaxation of ILP results in Linear Programming (LP). Rounding of solutions of LP.
  • The simplex algorithm - basics only
  • Duality in LP, duality theorems (weak and strong)
  • Polyhedra and polytopes
  • Branch and Bound
• Slides for topic 1
• Video - not available

2 Modeling tricks

• Content:
  • maximum function
  • fixed cost
  • absolute value
  • Conditional constraints
  • alternative sets of constraints
  • K out of N constraints must hold
• Slides for topic 2: slides by Leo Liberti, Mathematical model. Modeling tricks I, Modeling tricks II, Modeling tricks III (bilinear case), Modeling tricks IV.
  Videos: introduction to AMPL and about modeling tricks.

3 Total unimodular matrices (TUM)

• Content:
  • Definition of TUM
  • Properties of TUM
  • LP with TUM as a constraint matrix has an all-integer solution (theorem and its proof)
  • Incidence matrix is TUM (theorem and proof)
  • Bipartite graphs and TUMs
  • Example 1: shortest path formalism using TUM
  • Example 2: maximal pairing in bipartite graphs using TUM
  • Example 3: minimum s-t cut using TUM
• Slides for topic 3
• Lecture's video (partial recording)

4 Network simplex method

• Content:
  • Minimum-Cost Network Flow Problem (MCNF) formulation
  • Transportation Problem as an MCNFP
  • Maximum-Flow Problem as an MCNFP
  • Basic Feasible Solutions for MCNFPs
  • For optimality: MCNFP and its dual problem
  • Pivoting in the Network Simplex method
  • Optimality check of a basic feasible solution
• Slides for topic 4
• Lecture's video

5 Constraint generation

• Content:
  • Travelling Salesman Problem (TSP)
  • general formulations
  • model for constraint generation
  • automatic removal of all cycles
• Slides for topic 5
• Lecture's video

6 Benders decomposition

• Content:
  • Formulation of the LP: complicating variables
  • The Subproblem and its dual (DSP)
  • Reformulation of DSP and the full Master Problem (MP)
  • Restricted MP (RMP)
  • Bender's cuts
  • iterative algorithm
• Slides for topic 6: slides by Y Huang and Q P Zheng and a tutorial by Z C Taskin
• Lecture's video

7 Danzig-Wolfe decomposition

• Content:
  • Formulation of the LP: complicating/coupling constraints
  • Minkowski representation theorem, illustration
  • The feasible region of the subproblems
  • The full master problem
  • Reduced cost
  • DW algorithm
• Slides for topic 7: slides by A Papavasiliou
• Videos of the lecture: part 1, part 2, part 3.