Optimization Online


On t-branch split cuts for mixed-integer programs

Sanjeeb Dash(sanjeebd***at***us.ibm.com)
Oktay Gunluk(gunluk***at***us.ibm.com)

Abstract: In this paper we study the t-branch split cuts introduced by Li and Richard (2008). They presented a family of mixed-integer programs with n integer variables and a single continuous variable and conjectured that the convex hull of integer solutions for any n has unbounded rank with respect to (n-1)-branch split cuts. It was shown earlier by Cook, Kannan and Schrijver (1990) that this conjecture is true when n=2, and Li and Richard proved the conjecture when n=3. In this paper we show that this conjecture is also true for all n>3.

Keywords: mixed-integer programming, cutting planes, lattice-free cuts, t-branch split cuts

Category 1: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 11/09/2011
Entry Accepted: 11/09/2011
Entry Last Modified: 11/09/2011

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