11
$\begingroup$

I have a constraint programming problem that is easy to formulate and solve (with high solution quality) in LocalSolver. However, I would really prefer to use something open source for reproducibility. I tried using CP-SAT from Google OR-Tools, but it seems to be more of a global optimizer and didn't perform as well. I really like the "local search" approach that LocalSolver takes. Are there any other solvers that would work well for this?

Improve this question
$\endgroup$
2
  • $\begingroup$ You could always try and formulate as a linear program and solve with CBC. $\endgroup$
    – Kuifje
    Sep 22, 2022 at 19:03
  • 3
    $\begingroup$ If you're looking for a model-and-run tool and use set or list variables, AFAIK, there is no alternative. Maybe you can get what you need with OptaPlanner. You can also take a look at Constraint-Based Local Search solvers like Yuck or OscaR. Otherwise, you'll need to re-implement a local search algorithm yourself $\endgroup$
    – fontanf
    Sep 22, 2022 at 21:57

4 Answers 4

Reset to default
10
$\begingroup$

The simple answer is no.

While I haven't used LocalSolver myself, I sell a solver that solves similar types of problems (Octeract Engine) so I get asked this type of question a lot for my own solver.

Commercial optimisation solvers are, on average, orders (note the plural) of magnitude more performant than open-source alternatives. This is simple to verify, e.g. Octeract & Gurobi vs Couenne or even vs SCIP (SCIP is "source available" and is only free for non-commercial projects), on Binary Quadratic problems, or on Non-convex continuous quadratic problems.

This seems to baffle people a lot, especially people with non-optimisation backgrounds, but it is true nevertheless. People have different takes as to why, including my own infamous satire on this, but at the end of the day, optimisation software has a single job to do - find a good solution fast. This one thing is literally all people care about. If the free alternatives were even remotely comparable to commercial code in this one thing, none of us commercial solver folk would be able to sell a single solver copy. Since we do, as evidenced by the fact that we can all afford to develop solvers full-time, the original statement has to be true.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ That's nice, but my point here really was that if a commercial solver (in this case LocalSolver) works very well for your problems, you might want to consider buying it and support its developers. $\endgroup$
    – Nikos Kazazakis
    Sep 26, 2022 at 11:31
7
$\begingroup$

To our knowledge, there is no equivalent of LocalSolver in open source. More generally, there is no equivalent of LocalSolver in the market. LocalSolver's uniqueness, and thus innovation, comes from the two following key points:

1 - The LocalSolver modeling API offers nonlinear operators (prod, min, max, log, exp, pow, cos, sin, tan, if-then-else, etc.) but also some so-called "set" and "list"-related operators.

Set and list operators are critical to getting compact and structured math models for problems like routing, scheduling, packing, clustering, or even location problems, contrary to traditional solvers.

It also supports black-box optimization by offering the ability to implement your own mathematical operators; if these operators are time-consuming to evaluate, LocalSolver can rely on automatic surrogate modeling approaches to speed up the resolution.

2 - LocalSolver has changed a lot in 10 years. It is not a "local search" solver anymore. Today LocalSolver relies on the combination of many optimization methods under the hood. We cannot say more than LocalSolver combines exact and heuristic algorithmic approaches. Here "heuristic" refers to Local Search, but not only. These heuristics are unique; you will not find them in MILP or CP solvers.

Once coupled with the above-described modeling API, these methods deliver fast and scalable solutions to many problems beyond traditional solvers' scope, particularly routing and scheduling problems.

LocalSolver looks like MILP, MINLP, or even CP, but it is not. It is in between, that is, a kind of hybrid. In summary, as its name does not reflect, LocalSolver is a global optimization solver with a special, unique modeling API.

Your sentence "I would really prefer to use something open source for reproducibility" is unclear. Open source solvers are no more reproducible than commercial ones. It depends on what "reproducible" means in your statement. Could you elaborate on this?

If you wish to use LocalSolver for teaching or basic research, then it is free. If you are a business, we offer competitive pricing, particularly for startups and SMEs. It seems you use a pseudo here (you don't appear under this name as a user in our records), so I assume you will not explain what you really want.

Disclaimer: LocalSolver is commercial software. It is free for students and faculties.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Actually, my problem is that LocalSolver is too good! I'm reviewing a paper that isn't very good, and I found that LocalSolver is superior to the method being proposed in the paper. I was looking for the most transparent solver out there so I could justify my claims as strongly as possible. $\endgroup$
    – Kathryn Twomey
    Sep 26, 2022 at 18:26
  • $\begingroup$ Is the CBC open-source solver (with a dummy objective function) also superior to the method being proposed ? $\endgroup$
    – Kuifje
    Sep 27, 2022 at 9:26
  • $\begingroup$ No, the way I formulated the problem causes branch-and-bound to take too long. $\endgroup$
    – Kathryn Twomey
    Sep 27, 2022 at 16:40
3
$\begingroup$

You might want to try Gecode, although I have no idea whether it will do any better than OR-Tools. If you are not a C++ programmer, you can use MiniZinc to build the model and interface with Gecode. Both are open-source.

If you are inclined to move away from constraint programming models, you could (as suggested in a comment) try a linear (integer?) program with an open-source LP/MIP solver. It may also be amenable to various metaheuristics, whether based on neighborhood search or other.

Improve this answer
$\endgroup$
1
$\begingroup$

OptaPlanner (open source, Java or Kotlin) and OptaPy (open source, Python) use Local Search too, aside from many orthogonal features. Both are Apache License, so you can reuse it anywhere you like.

On VRP, a properly configured OptaPlanner beats LocalSolver on small and big datasets, according to our users. Your mileage may vary. Try it yourself.

OptaPlanner is a generational skip over traditional solvers such as LocalSolver. That innovation is hard to explain, see this comparison. For example: OptaPlanner doesn't have a limited list of operators it supports, because it supports constraints that reuse normal code and data types. Your opinion may vary.

Disclaimer: I am the creator and one of the main contributors of OptaPlanner.

Improve this answer
$\endgroup$
13
  • 6
    $\begingroup$ Maybe your answer sounds a bit too subjective. You should have a better argument than "according to our users" to support your claim. And calling something that requires programming "innovation" compared to a model-and-run framework is also debatable. It's different and have some benefits, but also some drawbacks $\endgroup$
    – fontanf
    Sep 27, 2022 at 14:32
  • 1
    $\begingroup$ I had assumed that OptaPlanner was just a routing package. Thanks for letting me know about it! $\endgroup$
    – Kathryn Twomey
    Sep 27, 2022 at 16:39
  • 1
    $\begingroup$ Some OR people have more a math background than a programming background, or have already learned MILP modelling at the university. It's easier for them to think their problems in terms of variables and equations and then to write them, even if it is to write them in a programming language. $\endgroup$
    – fontanf
    Sep 28, 2022 at 8:59
  • 1
    $\begingroup$ Tbh, it took me some time to understand the philosophy of OptaPlanner. Having done a tutorial on how to transform a model from another classical tool into an OptaPlanner model is a very good idea $\endgroup$
    – fontanf
    Sep 28, 2022 at 9:02
  • 1
    $\begingroup$ @GeoffreyDeSmet You cite and compare to LocalSolver but your knowledge about it seems very limited. Indeed, you incorrectly report LocalSolver as a "traditional MILP solver". LocalSolver is not a MILP solver. For example, and contrary to what you claim in your last sentence, LocalSolver does support user-written custom operators. This is called "external functions" in LocalSolver: localsolver.com/docs/last/modelingfeatures/…. Please correct your post accordingly. $\endgroup$
    – LocalSolver
    Oct 2, 2022 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.