Titre : Integral Simplex Using Decomposition: Cutting planes to make it work

Résumé :
You need to divide people into groups but you don't know how to make the most happy combination? The Set Partitioning Problem (SPP) is your solution! It is a model used in many applications such as vehicle routing, crew scheduling but also wedding organization. Recently, Ellhallaoui et al. developped a new algorithm for it, particularly efficient for degenerate problems, which is the case of most real-life problems.

In this talk, we will first recall this algorithm, the Integral Simplex Using Decomposition (ISUD), both theoretically and through a simple example. ISUD is based on the IPS decomposition (also introduced by Elhallaoui et al.) of SPP into a master and a complementary problem (CP). It is often optimal without branching, but fails on some particular instances. ISUD starts from a current integer feasible solution, and finds a direction leading to an improving integer feasible solution. Finding this kind of directions is the hard part of the algorithm. We propose a method in which cutting planes are added to the complementary problem to force the directions to lead to another integer solution. In this new cutting paradigm, cuts are applied prior to being infeasible, whereas most classical methods start from a fractional infeasible solution and make it integer either by cutting or branching a posteriori. We will also show that some classical cuts for the set partitioning problem can be transfered to the complementary problem, which yields a cutting-plane algorithm, and leads to optimality.

Nous vous remercions de confirmer votre présence.
http://doodle.com/29kapx4t4rx48yfp