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

School of Graduate Studies G. Galilei

Claude Lemaréchal

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.

Part I: Lagrangian Relaxation and column generation, theory (4-5 lectures)

Part II: Lagrangian Relaxation and column generation, numerics (2-3 lectures)

Part III: Cuts and Disjunctive Programming (2-3 lectures)


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)