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

}