Ph.D. Course on "Convex Analysis for Bounding and
Place: Dipartimento di Informatica,
Univeresità di Pisa, Pisa, Italy
Date: May 7 - 18, 2007
Contact person: A. Frangioni
These lectures will present some topics of combinatorial optimization
with the following objective:
Our aim is to explain the theory underlying these topics, thereby getting
a higher and more synthetic point of view. Generally speaking, this helps
understand "what one is doing". Rather than the usual matrix-like language
of linear programming, our concepts will therefore use a more geometric
language: support functions, normal cones, convex hulls etc.
The topics covered will essentially concern bounding. If time permits,
cutting will also be tackled.
- to place them in the context of modern convex analysis,
- yet to use an applied point of view and an intelligible language.
Part I: Lagrangian Relaxation and column generation, theory
- The methodology.
- Examples: LP relaxation, large-scale problems, complicating constraints;
the case of quadratic constraints: SDP relaxation.
Introduction of dual constraints. Hard and soft primal constraints.
- Minimal theory. The dual function and its subgradients. Duality
relations. Dual optimality and primal recovery.
- The convexifying effect of Lagrangian relaxation.
- Primal-Dual relations.
Part II: Lagrangian Relaxation and column generation, numerics
- Convex optimization: dual algorithms.
- Kelley and its stabilization.
- Primal interpretations.
Part III: Cuts and Disjunctive Programming (2-3 lectures)
- The problem: separate a ``parasitic'' point from the set of interest.
Good cuts - tight, deep, facet-defining.
- An ingenious concept: the reverse polar set.
- General approach to construct good cuts. Wolfe's algorithm.
- The case of disjunctive cuts.
C. Lemaréchal "Lagrangian relaxation", in: Computational
Combinatorial Optimization, M. Jünger, D. Naddef, eds., Springer
O. Briant, C. Lemaréchal, Ph. Meurdesoif, S. Michel, N. Perrot,
F. Vanderbeck "Comparison of bundle and classical column generation",
Inria Research Report
5453, 2005 (to appear in Mathematical Programming)
J.B. Hiriart-Urruty, C. Lemaréchal "Fundamentals of Convex Analysis",
Springer Verlag, 2001
E. Balas "Disjunctive programming", Annals of Discrete Mathematics 5,
pp. 3 - 51, 1979
G. Cornuéjols, C. Lemaréchal "A convex-analysis perspective on
disjunctive cuts", Mathematical Programming 106(3), pp. 567 - 586,
2005 (also available as Inria
Research Report 5317)