Just a reminder on the progresses to solve this problem over the last years:
Antoine Gargani and Philippe Refalo closed the CSPLib instance with CP+LNS in 2006. Then Pascal Van Hentenryck and Laurent Michel explained that LNS is not necessary if you break dynamically the symmetries. A bit later, on more difficult instances the best results where obtained with CBLS using an exact differential invariant that you can implement in 5 lines of Comet. Finally Stefan Heinz had the last word closing the most difficult instances with MIP (SCIP) by generating all the columns in advance (not so many).
So you can imagine how surprised I was reading in this section that LocalSolver outperforms MIP (Cplex) and CBLS ?!?!?
But now I think I understand how the results where conducted (please correct me if I’m wrong). My understanding is that they used the same kind of models (0/1 decision variables) for LocalSolver, CBLS and Cplex. In that case the results make complete sense because:
- in MIP you’ll get all the symmetries as would get with a completely naïve bin-backing formulation (nobody having a minimum background in OR would never model a bin-packing problem in MIP like that).
- in CBLS the differentiation of the objective will always give you 0 which means you are making completely random moves.
Unfortunately this is not really explained (the models are not given, and the CBLS moves neither) and I don’t want that someone reading this article think that CBLS is not great to solve complex problems (with a correct differentiation, CBLS solves the steel mill slab instance of CSPLib with about twenty greedy swaps ;-) )
If you use CBLS you should understand when the differentiation of the objective is correct, what a differential invariant is, and you should certainly not build naïve CBLS models in the same way, as you never model with 0/1 variables in CP.
In conclusion, Optimization is quite complex, you need to have a minimum of understanding on how to build good models for the underlying technology you are using. I personally don’t believe that good modelers (in MIP, LS or CP) will be replaced very soon by automatic tools to get the best possible results.
Two great blogs where you can read nice things on the art of good modeling and good formulation are: