Network Design Using Cut Inequalities
- 1 August 1996
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 6 (3) , 823-837
- https://doi.org/10.1137/s1052623494279134
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.}Keywords
This publication has 16 references indexed in Scilit:
- On two-connected subgraph polytopesDiscrete Mathematics, 1995
- Ground-state magnetization of Ising spin glassesPhysical Review B, 1994
- Separating from the dominant of the spanning tree polytopeOperations Research Letters, 1992
- MENTOR: an algorithm for mesh network topological optimization and routingIEEE Transactions on Communications, 1991
- On the spanning tree polyhedronOperations Research Letters, 1989
- On the exact ground states of three-dimensional Ising spin glassesJournal of Physics A: General Physics, 1982
- Optimum Communication Spanning TreesSIAM Journal on Computing, 1974
- Multi-Terminal Network FlowsJournal of the Society for Industrial and Applied Mathematics, 1961
- On the Problem of Decomposing a Graph into n Connected FactorsJournal of the London Mathematical Society, 1961
- Edge-Disjoint Spanning Trees of Finite GraphsJournal of the London Mathematical Society, 1961