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 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 (ℤ×ℤ+) -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 (ℤ×ℤ+) -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.
Homepage: https://rd.springer.com/article/10.1007%2Fs12532-018-0132-y
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

Citations by Year