Optimal network design

Last updated

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.

Contents

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. [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

Related Research Articles

<span class="mw-page-title-main">Travelling salesman problem</span> NP-hard problem in combinatorial optimization

The travelling salesman problem, also known as the travelling salesperson problem (TSP), asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

<span class="mw-page-title-main">Minimum spanning tree</span> Least-weight tree connecting graph vertices

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

<span class="mw-page-title-main">Greedy algorithm</span> Sequence of locally optimal choices

A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints are linear.

<span class="mw-page-title-main">Combinatorial optimization</span> Subfield of mathematical optimization

Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead.

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as an approximation ratio or approximation factor i.e., the optimal solution is always guaranteed to be within a (predetermined) multiplicative factor of the returned solution. However, there are also many approximation algorithms that provide an additive guarantee on the quality of the returned solution. A notable example of an approximation algorithm that provides both is the classic approximation algorithm of Lenstra, Shmoys and Tardos for scheduling on unrelated parallel machines.

<span class="mw-page-title-main">Euclidean minimum spanning tree</span> Shortest network connecting points

A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.

In mathematics, engineering, computer science and economics, an optimization problem is the problem of finding the best solution from all feasible solutions.

<i>k</i>-minimum spanning tree

The k-minimum spanning tree problem, studied in theoretical computer science, asks for a tree of minimum cost that has exactly k vertices and forms a subgraph of a larger graph. It is also called the k-MST or edge-weighted k-cardinality tree. Finding this tree is NP-hard, but it can be approximated to within a constant approximation ratio in polynomial time.

The Christofides algorithm or Christofides–Serdyukov algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space . It is an approximation algorithm that guarantees that its solutions will be within a factor of 3/2 of the optimal solution length, and is named after Nicos Christofides and Anatoliy I. Serdyukov ; the latter discovered it independently in 1976.

Capacitated minimum spanning tree is a minimal cost spanning tree of a graph that has a designated root node and satisfies the capacity constraint . The capacity constraint ensures that all subtrees incident on the root node have no more than nodes. If the tree nodes have weights, then the capacity constraint may be interpreted as follows: the sum of weights in any subtree should be no greater than . The edges connecting the subgraphs to the root node are called gates. Finding the optimal solution is NP-hard.

<span class="mw-page-title-main">David Shmoys</span> American mathematician

David Bernard Shmoys is a Professor in the School of Operations Research and Information Engineering and the Department of Computer Science at Cornell University. He obtained his Ph.D. from the University of California, Berkeley in 1984. His major focus has been in the design and analysis of algorithms for discrete optimization problems.

In computer science and operations research, randomized rounding is a widely used approach for designing and analyzing approximation algorithms.

The rectilinear Steiner tree problem, minimum rectilinear Steiner tree problem (MRST), or rectilinear Steiner minimum tree problem (RSMT) is a variant of the geometric Steiner tree problem in the plane, in which the Euclidean distance is replaced with the rectilinear distance. The problem may be formally stated as follows: given n points in the plane, it is required to interconnect them all by a shortest network which consists only of vertical and horizontal line segments. It can be shown that such a network is a tree whose vertices are the input points plus some extra points.

In computer science, the minimum routing cost spanning tree of a weighted graph is a spanning tree minimizing the sum of pairwise distances between vertices in the tree. It is also called the optimum distance spanning tree, shortest total path length spanning tree, minimum total distance spanning tree, or minimum average distance spanning tree. In an unweighted graph, this is the spanning tree of minimum Wiener index. Hu (1974) writes that the problem of constructing these trees was proposed by Francesco Maffioli.

Truthful job scheduling is a mechanism design variant of the job shop scheduling problem from operations research.

In the study of hierarchical clustering, Dasgupta's objective is a measure of the quality of a clustering, defined from a similarity measure on the elements to be clustered. It is named after Sanjoy Dasgupta, who formulated it in 2016. Its key property is that, when the similarity comes from an ultrametric space, the optimal clustering for this quality measure follows the underlying structure of the ultrametric space. In this sense, clustering methods that produce good clusterings for this objective can be expected to approximate the ground truth underlying the given similarity measure.

In computer science, multiway number partitioning is the problem of partitioning a multiset of numbers into a fixed number of subsets, such that the sums of the subsets are as similar as possible. It was first presented by Ronald Graham in 1969 in the context of the identical-machines scheduling problem. The problem is parametrized by a positive integer k, and called k-way number partitioning. The input to the problem is a multiset S of numbers, whose sum is k*T.

Unrelated-machines scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We need to schedule n jobs J1, J2, ..., Jn on m different machines, such that a certain objective function is optimized. The time that machine i needs in order to process job j is denoted by pi,j. The term unrelated emphasizes that there is no relation between values of pi,j for different i and j. This is in contrast to two special cases of this problem: uniform-machines scheduling - in which pi,j = pi / sj, and identical-machines scheduling - in which pi,j = pi.

References

  1. ↑ 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.
  2. ↑ Dionne, R.; Florian, M. (March 1979). "Exact and approximate algorithms for optimal network design". Networks. 9 (1): 37–59. doi:10.1002/net.3230090104.
  3. ↑ 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.
  4. ↑ 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.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.