Claude Lemarechal
INRIA Grenoble-Rhone-Alpes
Abstract:
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)