Wednesday 26
Non-linear optimisation, bi-level optimisation and yield management
Serigne Gueye
› 11:30 - 12:00 (30min)
› Bât. A - TD 34
Quelques approches pour résoudre des problèmes quadratiques en 0-1, en particulier de type affectation, avec application a un problème de crossdock.
Monique Guignard  1, *@  , Peter Hahn  1  , Aykut Ahlatcioglu  1  , Lucas Letocart  2  , Michael Bussieck.  3  
1 : Université de Pensylvanie
2 : Laboratoire d'Informatique de Paris-Nord  (LIPN)  -  Website
Université Paris XIII - Paris Nord, CNRS : UMR7030, Institut Galilée
Institut Galilée 99, avenue J.B Clément 93430 VILLETANEUSE -  France
3 : Université dePensylbanie
* : Corresponding author

Le problème d'affectation quadratique généralisé (GQAP en anglais) ou non (QAP), est NP-difficile, et en pratique très difficile a résoudre exactement, meme pour des instances de petite taille. Les couts d'affectation sont quadratiques, car ils dépendent des affectations par paires. Plusieurs approches de résolution exacte ou approchée pour le QAP et le GQAP seront présentées, ainsi que les résultats de nombreuses expériences numériques:
La méthode RLT (reformulation and linearization technique) adaptée au (G)QAP ne permet pas de résoudre des instances de grande taille. Le passage a des niveaux superieurs (RLT-2 et RLT-3) permet d'améliorer les bornes inférieures et a fortiori le temps de résolution par branch-and-bound.

Les méthodes de convexification de type QCR (quadratic convex reformulation) permettent de convexifier en utilisant des méthodes SDP des problèmes quadratiques en variables 0-1 purs et d'utiliser ensuite des logiciels du commerce. Des améliorations récentes permettent de renforcer les bornes inférieures.

La méthode de l'enveloppe convexe (Convex Hull en anglais), adaptée de la méthode de décomposition simpliciale, permet dans le cas convexe d'obtenir une borne inférieure et dans tous les cas de bonnes solutions approchées. De nombreuses expériences numériques avec des instances non convexes de GQAP et des instances QAP de QAPLIB, montrent que l'erreur est très faible et les temps de calcul raisonnables.
L'utilisation combinée de QCR inversée et de la méthode CH pour des instances GQAP convexes produit des résultats sensiblement améliores compares à CH utilisé seul.

Le problème d'affectation des camions aux portes d'entrée et de sortie d'un crossdock est un problème important en logistique. Il peut être formulé comme un GQAP dans le sens ou le cout de traitement d' un objet provenant d'un camion et expédié dans un autre camion dépend de l'emplacement choisi pour ces deux camions. De nombreux résultats numériques montrent qu'il devrait être possible de résoudre ce problème en temps réel lors de l'arrivée de nouveaux camions à décharger.


Online user: 2