- Design and Verify: A New Scheme for Generating Cutting-Planes Santanu S. Dey(santanu.deyisye.gatech.edu) Sebastian Pokutta(pokuttamit.edu) Abstract: A cutting-plane procedure for integer programming (IP) problems usually involves invoking a black-box procedure (such as the Gomory-Chvatal (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 where c and d 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 $P \cap \{x\in R^n: cx >= d + 1\} \cap Z^n$ 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 cutting-plane black-box. This paper undertakes a systematic study of properties of verification closures of various cutting-plane black-box procedures. Keywords: Cutting Planes, Verification Scheme, Integer Programming Category 1: Integer Programming (Cutting Plane Approaches ) Citation: Download: [PDF]Entry Submitted: 04/21/2011Entry Accepted: 04/21/2011Entry Last Modified: 04/21/2011Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.