Journal
MATHEMATICAL PROGRAMMING
Volume 178, Issue 1-2, Pages 361-380Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-018-1299-8
Keywords
Integer programming; Separation problem; Polyhedra; Extended formulations; Facets; Cutting plane algorithm; Split inequalities
Categories
Funding
- SID 2016
- PRIN 2016
Ask authors/readers for more resources
Given polyhedron P and and a point x* the separation problem for polyhedra asks to certify that x* is an element of 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 or facet.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available