Research ArticleOpen AccessGoogle Scholar indexed
Some Remarks on Application of Sandwich Methods in the Minimum Cost Flow Problem
Institute of Mathematics, University of Silesia, Katowice, Poland
Faculty of Mathematics and Natural Sciences, Cardinal Stefan Wyszyński University, Warsaw, Poland
- 1 Institute of Mathematics, University of Silesia, Katowice, Poland
- 2 Faculty of Mathematics and Natural Sciences, Cardinal Stefan Wyszyński University, Warsaw, Poland
American Journal of Operations Research·Volume 02 (2012)·Pages 22–35·Published 14 March 2012·DOI10.4236/ajor.2012.21003
Copy link · social · email
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.
KeywordsBicriteria Network Cost Flow ProblemSandwich AlgorithmsEfficient FrontierStochastic Costs
- 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
- 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
- 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
- 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
- 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.
- 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
- 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.
- 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
- 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