科研之友
微信
新浪微博
Facebook
分享链接
摘要
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.
- 出版日期2014-6
