Optimal network design
Optimal network design is a problem in combinatorial optimization. It is an abstract representation of the problem faced by states and municipalities when they plan their road network. Given a set of locations to connect by roads, the objective is to have a short traveling distance between every two points. More specifically, the goal is to minimize the sum of shortest distances, where the sum is taken over all pairs of points. For each two locations, there is a number representing the cost of building a direct road between them. A decision must be made about which roads to build with a fixed budget.
Formal definition
[edit]The input to the optimal network design problem is a weighted graph G = (V,E), where the weight of each edge (u,v) in the graph represents the cost of building a road from u to v; and a budget B.
A feasible network is a subset S of E, such that the sum of w(u,v) for all (u,v) in S is at most B, and there is a path between every two nodes u and v (that is, S contains a spanning tree of G).
For each feasible network S, the total cost of S is the sum, over all pairs (u,v) in E, of the length of the shortest path from u to v, which uses only edges in S. The objective is to find a feasible network with a minimum total cost.
Results
[edit]Johnson, Lenstra and Kan prove that the problem is NP-hard, even for the simple case where all edge weights are equal and the budget restricts the choice to spanning trees.[1]
Dionne and Florian studied branch and bound algorithms, and showed that they work in reasonable time on medium-sized inputs, but not on large inputs. Therefore, they presented heuristic approximation algorithms.[2]
Anshelevic, Dasgupta, Tardos and Wexler study a game of network design, where every agent has a set of terminals and wants to build a network in which his terminals are connected, but pay as little as possible. They study the computational problem of checking whether a Nash equilibrium exists. For some special cases, they give a polynomial time algorithm that finds a (1+ε)-approximate Nash equilibrium.[3]
Boffey and Hinxman present a heuristic method, and show that it yields high quality results. They also study solution methods based on branch-and-Bound, and evaluate the effects of making various approximations when calculating lower bounds. They also generalize the problem to networks with link construction cost not proportional to length, and with trip demands that are not all equal.[4]
See also
[edit]- Network planning and design
- Minimum routing cost spanning tree – a similar problem in which the selected set must be a spanning tree.
References
[edit]- ^ Johnson, D. S.; Lenstra, J. K.; Kan, A. H. G. Rinnooy (December 1978). "The complexity of the network design problem" (PDF). Networks. 8 (4): 279–285. doi:10.1002/net.3230080402.
- ^ Dionne, R.; Florian, M. (March 1979). "Exact and approximate algorithms for optimal network design". Networks. 9 (1): 37–59. doi:10.1002/net.3230090104.
- ^ Anshelevich, Elliot; Dasgupta, Anirban; Tardos, Eva; Wexler, Tom (2003). "Near-optimal network design with selfish agents". Proceedings of the thirty-fifth annual ACM symposium on Theory of computing. pp. 511–520. doi:10.1145/780542.780617. ISBN 1-58113-674-9.
- ^ Boffey, T.B.; Hinxman, A.I. (September 1979). "Solving the optimal network problem". European Journal of Operational Research. 3 (5): 386–393. doi:10.1016/0377-2217(79)90118-8.