'Cutting plane methods for integer and combinatorial optimization',
Hammamet, March 22-23, 2010
Pierre Bonami, Laboratoire d'Informatique Fondamentale, CNRS/Aix
Marseille Universitee, Marseille, France
Gérard Cornuéjols, Tepper School of Business,
Carnegie Mellon Univrsity, USA
Andrea Lodi, Dipartimento di Elettronica, Informatica e Sistemistica,
Universita di Bologna, Italy
We will focus on methods which present both a theoretical and
computational interest. The first half-day will be devoted to recalling
some of the best known and most efficient families of cutting planes,
their separation and their use. The rest of the course will be divided
into three advanced subtopics for which ongoing research is very active:
elementary closures, cuts for Mixed Integer NonLinear Programming (MINLP)
and cuts from Multiple Rows. We give below a more detailed program.
Introduction to cutting planes for MIP (Monday morning): We will present
several families of cutting planes. In particular: Gomory Fractional
and Mixed Integer cuts, Mixed-Integer Rounding (MIR) cuts,
Intersection cuts, Disjunctive cuts, Lift-and-Project cuts, and
Projected Chvatal-Gomory cuts.
Elementary Closures (Monday afternoon): After having defined the concept
of elementary closures, we will show some equivalences between families of cuts.
We will then discuss the problem of separating over closures. Finally, we
will discuss the use of normalizations in the separation of disjunctive cuts.
Cuts for MINLP (Tuesday Morning): In this part we will first discuss the
use of Disjunctive Programming to build strong relaxations for non-convex
problems (mainly quadratically constrained but also separable).
We will then focus on convex MINLPs (those whose continuous relaxation
is a convex program) and several cutting plane methods which have been proposed
for them: Outer Approximation cuts, Conic MIR cuts, Disjunctive Cuts.
An introduction to cuts from Multiple Rows (Tuesday Afternoon): In the
last three years, a very active area of research has been generalizations of
Gomory cuts using more than one row of the simplex tableau.
We will give us an introduction to this new and very active area of
research.
Prerequisites: Attendees with a good knowledge of the basics of Linear
Programming
--
-----------------------------------------
A. Ridha Mahjoub
Laboratoire LAMSADE
Université Paris Dauphine
Place du Maréchal de Lattre de Tassigny
75775 Paris Cedex 16
France
Tel: +33 (0)1 44 05 48 96
Fax: +33 (0)1 44 05 40 91
E-mail: mahjoub@lamsade.dauphine.fr
URL: http://www.lamsade.dauphine.fr/~mahjoub
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
