Approches de Décomposition et Reformulation en Programmation Entière

Francois Vanderbeck

Universite de Bordeaux 1, Institut de Mathematiques de Bordeaux et INRIA Bordeaux Sud-Ouest

Les solveurs de programmation linéaire en variables entières sont devenus remarquablement efficaces grâce à l’intégration récente de techniques de génération automatique de coupes, de préprocessing, d’heuristiques et des stratégies d’énumération bien pensées. Malgrés ces progès, l’exploitation de la structure des problèmes reste essentiellement au soin de l’utilisateur. Cet exposé récapitule les méthodes permettant de reformuler un programme linéaire en variables entières en exploitant sa structure. Le but est principalement d’obtenir de meilleures bornes par la programmation linéaire, mais aussi dans certain cas de décomposer le problème et d’éviter des symétries dans la représentation des solutions. En particulier, nous développerons les algorithmes basés sur la décomposition de Dantzig-Wolfe (génération de colonnes) et celle de Benders.

Branch and Price and Cut pour des problèmes de transport de biens ou de personnes

Dominique Feillet

Ecole des Mines de Saint-Etienne

Le sujet de cet exposé est la résolution de problèmes combinatoires, tels que ceux rencontrés pour le transport de biens ou de personnes, par des méthodes alliant génération de colonnes et génération de coupes. Plus précisément, la présentation se focalisera sur le cas où la génération de colonnes s’accompagne nécessairement de la génération de nouvelles coupes (par opposition au cas plus souvent étudié où la génération de coupes est facultative et utilisée pour renforcer la qualité des bornes). Une méthodologie générale sera présentée. Les modalités et difficultés d’application de cette méthodologie seront illustrées à travers trois cas d’études : le problème de tournées de véhicules avec fractionnement de la demande, le problème de tournées de véhicules avec routes multiples et un problème de conception de réseau de service pour le transport urbain de personnes.

Une methode de generation de colonnes basee sur un algorithme central de plans coupants

Mathieu Trampont

France Télécom - Orange Labs

Nous présentons ici une variante de génération de colonnes basée sur un algorithme de plan coupant central. Nous verrons le fonctionnement général de cet algorithme et son utilisation dans une méthode de génération de colonnes. Des techniques usuelles de stabilisation, comme le boxstep ou la méthode de stabilisation par point intérieur de Rousseau et al. peuvent être adaptées pour fonctionner avec cette méthode. Pour juger de l’efficacité de cette méthode, ses résultats sur un problème de conception de réseau seront comparés à ceux d’une génération de colonnes classique avec boxstep et stabilisation par point intérieur.

Optimisation de la planification de tournées de cars

Alexandre Huart, Université de Valenciennes, LAMIH-UMR 8530

Dans cette exposé, nous nous intéressons à un problème de tournées de véhicules (PTV) avec contrainte horaire. Il s’agit d’un problème combinatoire auquel sont confrontés les transporteurs de voyageurs. Une approche exacte basée sur la génération de colonnes permet de résoudre à l’optimum et en des temps acceptables des problèmes de PTV avec fenêtre de temps consistant à la visite d ?une centaine de clients. Pour résoudre des problèmes de taille moyenne et élevée, une nouvelle classe d’heuristiques à base de génération de colonnes permet d’obtenir de bons résultats. Nous proposons une heuristique de cette classe adaptée au transport de voyageurs et nous comparons nos résultats avec ceux d’une heuristique traditionnelle.