LS(Graph): a constraint-based local search framework for constrained optimum tree and path problems on graphs

(eng) Constrained Optimum Tree (COT) and Constrained Optimum Path (COP) are two classes of problems which arise in many real-life applications and are ubiquitous in communication networks, transportations, very large scale integration (VLSI) and distributed systems. Most of these problems are computationally very hard to solve. They have been traditionally approached by dedicated algorithms including heuristics and exact algorithms, which are often hard to extend with side constraints and to apply widely because they depend strongly on the problem structures. Moreover, it is required huge research and programming efforts for solving new problems. In this thesis, we construct a constraint-based local search (CBLS) framework, called LS(Graph), for solving COT/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 COT/COP applications at a high level of abstraction, while cleanly separating the model and the search procedure. The LS(Graph) framework will strengthen the modeling benefits of CBLS. By using LS(Graph), users can quickly develop a local search algorithm for a new problem which gives, in most of cases, an acceptable solution while waiting for experts who do research with huge efforts for dedicated algorithms. Moreover, this solution can be used as the initial solution in more complex and hybrid algorithms. The main technical contribution is a connected neighborhood based on rooted spanning trees. The idea behind is to use rooted spanning tree for representing solutions which are paths and their neighborhoods. This approach enables the genericity of the framework from both modeling and computation standpoints. The constructed framework is applied to some three COT (i.e., the edge-weighted k-cardinality tree problem, the quorumcast routing problem, the problem of minimizing congestions on ethernet networks) and four COP problems (i.e., the resource constrained shortest path problem, the edge-disjoint paths problem, the routing and wavelength assignment with delay side constraint problem, and the routing for network covering problem). Experimental results show the potential benefits of the approach. On the one hand, we show the facility and the genericity of the resolution of the COT/COP applications which can be extended with side constraints. On the other hand, for the quorumcast routing and the edge-disjoint paths problems, we show competitive results in comparing with existing techniques.