Optimization Online


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

Santanu S. Dey(santanu.dey***at***isye.gatech.edu)
Sebastian Pokutta(pokutta***at***mit.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 )


Download: [PDF]

Entry Submitted: 04/21/2011
Entry Accepted: 04/21/2011
Entry Last Modified: 04/21/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society