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))

    c.close
    m.close

    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
      }
    }
    println(c.Violation)
    println(m.GetSolution(true))
  }