Asteroid Files

What Is CBLS?
*************

Constraint-based local search is a technique for solving combinatorial problems
including both constraint and optimization problems.
It is based on the notion of neighbourhood exploration. One has a current solution, which has some qualities.
From this solution, the principle is to explore a limited set of neighbours obtained by slightly modifying the current solution.
This is called neighbourhood exploration. From the explored neighbours, one selects the one that improves the most
with respect to the current solution. This best neighbour becomes the new current solution.
Neighbourhood exploration is repeated until no improvement can be found.
This process can be enriched with various meta-heuristics such as taboo, metropolis, simulated annealing, random restart, etc.

Constraints can be handled in two different ways, either as objective function; one needs to compute
the violation degree of constraints, and aims at decreasing it as if it were an objective function.
The other is to consider only solutions that enforce all constraints, starting from a solution that enforces them all.

When implementing a local search approach, it is crucial to be able to evaluate quickly the objective function on neighbours.
It is exactly what a CBLS framework aims at. It enables computing the value of objective functions incrementally.
Objective functions are declared in the framework by means of so-called invariants,
that implement various operators (arithmetic, min-max, set operators, logics, etc.)
A CBLS framework might also come with a support for declaring constraints, and a library of standard constraints (alldiff, equalities, etc.)

Asteroid is based on the reference book Constraint-based Local Search
Asteroid offers a powerful Scala based:
* framework for invariant declaration, with an engine that is able to perform incremental update of these invariants
* library of standard invariants, which can be extended
* framework for declaring constraints
* library of standard constraints.

Main Features of Asteroid
*************************

* Propagation graph can be cyclic.
Two propagation graphs are handled:  a static graph that over-approximates the dependencies
between variables and invariants, and a dynamic graph that represents the real dependencies
given the data actually stored in the model. The static graph can include cycles.
This makes it possible e.g. to implement JobShop scheduler from standard invariants.

* No differentiation in invariants.
The engine relies on propagation to explore the neighbourhood. However, partial propagation is provided,
to keep neighbourhood exploration relatively fast. Thanks to partial propagation,
Asteroid is able to quickly compute a difference even if this involves complex structure involving invariants.

* Partial propagation is supported over the static graph.
Propagation is triggered when the value of a variable is queried by the search script.
Deciding whether the propagation will be total or partial is done depending on the variable:
if the variable is registered for partial propagation, the propagation will be partial.
It will be total otherwise. Violation degrees are automatically registered for fast propagation.

* The violation degree propagates upwards through the static propagation graph.
Each variable has a violation degree associated with each constraint system,
and this violation degree propagates upwards through invariants.
Although the propagation rule might be somewhat arbitrary,
it enables one to find the variable contributing the more to the overall violation.

* The engine is written in the Scala programming language.
As a consequence, it is portable, and be easily integrated within any Java application.
Also, it proposes a domain-specific language that eases the development of search script
and decreases the conceptual distance between algorithm and code.

* Libraries of standard invariants and constraints are proposed on integer and set of integer domains:
Invariant library includes logic, numeric, min/max, and set invariants.
Constraint library includes few global constraints: Alldiff, AtLeast, AtMost and equalities over integers.

* Lightweight Asteroid has been kept small and well structured to ensure that it can be easily understood and extended

Contributors
************
from CETIC www.cetic.be:
   Renaud De Landtsheer rdl@cetic.be