6533b830fe1ef96bd1297cde
RESEARCH PRODUCT
An exact algorithm for the min-cost network containment problem
Walter UkovichRaffaele PesentiFranca Rinaldisubject
Mathematical optimizationComputer Networks and Communicationsnetwork designpolyhedra containmentArc (geometry)Network planning and designPolyhedronExact algorithmDistribution (mathematics)Hardware and ArchitectureBounded functionLimit (mathematics)max weight directed cutSoftwareCutting-plane methodInformation SystemsMathematicsdescription
A network design problem which arises in the distribution of a public utility provided by several competitive suppliers is studied. The problem addressed is that of determining minimum-cost (generalized) arc capacities in order to accommodate any demand between given source–sink pairs of nodes, where demands are assumed to fall within predetermined ranges. Feasible flows are initially considered as simply bounded by the usual arc capacity constraints. Then, more general linear constraints are introduced which may limit the weighted sum of the flows on some subsets of arcs. An exact cutting plane algorithm is presented for solving both of the above cases and some computational results are reported. © 2004 Wiley Periodicals, Inc.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2004-01-15 | Networks |