Branch-and-cut algorithm for optimization of non-bifurcated multicommodity flows in survivable networks

• Autorzy: Walkowiak K.
• Języki publikacji: EN

Abstrakty

EN

This paper addresses the problem of non-bifurcated multicommodity flow optimization in survivable networks. As the objective we apply the Lost Flow in Link (LFL) function, which is an upper bound of the flow that can be lost due to a failure of a single link. Since the problem under consideration is NP-complete we propose an exact algorithm to find optimal results. To facilitate the high computation complexity caused by the NP-completeness, we propose three cut inequalities: mixed integer rounding, cover inequality and upper bound on the objective function. Cuts are combined with the branch-and-bound algorithm to construct the branch-an-cut algorithm. We evaluate the proposed cuts by making numerical experiments using five network topologies with various demand patterns. Results of simulation prove the robustness of our approach - combined application of all three cuts reduces the number of nodes and decision time by 80% compared to the branch-and-bound algorithm.

Słowa kluczowe

EN

branch-and-cut; survivable networks; MPLS

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Systems Science
• Rocznik: 2006
• Tom: Vol. 32, no 3
• Strony: 27--35
• Opis fizyczny: Bibliogr. 12 poz., rys., wykr.

Twórcy

autor

Walkowiak K.

• Faculty of Electronics, Wroclaw University of technology Wyb. Wyspiańskiego 27, 50-370 Wroclaw, Poland,

Bibliografia

• [1] Barnhart C, Hane C.A., Vance P.M., Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems, Operations Research, Vol. 48, No. 2, 2000, pp. 318-326.
• [2] Grover W., Mesh-based Survivable Networks: Options and Strategies for Optical, MPLS, SONET and ATM Networking. Prentice Hall PTR, Upper Saddle River, New Jersey, 2004.
• [3] Gunluk O., Branch-and-Citt Algorithm for Capacitated Network Design Problems, Math. Programming, 86, 1999, pp. 17-39.
• [4] Marchand H., Wolsey L.A., Aggregation and mixed integer rounding to solve MIPs, Operations Research, 49, 2001, pp. 363-371.
• [5] Mitchell J., Branch-and-cut methods for combinatorial optimization problems, [in:] Handbook of Applied Optimization, Oxford University Press, 2002.
• [6] Padberg M., Rinaldi G., Optimization of a 532-city traveling salesman problem by branch-and-cut, Operations Research Letters, 6, 1987.
• [7] Pióro M., Medhi D., Routing, Flow, and Capacity Design in Communication and Computer Networks, Morgan Kaufman Publishers, 2004.
• [8] Sharma V., Hellstrand F. (eds.), Framework for MPLS-based Recovery, RFC 3469, 2003.
• [9] Walkowiak K., A Branch and Bound Algorithm far Primary Routes Assignment in Survivable Connection Oriented Networks, Computational Optimization and Applications, KAP, Vol. 27, No. 2, 2004, pp. 149-171.
• [10] Walkowiak K., A New Method of Primary Routes Selection for Local Restoration, Lecture Notes in Computer Science, Springer Verlag, Vol. 3042, 2004, pp. 1024-1035.
• [11] Walkowiak K., Survivable Online Routing for MPLS Traffic Engineering, Lecture Notes in Computer Science, Springer Verlag, Vol. 3266. 2004, pp. 288-297.
• [12] Walkowiak K., Lagrangean Heuristic for Primary Routes Assignment in Survivable Connection-Oriented Networks, accepted for Computational Optimization and Applications, 2006.