The Discrete Ordered Median Problem revisited: new formulations, properties and algorithms

Diego Ponce Lopez 1, 2
2 INOCS - Integrated Optimization with Complex Structure
ULB - Université Libre de Bruxelles [Bruxelles], Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Résumé : Cette dissertation étudie en profondeur la structure du "Discrete Ordered Median Problem" (DOMP), afin de proposer de nouvelles formulations et de nouveaux algorithmes de résolution. De plus, une extension intéressante du DOMP nommée MDOMP ("Monotone Discrete Ordered Median Problem") a été étudiée.Cette thèse a été structurée en trois grandes parties.La première partie présente une étude riche aux niveaux théorique et expérimentale. Elle développe plusieurs formulations pour le DOMP qui sont basées sur des problèmes d'ordonnancement largement étudiés dans la littérature. Plusieurs d'entres elles nécessitent un nombre réduit de contraintes pour définir le problème en ce qui concerne certaines formulations connues antérieurement. Les bornes inférieures, qui sont obtenues par la résolution de la relaxation linéaire, donnent de meilleurs résultats que les formulations précédentes et ceci même avec tout processus de renforcement désactivé. S'ensuit une étude du polyhèdre de notre formulation la plus forte qui montre sa proximité entre l'enveloppe convexe des solutions entières de notre problème. Un algorithme de branch and cut et d'autres méthodes de résolution sont ensuite comparés. Les expérimentations qui montrent la puissance de nos méthodes s'appuient sur deux grandes familles d'instances. Les premières sont générées aléatoirement et les secondes proviennent de Beasley's OR-library. Ces expérimentations mettent en valeur la qualité de la borne obtenue par notre formulation.La seconde partie propose une formulation "set partitioning" avec un nombre exponentiel de variables. Dans ce chapitre, la formulation comporte des variables associées à un ensemble de demandes affectées à la même facilité selon l'ordre établi sur leurs distances correspondantes. Nous avons alors développé un algorithme de génération de colonnes pour la résolution de la relaxation continue de notre modèle mathématique. Cet algorithme est ensuite déployé au sein d'un Branch-and-Cut-and-Price afin de résoudre des instances de petites et moyennes tailles avec des temps compétitifs.La troisième partie présente l'analyse et la comparaison des différentes formulations du problème DOMP Monotone. Ces formulations combinent plusieurs manières de formuler l'ordre des éléments selon les moyennes pondérées en utilisant plusieurs programmes linéaires du polytope du p-median. Cette approche donne lieu à deux formulations performantes du DOMP sous l'hypothèse de monotonie des vecteurs lambda. Ces formulations sont comparées de manière théorique puis comparées à d'autres formulations valides pour le cas général du vecteur lambda. Une autre formulation est également proposée, elle exploite l'efficacité du caractère rationnel de la monotonie. Cette dernière permet de résoudre efficacement quelques instances où la monotonie a légèrement disparue. Ces formulations ont fait l'objet de plusieurs expérimentations dècrites dans ce manuscrit de thèse. Elles montrent que les formulations spécifiques permettent de résoudre des instances plus importantes que pour le cas général.
Type de document :
Thèse
Operations Research [cs.RO]. Université Libre de Bruxelles (U.L.B.), Belgium, 2016. English
Liste complète des métadonnées

Littérature citée [73 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/tel-01421868
Contributeur : Bernard Fortz <>
Soumis le : vendredi 23 décembre 2016 - 11:11:26
Dernière modification le : vendredi 13 avril 2018 - 01:28:07
Document(s) archivé(s) le : lundi 20 mars 2017 - 20:19:47

Fichier

Identifiants

  • HAL Id : tel-01421868, version 1

Collections

Citation

Diego Ponce Lopez. The Discrete Ordered Median Problem revisited: new formulations, properties and algorithms. Operations Research [cs.RO]. Université Libre de Bruxelles (U.L.B.), Belgium, 2016. English. 〈tel-01421868〉

Partager

Métriques

Consultations de la notice

237

Téléchargements de fichiers

83