“Facet" Separation with One Linear Program
(2016) , 22 pages
Files
coredp2016_21web.pdf
Open Access - Adobe PDF
- 317.4 KB
Details
- Authors
- 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.
- Affiliations
Citations
Conforti, M., & Wolsey, L. (2016). “Facet” Separation with One Linear Program (CORE Discussion Paper 2016/21). https://hdl.handle.net/2078.5/183271