A new polynomial-time implementation of the out-of-kilter algorithm using Minty’s lemma

• Autorzy: Ghiyasvand M.
• Języki publikacji: EN

Abstrakty

EN

It is less well known how to use the out-of-kilter idea to solve the min-cost flow problem because the generic version of the out-of-kilter algorithm runs in exponential time, although it is the sort of algorithm that computers can do easily. Ciupala (2005) presented a scaling out-of-kilter algorithm that runs in polynomial time using the shortest path computation in each phase. In this paper, we present a new polynomial time implementation of out-of-kilter idea. The algorithm uses a scaling method that is different from Ciupala’s scaling method. Each phase of Ciupala’s method needs a shortest path computation, while our algorithm uses Minty’s lemma to transform all the out-of-kilter arcs into in-kilter arcs. When the given network is infeasible, Ciupala’s algorithm does not work, but our algorithm presents some information that helps to repair the infeasible network.

Słowa kluczowe

EN

network flows; minimum cost flow problem; out- of-kilter algorithm; Minty’s lemma

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2014
• Tom: Vol. 43, no. 1
• Strony: 79--94
• Opis fizyczny: Bibliogr. 16 poz., rys.

Twórcy

autor

Ghiyasvand M.

• Department of Mathematics, Faculty of Science Bu-Ali Sina University, Hamedan, Iran

Bibliografia

• 1. AHUJA R.K., GOLDBERG A.V., ORLIN J.B. and TARJAN R.E. (1992)
• 2. Finding minimum-cost flows by double scaling. Mathematical Programming 53, 243-266.
• 3. AHUJA R.K., MAGNANTI T.L. and ORLIN J.B. (1993) Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs, NJ.
• 4. BUSAKER R.G. and GOWEN P.J. (1961) A procedure for Determining a Family of minimal-cost Network Flow patterns. Technical Report 15, O.R.O.
• 5. CIUPALA L. (2005) A scaling out-of-kilter algorithm for minimum cost flow. Control and Cybernetics 34(4), 1169-1174.
• 6. EDMONDS I. and KARP R.M. (1972) Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the Association on Computing Machinery 19, 248-264.
• 7. ERVOLINA T.R. and MCCORMICK S.T. (1993) Two strongly polynomial cut canceling algorithms for minimum cost network flow. Discrete Applied Mathematics 46, 133-5.
• 8. FULKERSON D.R. (1961) An out-of-kilter method for minimal cost flow problems. SIAM Journal on Applied Mathematics 9, 18-27.
• 9. GOLDBERG A.V and TARJAN R.E. (1990) Finding minimum-cost circulations by successive approximation. Mathematics of Operations Research 16, 430-466.
• 10. GONDRAN M. and MINOUX M. (1984) Graphs and Algorithms (trans. S. Vajda). Wiley, New York.
• 11. HASSIN R. (1983) The minimum cost flow problem: A unifying approach to dual algorithms and a new tree search algorithm. Mathematical Programming 25, 228-239.
• 12. HOFFMAN A.J. (1960) Some recent applications of the theory of linear in- equalities to extremal combinatorial analysis. In: R. Bellman and M. Hall (eds.), Combinatorial Analysis. Proc. of Symposia in Applied Mathematics, X. American Mathematical Society, Providence, Rhode Island, 113-127.
• 13. JEWELL W.S. (1958) Optimal Flow through Networks. Technical Report 8, M.I.T.
• 14. MINTY G.J. (1960) Monotone networks. Proc. Roy. Soc. London, 257, 194-212.
• 15. MINTY G.J. (1966) On the Axiomatic Foundations of the Theories of Directed linear Graphs, Electrical Networks and Programming. Journal of Mathematics and Mechanics 15, 485-520.
• 16. ORLIN J.B. (1993) A faster strongly polynomial minimum cost flow algorithm. Operations Research, 41, 338 350.