Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Reflections on generating (disjunctive) cuts

Optimization and Applications Seminar
Three operations are fundamental for combinatorial optimization: to branch, to bound, to cut. We develop an intrinsic study of cutting, with no reference to the combinatorial origin of the problem; we rather use tools from continuous mathematics (convex analysis). We investigate the questions of - which cuts to construct, - how to construct them. They call for concepts like separating and supporting hyperplanes, exposed points, support functions, polar and reverse polar sets. The case of the convex hull of two polyhedra (disjunctive cuts) serves as a leading thread in our study. Paper in preparation, based on: G. Cornuejols, C. Lemarechal: A convex-analysis perspective on disjunctive cuts. MathProg 106: 567-586 (2006) F. Cadoux: Computing deep facet-defining disjunctive cuts for mixed-integer programming. MathProg (online first)

Type of Seminar:
Public Seminar
Prof. Claude Lemaréchal
INRIA Grenoble-Rhone-Alpes, France
May 18, 2009   16:30 /

ETH Zentrum, Main Building, Room HG G 19.1
Contact Person:

Prof. M. Morari
File Download:

Request a copy of this publication.
Biographical Sketch:
Claude Lemaréchal was born in Paris in 1944. He has permanently worked for Inria (the French National Institute of Research for Computer Science and Control), where he is Director of Research; he led there several successive research teams (System Theory, Mathematical Programming, Numerical Optimization). He is renowned for his works in optimization, particularly in domains related with operations research and its links with nonlinear optimization (Dantzig Prize 1994). He has actively participated in the development of numerical methods in various branches of industry. Most significant results were obtained in geophysics (meteorology) and production management (electrical energy).