Groupe d’études et de recherche en analyse des décisions

Résolution du problème complémentaire dans un contexte de génération de colonnes

Hocine Bouarab

L'algorithme d'IPS (Improved Primal Simplex) rajoute à la génération de colonnes un troisième niveau qui est le problème complémentaire (PC). Le PC fournit les combinaisons convexes de colonnes incompatibles rajoutées au problème réduit. Pour ce faire, le PC interagit avec le sous-problème dans un cadre de génération de colonnes. Les tests numériques effectués pour résoudre par l'algorithme d'IPS des instances du MDVSP (Multiple Depot Vehicle Scheduling Problem) révèlent la forte dégénérescence du PC. Dans cette présentation, nous montrons comment les itérations de génération de colonnes du PC ont été réduites d'un facteur de 25 en moyenne pour les instances les plus dégénérées du MDVSP.

Nous vous remercions de confirmer votre présence.