Local Solver is out

LocalSolver is a back-box commercial local search solver developed at Bouygues.
It's free for academics but since I'm not academic I cannot fully try it. Here are some thoughts after reading a bit their website:
It seems very nice and the results are quite impressive but to me it doesn't mean that tree search methods are dead.
Approaches like LNS (large neighborhood search) are very powerful to explore complex neighborhood with tree search methods like CP.
Also counting the number of 0-1 variables and the number of moves per second is not the argument that I prefer to judge the quality of the solution I can potentially get with a solver.
I prefer much more to have some kind of control to do very complex moves and self designed search as CBLS in Comet.
The thesis of Sebastien Mouthuy "Constraint-based very Large-Scale Neighborhood Search" is very nice on this topic of building very complex moves.
Anyway, it's always a good news to see new technology in optimization coming out. I'm looking forward to read feedback or user experience from the local search community. Maybe this will become the future "cplex" for local search i.e. a kind of standard benchmarking tool...

Hexiom Puzzle

Hexiom is a very interesting game that you can play online here

“The object of Hexiom is to arrange all tiles in a way that they are adjacent to exactly the number of other tiles as they are showing.”

Two solutions are for instance:

This puzzle can be solved with CP in a nice way (like most of the problems of course ;-)).

If you don’t want to see my model right now, just think about which decision variables and constraints you would use before continuing the reading of this post.

I use 3 types of variables in this model:

1) Type1: I call them used(i) with domain {0,1} to tell whether or not there is a tile in position i.

2) Type2: I call them nbNeighbors(i) is a variable representing the number of neighboring tiles of position i. The domain of these should be {0,1,2,3,4,5,6} because tiles are hexagons

3) Type3: I call them card(i). Those are almost the same as Type 2 but I also include 7 so their domain will be be {0,1,2,3,4,5,6,7}. It will become clear with the explanation on the constraints why we also need Type3 variables.

Now the constraints:

If you have for instance in input 3,4,0,2,2… it means that you must have one tile with 3 adjacent tiles, one tile with 4 adjacent ones, one isolated tile, two tiles with two adjacent tiles, ….

All of this can be imposed with just one Global Cardinality Constraint (GCC ) posted on the card variables. The problem is that we don’t want to count a value in the card variables if there is not tile placed in this position. This is why I introduced the value 7 in the domain of the card variables: If there is not tile in a position i, card(i) will take value 7 rather than taking as value the number of adjacent tiles to position I (i.e. nbNeighbors(i)). Of course in our GCC the number of occurrences for value 7 is not constrained.

To enforce the value 7 when there is no tile we have several options but not all of them are equivalent in terms of filtering. The optimal filtering is obtained by using a table constraint where you specify that the three variables (nbNeighbors(i),used(i),card(i)) altogether must be equal to one of those tuples: (0,0,7), (1,0,7), (2,0,7), (3,0,7), (4,0,7), (5,0,7), (6,0,7), (0,1,0), (1,1,1), (2,1,2), (3,1,3), (4,1,4), (5,1,5), (6,1,6)

Where nbNeighbors(i) is equal to sum(neighbors(i))(i => used(i)).

If you have a MIP background, you might be tempted to write something like:

card(i) == (used(i) * nbNeighbors + (1- used(i)) * 7)

Unfortunately, using sum and prods to do it would have a weaker pruning than with the table option because products and summations mainly reason on the bounds of the domains in CP.

In this model, it is also important to try to place tiles on the left branch and remove it on the right branch during the search tree exploration (optimistic heuristic). With this strategy we can find a solution to the hardest instance with only two backtracks!

Here is it's solution (level 40)

The source file of this model in Scampi is available here

In the real hexiom, I think some positions of some tiles are forced. Of course it is not difficult to enfore that in this model (just force the value of card(i)).

An interesting variant to me would be to consider the overconstrained problem and try to place as many tiles as possible, or try to collect has many points as possible (number on the tiles).

Let me know if you also implement a model for Hexiom in another system such that I attach a link to them on this blog.

Introduction of the Orbel Wolsey-Award

You are looking for a motivation to open-source one of your implementation related to Operations Research. The ORBEL Wolsey-Award may interest you!

Scampi Solver

We just released our modest open-source scala library called Scampi to solve OR problems (currently CP, MIP, Derivative Free Optimization, Discrete Event Simulation):

Maybe you'll find it useful, maybe not but for us it was a way to promote Scala (a very nice language) and Operations Research.

Thank you to all the people from n-Side who have contributed or gave us some time to develop on Scampi and our two interns of this summer Cyrille Dejemeppe (UCL) who worked on the derivative free optimization package and Hrayr Kostanyan (ULB) who contributed on the linear programming package. We hope more documentation will come soon and please already accept our apologies for the bugs you may encounter if you try to use it.

PhD Fellowship Award by IBM on CP topics

Patrick Albert (IBM) just announced the PhD Fellowship Award by IBM for topics related to R&D Optimization at IBM, in particular the two following topics:

- Fine grained, constraint-level multi threading in CP solvers.
- Just-in-time compilation techniques for CP solvers.

For more info, contact him and/or consult this page.

2nd DHC to Pascal Van Hentenryck

After the University of Louvain it is now the university of Nantes that recognizes the contributions and impact of Pascal Van Hentenryck by confering him the title of Doctor Honoris Causa (more info here).

This is always a good news for the visibility of CP. Congratulation to him!

CP solves 99% of the problems

Laurent Perron gave an interesting talk at CP'11. Laurent was in charge of ILOG CP Opt and he is now at Google developping the OR department. During his talk he made this remark: "ILOG CP was an expensive product, thus we had only complex problems that were very difficult to solve. When a product costs a lot of money then the companies are interested in it only when they have a very complex (and difficult) problems. Or-tools (the Google CP Solver) is mainly used in internal by Googlers and most of the time for solving easy problems. Almost all problems that we solve everyday are easy." I also remember that Laurent explained to me that he received requests for solving "simple" questions like : enumerate all the possible combinations of these variables. If you need to write such a code from scratch this is not an easy task at all. In fact, some people would like to have a simple tool for writing things like "for each combination of values in this array satisfying this constraint do something". In this case CP is really a good answer.
So maybe the answer about the problems solved by CP is the one proposed by Laurent and that is verified at Google: 99% of the real life problems arising everywhere :-)