Complexity and Approximation of the Continuous Network Design Problem

DOI10.4230/LIPICS.APPROX-RANDOM.2014.226MaRDI QIDQ2969620zbMATH OpenFDO

Authors Martin Gairing, Tobias Harks, Max Klimm

Publication date 22 March 2017

Full work available at URL https://arxiv.org/abs/1307.4258

zbMATH Keywords

computational complexityapproximation algorithmbilevel optimizationnetwork designwardrop equilibriumoptimization under equilibrium constraints

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Transportation, logistics and supply chain management (90B06)

Abstract: We revisit a classical problem in transportation, known as the continuous (bilevel) network design problem, CNDP for short. We are given a graph for which the latency of each edge depends on the ratio of the edge flow and the capacity installed. The goal is to find an optimal investment in edge capacities so as to minimize the sum of the routing cost of the induced Wardrop equilibrium and the investment cost. While this problem is considered as challenging in the literature, its complexity status was still unknown. We close this gap showing that CNDP is strongly NP-complete and APX-hard, both on directed and undirected networks and even for instances with affine latencies. As for the approximation of the problem, we first provide a detailed analysis for a heuristic studied by Marcotte for the special case of monomial latency functions (Mathematical Programming, Vol.~34, 1986). Specifically, we derive a closed form expression of its approximation guarantee for arbitrary sets S of allowed latency functions. Second, we propose a different approximation algorithm and show that it has the same approximation guarantee. As our final -- and arguably most interesting -- result regarding approximation, we show that using the better of the two approximation algorithms results in a strictly improved approximation guarantee for which we give a closed form expression. For affine latencies, e.g., this algorithm achieves a 1.195-approximation which improves on the 5/4 that has been shown before by Marcotte. We finally discuss the case of hard budget constraints on the capacity investment.

Recommendations

• Complexity and approximation of the continuous network design problem
• On the approximability of some network design problems
• On the approximability of some network design problems
• Approximation algorithms for network design problems
• Approximability of capacitated network design
• Approximability of capacitated network design
• Approximation Algorithms for a Network Design Problem
• Approximation Algorithms for Network Design Problems on Bounded Subsets
• scientific article; zbMATH DE number 1670539
• Approximation algorithms for a capacitated network design problem

Cited in

(3)

• The Continuous-Time Service Network Design Problem
• Approximating multi commodity network design on graphs of bounded pathwidth and bounded degree
• Complexity and approximation of the continuous network design problem

This page was built for publication: Complexity and Approximation of the Continuous Network Design Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2969620)