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 focus on cuts which are deep for the Euclidean distance, and facet-defining. The existence of a unique deepest cut is shown and cases when it is decomposable as a combination of facet-defining cuts are characterized using the reverse polar set. When Q is a split polyhedron, a new description of the reverse polar is given. A theoretical successive projections algorithm is proposed that could be used to compute deep facet-defining split cuts.
Type de document :
Rapport
[Research Report] RR-6177, INRIA. 2007, pp.22
Liste complète des métadonnées

https://hal.inria.fr/inria-00144289
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 2 mai 2007 - 16:45:25
Dernière modification le : mercredi 11 avril 2018 - 01:58:16
Document(s) archivé(s) le : mardi 21 septembre 2010 - 12:47:20

Fichiers

RR-6177.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00144289, version 2

Citation

Florent Cadoux. Computing deep facet-defining disjunctive cuts for mixed-integer programming. [Research Report] RR-6177, INRIA. 2007, pp.22. 〈inria-00144289v2〉

Partager

Métriques

Consultations de la notice

285

Téléchargements de fichiers

219