Ph.D. Course "Convex Analysis for Bounding and Cutting" C. Lemarechal
Forum 'Annonces' - Sujet créé le 2007-01-11
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
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
* The general idea.
* 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.
* Dual algorithms.
Part II: Column Generation
* The idea. Examples.
* Equivalence with Lagrangian relaxation.
* Theoretical and algorithmic consequences.
Part III: Cuts and Disjunctive Programming
* 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)
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
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
* The general idea.
* 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.
* Dual algorithms.
Part II: Column Generation
* The idea. Examples.
* Equivalence with Lagrangian relaxation.
* Theoretical and algorithmic consequences.
Part III: Cuts and Disjunctive Programming
* 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)