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

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 :
Preprints, Working Papers, ...
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, September 17, 2019 - 4:20:06 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

Citation

Samuel Deleplanque, Martine Labbé, Diego Ponce Lopez, Justo Puerto. A Branch-Price-and-Cut Procedure for the Discrete Ordered Median Problem. 2018. ⟨hal-01954865⟩

Share

Metrics

Record views

80

Files downloads

83