Computing deep facet-defining disjunctive cuts for mixed-integer programming - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2007

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

Résumé

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.
Fichier principal
Vignette du fichier
RR-florent-cadoux.pdf (243.49 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00144289 , version 1 (02-05-2007)
inria-00144289 , version 2 (02-05-2007)

Identifiants

  • HAL Id : inria-00144289 , version 1

Citer

Florent Cadoux. Computing deep facet-defining disjunctive cuts for mixed-integer programming. [Research Report] 2007, pp.22. ⟨inria-00144289v1⟩

Collections

INRIA-RRRT
124 Consultations
367 Téléchargements

Partager

Gmail Facebook X LinkedIn More