Solving fixed charge network problems with group theory-based penalties
✍ Scribed by R. L. Rardin; V. E. Unger
- Publisher
- John Wiley and Sons
- Year
- 1976
- Tongue
- English
- Weight
- 926 KB
- Volume
- 23
- Category
- Article
- ISSN
- 0894-069X
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
Many well‐known transportation, communication, and facilities location problems in operations research can be formulated as fixed charge network problems, i.e. as minimum cost flow problems on a capacitated network in one commodity where some arcs have both fixed and variable costs. One approach to solving such problems is to use group theoretic concepts from the theory of integer programming to provide bounds for a branch‐and‐bound procedure. This paper presents such a group‐theory based algorithm for exact solution of fixed charge network problems which exploits the special structures of network problems. Computational results are reported for problems with as many as 100 fixed charge arcs.