Home

A Constraint-Based Local Search Engine written in SCALA

NEWS: Asteroid has now been integrated with Scampi, to give rise to OscaR, a new multi algorithm platform for combinatorial optimization This forge will therefore be closed as soon as we have transfered the Wiki.

NEWS: Asteroid 0.3 Released on May 30 2012, delivers tremendous efficiency improvement and support for JobShop scheduling

**Have a look at our on-line applet ! ** (firefox might not work)

1. Introduction

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:
* 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.

2. 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 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

3. License

Asteroid source code is released soon under the LGPL V2.1 Open Source license or above.

4. Versions

• V0.1 - initial version
• V0.2 - many performance improvements
• V0.3 - tremendous efficiency improvement and support for JobShop scheduling

See the full release notes

5. Getting Asteroid

5.1 Asteroid Library

• Download the "asteroid jar file":https://forge.pallavi.be/attachments/download/57/asteroid-0.2.jar and include it in your scala project. Recommanded IDE to develop in Scala are Eclipse (with the Scala plugin or "IDEA IntelliJ":http://www.jetbrains.com/idea/download (the community edition support Scala).

• To run it in standalone, you will also need the scala-library.jar in your classpath. As an example, assuming the asteroid and scala-library jar files are in your current directory you can test the NQueens using the command (on Windows, in Linux, replace the ";" by ":" as usual)

java -cp asteroid-X.Y.jar;scala-library.jar constraints.tests.NQueens

Note some example have an UI and require the Swing wrapper:

java -cp asteroid-X.Y.jar;scala-library.jar;scala-swing.jar constraints.tests.BigSudokuGen

• The Scala doc of the library is "available here":http://asteroid.accessible-it.org/doc/index.html

5.3 Documentation

• [Architecture]
• [About Propagation]
• [Getting started]
• [Writing invariants and constraints]
• Scaladoc
• slides are available in the "file" section of this website.

5.4 Examples

There are only very few examples at this time, they are several versions of the NQueen, as well as other classical problems surch a basic PigeonHoles and SendMoreMoney

• NQueens
• NQueens2
• NQueens3
• PigeonHoles
• SendMoreMoney

Some example are described and commented in the section [Getting started]

Your can also see some online applet running

5.5 Quality assessment & Maturity

Asteroid is in alpha stage; validation is ongoing.
We expect to release a validated version by June 2012.

Yet, several validation mechanisms are integrated into Asteroid development process and code:

• Test coverage analysis is regularly run on Asteroid and is available here
• Built-in self checking of invariants

Asteroid is also moving to the standard Scala convention: http://docs.scala-lang.org/style/naming-conventions.html

6. Feedback & contribution

Feedback and contributions are welcome.
Please contact Renaud De Landtsheer: rdl@cetic.be

Project Admins:

• Renaud De Landtsheer
• Christophe Ponsard