iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1023/A:1022523615101
Minimum Maximal Flow Problem: An Optimization over the Efficient Set | Journal of Global Optimization Skip to main content
Springer Nature Link
Log in

Minimum Maximal Flow Problem: An Optimization over the Efficient Set

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

The network flow theory and algorithms have been developed on the assumption that each arc flow is controllable and we freely raise and reduce it. We however consider in this paper the situation where we are not able or allowed to reduce the given arc flow. Then we may end up with a maximal flow depending on the initial flow as well as the way of augmentation. Therefore the minimum of the flow values that are attained by maximal flows will play an important role to see how inefficiently the network can be utilized. We formulate this problem as an optimization over the efficient set of a multicriteria program, propose an algorithm, prove its finite convergence, and report on some computational experiments.

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. L.T.H. An, P.D. Tao and L.D. Muu, Numerical solution for optimization over the efficient set by d.c. optimization algorithms, Operations Research Letters 19 (1996) 117-128.

    Google Scholar 

  2. H.P. Benson, An all-linear programming relaxation algorithm for optimizing over the efficient set, Journal of Global Optimization 1 (1991) 83-104.

    Google Scholar 

  3. H.P. Benson, A finite nonadjacent extreme-point search algorithm for optimization over the efficient set, Journal of Optimization Theory and Applications 73 (1992) 47-64.

    Google Scholar 

  4. H.P. Benson, A geometric analysis of the efficient outcome set in multiple objective convex program with linear criteria functions, Journal of Global Optimization 6 (1995) 213-251.

    Google Scholar 

  5. H.P. Benson and D. Lee, Outcome-based algorithm for optimizing over the efficient set of a bicriteria linear programming, Journal of Optimization Theory and Applications 88 (1996) 77-105.

    Google Scholar 

  6. H.P. Benson and S. Sayin, Optimization over the efficient set: four special case, Journal of Optimization Theory and Applications 80 (1994) 3-18.

    Google Scholar 

  7. S. Bolintineanu, Minimization of a quasi-concave function over an efficient set, Mathematical Programming 61 (1993) 89-110.

    Google Scholar 

  8. P.C. Chen, P. Hansen and B. Jaumard, On-line and off-line vertex enumeration by adjacency lists, Operations Research Letters 10 (1991) 403-409.

    Google Scholar 

  9. J.P. Dauer and T.A. Fosnaugh, Optimization over the efficient set, Journal of Global Optimization 7 (1995) 261-277.

    Google Scholar 

  10. J.G. Ecker and J.H. Song, Optimizing a linear function over an efficient set, Journal of Optimization Theory and Applications 83 (1994) 541-563.

    Google Scholar 

  11. J. Fülöp, A cutting plane algorithm for linear optimization over the efficient set, in: S. Komlösi, T. Rapcsàk and S. Shaible (eds.) Generalized Convexity, Lecture Notes in Economics and Mathematical Systems 405, (Springer, Berlin, 1994) pp. 374-385.

    Google Scholar 

  12. M.R. Garay and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, (Freeman, San Francisco, 1979).

    Google Scholar 

  13. R. Horst, J. de Vries and N.V. Thoai, On finding new vertices and redundant constraints in cutting plane algorithms for global optimization, Operations Research Letters 7 (1988) 85-90.

    Google Scholar 

  14. R. Horst and N.V. Thoai, Maximizing a concave function over the efficient or weakly-efficient set, European Journal of Operational Research 117 (1999) 239-252.

    Google Scholar 

  15. R. Horst and H. Tuy, Global Optimization: Deterministic Approach, (Springer, Berlin, 1996).

    Google Scholar 

  16. M. Iri, An essay in the theory of uncontrollable flows and congestion, Technical Report, Department of Information and System Engineering, Faculty of Science and Engineering, Chuo University, TRISE 94-03 (1994).

  17. M. Iri, Network flow - theory and applications with practical impact, in: J. Doležal and J. Fidler (eds.) System Modelling and Optimization, (Chapman & Hall, London, 1996) pp. 24-36.

    Google Scholar 

  18. M. Iri, Theory of uncontrollable flows - a new type of network-flow theory as a model for the 21th century of multiple values, Computers and Mathematics with Applications 35 (1998) 107-123.

    Google Scholar 

  19. O.L. Mangasaarian, Nonlinear Programming, (MacGraw-Hill, New York, 1969).

    Google Scholar 

  20. L.D. Muu, A convex-concave programming method for optimizing over the efficient set, Acta Mathematica Vietnamica 25 1, 67-85.

  21. P.H. Naccache, Connectedness of the set of nondominated outcomes in multicriteria optimization, Journal of Optimization Theory and Applications 25 (1978) 459-467.

    Google Scholar 

  22. J. Philip, Algorithms for the vector maximization problem, Mathematical Programming 2 (1972) 207-229.

    Google Scholar 

  23. T.Q. Phong and J.Q. Tuyen, Bisection search algorithm for optimizing over the efficient set, Vietnam Journal of Mathematics 28:3 (2000) 217-226.

    Google Scholar 

  24. S. Sayin, Optimizing over the efficient set using a top-down search of faces, Operations Research 48 (2000) 65-72.

    Google Scholar 

  25. Y. Sawaragi, H. Nakayama and T. Tanino, Theory of Multiobjective Optimization (Academic Press, Orlando, FL, 1985).

    Google Scholar 

  26. J.M. Shi and Y. Yamamoto, A global optimization method for minimum maximal flow problem, Acta Mathematica Vietnamica 22 (1997) 271–287.

    Google Scholar 

  27. R.E. Steuer, Multiple Criteria Optimization: Theory, Computation and Application (Wiley, New York, 1985).

    Google Scholar 

  28. P.T. Thach, H. Konno and D. Yokota, Dual approach to minimization on the set of paretooptimal solutions, Journal of Optimization Theory and Applications 88 (1996) 689-707.

    Google Scholar 

  29. T.V. Thieu, B.T. Tam and V.T. Ban, An outer-approximation method for globally minimizing a concave function over a compact convex set, Acta Mathematica Vietnamica 8 (1983) 21-40.

    Google Scholar 

  30. N.V. Thoai, A class of optimization problems over the efficient set of a multiple criteria nonlinear programming problem, European Journal of Operational Research 122 (2000) 58-68.

    Google Scholar 

  31. N.V. Thoai, Conical algorithm in global optimization for optimizing over efficient sets, Journal of Global Optimization 18 (2000) 321-336.

    Google Scholar 

  32. D.J. White, Optimality and Efficiency, (John Wiley & Sons, Chichester, 1982).

    Google Scholar 

  33. D.J. White, The maximization of a function over the efficient set via a penalty function approach, European Journal of Operational Research 94 (1996) 143-153.

    Google Scholar 

  34. S. Yamada, T. Tanino and M. Inuiguchi, An inner approximation method for optimization over the weakly efficient set, Journal of Global Optimization 16 (2000) 197-217.

    Google Scholar 

  35. Y. Yamamoto, Optimization over the efficient set: Overview, to appear in Journal of Global Optimization.

Download references

Author information

Authors and Affiliations

  1. Institute of Policy and Planning Sciences, University of Tsukuba, Tsukuba, Ibaraki, 305-8573, Japan

    M. Shigeno, I. Takahashi & Y. Yamamoto

Authors
  1. M. Shigeno
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. I. Takahashi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Y. Yamamoto
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Shigeno, M., Takahashi, I. & Yamamoto, Y. Minimum Maximal Flow Problem: An Optimization over the Efficient Set. Journal of Global Optimization 25, 425–443 (2003). https://doi.org/10.1023/A:1022523615101

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1022523615101

Search

Navigation