On t-Branch Split Cuts for Mixed-Integer Programs

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.

By: Sanjeeb Dash; Oktay Günlük

Published in: Mathematical Programming , volume 141, (no 1-2), pages 591-599; 10.1007/s10107-012-0542-y in 2013

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .