A Branch-Price-and-Cut Procedure for the Discrete Ordered Median Problem

Samuel Deleplanque 1 Martine Labbé 2, 3 Diego Ponce Lopez 4 Justo Puerto 5
1 IFFSTAR
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
3 ULB - Université Libre de Bruxelles [Bruxelles]
4 CIRRELT - Centre Interuniversitaire de Recherche sur les Réseaux d'Entreprise, la Logistique et le Transport
5 IMUS - Departamento de Matemática Aplicada I
Abstract : The Discrete Ordered Median Problem (DOMP) is formulated as a set partitioning problem using an exponential number of variables. Each variable corresponds to a set of demand points allocated to the same facility with the information of the sorting position of their corresponding costs. We develop a column generation approach to solve the continuous relaxation of this model. Then, we apply a branch-price-and-cut algorithm to solve small to large sized instances of DOMP in competitive computational time.
Document type :
Journal articles
Complete list of metadatas

Cited literature [41 references]  Display  Hide  Download
https://hal.inria.fr/hal-01954865
Contributor : Martine Labbé <>
Submitted on : Friday, December 14, 2018 - 8:09:00 AM
Last modification on : Tuesday, November 19, 2019 - 5:30:45 PM
Long-term archiving on: Friday, March 15, 2019 - 1:17:12 PM

File

DOMPbcp.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01954865, version 1

Collections

CNRS | CRISTAL | INRIA | UNIV-LILLE

Citation

Samuel Deleplanque, Martine Labbé, Diego Ponce Lopez, Justo Puerto. A Branch-Price-and-Cut Procedure for the Discrete Ordered Median Problem. INFORMS Journal on Computing, Institute for Operations Research and the Management Sciences (INFORMS), In press. ⟨hal-01954865⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

144

Files downloads

155

 

 

Contact

archive-ouverte@inria.fr