Invited Session Mon.1.MA 042

Monday, 10:30 - 12:00 h, Room: MA 042

Cluster 11: Integer & mixed-integer programming [...]

Recent progress in MIP


Chair: Oktay Günlük



Monday, 10:30 - 10:55 h, Room: MA 042, Talk 1

Marco Molinaro
Strength of cross cuts

Coauthors: Sanjeeb Dash, Oktay Günlük


Split cuts are among the most important cuts in practice, and modern heuristics can essentially harness their full power. Aiming at improving over split cuts, we study their most natural generalization, cross cuts. We present a theoretical comparison of the strength of the cross-closure and the second split-closure. We also analyze the strength of cross cuts from the important 2-row and basic relaxations and resolve two open questions posed by Dash, Dey and Günlük (2010).



Monday, 11:00 - 11:25 h, Room: MA 042, Talk 2

Sanjeeb Dash
On t-branch split cuts for mixed-integer programs

Coauthor: Oktay Gunluk


We settle a conjecture of Li and Richards on t-branch split cuts, and show that there are mixed-integer programs with n+1 variables which are unsolvable by (n-1)-branch split cuts, thus extending the well-known 3-variable example of Cook, Kannan and Schrijver which is unsolvable by split cuts.



Monday, 11:30 - 11:55 h, Room: MA 042, Talk 3

Egon Balas
Cut generating points on the boundary of a lattice-free convex set

Coauthors: Francois Margot, Selvaprabu Nadarajah


A new paradigm for generating cuts in mixed integer programming (Balas and Margot, 2011) identifies a set Q of boundary points of a lattice-free convex set S, such that the reverse polar of Q provides valid cuts. We discuss ways of generating such boundary points, and the properties of the resulting sets. We compare the cuts generated from such sets, which we call generalized or look-ahead intersection cuts, to cuts belonging to known families. In particular, we show that the new paradigm offers a way to generate in a non-recursive fashion deep cuts that can otherwise be generated only through several iterations of one of the standard procedures. Finally, we discuss implementation aspects and some preliminary computational experience.


  The majority of financial loan companies provide the service of getting North Carolina Payday Loans for U.S. citizens. This pill gives a hand to thousands who suffer from erectile dysfunction. People who take Viagra Super Active can forget about their impotence and have a normal intimate life.