Séminaire Daniel Porumbel

07 Novembre 2013 (15h30, salle de séminaire)

Daniel Porumbel, Université d'Artois.

Titre : Sur l'optimisation du polytope dual de Cutting-Stock et Arc-Routing: une méthode à base d'un sous-problème d'intersection et de séparation.

Résumé : La génération de colonnes peut être vue comme une méthode à base de plans coupants ("cutting planes") dans le polytope dual P. A chaque étape, on sépare la solution duale courante Yub en trouvant une inégalité duale qui n'est pas vérifiée par Yub; cela nécessite la résolution d'un sous-problème de séparation dans le polytope dual P.

On présente une méthode (appelée Integer Ray Method) qui optimise P en utilisant un sous-problème d'intersection au lieu du sous-problème de séparation. Etant donné un rayon R le sous problème d'intersection demande de trouver le plus grand t > 0 tel que le point tR appartien à P. Cela génère: (a) une solution duale-faisable Ylb = tR appartient à P et automatiquement une borne minorante (duale) et (b) une contrainte de P saturée par Ylb. Ce type de contraintes peuvent être générées de manière itérative (une contrainte pour chaque rayon); ainsi, comme dans la génération de colonnes classique, cela peut conduire à la détermination d'une borne supérieure (primale) Yub pour l'optimum du P. En utilisant de rayons de plus en plus adaptés, Ylb et Yub convergent vers l'optimum du P. Si on utilise que des rayons R entiers, il est possible de résoudre le sous-problème d'intersection via la programmation dynamique. Cette approche a été testée sur deux problèmes (le Cutting-Stock et le Arc Routing Problem) pour lesquels on présente des résultats numériques.