swMATH ID: 
31758

Software Authors: 
Fukasawa, Ricardo; Poirrier, Laurent; Xavier, Álinson S.

Description: 
Intersection cuts for single row corner relaxations. We consider the problem of generating inequalities that are valid for onerow relaxations of a simplex tableau, with the integrality constraints preserved for one or more nonbasic variables. These relaxations are interesting because they can be used to generate cutting planes for general mixedinteger problems. We first consider the case of a single nonbasic 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 tworow model, and prove that all its facets arise from a finite number of maximal (ℤ×ℤ+) free splits and wedges. The resulting cuts generalize both MIR and 2step MIR inequalities. Then, we describe an algorithm for enumerating all the maximal (ℤ×ℤ+) free sets corresponding to facetdefining 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 socalled trivial fillin function to exploit the integrality of more nonbasic variables. To that end, we present a practical algorithm for computing the coefficients of this lifting function. 
Homepage: 
https://rd.springer.com/article/10.1007%2Fs125320180132y

Source Code: 
https://github.com/iSoron/onerow

Keywords: 
integer programming;
lifting;
cutting planes

Related Software: 
lifting;
MIPLIB;
infinite group relaxation;
CPLEX;
gmp

Cited in: 
2 Documents
