Hal will be stopped for maintenance from friday on june 10 at 4pm until monday june 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Computing deep facet-defining disjunctive cuts for mixed-integer programming

Florent Cadoux 1
1 BIPOP - Modelling, Simulation, Control and Optimization of Non-Smooth Dynamical Systems
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, Grenoble INP - Institut polytechnique de Grenoble - Grenoble Institute of Technology
Abstract : The problem of separation is to find an affine hyperplane, or "cut", that lies between the origin O and a given closed convex set Q in a Euclidean space. We study cuts which are deep in a well-defined geometrical sense, and facet-defining. The cases when the deepest cut is decomposable as a combination of facet-defining cuts are characterized using the reverse polar set. When Q is a disjunctive polyhedron, a description of the reverse polar, linked to the so-called cut generating linear program of lift-and-project techniques, is given. A successive projections algorithm onto the reverse polar is proposed that computes the decomposition of the deepest cut into facet-defining cuts. Illustrative numerical experiments show how these cuts compare with the deepest cut, and with the most violated cut.
Document type :
Journal articles
Complete list of metadata

Contributor : Florent Cadoux Connect in order to contact the contributor
Submitted on : Wednesday, June 17, 2009 - 2:36:10 PM
Last modification on : Thursday, January 20, 2022 - 5:28:06 PM

Links full text




Florent Cadoux. Computing deep facet-defining disjunctive cuts for mixed-integer programming. Mathematical Programming, Springer Verlag, 2010, 122 (2), pp.197-223. ⟨10.1007/s10107-008-0245-6⟩. ⟨inria-00396289⟩



Record views