×

Parametric maximal flows in generalized networks - complexity and algorithms. (English) Zbl 0662.90028

The author considers the problem of determining parametric maximal flows in networks with gains. Two kinds of parametrization are investigated: parametric flows leaving the source and parametric capacities of the arcs. Both characteristics are linear functions of the parameter \(\lambda\). The goal is to determine the optimal value function \(x_ t(\lambda)\) (amount of flow entering the sink t). Points at which the slope of \(x_ t(\lambda)\) changes are called breakpoints. An efficient implementation of the general piece-by-piece fashion for solving parametric linear programs (vertical approach) is given. A worst-case analysis with respect to the number of breakpoints in the optimal objective value function is performed. The result is an exponential growth of the number of breakpoints depending on the number of vertices in the underlying graph. The worst-case complexity results are the motivation for adapting the idea of a horizontal approximation method developed by H. W. Hamacher and L. R. Foulds [Z. Oper. Res. 33, No.1, 21-37 (1989] for parametric flows in pure networks to the more general case which includes flows with gains. The last algorithm is illustrated by a numerical example.
Reviewer: E.Ciurea

MSC:

90B10 Deterministic network models in operations research
90C35 Programming involving graphs or networks
90C31 Sensitivity, stability, parametric optimization
Full Text: DOI

References:

[1] DOI: 10.1007/BF02591893 · Zbl 0585.90065 · doi:10.1007/BF02591893
[2] Christophides N., Graph Theory – An Algorithmic Approach (1975)
[3] DOI: 10.1287/mnsc.24.12.1209 · doi:10.1287/mnsc.24.12.1209
[4] DOI: 10.1287/opre.21.2.528 · Zbl 0304.90043 · doi:10.1287/opre.21.2.528
[5] Hamacher H.W., To appear in Ztschr. f. Ops. Res. Ser. A:Theory 21 (1988)
[6] Mehlhorn K., Graph Algorithms and NP-Completeness (Data Structures and Algorithms) 2 (1984) · Zbl 0556.68002
[7] DOI: 10.1007/BF01581642 · Zbl 0443.90102 · doi:10.1007/BF01581642
[8] Nozicka F., Theorie und Verfahren der parame-trischen linearen Optimierung (1974)
[9] DOI: 10.1016/0016-0032(67)90046-4 · Zbl 0203.22402 · doi:10.1016/0016-0032(67)90046-4
[10] DOI: 10.1080/02331938508842988 · Zbl 0567.90024 · doi:10.1080/02331938508842988
[11] Ruhe G., Foundations of Control Engineering 9 pp 123– (1984)
[12] DOI: 10.1007/BF01580132 · Zbl 0287.90030 · doi:10.1007/BF01580132
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.