A comparative study of formulations and solution methods for the discrete ordered p-median problem

Martine Labbé 1, 2 Diego Ponce Lopez 1, 3 Justo Puerto 3
1 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
Abstract : This paper presents several new formulations for the Discrete Ordered Median Problem (DOMP) based on its similarity with some scheduling problems. Some of the new formulations present a considerably smaller number of constraints to define the problem with respect to some previously known formulations. Furthermore, the lower bounds provided by their linear relaxations improve the ones obtained with previous formulations in the literature even when strengthening is not applied. We also present a polyhedral study of the assignment polytope of our tightest formulation showing its proximity to the convex hull of the integer solutions of the problem. Several resolution approaches, among which we mention a branch and cut algorithm, are compared. Extensive computational results on two families of instances, namely randomly generated and from Beasley's OR-library, show the power of our methods for solving DOMP.
Type de document :
Article dans une revue
Computers and Operations Research, Elsevier, 2017, 78, pp.230-242. 〈10.1016/j.cor.2016.06.004〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01419555
Contributeur : Bernard Fortz <>
Soumis le : lundi 19 décembre 2016 - 16:13:58
Dernière modification le : vendredi 13 avril 2018 - 01:28:06

Identifiants

Collections

Citation

Martine Labbé, Diego Ponce Lopez, Justo Puerto. A comparative study of formulations and solution methods for the discrete ordered p-median problem. Computers and Operations Research, Elsevier, 2017, 78, pp.230-242. 〈10.1016/j.cor.2016.06.004〉. 〈hal-01419555〉

Partager

Métriques

Consultations de la notice

102