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 best way to go for you to know the credible Michigan Loans Online providers. Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.