“Facet” Separation with One Linear Program

Michele Conforti and Laurence A. Wolsey ()
Additional contact information
Michele Conforti: Universitá di Padova
Laurence A. Wolsey: Université catholique de Louvain, CORE, Belgium

No 2016021, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: Given polyhedron P and and a point x , the separation problem for polyhedra asks to certify that x P and if not, to determine an inequality that is satisfied by P and violated by x . This problem is repeatedly solved in cutting plane methods for Integer Programming and the quality of the violated inequality is an essential feature in the performance of such methods. In the paper we address the problem of finding efficiently an inequality that is violated by x and either defines an improper face or a facet of P. We provide some evidence that our method works on structured and unstructured problems.

Keywords: integer programming; separation problem; polyhedra; extended formulations; facets; cutting plane algorithm; split inequalities; Benders’ algorithm (search for similar items in EconPapers)
Date: 2016-06-01
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2016.html (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2016021

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().