Hacker News Reader

Comment by 7thaccount | Hacker News Reader

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.

View on HN

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.

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.

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

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

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.

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.

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.

Hmmm...for this problem, have you tried Hexaly? Just curious.

No I haven't, but in our case CP-SAT works very well and license-wise it's free.

Yes, highly recommended. There is abit of a gap in modeling approaches to classic MILP but the team are very proactive to make it work.

Also very permissive license with unlimited deployment and cores!

Well these are generic solvers, meaning that they are tuned to perform on a variety of problems well, so you can easily find cases where you get unexpectedly low performance.

My advice is if you are on the clock, just use whatever works best out of the box.

Now if you plan to solve this problem thousands of times daily, then I would invest in writing custom callbacks in CPLEX to inject feasible solutions during the search since its heuristics are suffering in your problem case.

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

Did you tried highs it is way faster than CBC and open source.

https://highs.dev/

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

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/

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.

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

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)

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.

Thanks Aeolun! We're going to improve the documentation further. I am going to take this feedback along.

Huh, didn't know Optaplanner was forked. Bit sad, you would have thought it was good fit for IBM to all the enterprisey business automation stuff. Does Optaplanner have anyone left working on IBM(/RH) side?

Anyways, I wish the best for Timefold team, hopefully they can find success independently. With all the money sloshing around for all sorts of dumb AI projects, I think Timefold definitely deserves a portion too.

There are little to no commits on the optaplanner repo since May 2023, apart from CI/build changes.

I just hate it when you go to the pricing page and theres NO PRICING. None.

A lot of these companies started out with listed pricing and then grew and got crazy expensive. One of the nice things about the Mosek solver is that the price is listed and it is reasonable. I just dislike their API and documentation as it's written for mathematicians and not business SMEs.

> their API and documentation as it's written for mathematicians and not business SMEs

I've never worked with any of these, but that's what I would expect as well. API documentation that describes how to solve each kind of mathematical optimization problem.

Do you have an example of an optimization solver with API documentation for business SMEs?

Yeah. GUROBI makes it really easy to just do something like

m.addConstr(x+y<=limit);

Where m is a model object, x & y are decision variables and limit is a constant.

The above is a no brainer for any business expert. Some solvers are a LOT more low level though and you have to think of the problem in matrix form and specify row/column stuff and it's a lot more involved and assumes significantly more knowledge of the user than the former.

Gurobi does require you to iterate over doubly-nested arrays frequently (like when establishing a constraint between two entity sets)

Just fork the community edition and add your own implementation of "nearby selection" and "multithreaded solving"... in effect, you get the enterprise edition for free, you just have to pay your own developers. Believe it or not, there are software companies that would go this route. I worked for one... as a developer, my time was far less important than the penny pinching and the heavy bureaucracy required for procurement.

It would cost less to pay Timefold whatever price they quote.

Sorry. We're working on it... we're a startup.

We're still figuring out a good, clear, honest pricing model for Enterprise that works well across company sizes (small - big), industries (healthcare vs telecom vs ...) and usage frequency (strategic vs operational planning).

We're happy to send you our pricing table version 1 (use contact us form on Timefold website), but we need your feedback if it fits your business model, deployment model, usage model, etc to validate our pricing model.

easy to raise prices later. in your billing model include plan per customer.

What about this one:

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?

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

My understanding is that Gurobi the best -- but also the most expensive.

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.

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…

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.

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.

Reply on news.ycombinator.com