  


Intersection Cuts for Single Row Corner Relaxations
Ricardo Fukasawa(rfukasawauwaterloo.ca) Abstract: 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 (Z × Z+)free splits and wedges. The resulting cuts generalize both MIR and 2step MIR inequalities. Then, we describe an algorithm for enumerating all the maximal (Z × Z+)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. Keywords: Lifting, Cuttingplanes Category 1: Integer Programming (Cutting Plane Approaches ) Citation: Download: [PDF] Entry Submitted: 05/17/2016 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  