SEMINAIRE D'ANALYSE NUMERIQUE
Année universitaire 2015-2016
Jeudi 4 février 2016 :
Samuel ROSAT (Polytechnique Montréal – Département de
mathématiques et de génie industriel)
The ISUD algorithm: an
all-integer simplex that outperforms CPLEX's branch and bound on
large scale set partitioning problems.
The Integral Simplex Using Decomposition (ISUD) is a primal algorithm best suited for {0,1}-linear programming first introduced by Zaghrouti et al. in 2014.
It is based on iterative improvements of a given initial integer solution by performing (linear) simplex pivots.
At each step, a subproblem (SP) is solved to determine a feasible improving direction, i.e., such that a nonzero step can be taken in that direction without violating the linear constraints, and that strictly improves the cost of the current solution.
The bottleneck of the method is to ensure that following this direction leads to an integer solution.
Branch and bound, cutting planes or other techniques can be necessary to palliate that problem, but a simplistic branching method is sufficient to obtain good results on many large scale problems.
In this talk, we present the algorithm in a primal form and discuss some theoretical and practical features.
We describe how the zero-valued variables are partitioned into compatible and incompatible variables, where the former ensure nondegenerate simplex pivots and the latter degenerate ones.
We prove that this partition allows an exact decomposition of SP in the linear case, and show that this decomposition holds in the integer case for a particular class of problems.
We also give a geometrical interpretation of the different problems and concepts.
Then, we present different methods to foster directions that lead to integer solutions based on cutting planes and normalization weights.
We show that the decomposition naturally leads to a practical implementation that proves highly efficient on large scale set partitioning instances from industrial scheduling applications (up to 1600 constraints and 570000 variables).
Finally, we discuss future directions of research ; one of the most promising being the embedding of column generation within ISUD, that would allow to solve practical instances in scheduling, and other applications.
We will explain why we believe that ISUD is particularly well-suited for embedding column generation, and why it should perform even better in the context of column generation than in the static case.
This talk is based on the work conducted at the GERAD research center by several professors, post-docs and graduate students (Issmail Elhallaoui, Omar Foutlane, Samuel Rosat, François Soumis, Adil Tahir, Abdelouahab Zaghrouti, and others).
