  


Latticefree sets, multibranch split disjunctions, and mixedinteger programming
Sanjeeb Dash (sanjeebdus.ibm.com) Abstract: In this paper we study the relationship between valid inequalities for mixedinteger sets, latticefree sets associated with these inequalities and the multibranch split cuts introduced by Li and Richard (2008). By analyzing $n$dimensional latticefree sets, we prove that for every integer $n$ there exists a positive integer $t$ such that every facetdefining inequality of the convex hull of a mixedinteger polyhedral set with $n$ integer variables is a $t$branch split cut. We use this result to give a finite cuttingplane algorithm to solve mixedinteger programs. We also show that the minimum value $t$, for which all facets of polyhedral mixedinteger sets with $n$ integer variables can be generated as $t$branch split cuts, grows exponentially with $n$. In particular, when $n=3$, we observe that not all facetdefining inequalities are 6branch split cuts. Keywords: Latticefree sets, multibranch split disjunctions, and mixedinteger programming Category 1: Integer Programming Category 2: Integer Programming ((Mixed) Integer Linear Programming ) Category 3: Integer Programming (Cutting Plane Approaches ) Citation: IBM Research Report Download: [PDF] Entry Submitted: 09/20/2011 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  