Design and Verify — A New Scheme for Generating Cutting-Planes —

A cutting-plane procedure for integer programming (IP) problems usually involves invoking a black-box procedure (such as the Gomory-Chvátal (GC) 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 cx ≤ d, 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 P ∩ {x ∈ Rn: cx ≥ d + 1} ∩ Zn is empty using cutting planes from the black-box. (Here P 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 black box. This verification paradigm naturally leads to the question of how much extra strength one might hope to gain by having an oracle in place that provides us with potential cutting-planes and we are left with the task of verifying that its output is valid. We show that the verification closures are almost admissible operators, i.e., they are well-defined closures and share many properties that are common to known cutting planes closures. Moreover the verification closur