Optimization Online


Intersection Cuts for Single Row Corner Relaxations

Ricardo Fukasawa(rfukasawa***at***uwaterloo.ca)
Laurent Poirrier(lpoirrier***at***uwaterloo.ca)
Alinson S. Xavier(axavier***at***uwaterloo.ca)

Abstract: We consider the problem of generating inequalities that are valid for one-row relaxations of a simplex tableau, with the integrality constraints preserved for one or more non-basic variables. These relaxations are interesting because they can be used to generate cutting planes for general mixed-integer problems. We first consider the case of a single non-basic integer variable. This relaxation is related to a simple knapsack set with two integer variables and two continuous variables. We study its facial structure by rewriting it as a constrained two-row model, and prove that all its facets arise from a finite number of maximal (Z Z+)-free splits and wedges. The resulting cuts generalize both MIR and 2-step MIR inequalities. Then, we describe an algorithm for enumerating all the maximal (Z Z+)-free sets corresponding to facet-defining inequalities, and we provide an upper bound on the split rank of those inequalities. Finally, we run computational experiments to compare the strength of wedge cuts against MIR cuts. In our computations, we use the so-called trivial fill-in function to exploit the integrality of more non-basic variables. To that end, we present a practical algorithm for computing the coefficients of this lifting function.

Keywords: Lifting, Cutting-planes

Category 1: Integer Programming (Cutting Plane Approaches )


Download: [PDF]

Entry Submitted: 05/17/2016
Entry Accepted: 05/17/2016
Entry Last Modified: 05/17/2016

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