LS(Graph): a constraint-based local search for constraint optimization on trees and paths
(2012) Constraints : an international journal — Vol. 17, p. 1-52 (2012)
Files
fulltext.pdf
Open Access - Adobe PDF
- 3.67 MB
Details
- Authors
- Abstract
- 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.
- Affiliations
Brown University Victoria Research Laboratories
Citations
Pham Quang, D., Deville, Y., & Van Hentenryck, P. (2012). LS(Graph): a constraint-based local search for constraint optimization on trees and paths. Constraints : an international journal, 17, 1-52. https://doi.org/10.1007/s10601-012-9124-0 (Original work published 2012)