Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Algorithms for flows with parametric capacities

  • Published:
Zeitschrift für Operations-Research Aims and scope Submit manuscript

Abstract

We consider the problem of finding maximal flows with respect to capacities which are linear functions of a parametert ∈ [0,T]. Since this problem is a special case of a parametric linear program the classichorizontal approach can be applied in which optimal solutions are computed for successive subintervals of [0,T]. We discuss an alternative algorithm which approximates in each iteration the optimal solution for allt ∈ [0,T]. Thisvertical algorithm is a labeling type algorithm where the flow variables are piecewise linear functions. Flow augmentations are done alongconditional flow augmenting paths which can be found by modified path algorithms. The vertical algorithm can be used to solve the parametric flow problem optimally as well as to compute a good approximation for allt if the computation of the optimal solution turns out to be too time consuming.

Zusammenfassung

Wir betrachten maximale Flußprobleme, in denen die Kapazitäten lineare Funktionen eines Parameterst ∈ [0,T] sind. Da dieses Problem ein Spezialfall eines parametrischen linearen Programms ist, kann man den klassischen horizontalen Ansatz anwenden, mit dem optimale Lösungen sukzessive auf Teilintervallen von [0,T] bestimmt werden. Wir stellen einen alternativen Algorithmus vor, der in jeder Iteration die optimale Lösung für allet ∈ [0,T] approximiert. Dieser vertikalen Ansatz ist eine Art Markierungsalgorithmus, wobei die Flußvariablen stückweise lineare Funktionen sind. Flußvergrößerungen werden aufbedingten flußvergrößernden Wegen durchgeführt, die mittels modifizierter kürzester Wege Algorithmen gefunden werden können. Der vertikale Algorithmus kann sowohl zur Berechnung des optimalen parametrischen Flusses als auch zur Berechnung einer guten Approximation für allet benutzt werden, falls sich herausstellt, daß die Berechnung der optimalen Lösung zu zeitaufwendig ist.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bellman RE (1958) On a routing problem. Quart Appl Math 16:87–90

    MathSciNet  MATH  Google Scholar 

  2. Carstensen PJ (1983) The complexity of some problems in parametric linear and combinatorial programming. PhD Dissertation Mathematics Department, University of Michigan, Ann Arbor, Michigan

    Google Scholar 

  3. Carstensen PJ (1983) Complexity of some parametric integer and network programming problems. Math Programming 26:64–75

    Article  MathSciNet  MATH  Google Scholar 

  4. Edmonds J, Karp RM (1972) Theoretical improvement in algorithmic efficiency for network flow problems. Journal of the ACM 19:248–264

    Article  MATH  Google Scholar 

  5. Eisner MJ, Severence DG (1976) Mathematical techniques for efficient record segmentation in large shared databases. Journal of the ACM 23/4:619–635

    Article  MathSciNet  MATH  Google Scholar 

  6. Ford LR (1956) Network flow theory. Rand Paper P 923, Santa Monica

  7. Ford LR, Fulkerson DR (1962) Flows in networks. Princeton University Press, Princeton, NY

    MATH  Google Scholar 

  8. Gal T (1979) Postoptimal analysis, parametric programming and related topics. McGraw-Hill, New York

    MATH  Google Scholar 

  9. Hamacher HW (1980) Algebraic flows in regular matroids. Discrete Applied Mathematics 2:27–38

    Article  MathSciNet  MATH  Google Scholar 

  10. Hamacher HW (1980) Maximal algebraic flows: algorithms and examples. In: Pape U (ed) Discrete structures and algorithms. Hanser, Muenchen, pp 153–166

    Google Scholar 

  11. Karzanov AV (1974) Determining the maximal flow in a network by the method of preflows. Soviet Math Dokl 15:434–437

    MATH  Google Scholar 

  12. Murty K (1976) Linear and combinatorial programming. Wiley, New York

    MATH  Google Scholar 

  13. Murty K (1980) Computational complexity of parametric linear programming. Math Programming 19:213–219

    Article  MathSciNet  MATH  Google Scholar 

  14. Ruhe G (1985) Characterization of all optimal solutions and parametric maximal flows in networks. MOS, Series Optimization 16:51–61

    Article  MathSciNet  MATH  Google Scholar 

  15. Somers JE (1976) Parametric network flow problems. PhD Thesis, University of California, Berkeley, Mathematics Department

    Google Scholar 

  16. Stone H (1977) Multiprocessor scheduling with aid of network flows algorithms. IEEE Transactions on Software Engineering, SE-3:85–93

    Article  MATH  Google Scholar 

  17. Stone H (1978) Critical load factors. IEEE Transactions on Software Engineering, SE-4:254–258

    Article  MATH  Google Scholar 

  18. Zadeh N (1973) A bad network problem for the simplex method and other minimum cost flow algorithms. Mathematical Programming 5:255–266

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Fachbereich Mathematik, Universität Kaiserslautern, FRG

    H. W. Hamacher

  2. Center for Optimization and Combinatorics, University of Florida, Gainesville, USA

    H. W. Hamacher

  3. Department of Management, University of Waikato, New Zealand

    L. R. Foulds

Authors
  1. H. W. Hamacher
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. L. R. Foulds
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Partially supported by NSF Grants ECS-8412926 and INT-8521433, and NATO Grant RG 85/0240.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hamacher, H.W., Foulds, L.R. Algorithms for flows with parametric capacities. ZOR - Methods and Models of Operations Research 33, 21–37 (1989). https://doi.org/10.1007/BF01415514

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01415514

Key words

Search

Navigation