Benders decomposition for the discrete ordered median problem
研究了离散有序中位数问题，提出新的混合整数规划模型和Benders分解算法，允许权重为负以处理公平性、厌恶型设施等场景，计算实验表明新方法优于现有方法。
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. • DOMP explores facility location, ranking clients by allocation cost. • New mixed-integer programming models and optimizations for DOMP are introduced. • Benders decomposition enhances state-of-the-art formulations. • DOMP’s scope widens to include diverse problem variants and negative objectives. • Comprehensive computational results validate claims and facilitate future comparisons.