Optimization Online


Lattice-free sets, multi-branch split disjunctions, and mixed-integer programming

Sanjeeb Dash (sanjeebd***at***us.ibm.com)
Neil Dobbs (nbdobbs***at***us.ibm.com)
Oktay Gunluk (gunluk***at***us.ibm.com)
Tomasz Nowicki (tnowicki***at***us.ibm.com)
Grzegorz Swirszcz (swirszcz***at***us.ibm.com)

Abstract: In this paper we study the relationship between valid inequalities for mixed-integer sets, lattice-free sets associated with these inequalities and the multi-branch split cuts introduced by Li and Richard (2008). By analyzing $n$-dimensional lattice-free sets, we prove that for every integer $n$ there exists a positive integer $t$ such that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with $n$ integer variables is a $t$-branch split cut. We use this result to give a finite cutting-plane algorithm to solve mixed-integer programs. We also show that the minimum value $t$, for which all facets of polyhedral mixed-integer 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 facet-defining inequalities are 6-branch split cuts.

Keywords: Lattice-free sets, multi-branch split disjunctions, and mixed-integer 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
Entry Accepted: 09/20/2011
Entry Last Modified: 01/21/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society