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

Samuel Deleplanque (), Martine Labbé (), Diego Ponce () and Justo Puerto ()
Additional contact information
Samuel Deleplanque: Ifsttar, COSYS, ESTAS, Université Lille Nord de France, 59000 Lille, France
Martine Labbé: Départament d’Informatique, Faculté des Sciences, Université Libre de Bruxelles, 1050 Bruxelles, Belgium
Diego Ponce: Instituto de Matemáticas de la Universidad de Sevilla (IMUS), 41012 Sevilla, Spain; Department of Mechanical, Industrial and Aerospace Engineering, Concordia University, Montreal, Quebec H3G 1M8, Canada; Centre interuniversitaire de recherche sur les réseaux d’enterprise, la logistique et le transport (CIRRELT), Montreal, Quebec H3T 1J4, Canada
Justo Puerto: Instituto de Matemáticas de la Universidad de Sevilla (IMUS), 41012 Sevilla, Spain

INFORMS Journal on Computing, 2020, vol. 32, issue 3, 582-599

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.

Keywords: discrete optimization; location theory; branch and price; ordered median problems (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2019.0915 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:32:y:3:i:2020:p:582-599

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().