Author : Alastair Neil Andrew
Release : 2014
Genre :
Kind : eBook
Book Rating : /5 ( reviews)
Book Synopsis Extracting and Exploiting Interaction Information in Constraint-based Local Search by : Alastair Neil Andrew
Download or read book Extracting and Exploiting Interaction Information in Constraint-based Local Search written by Alastair Neil Andrew. This book was released on 2014. Available in PDF, EPUB and Kindle. Book excerpt: Local Search is a simple and effective approach for solving complex constrained combinatorial problems. To maximise performance, Local Search can utilise problem-specific information and be hybridised with other algorithms in an often intricate fashion. This results in algorithms that are tightly coupled to a single problem and difficult to characterise; experience gained whilst solving one problem may not be applicable in another. Even if it is, the translation can be a non-trivial task offering little opportunity for code reuse. Constraint Programming (CP) and Linear Programming (LP) can be applied to many of the same combinatorial problems as Local Search but do not exhibit these restrictions. They use a different paradigm; one where a problem is captured as a general model and then solved by a independent solver. Improvements to the underlying solver can be harnessed by any model. The CP community show signs of moving Local Search in this direction; Constraint-Based Local Search (CBLS) strives to achieve the CP ideal of "Model + Search". CBLS provides access to the performance benefits of Local Search without paying the price of being specific to a single problem. This thesis explores whether information to improve the performance of CBLS can be automatically extracted and exploited without compromising the independence of the search and model. To achieve these goals, we have created a framework built upon the CBLS language COMET. This framework primarily focusses on the interface between two core components: the constraint model, and the search neighbourhoods. Neighbourhoods define the behaviour of a Local Search and how it can traverse the search space. By separating the neighbourhoods from the model, we are able to create an independent analysis component. The first aspect of our work is to uncover information about the interactions between the constraint model and the search neighbourhoods. The second goal is to look at how information about the behaviour of neighbourhoods - with respect to a set of constraints - can be used within the search process. In particular, we concentrate on enhancing a form of Local Search called Variable Neighbourhood Search (VNS) allowing it to make dynamic decisions based upon the current search state. The resulting system retains the domain independence of model-based solution technologies whilst being able to configure itself automatically to a given problem. This reduces the level of expertise required to adopt CBLS and provides users with another potential tool for tackling their constraint problems.
