Design and verify: a new scheme for generating cutting-planes

• 成果类型: Article
• 署名作者: Dey, Santanu S.; Pokutta, Sebastian
• 署名单位: University System of Georgia; Georgia Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-013-0645-0
• 发表日期: 2014
• 页码: 199-222
• 关键词: Rank; polyhedra; PROGRAMS; closures; proofs

摘要

A cutting-plane procedure for integer programming (IP) problems usually involves invoking a black-box procedure (such as the Gomory-Chvatal procedure) to compute a cutting-plane. In this paper, we describe an alternative paradigm of using the same cutting-plane black-box. This involves two steps. In the first step, we design an inequality where and are integral, independent of the cutting-plane black-box. In the second step, we verify that the designed inequality is a valid inequality by verifying that the set is empty using cutting-planes from the black-box. Here is the feasible region of the linear-programming relaxation of the IP. We refer to the closure of all cutting-planes that can be verified to be valid using a specific cutting-plane black-box as the verification closure of the considered cutting-plane black-box. This paper undertakes a systematic study of properties of verification closures of various cutting-plane black-box procedures.