This looks like an interesting tool that can be very effective on certain model classes with 0-1 variables.
More information at:
- http://localsolver.com
- http://pageperso.lif.univ-mrs.fr/~frederic.gardi/downloads/LocalSolver_4OR_2010.pdf
I believe this is a local search tool with a simulated annealing framework. From what I understand this method really wants to evaluate many solutions as quickly as possible. The method does not like real hard constraints (i.e. preferably constraints go into the objective with an appropriate cost or penalty when violated). In the words of the above paper: “LocalSolver is not designed for solving hardly-constrained optimization problems”.
I suspect the graph shown in http://localsolver.com/images/content/complexity_curves.png is only representative for problems that are suited for this LS approach (so may be no need yet to throw away our MIP and CP solvers).
This also caught my eye:
Please note that business, trial or academic licenses are not available to any individual or entity having their residence or registered office within USA or Canada. Individuals or entities having their residence or registered office within USA or Canada must strictly refrain from downloading any business, trial or academic license.
Dear M. Kalvelagen,
ReplyDeleteWe thank you for pointing out LocalSolver on your blog. You have well understood the main principles behind LocalSolver:
1) multithreaded adaptive simulated annealing;
2) autonomous moves maintaining feasibility at each iteration (here is the main innovation);
3) highly-optimized incremental evaluation in order to explore millions of solutions per minute of running time.
The main capabilities of LocalSolver is to scale in comparison to classical tree-search solvers (as explained on the complexity graph). Optimization models with millions 0-1 decisions can be tackled in minutes. Note that only *decision variables* have to be 0-1; of course, all intermediate variables can be integer (64-bit, even on x86 platforms).
As you noticed, LocalSolver is not intented to solve hardly-constrained problems. For example, problems where only a few solutions exist, or worst, only one or zero solution (decision problems or satisfaction problems). But any problem of this form can be modeled in a suited optimization problem by basic transformations. The idea is quite similar to your idea of "elastic formulation", which corresponds mainly to the needs of real-life optimization where "no solution found" is not an appropriate answer for users. It does not mean that only "unconstrained" problems can be solved by LocalSolver: have a look to models given in Example Tour (http://www.localsolver.com/exampletour.html). In particular, constraints which induce the combinatorial structure of your problem can and must be set as constraints. On the other hand, business constraints unlikely to be satisfied have to be avoided (and put as primary objectives). More documentation (tutorials, examples) will be available soon about modeling in LocalSolver, because we are aware that modeling practices for local search are a bit different from modeling for MIP or CP.
For some administrative reasons (insurance), LocalSolver is not actually available in USA and Canada. But we work hard to make it available very soon in these countries.
Best regards,
Frédéric Gardi
http://www.localsolver.com
http://pageperso.lif.univ-mrs.fr/~frederic.gardi