User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

LS(Graph): a constraint-based local search for constraint optimization on trees and paths

Primary tabs

download
  • Open access
  • PDF
  • 3.67 M
Pham Quang, Dung [UCL] Deville, Yves [UCL] Van Hentenryck, Pascal [Brown University]

Constrained optimum tree (COT) and constrained optimum path (COP) problems arise in many real-life applications and are ubiquitous in communication networks. They have been traditionally approached by dedicated algorithms, which are often hard to extend with side constraints and to apply widely. This paper pro- poses a constraint-based local search framework for COT/COP applications, bring- ing the compositionality, reuse, and extensibility at the core of constraint-based local search and constraint programming systems. The modeling contribution is the abil- ity to express compositional models for various COT/COP applications at a high level of abstraction, while cleanly separating the model and the search procedure. The main technical contribution is a connected neighborhood based on rooted span- ning trees to find high-quality solutions to COP problems. This framework is applied to some COT/COP problems, e.g., the quorumcast routing problem, the edge-disjoint paths problem, and the routing and wavelength assignment with delay side constraints problem. Computational results show the potential importance of the approach.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès libre
Publication date 2012
Language Anglais
Journal information "Constraints : an international journal" - Vol. 17, p. 1-52 (2012)
Peer reviewed yes
Publisher Springer New York LLC ((United States) New York)
issn 1383-7133
e-issn 1572-9354
Publication status Publié
Affiliations UCL - SST/ICTM/INGI - Pôle en ingénierie informatique
Brown University - Victoria Research Laboratories
FUNDP - LET_Histoire
Keywords Combinatorial optimization ; Routing ; ICTEAM:MLAI ; Edge-disjoint paths ; Quorumcast routing ; wavelength assignment with delay constraints ; Constrained optimum paths ; Constrained optimum trees ; Graphs ; Constraint-based local search ; 1160
Links
  1. Acar, U., Blelloch, G., Harper, R., Vittes, J., & Woo, S. (2004). An experimental analysis of change propagation in dynamic trees. In Proc 15th SODA (pp. 524–533).
  2. Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: Theory, algorithms, and applications. Englewood Cliffs: Prentice Hall.
  3. Ahuja Ravindra K., Orlin James B., Sharma Dushyant, A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem, 10.1016/s0167-6377(02)00236-5
  4. Ali, M., Ramamurthy, B., & Deogun, J. (1999). Genetic algorithm for routing in wdm optical networks with power considerations. Part I: The unicast case. In Proceedings of the 8th IEEE ICCCN’99 (pp. 335–340). Boston-Natick, MA, USA.
  5. Ali Maher, Ramamurthy Byrav, Deogun Jitender S., Routing and wavelength assignment with power considerations in optical networks, 10.1016/s1389-1286(00)00015-3
  6. Alstrup Stephen, Holm Jacob, Lichtenberg Kristian De, Thorup Mikkel, Maintaining information in fully dynamic trees with top trees, 10.1145/1103963.1103966
  7. Andrade Rafael, Lucena Abilio, Maculan Nelson, Using Lagrangian dual information to generate degree constrained spanning trees, 10.1016/j.dam.2005.06.011
  8. Awerbuch, B., Gawlick, R., Leighton, T., & Rabani, Y. (1994). On-line admission control and circuit routing for high performance computing and communication. In 35th IEEE symposium on foundations of computer science (FOCS1994) (pp. 412–423).
  9. Badeau Philippe, Guertin François, Gendreau Michel, Potvin Jean-Yves, Taillard Eric, A parallel tabu search heuristic for the vehicle routing problem with time windows, 10.1016/s0968-090x(97)00005-3
  10. Banerjee, D., Mehta, V., & Pandey, S. (2004). A genetic algorithm approach for solving the routing and wavelength assignment problem in wdm networks. In 3rd IEEE/IEE international conference on networking, ICN’2004 (pp. 70–78). Paris.
  11. Banerjee D., Mukherjee B., Wavelength-routed optical networks: linear formulation, resource budgeting tradeoffs, and a reconfiguration study, 10.1109/90.879346
  12. Banerjee S., Jay Yoo, Chien Chen, Design of wavelength-routed optical networks for packet switched traffic, 10.1109/50.622888
  13. Baveja Alok, Srinivasan Aravind, Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems, 10.1287/moor.25.2.255.12228
  14. Beasley, J. E. (2012). Or-library. http://people.brunel.ac.uk/~mastjjb/jeb/info.html . Accessed 15 Nov 2009.
  15. Beasley J. E., Christofides N., An algorithm for the resource constrained shortest path problem, 10.1002/net.3230190402
  16. Bender Michael A., Farach-Colton Martín, Pemmasani Giridhar, Skiena Steven, Sumazin Pavel, Lowest common ancestors in trees and directed acyclic graphs, 10.1016/j.jalgor.2005.08.001
  17. Berkman Omer, Vishkin Uzi, Recursive Star-Tree Parallel Data Structure, 10.1137/0222017
  18. Blesa Maria J., Blum Christian, Finding Edge-disjoint Paths in Networks: An Ant Colony Optimization Algorithm, 10.1007/s10852-007-9060-y
  19. Blum Christian, A new hybrid evolutionary algorithm for the huge k-cardinality tree problem, 10.1145/1143997.1144092
  20. Blum Christian, Blesa Maria J., New metaheuristic approaches for the edge-weighted k-cardinality tree problem, 10.1016/j.cor.2003.11.007
  21. Bui, T., & Sundarraj, G. (2004). Ant system for the k-cardinality tree problem. In K. Deb, et al. (Ed.), Proceedings of the genetic and evolutionary computation conference (GECCO 2004) (Vol. 3102, pp. 36–47).
  22. Chekuri, C., & Khanna, S. (2003). Edge disjoint paths revisited. In Proceedings of the 14th ACM-SIAM symposium on discrete algorithms (SODA2003) (pp. 628–637).
  23. Chen, C., & Banerjee, S. (1996). A new model for optimal routing and wavelength assignment in wavelength division multiplexed optical networks. In INFOCOM 1996 (pp. 164–171).
  24. Cheung, S. Y., & Kumar, A. (1994). Efficient quorumcast routing algorithms. In Proceedings of INFOCOM’94 (pp. 840–847).
  25. Chimani, M., Kandyba, M., Ljubic, I., & Mutzel, P. (2009). Obtaining optimal k-cardinality trees fast. ACM Journal of Experimental Algorithmics, 14(2), 5.1–5.23.
  26. Chlamtac I., Ganz A., Karmi G., Lightpath communications: an approach to high bandwidth optical WAN's, 10.1109/26.153361
  27. Clímaco João C. N., Craveirinha José M. F., Pascoal Marta M. B., A bicriterion approach for routing problems in multimedia networks, 10.1002/net.10073
  28. de Aragão, M., Uchoa, E., & Werneck, R. (2001). Dual heuristics on the exact solution of large Steiner problems. In Proceedings of the Brazilian symposium on graphs, algorithms and combinatorics GRACO’01. Fortaleza.
  29. Du, B., Gu, J., Tsang, D., & Wang, W. (1996). Quorumcast routing by multispace search. In Proceedings of IEEE Globecom1996 (pp. 1069–1073).
  30. Dumitrescu I., Boland N., Improved preprocessing, labeling and scaling algorithms for the Weight-Constrained Shortest Path Problem, 10.1002/net.10090
  31. Dutta, R., & Rouskas, G. N. (2000). A survey of virtual topology design algorithms for wavelength routed optical networks. Optical Networks, 1(1), 73–89.
  32. Fischer, T. (2007). Improved local search for large optimum communication spanning tree problems. In MIC’2007—7th metaheuristics international conference.
  33. Frederickson Greg N., A Data Structure for Dynamically Maintaining Rooted Trees, 10.1006/jagm.1996.0835
  34. Funke Birger, Grünert Tore, Irnich Stefan, Local Search for Vehicle Routing and Scheduling Problems: Review and Conceptual Integration, 10.1007/s10732-005-1997-2
  35. Gruber, M., van Hemert, J., & Raidl, G. (2006). Neighborhood searches for the bounded diameter minimum spanning tree problem embedded in a VNS, EA, and ACO. In Proceedings of the genetic and evolutionary computation conference (pp.  1187–1194).
  36. Henzinger Monika R., King Valerie, Randomized fully dynamic graph algorithms with polylogarithmic time per operation, 10.1145/320211.320215
  37. Ho Trong Viet, Bonaventure Olivier, Deville Yves, Pham Quang Dung, Francois Pierre, Using local search for traffic engineering in switched Ethernet networks, 10.1109/itc.2010.5608731
  38. Hyytia, E. (2004). Resource allocation and performance analysis problems in optical networks. Ph.d. thesis, Dpt. of Electrical and Communications Engineering, Helsinki University of Technology, Helsinki, Sweden.
  39. Jaumard B., Meyer C., Yu X., How much wavelength conversion allows a reduction in the blocking rate?, 10.1364/jon.5.000881
  40. Jaumard B., Meyer C., Thiongane B., Comparison of ILP formulations for the RWA problem, 10.1016/j.osn.2007.05.002
  41. Kanellakis Paris-C., Papadimitriou Christos H., Local Search for the Asymmetric Traveling Salesman Problem, 10.1287/opre.28.5.1086
  42. Kleinberg, J. (1996). Approximation algorithms for disjoint-paths problems. PhD thesis. Cambridge: MIT Press.
  43. Kolliopoulos Stavros G., Stein Clifford, Approximating disjoint-path problems using packing integer programs, 10.1007/s10107-002-0370-6
  44. Kolman, P., & Scheideler, C. (2001). Simple on-line algorithms for the maximum disjoint paths problem. In 13th ACM symposium on parallel algorithms and architectures (SPAA’01) (pp. 38–47).
  45. Krishnamoorthy Mohan, Ernst Andreas T., Sharaiha Yazid M., 10.1023/a:1011977126230
  46. Krishnaswamy R.M., Sivarajan K.N., Algorithms for routing and wavelength assignment based on solutions of LP-relaxations, 10.1109/4234.957386
  47. Lee Kyungsik Lee, Kang Kug Chang Kang, Lee Taehan Lee, Park Sungsoo Park, An Optimization Approach to Routing and Wavelength Assignment in WDM All-Optical Mesh Networks without Wavelength Conversion, 10.4218/etrij.02.0402.0206
  48. Low Chor Ping, A fast search algorithm for the quorumcast routing problem, 10.1016/s0020-0190(98)00033-7
  49. Mukherjee, B. (2006). Optical WDM networks. Springer.
  50. Nardelli Enrico, Proietti Guido, Widmayer Peter, Finding All the Best Swaps of a Minimum Diameter Spanning Tree Under Transient Edge Failures, 10.7155/jgaa.00039
  51. Noronha Thiago F., Ribeiro Celso C., Routing and wavelength assignment by partition colouring, 10.1016/j.ejor.2004.09.007
  52. Ozdaglar A.E., Bertsekas D.P., Routing and wavelength assignment in optical networks, 10.1109/tnet.2003.810321
  53. Pham, Q. D. (2011) LS(Graph): A constrained-based local search framework for constrained optimum tree and path problems on graphs. PhD thesis, Université catholique de Louvain.
  54. Pham, Q. D., Deville, Y., & Hentenryck, P. V. (2010). Constraint-based local search for constrained optimum paths problems. In Proceedings of the seventh international conference on integration of artificial intelligence and operations research techniques in constraint programming, CPAIOR’2010 (pp.  267–281).
  55. Ramaswami R., Sivarajan K.N., Routing and wavelength assignment in all-optical networks, 10.1109/90.469957
  56. Reimann, M., & Laumanns, M. (2004) A hybrid aco algorithm for the capacitated minimum spanning tree problem. In Proceedings of first international workshop on hybrid metaheuristics (pp. 1–10).
  57. Sleator Daniel D., Endre Tarjan Robert, A data structure for dynamic trees, 10.1016/0022-0000(83)90006-5
  58. Sleator Daniel Dominic, Tarjan Robert Endre, Self-adjusting binary search trees, 10.1145/3828.3835
  59. Tarjan, R. E., & Werneck, R. F. (2005). Self-adjusting top trees. In Proceedings of the 16th annual ACM-SIAM symposium on discrete algorithms (SODA) (pp. 813–822).
  60. Tarjan Robert E., Werneck Renato F., Dynamic trees in practice, 10.1145/1498698.1594231
  61. Tornatore, M., Maier. G., & Pattavina, A. (2002). Wdm network optimization by ilp based on source formulation. In Proceedings of IEEE INFOCOM (pp. 1813–1821).
  62. Van Hentenryck, P., & Michel, L. (2005). Constraint-based local search. London: MIT Press.
  63. Wang Bin, Hou Jennifer C., An efficient QoS routing algorithm for quorumcast communication, 10.1016/s1389-1286(03)00322-0
  64. Ye Yabin, Chai Teck, Cheng Tee, Lu Chao, Algorithms for the design of WDM translucent optical networks, 10.1364/oe.11.002917
  65. Yetginer Emre, Zeyu Liu, Rouskas George N., RWA in WDM rings: An efficient formulation based on maximal independent set decomposition, 10.1109/lanman.2010.5507142
  66. Zachariasen Martin, Local search for the Steiner tree problem in the Euclidean plane, 10.1016/s0377-2217(99)00131-9
  67. Zang, H., Jue, J. P., & Mukherjee, B. (2000). A review of routing and wavelength assignment approaches for wavelength-routed optical wdm networks. Optical Networks Magazine, 1(1), 47–60.
Bibliographic reference Pham Quang, Dung ; Deville, Yves ; Van Hentenryck, Pascal . LS(Graph): a constraint-based local search for constraint optimization on trees and paths. In: Constraints : an international journal, Vol. 17, p. 1-52 (2012)
Permanent URL http://hdl.handle.net/2078.1/113406