object Queens extends Model {
def main(args: Array[String]) {
val cp = new CPSolver()
val n = 6 //number of queens
val Queens = 0 until n
//variables
val queens = for(i <- Queens) yield CPVarInt(cp,1 to n)
var nbsol = 0
cp.onSolution {
nbsol += 1
}
cp.solveAll subjectTo {
cp.add(alldifferent(queens))
cp.add(alldifferent(for(i <- Queens) yield queens(i) + i))
cp.add(alldifferent(for(i <- Queens) yield queens(i) - i))
} exploring {
//exploration of the search tree
new Binary(queens)
}
//print some statistics
println("#sol",nbsol)
cp.printStats()
}
}
object Queen extends Application with jacop {
val n = 50
val q: List[IntVar] = for (i <- List.range(0, n)) yield new IntVar("q"+i, 0, n)
def noattack(i: Int, j: Int, qi: IntVar, qj: IntVar) = {
qi != qj
qi + i != qj + j
qi - i != qj - j
}
for (i <- 0 until n; j <- i+1 until n) noattack(i, j, q(i), q(j))
val result = satisfy( search(q, first_fail, indomain_middle) )
if (result)
q.foreach(qi => {
for( i <- 0 until n)
if (qi.value() == i) print(" # ") else print(" . ")
println
})
else println("No solution")
}
I’m just back from Informs Analytics. I was there with 4 of my colleagues from n-Side. We were presenting posters about our products (this is a picture of my poster)
It was really a nice experience and a nice organization. If you feel sometimes alone or isolated doing optimization… Go there ! You’ll see that analytics (the new buzzword for OR) is used in every big organizations.
It was also fun to put a face on names that you know from Internet (like Natan Brixius having a blog on Microsoft Solver Foundation, Bob Fourer from Ampl and many others from Or-Exchange).
I was also very seduced by the presentations on Knitro solver (non linear continuous optimization) made by Richard Waltz. Continuous optimization is a technology that we use a lot at n-Side and we learned a lot there thanks to Richard!
I also attended a presentation given by Greg Glockner (Gurobi) on how to debug/detect numerical issues of a MIP. He is a great presenter! I didn’t know for instance that if you write in a MIP a constraint like y <= 10000000000 x with x a binary variable, you can get into troubles and have y taking positive values even without forcing x to 1 due to rounding errors. I found it a bit fun. CP doesn’t have those kinds of numeric issues because it is discrete by nature.
Of course the battle of MIP solver was more fierce than ever (FICO, CPLEX, GUROBI, …). It seems that they are fighting for some percents of speed-up on some benchmarks (mittleman bench among others). Honestly, I’m not sure it really matters to the end user. First, we even don’t know what kind of problems is present in those benchmarks. Second, what I would like to see is how easy it is to make a column generation, a branch and price or a new cut…
The Edelman award was really impressive. A bit like a Hollywood show http://www.flickr.com/photos/informs/5611418031/in/photostream The winner was MIDWEST ISO. They converted a local electricity market to a larger regional one resulting in lower electricity costs and more efficient market. Of course all that taking the constraints of the network into account. That was really great to me and my colleague to see this winner because we have a very similar product at n-Side where we are in charge of coupling the European market.
My main regret was that CP doesn’t have the status it should have at INFORMS. The only place where I’ve seen a CP application was on the Monsanto poster of my friend Ravichandran Venkatesh. They use CP to solve a kind of hybrid placement/scheduling problem for greenhouses.
The reason may be that CP is too focused on the AI community and less on Informs. This is sad because many of the problems solved there could be solved by CP or by hybridization with CP. For instance I’ve seen a presentation given by Fico where they try to build optimal planograms for supermarkets. A planogram is something like that:
They use a column generation for that. Great! But they have a log of sequence like constraints (regular, stretch…). So I’ve told them that CP would be very appropriate to do that.
In conclusion, It would be nice to see in the future more CP there. For instance I would enjoy seeing Google winning the Edelman award solving a real application with his new CP Solver ;-).
Recently, I heard from someone (that I was trying to convince how CP is cool) : « yes but you know, most of the time we have an objective function … ». This person has a very strong MIP background and it’s not the first time I heard such a belief. Needless to say this is wrong and no, CP is not only for satisfaction problems.
CP usually solves optimization problems with B&B by optimizing one variable having its own domain. In short, this is how it works:
When a solution is found, a constraint is dynamically added (without restarting the search) such that the next solution found is strictly better. The last solution found is by construction optimal (correct me if I’m wrong but I think this adaptation of B&B to CP was imagined by Pascal Van Hentenryck).
This is also completely false to say that CP doesn’t use lower bounds. Usually the objective function/variable is linked into one (or several) global constraint computing very good lower bounds on it (look for instance the paper of Jean-Charles: « Arc consistency for global cardinality constraints with costs ». With this kind of constraints you can solve TSP problems with CP. This is a small demo on google map I made some time ago http://travellingsalesmanproblem.appspot.com/ It is a bit slow due to the time needed to collect the distance matrix L
This is a very nice and interesting problem for CP posted recently on stackoverflow :
" Bob has a store, and wants to do a sale. His store carries a number of products, and he has a certain integer quantity of units of each product in stock. He also has a number of shelf-mounted price labels (as many as the number of products), with the prices already printed on them. He can place any price label on any product (unitary price for one item for his entire stock of that product), however some products have an additional restriction - any such product may not be cheaper than a certain other product. "
You must find how to arrange the price labels, such that the total cost of all of Bob's wares is as low as possible. The total cost is the sum of each product's assigned price label multiplied by the quantity of that product in stock. "
This can be modeled easily with some precedence constraints and an global alldiff constraint with costs (see Filippo Focacci, Andrea Lodi, Michela Milano: Cost-Based Domain Filtering. CP 1999 for the filtering algorithm) .
As soon is I find the time to do it, I'll generate some instances to test it....
