COST/MINO PhD School on Advanced Optimization Methods 2016

Program

The school will cover the following topics:



Program at a glance

Day/Time

9.00-11.00

11.30-13.30

15.00-17.00

Monday
June 6

PC1

PC2

IP1

Tuesday
June 7

IP2

PC3

IP3

Wednesday
June 8

IP4

DW1

IP5

Thursday
June 9

DW2

SDP1

PC4

Friday
June 10

PC5

SDP2


Every day:

11.00-11.30 coffee break
13.30-15.00 lunch


Polyhedral Combinatorics
by Santanu S. Dey

Polyhedral combinatorics is the branch of mathematics that deals with the study of polyhedra associated with integer vectors satisfying linear constraints. It has proven to be a powerful unifying methodology for tackling many combinatorial optimization problems. For example, it has lead to polynomial-time algorithms for many combinatorial optimization problems. Techniques based on polyhedral combinatorics have also been used to develop powerful computational tools withing modern mixed-integer programming solvers. In particular cutting-plane theory has revolutionized how mixed-integer programming problems are solved. This lecture series will cover the basics of polyhedral combinatorics with focus on mixed-integer programming theory.

  • Lecture PC1: Fundamental results on systems of linear inequalities: Farkas' lemma and variants, linear programming duality. Structure of polyhedron: recession cone, linearity space, faces, facets, minimal faces, decomposition of a polyhedron.

  • Lecture PC2: Fundamental theory of integer programming and related topics: integer hull of a polyhedron, Hilbert basis, theorem of Doignon. How to prove a polyhedron is integral: totally unimodular matrices, totally dual integral systems, other techniques.

  • Lecture PC3: General mixed integer programming and polyhedral methods - introduction to cutting-plane theory for integer programs: Chv´ tal-Gomory (CG) cuts, rank and closure of a CG cuts.

  • Lecture PC4: Cutting-planes for mixed integer programs: split disjunctive cuts, mixed-integer rounding (MIR) inequalities, equivalence of split disjuntive closure and MIR closure, some polyhedrality results of closures of these cutting-planes.

  • Lecture PC5: New results in cutting-plane theory: maximal lattice-free convex sets and related multi-term disjunctive cutting-planes, cut-generating functions and gauge functions of lattice-free convex sets.


Interior Point Methods
by Jordi Castro

  • Lecture IP1. Fundamentals and background material. - Basics of convexity. Optimality conditions. Duality. Newton's method.

  • Lectures IP2-IP4. Primal-dual path following methods: - Central path and barrier problem. - Primal-dual path following algorithms. Convergence and complexity. - Implementation of IPMs - Extension to quadratic and convex problems.

  • Lecture IP5. IPMs for large-scale and integer problems. - Using iterative solvers. - Application to facility location.



Advanced Dantzig-Wolfe Decomposition
by Antonio Frangioni

  • Lecture DW1. Lagrangian Relaxation, Dantzig-Wolfe Decomposition, Column Generation: all is one, one is all.

  • Lecture DW2. Beyond by-the-book: stabilization, partial decomposition, structured decomposition.



Semidefinite Programming
by Veronica Piccialli