lundi 27 février 2012

Asteroid is out! new open-source CBLS Solver ...

Plenty of good news in the local search community these days!
But this one is even better since it is an open-source solver with a commercial friendly license (LGPL) and developed in Scala (my current favorite programming language).
This is a new CBLS solver developed by Renaud De Landtsheer at the Cetic.
This solver is very close to the constrained base local search and the models you would see in the Book of Pascal Van Hentenryck and Laurent Michel.
I guess the name of this solver (Asteroid) is an allusion to the pioneering CBLS system Comet:
Cetic is a research center in Computer Science in Belgium. I’m very happy they start to invest into optimization and also to open-source it.
Here is an n-queens model to give you a taste of it:

val N:Int=40
val min = 0
val max = N-1
val range:Range = Range(0,N)
val tabulength = 1
val m: Model = new Model(false)
val MaxIT = 10000

println("NQueens(" + N + ")")
val Queens:Array[IntVar] = new Array[IntVar](N)
for (q <- range){Queens(q) = new IntVar(m, min, max, q, "queen" + q)}

val c:ConstraintSystem = new ConstraintSystem(m)

//c.Post(AllDiff(Queens)) handled trough permutations
c.Post(AllDiff(for ( q <- range) yield (q plus Queens(q)).ToIntVar))
c.Post(AllDiff(for ( q <- range) yield (q minus Queens(q)).ToIntVar))


var it:Int =0

val Tabu = (for(q <- range)yield -1).toArray

var longueurplateau = 0;
while((c.Violation.GetValue() > 0) && (it < MaxIT)){
val oldviolation:Int = c.Violation
val allowedqueens = range.filter(q => Tabu(q) < it)
val (q1,q2):(Int,Int) = SelectMin2(allowedqueens,allowedqueens, (q1:Int, q2:Int) => c.GetSwapViol(Queens(q1),Queens(q2)), (q1:Int,q2:Int) => q1 != q2)

Queens(q1) :=: Queens(q2)
Tabu(q1) = it + tabulength
Tabu(q2) = it + tabulength

it += 1
println("it: " + it + " " + c.Violation + " (swapped "+ q1 + " and " + q2 + ")")
if(oldviolation <= c.Violation.GetValue()) longueurplateau+=1 else longueurplateau = 0

if (longueurplateau > 5){
println("jump away")
for (i <- 1 to N/5){
Queens(SelectFrom(range)) :=: Queens(SelectFrom(range))
longueurplateau = 0

8 commentaires:

  1. Programmers, armed with the right tools, will expected turn the heroes for the subsequent era of craving Web applications plus will be instrumental in assisting establish either a association can have or mangle it in the latest market.

  2. What are the originality that are brought by this new tool?
    What are the differences and the improvements over Comet?

  3. Asteroid is:
    * A CBLS solver
    * Without differentiation (mainly due to budget constraint)
    * Aiming at supporting cycles in the propagation graph (not tested so far, wait for next release)
    * With partial propagation, computed over the static propagation graph (this aims at compensating for the lack of differentiation)
    * Where a violation degree can be computed for any variable (thus violation degrees percolate upwards through invariants)
    * Open source LGPL (which really makes a difference for research and small companies)

    If you feel that there is room for improvement, with respect to the fundamental algorithms or the implementation, I would be very interested to integrate your contributions or to get your suggestions.

    PS: We are currently elaborating a roadmap, and the first steps will deeply impact the API, both on the naming convention and in a smaller proportion, on the behavioural aspect.

  4. Reanaud,

    Thanks for the answer
    What is differentiation?

  5. Differentiation enables you to get the delta that will be gained on the violation degree of a constraint system if you perform some move. It is efficient because it delivers this delta without actually performing the move, so there is no need to restore some state between two such queries. The moves for which Comet is able to compute the delta are:
    * swapping the value of two variables
    * assigning some value(s) to some variable(s)

    Unfortunately, differentiation is difficult to compute, especially if the structure of the problem is intricate (eg multiple or long path from the modified variables to the violation degree) and it may happen that Comet is unable to compute the differentiation, it just returns zero.

    Asteroid does not have differentiation, so choosing the next current solution requires actually moving to each neighbour in turn, and backtracking every time to the current solution. Yet it provides more less the same syntactic interface, eg: GetSwapViolation(IntVar1,IntVar2) instead of the GetSwapDelta(IntVar1,IntVar2) found in Comet.

    To still ensure acceptable efficiency, Asteroid performs partial propagation while exploring neighbourhoods. The idea is that neighbours are typically explored with respect to a single objective function, which might be the violation degree of some constraint system. We thus only need to propagate what is needed to ensure that this objective function is correctly updated. Other parts of the model such as tabu mechanics, and violation degree attributed to each variable are only propagated once the neighbour is chosen. Furthermore, backtracking between each neighbour is performed lazily: propagation is not performed immediately, so that the backtracking is aggregated with the exploration of the next neighbour or the move to the selected neighbour.

    1. Cool!

      Thanks for the answer.
      This is interesting

  6. I am proud to announce that we released Asteroid v0.2.

    Release 0.2 brings significant performance improvements.
    This is due to deep reworking of the basic propagation layer:
    *The data structure storing the dependency was switched from Sorted sets O(log(n)) to doubly linked lists + keys O(1). As a consequence, declaration of the dependencies of invariants now proceeds by calling a dedicated method of the API instead of implementing a query method
    *Bulk load mechanism is added. It enables interesting speed up in case a set of invariant all listen to the same array of variables. It enables instantiating a collection invariants much faster if they all listen to the same array of variables.

    It stays globally compatible with the 0.1 API

    Other improvements include:
    * Objective concept, providing neighborhood evaluation with partial propagation support
    * Refactored IntInvariant/IntSetInvariant and related propagation
    * Naming conventions, which now respect the standard SCALA convention
    * dot export of the static and dynamic propagation graphs to enable visualizing the declared problem

    NOTE: the support for cyclic propagation graph, and the JobShop are removed, but the purpose of v0.3 is to reintroduce them.

    See the release notes for the full list of changes

    Enjoy, and do not hesitate to send feedback.

  7. Just to mention that Asteroid was moved to SourceForge