Network Design Using Cut Inequalities

TLDR

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.