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:
Dear Pierre,
RépondreSupprimerThe purpose of our LocalSolver's paper is not to compare state-of-the-art implementations for some hard combinatorial problems, but to compare *black-box* (that is, model-and-run) math programming solvers using *standard models* (suited for each solver). This point is clearly mentionned at the beginning of the section presenting the computational results.
Concerning the steel mill slab design problem, we have used a standard model for MIP, which is the kind of model which is actually written by so many practitioners. For Comet CBLS, we have not used a 0-1 model at all, because we perfectly understand how modeling in Comet: we have used a model using global contraints. What explained the bad results of Comet is the use of the autonomous search & moves features of Comet. According to us, this features are not effective and Comet is not an effective black-box solver (but an effective white-box solver). The reviewers (which were clearly some people of the Comet team) force us to perform the comparison between LocalSolver and Comet in a black-box manner. So we did it...
We have read your paper on CBLS for the steel mill slab design too. I do not say that obtaining state-of-the-art results on this problem with Comet is just a question of *modeling* capabilities. Note that any hand-made local-search algorithms properly implemented will obtain state-of-the-art results on this problem.
Best regards,
Frédéric Gardi
Dear Fredéric,
RépondreSupprimerI think Comet put everything in place such that you can implement your self a model and run approach given a constraint system. But the one given as an example in the Comet tutorial was introduced for didactical reason and not intended to be competitive. So I agree with you it’s not so relevant to compare with it ;-) (if this is the one you refer to in the paper).
What I’m afraid of (and maybe I’m wrong) is that the differentiation in your model is not exact (the getDelta will always return 0). As you know I worked on this problem a while ago using Comet and I had to implement a small custom differentiable invariant to have it right even using global constraints. This is why I would appreciate if you could post the exact model you employed in your experiments.
As we already exchanged by mail, we have a different opinion about what a standard practitioner is. I expect a standard practitioner of MIP to know when Dantzig Wolfe decomposition is appropriate for bin-packing like problems.
Anyway it’s just a naming and presentation issue but you could well name your “state of the art” column in the paper: “state-of-the art MIP model” since that one was obtained by Stefan Heinz with a MIP solver (SCIP).
Ce commentaire a été supprimé par un administrateur du blog.
RépondreSupprimerCe commentaire a été supprimé par un administrateur du blog.
RépondreSupprimerBrilliant blog about this topic understand a bit the technology you use to build good models! , I have been recently in your blog once or twice now. I immediately wanted to say my thanks for the knowledge provided here,
RépondreSupprimerCe commentaire a été supprimé par un administrateur du blog.
RépondreSupprimerCe commentaire a été supprimé par un administrateur du blog.
RépondreSupprimerCe commentaire a été supprimé par un administrateur du blog.
RépondreSupprimerwill check back in the future and see if you have more articles.Thanks for posting this I appreciate the information and the effort you put into your site.
RépondreSupprimergbtr presidential palace. Thank you so much dear! I’m happy to hear that you’re inspired and on your way- I wish you nothing but the best!!
RépondreSupprimerpresidential palace. Thank you so much dear! I’m happy to hear that you’re inspired and on your way- I wish you nothing but the best!!
RépondreSupprimerpalace. Thank you so much dear! I’m happy to hear that you’re inspired and on your way- I wish you nothing but the best!!
RépondreSupprimerBrilliant web log concerning this subject perceive a little the technology you employ to make sensible models! , I actually have been recently in your web log once or double currently. I instantly wished to mention my thanks for the information provided here,
RépondreSupprimer