Approximation methods for solving the stochastic network flow problem with the moment multicriterion



Abstract

In this paper, the stochastic modification of the bicriterial minimum cost flow problem is presented. After the problem’s formulation two approximate algorithms based on sandwich method for a convex curve approximation are presented. The obtained results are illustrated by examples.


Keywords

bicriteria network problems; sandwich algorithm; stochastic costs

1. Burkard R.E., Hamacher H.W., Rote G., Sandwich approximation of univariate convex functions with an applications to separable convex programming, Naval Res. Logist. 38 (1991), 911–924.
2. Fruhwirth B., Burkard R.E., Rote G., Approximation of convex curves with application to the bi-criteria minimum cost flow problem, European J. Oper. Res. 42 (1989), 326–338.
3. Goldfarb D., Idnani A., A numerically stable dual method for solving strictly convex quadratic programs, Math. Program. 27 (1983), 1–33.
4. Rote G., The convergence rate of the sandwich algorithm for approximating convex functions, Computing 48 (1992), 337–361.
5. Ruhe G., Complexity results for multicriterial and parametric network flows using a pathological graph of Zadeh, Z. Oper. Res. 32 (1988), 9–27.
6. Sedeno-Noda A., Gonzalez-Martin C., The biobjective minimum cost flow problem, European J. Oper. Res. 124 (2000), 591–600.
7. Siem A.Y.D., den Hertog D., Hoffmann A.L., A method for approximating univariate convex functions using only function value evaluations, CentER Discussion Paper 67 (2007), 1–26.
8. Yang X.Q., Goh C.J., Analytic efficient solution set for multi-criteria quadratic programs, European J. Oper. Res. 92 (1996), 166–181.
9. Yang X.Q., Goh C.J., A method for convex curve approximation, European J. Oper. Res. 97 (1997), 205–212.
10. Zadeh N., A bad network for the simplex method and other minimum cost flow algorithms, Math. Program. 5 (1973), 255–266.
Download

Published : 2010-09-30


KostrzewskaM., & SochaL. (2010). Approximation methods for solving the stochastic network flow problem with the moment multicriterion. Annales Mathematicae Silesianae, 24, 39-60. Retrieved from https://journals.us.edu.pl/index.php/AMSIL/article/view/14034

Marta Kostrzewska  marta.kostrzewska83@gmail.com
Instytut Matematyki, Uniwersytet Śląski w Katowicach  Poland
Lesław Socha 
Instytut Fizyki, Uniwersytet Śląski w Katowicach & Wydział Matematyczno-Przyrodniczy, Uniwersytet Kardynała Stefana Wyszyńskiego w Warszawie  Poland



The Copyright Holders of the submitted text are the Author and the Journal. The Reader is granted the right to use the pdf documents under the provisions of the Creative Commons 4.0 International License: Attribution (CC BY). The user can copy and redistribute the material in any medium or format and remix, transform, and build upon the material for any purpose.

  1. License
    This journal provides immediate open access to its content under the Creative Commons BY 4.0 license (http://creativecommons.org/licenses/by/4.0/). Authors who publish with this journal retain all copyrights and agree to the terms of the above-mentioned CC BY 4.0 license.
  2. Author’s Warranties
    The author warrants that the article is original, written by stated author/s, has not been published before, contains no unlawful statements, does not infringe the rights of others, is subject to copyright that is vested exclusively in the author and free of any third party rights, and that any necessary written permissions to quote from other sources have been obtained by the author/s.
  3. User Rights
    Under the Creative Commons Attribution license, the users are free to share (copy, distribute and transmit the contribution) and adapt (remix, transform, and build upon the material) the article for any purpose, provided they attribute the contribution in the manner specified by the author or licensor.
  4. Co-Authorship
    If the article was prepared jointly with other authors, the signatory of this form warrants that he/she has been authorized by all co-authors to sign this agreement on their behalf, and agrees to inform his/her co-authors of the terms of this agreement.