“Facet” separation with one linear program
(2019) Mathematical Programming — Vol. 178, n° 1-2, p. 361-380 (2019)
Files
Rep3090.pdf
Open Access - Adobe PDF
- 2.35 MB
Details
- Authors
Wolsey, Laurence 
- Abstract
- Given polyhedron $P$ and a point $x*$, the separation problem of polyhedra asks to certify that $x* \in 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 this 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 show that, by solving a single linear program, one almost surely obtains such an improper face of facet.
- Affiliations
Citations
Conforti, M., & Wolsey, L. (2019). “Facet” separation with one linear program. Mathematical Programming, 178(1-2), 361-380. https://doi.org/10.1007/s10107-018-1299-8 (Original work published 2019)