Benders decomposition for the discrete ordered median problem

Ivana Ljubić, Miguel A. Pozo, Justo Puerto and Alberto Torrejón

European Journal of Operational Research, 2024, vol. 317, issue 3, 858-874

Abstract: Ordered median optimization has been proven to be a powerful tool to generalize many well-known problems from the literature. In Location Theory, the Discrete Ordered Median Problem (DOMP) is a facility location problem where clients are first ranked according to their allocation cost to the nearest open facility, and then these costs are multiplied by a suitable weight vector λ. That way, DOMP generalizes many well-known discrete location problems including p-median, p-center or centdian. In this article, we also allow negative entries of λ, allowing us to derive models for better addressing equity and fairness in facility location, for modeling obnoxious facility location problems or for including other client preference models. We present new mixed integer programming models for DOMP along with algorithmic enhancements for solving the DOMP to optimality using mixed integer programming techniques. Specifically, starting from state-of-the-art formulations from the literature, we present several Benders decomposition reformulations applied to them. Using these approaches, new state-of-the-art results have been obtained for different ordered weighting vectors.

Keywords: Discrete location; Ordered median optimization; Benders decomposition; Branch-and-Benders-cut (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724003291
Full text for ScienceDirect subscribers only

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:eee:ejores:v:317:y:2024:i:3:p:858-874

DOI: 10.1016/j.ejor.2024.04.030

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().