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

• 成果类型: Article
• 署名作者: Cadoux, Florent
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-008-0245-6
• 发表日期: 2010
• 页码: 197-223
• 关键词: fenchel cutting planes

摘要

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 study cuts which are deep in a well-defined geometrical sense, and facet-defining. The cases when the deepest cut is decomposable as a combination of facet-defining cuts are characterized using the reverse polar set. When Q is a disjunctive polyhedron, a description of the reverse polar, linked to the so-called cut generating linear program of lift-and-project techniques, is given. A successive projections algorithm onto the reverse polar is proposed that computes the decomposition of the deepest cut into facet-defining cuts. Illustrative numerical experiments show how these cuts compare with the deepest cut, and with the most violated cut.