Models for the Discrete Ordered Median Problem based on DC decomposition

The Discrete Ordered Median Problem is a flexible model for a large variety of location problems. It relies on sorting allocation costs non-decreasingly before applying a weight vector. Being a non-linear operation, the cost-sorting is particularly challenging from a modeling point of view. Promising approaches use radius variables or reformulations of the ordered median objective function leading to efficient mixed-integer linear programming models. This study introduces an alternative modeling paradigm that exploits a known Difference of Convex functions (DC) decomposition of ordered median functions. The proposed framework offers a systematic way to combine existing formulations and to derive new ones. To illustrate its potential, we develop several new models for the Discrete Ordered Median Problem based on this concept. An extensive computational study is conducted to evaluate their performance against current state-of-the-art formulations. The results show that the proposed approach can lead to highly competitive and previously undiscovered models.