  


On mixedinteger sets with two integer variables
Sanjeeb Dash (sanjeebdus.ibm.com) Abstract: We show that every facetdefining inequality of the convex hull of a mixedinteger polyhedral set with two integer variables is a crooked cross cut (which we defined recently in another paper). We then extend this observation to show that crooked cross cuts give the convex hull of mixedinteger sets with more integer variables provided that the coefficients of the integer variables form a matrix of rank 2. We also present an alternative characterization of the crooked cross cut closure of mixedinteger sets similar to the one about the equivalence of different definitions of split cuts presented in Cook, Kannan, and Schrijver (1990). This characterization implies that crooked cross cuts dominate the 2branch split cuts defined by Li and Richard (2008). Finally, we extend our results to mixedinteger sets that are defined as the set of points (with some components being integral) inside a closed, bounded, convex set. Keywords: latticefree cuts, split cuts, disjunctive cuts Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Category 2: Integer Programming (Cutting Plane Approaches ) Citation: Download: [PDF] Entry Submitted: 06/16/2010 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  