6 ms·

There are plenty of commercial solvers out there that beat the pants off the open source options in terms of performance and in terms of depleting one's wallet

There are plenty of commercial solvers out there that beat the pants off the open source options in terms of performance and in terms of depleting one's wallet :) CPLEX, Xpress, GUROBI, and Hexaly all come to mind. Hexaly is really good for scheduling problems and things like vehicle routing. You typically access these via an API they offer you for the popular industry languages. This approach seems to make a lot more sense to me than having a dedicated solver language that isn't as good for all the general purpose stuff. Calling GUROBI from Python is a breeze as is all the standard stuff in Python. Mosek is a lot cheaper than GUROBI, but both of it's APIs are extremely low level and the performance isn't as good as GUROBI either.

shoo 3y ago
Yup. & when you get a model that works matched up with an industrial scale decision problem that's valuable to solve, arguably it's only of academic interest if you can solve it "optimally". The problem is only a simplified model of reality anyway -- it's often better to get a quick close-enough approximate solution to a problem that's a good approximation of the situation than an exact optimal solution to a simpler problem that's a poorer approximation. If you're lucky enough to get a problem that's basically stable over time, where the problem structure doesn't change, then maybe you can get improved solutions rapidly at industrial scale replacing use of a black-box MIP solver like Gurobi/CPLEX with a decomposition that exploits the problem structure, where sub-problems can be solved by some specialized graph algorithm or heuristic or brute force (if they all have bounded size), and the general purpose MIP/LP solver can be left with the job of figuring out how to deal with the shared resources and constraints that bind the subproblems together. The downside to a highly specialised custom solver is that it usually isn't flexible to changing requirements (unless you get very lucky) -- a slight change in business rule can break the problem structure that underpins the entire solution approach.
- 7thaccount 3y ago
  I disagree with the first statement for some industries. My industry has several companies that have amongst the hardest MILP problems in the world that have millions of variables and constraints and need to be globally optimal for the sake of fairness and to save many millions of dollars per year. Electricity markets are extremely complicated and although it would be amazing to simplify things, the decisions and prices need to be correct. Also, performance is critical as these auctions are running 24/7. They're also always being changed as well, so black-box globally optimal solutions are a need to have.
polivier 3y ago
> There are plenty of commercial solvers out there that beat the pants off the open source options in terms of performance and in terms of depleting one's wallet :) While this is generally true, there are some exceptions. I recently compared the performance of CP-SAT vs CPLEX for a problem (linear constraints and objective). For large instances where proving optimality in a reasonable time was out of the question, CP-SAT had much faster convergence to near-optimal solutions than CPLEX when the time limit was small enough (~30s to a few minutes). This is with the CPLEX solver tuned towards improving the upper bound as much as possible (it was a minimization problem).
- whatever1 3y ago
  If feasibility is your goal then cp/sat solvers/heuristics should be your tool of choice. I you have optimality requirements (aka from the feasible solutions find the absolutely best) then optimization is the way to go
  - sterlind 3y ago
    can't you just use the strong duality theorem to reframe an integral optimization problem as a system of integer inequalities? I thought you usually don't do that because the satisfaction problem is harder in practice.
    - whatever1 3y ago
      No unfortunately strong duality does not hold for integer problems. But your intuition is right, this is roughly how IP optimizers work. They relax the problem to a continuous one (aka convert the {0,1} to [0,1]), solve this super easy linear problem and try to find integral solutions close this linear optimum. If not, start branching on the integers and solve smaller and smaller linear problems until you prove optimality.
  - polivier 3y ago
    I think that you've misunderstood what I said. For large instances of this specific problem (and when the time limit is too short to allow either CP-SAT or CPLEX to prove optimality) the best integer feasible solution found by CP-SAT is generally of better quality (w.r.t. the objective value) than the best integer feasible solution found by CPLEX. Furthermore, in some cases, CP-SAT can offer a certificate of optimality faster than CPLEX.
TimTheTinker 3y ago
Are the commercial offerings you mentioned better than TimeFold? [0] (formerly known as OptaPlanner before the main developers forked it) TimeFold's heuristics-based approach makes fast solutions to even highly-complex scenarios within the reach of anyone who can write Java or Python expressions that evaluate to true when constraints are satisfied. [0] https://timefold.ai/ https://timefold.ai/
- Aeolun 3y ago
  I found Optaplanner to be nice, but supremely unergonomic to use. I could replicate their example problems and not much else. > All OptaPlanner features are part of Community Edition, except for Multithreaded Solving Of course, because why not. If you can take features away from an existing thing to make more money.
  - ge0ffrey 3y ago
    Could you elaborate on how OptaPlanner/Timefold wasn't ergonomic? I 'd love to understand this better, so we can improve it in Timefold Community. To help deal with new problems, we're creating out-of-the-box quickstarts for common use cases: https://github.com/TimefoldAI/timefold-quickstarts https://github.com/TimefoldAI/timefold-quickstarts As for the Community/Enterprise split - we want to continue the open source project, but we need to eat too :) Geoffrey (Timefold co-founder / OptaPlanner creator)
    - Aeolun 3y ago
      Basically, the documentation was set up so that I could come in and do a bunch of the example problems fairly easily, but the part where I model my own problem and execute/solve that was always underserved. Or it felt like that to me anyway. I don’t have a background in the theory, but I can easily see that it could solve my problems if only I could figure it out. > As for the Community/Enterprise split - we want to continue the open source project, but we need to eat too :) Yeah, I don’t begrudge you that. It’s just that when I see that multithreading is locked away I just know that the moment I start using the product I’ll find out my toy problems are enterprise scale. Sort of like murpheys law, but for software features.
