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

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

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.

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.

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.

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.

See also

* Network planning and design
* Minimum routing cost spanning tree – a similar problem in which the selected set must be a spanning tree.

References

{{Reflist

Combinatorial optimization
Networks
Transport
Spanning tree