A Refined Gomory-Chvátal Closure for Polytopes in the Unit Cube

Juliane Dunkel(julianemit.edu)
Andreas S. Schulz(schulzmit.edu)

Abstract: We introduce a natural strengthening of Gomory-Chvátal cutting planes for the important class of 0/1-integer programming problems and study the properties of the elementary closure that arises from the new class of cuts. Most notably, we prove that the new closure is polyhedral, we characterize the family of all facet-defining inequalities, and we compare it to elementary closures associated with other cutting-plane procedures.

Keywords:

Category 1: Integer Programming (0-1 Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Citation: Massachusetts Institute of Technology, March 2012

Download: [PDF]

Entry Submitted: 03/23/2012
Entry Accepted: 03/23/2012
Entry Last Modified: 03/23/2012

Modify/Update this entry