Some Remarks on Application of Sandwich Methods in the Minimum Cost Flow Problem

Marta Kostrzewska, Leslaw Socha

Faculty of Mathematics and Natural Sciences, Cardinal Stefan Wyszyński University, Warsaw, Poland.
Institute of Mathematics, University of Silesia, Katowice, Poland.

DOI: 10.4236/ajor.2012.21003                

Abstract

In this paper, two new sandwich algorithms for the convex curve approximation are introduced. The proofs of the linear convergence property of the first method and the quadratic convergence property of the second method are given. The methods are applied to approximate the efficient frontier of the stochastic minimum cost flow problem with the moment bicriterion. Two numerical examples including the comparison of the proposed algorithms with two other literature derivative free methods are given.

Keywords

Bicriteria Network Cost Flow Problem; Sandwich Algorithms; Efficient Frontier; Stochastic Costs

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	A. Sedeno-Noda and C. Gonzalez-Martin, “The Biobjective Minimum Cost Flow Problem,” European Journal of Operational Research, Vol. 124, No. 3, 2000, pp. 591- 600. doi:10.1016/S0377-2217(99)00191-5
[2]	X. Q. Yang and C. J. Goh, “Analytic Efficient Solution Set for Multi-Criteria Quadratic Programs,” European Journal of Operational Research, Vol. 92, No. 1, 1996, pp. 166-181. doi:10.1016/0377-2217(95)00040-2
[3]	G. Ruhe, “Complexity Results for Multicriterial and Parametric Network Flows Using a Pathological Graph of Zadeh,” Zeitschrift für Operations Research, Vol. 32, No. 1, 1988, pp. 9-27. doi:10.1007/BF01920568
[4]	N. Zadeh, “A Bad Network for the Simplex Method and Other Minimum Cost Flow Algorithms,” Mathematical Programming, Vol. 5, No. 1, 1973, pp. 255-266. doi:10.1007/BF01580132
[5]	R. E. Burkard, H. W. Hamacher and G. Rote, “Sandwich Approximation of Univariate Convex Functions with an Applications to Separable Convex Programming,” Naval Research Logistics, Vol. 38, 1991, pp. 911-924.
[6]	B. Fruhwirth, R. E. Burkard and G. Rote, “Approximation of Convex Curves with Application to the Bi-Criteria Minimum Cost Flow Problem,” European Journal of Operational Research, Vol. 42, No. 3, 1989, pp. 326-338. doi:10.1016/0377-2217(89)90443-8
[7]	A. Y. D. Siem, D. den Hertog and A. L. Hoffmann, “A Method for Approximating Univariate Convex Functions Using Only Function Value Evaluations,” Center Discussion Paper, Vol. 67, 2007, pp. 1-26.
[8]	X. Q. Yang and C. J. Goh, “A Method for Convex Curve Approximation,” European Journal of Operational Re- search, Vol. 97, No. 1, 1997, pp. 205-212. doi:10.1016/0377-2217(95)00368-1
[9]	G. Rote, “The Convergence Rate of the Sandwich Algorithm for Approximating Convex Functions,” Computing, Vol. 48, No. 3-4, 1992, pp. 337-361. doi:10.1007/BF02238642