2017/09/07 by Nesrine Bakkar Ennaifer, Safa Bhar Layeb, Ennaifer, Nesrine Bakkar +4
Business, Management and Accounting · Engineering · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Facility Location and Emergency Management #Optimization and Control (math.OC) #Sustainable Supply Chain Management #Vehicle Routing Optimization Methods #math.CO #math.OC
paper · pdf · doi:10.48550/arxiv.1709.02731
arxiv created 2017/09/07 · openalex publication_date 2017/09/07 · arxiv updated 2017/09/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
We aim to derive effective lower bounds for the Discrete Cost Multicommodity Network Design Problem (DCMNDP). Given an undirected graph, the problem requires installing at most one facility on each edge such that a set of point-to-point commodity flows can be routed and costs are minimized. In the literature, the Lagrangian relaxation is usually applied to an arc-based formulation to derive lower bounds. In this work, we investigate a path-based formulation and we solve its Lagrangian relaxation using several non-differentiable optimization techniques. More precisely, we devised six variants of the deflected subgradient procedures, using various direction-search and step-length strategies. The computational performance of these Lagrangian-based approaches are evaluated and compared on a set of randomly generated instances, and real-world problems.