Network design using cut inequalities

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.