Constraint-based local search for solving non-simple paths problems on graphs: application to the routing for network covering problem

Pham, Quang Dung;Deville, Yves;Do, Phan-Thuan;Ho, Tuong Vinh
(2010) Proceedings of the 2010 Symposium on Information and Communication Technology — Location: Hanoi, Viet nam (27.August.2010)

Files

non-simple.pdf
  • Open Access
  • Adobe PDF
  • 246.07 KB
Download

Details

Authors
  • Pham, Quang DungUCLouvain
    Author
  • Deville, Yvesorcid-logoUCLouvain
    Author
  • Do, Phan-ThuanSchool of Information and Communication Technology
    Author
  • Ho, Tuong VinhInstitut de la Francophonie pour l’Informatique
    Author
Abstract
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 proposes a constraint-based local search (CBLS) framework for COP applications, bringing the compositionality, reuse, and extensibility at the core of CBLS and CP systems. The modeling contribution is the ability to express compositional models for various COP applications at a high level of abstraction, while cleanly separating the model and the search procedure. The main technical contribution is a connected neigh- borhood based on rooted spanning trees to find high-quality solutions to COP problems. The framework, implemented in COMET, is applied to Resource Constrained Shortest Path (RCSP) problems (with and without side constraints) and to the edge-disjoint paths problem (EDP). Computational results show the potential significance of the approach.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Pham, Q. D., Deville, Y., Do, P.-T., & Ho, T. V. (2010). Constraint-based local search for solving non-simple paths problems on graphs: application to the routing for network covering problem. In Nguyen Trong Giang, Nguyen Thuc Hai, Huynh Quyet Thang (ed.), Proceedings of the 2010 Symposium on Information and Communication Technology (p. p. 1-8). https://hdl.handle.net/2078.5/254121