eigenvalue 3y ago
What about this one: https://www.cvxpy.org/ https://www.cvxpy.org/ If you can convert your problem into a convex one (which I believe is often possible if you’re clever about how you express it), that would seem to be a pretty good option, no?
- mlsu 3y ago
  CVXpy is a frontend that transforms problems into a form that different solvers can understand. It does make it very easy to format problems in Python but you still need a solver like Gurobi on the backend. You can use a variety of solvers on the same problem though, which is nice: https://www.cvxpy.org/tutorial/advanced/index.html#choosing-a-solver https://www.cvxpy.org/tutorial/advanced/index.html#choosing-... My understanding is that Gurobi the best -- but also the most expensive.
sterlind 3y ago
Gurobi is a MIP solver right, not a planner? I use Gurobi at work for a certain kind of bi-level programming and it's amazing, like literally ~500x faster than CBC. Picat's planner is more like a Prolog flavor of PDDL (e.g. fast-downward and its ilk.)
- hokkos 3y ago
  Did you tried highs it is way faster than CBC and open source. https://highs.dev/ https://highs.dev/
- 7thaccount 3y ago
  MIP, LP, Nonlinear for GUROBI. GUROBI and CPLEX can do planning of course if you formulate your problem in a certain way, but some solvers like Hexaly show large performance gains for things like vehicle routing vs GUROBI as they take a very different approach (don't use LP or MIP).
Aeolun 3y ago
If any of these had reasonable pricing I’d be happy to pay, but if the first price you see is ‘contact us’ you can be certain it’s too much for hobby use…
- criddell 3y ago
  It’s worth asking for free access. Make it clear that you are an individual (not a commercial users) looking to learn and that you wouldn’t be a burden on their network or support system.
- 7thaccount 3y ago
  For GUROBI at least, you can access a free version directly through Anaconda or Pip I think that is limited to a few months and can only solve smaller problems. It does give you a sense of its capabilities. It is also free for academics. It is extremely expensive for production use though.
c0brac0bra 3y ago
Thanks so much for sharing these. I had no idea that there were commercial API offerings for this kind of stuff. Just never worked for a business that had this sort of need. I will definitely bookmark them for the future.

shoo 3y ago

Yup. & when you get a model that works matched up with an industrial scale decision problem that's valuable to solve, arguably it's only of academic interest if you can solve it "optimally". The problem is only a simplified model of reality anyway -- it's often better to get a quick close-enough approximate solution to a problem that's a good approximation of the situation than an exact optimal solution to a simpler problem that's a poorer approximation. If you're lucky enough to get a problem that's basically stable over time, where the problem structure doesn't change, then maybe you can get improved solutions rapidly at industrial scale replacing use of a black-box MIP solver like Gurobi/CPLEX with a decomposition that exploits the problem structure, where sub-problems can be solved by some specialized graph algorithm or heuristic or brute force (if they all have bounded size), and the general purpose MIP/LP solver can be left with the job of figuring out how to deal with the shared resources and constraints that bind the subproblems together. The downside to a highly specialised custom solver is that it usually isn't flexible to changing requirements (unless you get very lucky) -- a slight change in business rule can break the problem structure that underpins the entire solution approach.

7thaccount 3y ago
I disagree with the first statement for some industries. My industry has several companies that have amongst the hardest MILP problems in the world that have millions of variables and constraints and need to be globally optimal for the sake of fairness and to save many millions of dollars per year. Electricity markets are extremely complicated and although it would be amazing to simplify things, the decisions and prices need to be correct. Also, performance is critical as these auctions are running 24/7. They're also always being changed as well, so black-box globally optimal solutions are a need to have.

polivier 3y ago

> There are plenty of commercial solvers out there that beat the pants off the open source options in terms of performance and in terms of depleting one's wallet :) While this is generally true, there are some exceptions. I recently compared the performance of CP-SAT vs CPLEX for a problem (linear constraints and objective). For large instances where proving optimality in a reasonable time was out of the question, CP-SAT had much faster convergence to near-optimal solutions than CPLEX when the time limit was small enough (~30s to a few minutes). This is with the CPLEX solver tuned towards improving the upper bound as much as possible (it was a minimization problem).

whatever1 3y ago
If feasibility is your goal then cp/sat solvers/heuristics should be your tool of choice. I you have optimality requirements (aka from the feasible solutions find the absolutely best) then optimization is the way to go
- sterlind 3y ago
  can't you just use the strong duality theorem to reframe an integral optimization problem as a system of integer inequalities? I thought you usually don't do that because the satisfaction problem is harder in practice.
  - whatever1 3y ago
    No unfortunately strong duality does not hold for integer problems. But your intuition is right, this is roughly how IP optimizers work. They relax the problem to a continuous one (aka convert the {0,1} to [0,1]), solve this super easy linear problem and try to find integral solutions close this linear optimum. If not, start branching on the integers and solve smaller and smaller linear problems until you prove optimality.
- polivier 3y ago
  I think that you've misunderstood what I said. For large instances of this specific problem (and when the time limit is too short to allow either CP-SAT or CPLEX to prove optimality) the best integer feasible solution found by CP-SAT is generally of better quality (w.r.t. the objective value) than the best integer feasible solution found by CPLEX. Furthermore, in some cases, CP-SAT can offer a certificate of optimality faster than CPLEX.

TimTheTinker 3y ago

Are the commercial offerings you mentioned better than TimeFold? [0] (formerly known as OptaPlanner before the main developers forked it) TimeFold's heuristics-based approach makes fast solutions to even highly-complex scenarios within the reach of anyone who can write Java or Python expressions that evaluate to true when constraints are satisfied. [0] https://timefold.ai/ https://timefold.ai/

Aeolun 3y ago
I found Optaplanner to be nice, but supremely unergonomic to use. I could replicate their example problems and not much else. > All OptaPlanner features are part of Community Edition, except for Multithreaded Solving Of course, because why not. If you can take features away from an existing thing to make more money.
- ge0ffrey 3y ago
  Could you elaborate on how OptaPlanner/Timefold wasn't ergonomic? I 'd love to understand this better, so we can improve it in Timefold Community. To help deal with new problems, we're creating out-of-the-box quickstarts for common use cases: https://github.com/TimefoldAI/timefold-quickstarts https://github.com/TimefoldAI/timefold-quickstarts As for the Community/Enterprise split - we want to continue the open source project, but we need to eat too :) Geoffrey (Timefold co-founder / OptaPlanner creator)
  - Aeolun 3y ago
    Basically, the documentation was set up so that I could come in and do a bunch of the example problems fairly easily, but the part where I model my own problem and execute/solve that was always underserved. Or it felt like that to me anyway. I don’t have a background in the theory, but I can easily see that it could solve my problems if only I could figure it out. > As for the Community/Enterprise split - we want to continue the open source project, but we need to eat too :) Yeah, I don’t begrudge you that. It’s just that when I see that multithreading is locked away I just know that the moment I start using the product I’ll find out my toy problems are enterprise scale. Sort of like murpheys law, but for software features.

