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, INPG - Institut National Polytechnique de Grenoble
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.
Type de document :
Article dans une revue
Mathematical Programming, Springer Verlag, 2010, 122 (2), pp.197-223. 〈10.1007/s10107-008-0245-6〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00396289
Contributeur : Florent Cadoux <>
Soumis le : mercredi 17 juin 2009 - 14:36:10
Dernière modification le : mercredi 11 avril 2018 - 01:58:52

Lien texte intégral

Identifiants

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

191