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?

$\endgroup$
4
  • $\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
  • 1
    $\begingroup$ When using CP-SAT, make sure to use it multi-threaded as it is much better that way. IIRC, at around thread 7 and above the new assets will be various kinds of improving local search assets (either using large neighborhood search or in the msot recent version also violation based local search). $\endgroup$
    – Zayenz
    Dec 6, 2023 at 8:26
  • $\begingroup$ Why don't you just ask for a trial or academic license? $\endgroup$
    – root-11
    Dec 6, 2023 at 17:49

4 Answers 4

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 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, 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.

$\endgroup$
2
  • 4
    $\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$ Sep 26, 2022 at 11:31
  • $\begingroup$ Note: Apache license applies from Version 8.0.3 onwards for SCIP. $\endgroup$
    – kur ag
    Dec 5, 2023 at 6:53
8
$\begingroup$

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

1 - The Hexaly modeling API offers nonlinear operators (prod, min, max, log, exp, pow, cos, sin, tan, if-then-else, etc.) and set-oriented operators.

The "set" and "list" decisions are unique to Hexaly API. They are critical to getting compact and structured models for problems like routing, scheduling, packing, clustering, matching, assignment, and 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, Hexaly uses automatic surrogate modeling approaches to speed up the resolution.

2 - Hexaly has changed a lot in 10 years. It is not a "local search" solver anymore. Today, Hexaly relies on combining many optimization methods under the hood. We cannot say more that Hexaly 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.

Hexaly looks like MILP, MINLP, or even CP, but it is not. It is in between, which is a kind of hybrid. As its name does not reflect, Hexaly 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 Hexaly 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: Hexaly is commercial software. It is free for students and faculties.

$\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$ 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$ 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.

$\endgroup$
-1
$\begingroup$

Take a look at Timefold Solver, our open-source solver backed by our open core company.

Timefold Solver is a fast and scalable solver that supports various metaheuristics, incremental score calculation and real-time planning.

$\endgroup$

Your Answer

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

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