eigenvalue 3y ago

What about this one: https://www.cvxpy.org/ https://www.cvxpy.org/ If you can convert your problem into a convex one (which I believe is often possible if you’re clever about how you express it), that would seem to be a pretty good option, no?

mlsu 3y ago
CVXpy is a frontend that transforms problems into a form that different solvers can understand. It does make it very easy to format problems in Python but you still need a solver like Gurobi on the backend. You can use a variety of solvers on the same problem though, which is nice: https://www.cvxpy.org/tutorial/advanced/index.html#choosing-a-solver https://www.cvxpy.org/tutorial/advanced/index.html#choosing-... My understanding is that Gurobi the best -- but also the most expensive.

sterlind 3y ago

Gurobi is a MIP solver right, not a planner? I use Gurobi at work for a certain kind of bi-level programming and it's amazing, like literally ~500x faster than CBC. Picat's planner is more like a Prolog flavor of PDDL (e.g. fast-downward and its ilk.)

hokkos 3y ago
Did you tried highs it is way faster than CBC and open source. https://highs.dev/ https://highs.dev/
7thaccount 3y ago
MIP, LP, Nonlinear for GUROBI. GUROBI and CPLEX can do planning of course if you formulate your problem in a certain way, but some solvers like Hexaly show large performance gains for things like vehicle routing vs GUROBI as they take a very different approach (don't use LP or MIP).

Aeolun 3y ago

If any of these had reasonable pricing I’d be happy to pay, but if the first price you see is ‘contact us’ you can be certain it’s too much for hobby use…

criddell 3y ago
It’s worth asking for free access. Make it clear that you are an individual (not a commercial users) looking to learn and that you wouldn’t be a burden on their network or support system.
7thaccount 3y ago
For GUROBI at least, you can access a free version directly through Anaconda or Pip I think that is limited to a few months and can only solve smaller problems. It does give you a sense of its capabilities. It is also free for academics. It is extremely expensive for production use though.

c0brac0bra 3y ago

Thanks so much for sharing these. I had no idea that there were commercial API offerings for this kind of stuff. Just never worked for a business that had this sort of need. I will definitely bookmark them for the future.