Network Design Using Cut Inequalities

Francisco Barahona

SIAM Journal on Optimization · 1996 · 146 citations · 16 references

Concepts

TL;DR

Network loading problems are typically aggregated into a backbone network for analysis. The study investigates network loading with and without bifurcations. A cut‑condition relaxation for multicommodity flows is applied, and solutions from the bifurcated case are used to construct solutions for the nonbifurcated problem. Applying this approach to practical backbone networks yielded feasible solutions and bounds on the optimality gap.

Abstract

We study the network loading problem, with and without bifurcations. We use a relaxation based on the cut condition for multicommodity flows. We use a solution of the bifurcated case to derive a solution to the nonbifurcated problem. A standard procedure is to aggregate the problem into a backbone network. We applied this method to backbone networks coming from practical instances; we obtained feasible solutions and bounds for the gap from optimality.

References

16