Séminaires 2014 - 2015
Sauf mention contraire, le séminaire de Mathématiques Discrètes a lieu le jeudi à 14h30 en Salle C319. Les responsables sont Louis Esperet et András Sebő, n'hésitez pas à les contacter.
|27 novembre 2014||Hyung-Chan An
|25 novembre 2014||Ola Svensson
|6 novembre 2014||Marthe Bonamy
|2 octobre 2014||François Margot
(Tepper School of Business, Carnegie Mellon, USA)
|Cut generation through binarization|
- Jeudi 27 novembre 2014 (à 14h30):
Hyung-Chan An (EPFL, Lausanne) : tba
- Mardi 25 novembre 2014 (à 14h30):
Ola Svensson (EPFL, Lausanne) : tba
- Jeudi 6 novembre 2014 (à 14h30):
Marthe Bonamy (LIRMM, Montpellier) : tba
- Jeudi 2 octobre 2014 (à 14h30):
François Margot (Tepper School of Business, Carnegie Mellon) : Cut generation through binarization
Cutting planes (or cuts) are an essential component of state-of-the-art solvers for Mixed-Integer Linear Program (MILP). Among the many classes of cuts, split cuts are one of the most useful and essential. It is known that split cuts are able to close a large part of the integrality gap for usual benchmark instances, but this requires a large cpu time. Empirical split cut generation aims at generating fast the most useful split cuts. Advances in this direction usually focus on finding strong disjunctions, involving several variables. In this talk, our aim is to use combinations of simple split cuts, i.e. cuts obtained using disjunctions of the form x_j = 0 or x_j = 1 for a binary variable x_j to generate cuts that have similar strength as general split cuts.
Our cut generation scheme is based on two components. First, we use a binarization of general integer variables (i.e., replacing a general integer variable by a sum of binary variables), augmented by additional symmetry breaking constraints. This binarization was introduced by Roy for generating strong Lift-and-Project cuts. Second, we then use rank-2 simple-split cuts, i.e, cuts that can be obtained as a simple split cut for a polyhedron obtained by adding all simple split cuts for the binarization of the problem. We show that for a pure integer problem with two integer variables, these cuts are sufficient to obtain the integer hull of the problem, but that this does not generalize to problems in higher dimensions. We also give an algorithm to compute an approximation of the rank-2 simple split cut closure. We report empirical results on 22 benchmark instances showing that the bounds obtained compare favorably with those obtained with other approximate methods to compute the split closure or lattice-free cut closure. It gives a better bound than the split closure on 6 instances while it is weaker on 9 instances, for an average gap closed 3.8% smaller than the one for the split closure.
Joint work with Pierre Bonami, IBM ILOG CPLEX.