# Ph.D. Course on "Convex Analysis for Bounding and
Cutting"

## Claude Lemaréchal

Place: Dipartimento di Informatica,
Univeresità di Pisa, Pisa, Italy
Date: May 7 - 18, 2007

Timetable

Contact person: A. Frangioni

### Programme

These lectures will present some topics of combinatorial optimization
with the following objective:
- to place them in the context of modern convex analysis,
- yet to use an applied point of view and an intelligible language.

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.
**Part I: Lagrangian Relaxation and column generation, theory
(4-5 lectures)**

- 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
(2-3 lectures)**

- 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.

### Bibliography

C. Lemaréchal "Lagrangian relaxation", in: *Computational
Combinatorial Optimization*, M. Jünger, D. Naddef, eds., Springer
Verlag, 2001
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)