Optimal network design
From Wikipedia, the free encyclopedia
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.
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.