  


Two Row Mixed Integer Cuts Via Lifting
Santanu Dey(santanu.deyuclouvain.be) Abstract: Recently, Andersen et al.(2007), Borozan and Cornuejols (2007) and Cornuejols and Margot(2007) characterized extreme inequalities of a system of two rows with two free integer variables and nonnegative continuous variables. These inequalities are either split cuts or intersection cuts (Balas (1971)) derived using maximal latticefree convex sets. In order to use these inequalities to obtain cuts from two rows of a general simplex tableau, one approach is to extend the system to include all possible nonnegative integer variables (giving the tworow mixed integer infinitegroup problem), and to develop lifting functions giving the coefficients of the integer variables in the corresponding inequalities. In this paper, we study the characteristics of these lifting functions. We begin by observing that functions giving valid coefficients for the nonnegative integer variables can be constructed by lifting a subset of the integer variables and then applying the fillin procedure presented in Johnson (1974). We present conditions for these `general fillin functions' to be extreme for the tworow mixed integer infinitegroup problem. We then show that there exists a unique `trivial' lifting function that yields extreme inequalities when starting from a maximal latticefree triangle with multiple integer points in the relative interior of one of its sides, or a maximal latticefree triangle with integral vertices and one integer point in the relative interior of each side. In all other cases (maximal latticefree triangle with one integer point in the relative interior of each side and nonintegral vertices, and maximal latticefree quadrilaterals), nonunique lifting functions may yield distinct extreme inequalities. For the case of a triangle with one integer point in the relative interior of each side and nonintegral vertices, we present sufficient conditions to yield an extreme inequality for the tworow mixed integer infinitegroup problem. Keywords: Infinite Group Relaxation, Lifting Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Category 2: Integer Programming (Cutting Plane Approaches ) Citation: CORE DP 2008/30, Universite catholique de Louvain, Belgium. Download: [PDF] Entry Submitted: 06/21/2008 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  