An extended version of a Branch-Price-and-Cut Procedure for the Discrete Ordered Median Problem

2018/02/09 by Samuel Deleplanque, Martine Labbé, Deleplanque, Samuel +5
Engineering · #90C06 #90C11 #90C27 #90C39 #Advanced Manufacturing and Logistics Optimization #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Packing Problems #Vehicle Routing Optimization Methods

paper · pdf · doi:10.48550/arxiv.1802.03191

openalex publication_date 2018/02/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 to optimality small to moderate size of DOMP in competitive computational time.

Related

• A Branch-and-Price approach for the Continuous Multifacility Monotone Ordered Median Problem
• An exact copositive programming formulation for the Discrete Ordered Median Problem: Extended version
• Constant-Factor Approximation for Ordered k-Median
• Lotsize optimization leading to a p-median problem with cardinalities
• An Optimization Algorithm for the Ordered Open-End Bin-Packing Problem