Ask HN: Do you use an optimization solver? Which one? Do you like it?
We’re trying to bring new ideas to the optimization space. We’ve used a bunch of technologies over time (CP, MIP, LP, heuristics, etc.). We’ve built our own solver (for https://www.nextmv.io) and learned a lot along the way.
Solvers are amazing. MIP solvers, for example, are some of the fastest and most mature software packages that exist. They’re also wickedly challenging to use effectively.
Do you use optimization solvers? Which ones? Why? Do you like them? Why or why not?
157 comments
[ 3.5 ms ] story [ 225 ms ] threadIt was much easier to build a score-calculator for min/max based on user-tweaked parameters, then, jiggle the data, re-calculate score, and keep doing it until there was significant improvement (again, standard SA). I would absolutely love to convert the entire production plan logic with material availability, lead-times, customer demand, quality control windows etc. to something like nextmv.io but looking at your docs, I have no idea where to begin.
Cost is a big factor too because 3 years ago I bought 4 old 24-core Xeons off eBay and they've been chugging non-stop simulating billion+ flops per hour with electricity being the only cost. I don't mind paying $50-100/day for cloud if the results are great and code is easy to manage. We have the same chicken-egg problem everyone in supply chain currently has - we don't have enough materials to make everything, don't know when we'll get everything, and so don't know the best order to buy/make everything in. I would love to write a solver for this using our dataset but I kind of don't want to re-invent the wheel.
As it stands, every solver I find is one layer of abstraction away from what I want to code in. I can explain the problem in length if you want but it's honestly nothing unique - just the standard MRP/ERP planning with ton of BOM items, PO delays, labor/machine capacity constraints etc.
Your existing tutorials explain how I can use your API/SDK to perform OR operations. That's great and a necessity. However, it's not sufficient for me because my questions are: How do I represent my production calendar in the JSON blob for your algo? How do I put a constraint of 100hrs/week/machine but also 168hrs/week/room full of specific machines. In other words, while each machine can run 100hrs/week, if there are 4 of them in the same room, only one can run at a time, and so combined machines in a given room cannot be over 168hrs/week. Maybe a tutorial or a higher-level library to help people like me convert business rules into JSON format for your APIs. Because even if I might be capable of using your API as-is, I unfortunately don't have the time to implement these things myself. Hope this makes sense and gives you some insight into at least one of your target use-cases.
We haven't put a lot more examples into our SDK docs lately since we've been working more on our routing engine and cloud offering. Now we're getting back to more foundational questions like "what should our solver be?" and "how should model formulation work?"
Hop started off as a decision diagram solver, but even internally we strap a lot of different techniques onto it. My hope is to support those patterns better, which is really why I posed this question.
I'd be interested to know: what made the process of converting business logic into solver-speak painful?
The fact that every solver doc I found shows me two near identical variables and 4 identical constraints. I can solve that using Excel Add-In. My problem is mind-numbingly complex, like everyone else doing supply-chain optimization. So I need examples for each type of constraint I have but instead, the tools expect me to figure out everything based on very generic examples. Dates are a big deal in what I do. I have no idea how to convert "each day the customer order is delayed is bad, but I also can't make things 3 months before they want it" into solver-speak. Cleaning a machine takes time, so it is often better to make similar things in a row (campaign-mode). No idea how to convert that to solver-speak.
The good thing is that once I understand how to convert my data into solver-speak, I can keep it updated on the fly since business logic doesn't change daily, just the data-set.
Feel free to contact me directly and/or we can Zoom etc. if you wish to discuss further. Wish you the best of luck either way!
if your problems can be attacked by LP / MIP type stuff, there's a book "model building in mathematical programming" by Williams that has a couple dozen different optimisation problems for a range of applications, with worked examples of how to formulate a model to solve each of them. each problem will be much less complex than your real-world optimisation puzzle but if you browse through the problem descriptions you might be able to match some against parts of your situation & get ideas for how Williams would model and optimise it.
What I saw often, and this was in finance, that one or two developers gain proficiency in converting problems to a specific solver tool, and then we could never move to a different library because it would have been so much effort to relearn.
This would be something in the objective function, I think? Assign some daily cost to having stock in inventory and a penalty per day that the "supply delivery to customer" task completes after the deadline.
IIRC ILOG solver used to have a lot of constraints that made implementing that kind of thing easier.
https://github.com/jodavaho/highfleet-ship-opt
I think there are much better algorithms in metaheuristic search than just simulated annealing.
What do you mean by quasi optimal?
Genetic algorithms product quasi optimal results but simulated annealing will not?
There is a third edition, 9 years later: https://link.springer.com/book/10.1007/978-3-319-91086-4
You already did that once, for your simulated annealing code.
It really feels like a tools or language problem. Heck, we used to have to manually work out derivatives for continuous optimization problems, but nowadays programming languages with performant built-in autodiff often make this trivial. Removing the manual derivation hassle let loose a flood of cool ideas and applications, even though there was no technical hurdle preventing them in the first place.
Alternate problem specifications is a well-explored area (what is Prolog if not a way of describing problems for a constraint satisfier?), but I wonder how many other neat things are dammed up behind usability problems.
I have a niggling feeling somewhere that JSON is the wrong language for this. Something like cue lang may be the right thing. (https://www.sobyte.net/post/2022-04/cue/)
The nice thing about scoring with SA is that I don't need to think like an operations research student. I just think in code with if/then/else and the number of dimensions don't matter. The code is working fine for now but now the problem is a business requirement to make it MUCH more complex and factor in a whole new set of constraints. SA will straight up not work with it because the scoring itself can take tens of seconds now. So I need to come up with a new 'proper' way, hence my renewed interest in solvers.
pretty sure there's heuristics at play...but how would you do it ? take your own example of
>constraint of 100hrs/week/machine but also 168hrs/week/room full of specific machines. In other words, while each machine can run 100hrs/week, if there are 4 of them in the same room, only one can run at a time, and so combined machines in a given room cannot be over 168hrs/week
From my experience, the most important thing to get right in any local search algorithm is the state representation and the moves generated. If those work well, then any combination of metheuristics like simulated annealing, tabu search, population based search, restarts, parallel exploration, portfolio methods, and so on. Quite often the literature focuses only on the meta heuristic, but not so much on the representation, which IMHO can be an issue.
As an example, for some problems that I have solved with local search, the most impact in improving performance of the algorithms have been in improving the base. Making moves and score updates fast, and making the moves generated meaningful in the context.
I'm doing almost exactly this right now on a client project (I consult in supply chain optimization)
For NLP i usually go with either https://worhp.de/ or just IpOpt.
Hadn't heard of JoD - that looks really interesting. What are your experiences so far?
My experience so far: Quiet good at finding feasible solutions when constraints are complex. Really young code with a lot of potential. Not that good at finding optimas.
I don't mind the overhead in developer time. Once you 'git gud' at translating problems to MIP/ LP, it's just a matter of learning syntax. The real trick is in translating problems.
It's a shame more CS courses don't focus on this problem translation meta-algorithm. You can get it in tough theory courses with problem mapping to prove complexity, but its usefulness goes way, way beyond that somewhat niche application. Learning to model problems as max flow, graph partitioning / matching, LP, MIP, gives you absolute super powers way, way beyond what you'd gain by having a solver that's easier to work with.
I needed shadow prices defined using the master problem dual solution. In my problem instances I would very often run into scenarios where the primal (and hence also dual) master LP problem had a unique objective value but the dual solutions at which that maxima was attained were non-unique. I learned that it only makes sense to talk about shadow prices in some allowable range for each dual decision variable, but LP solvers generally don't give you an API to extract much information about this from the current internal state of the simplex algorithm [0]. I read a bunch of LP solver documentation and the best one I found discussing this kind of stuff was the section in MOSEK's manual about sensitivity analysis[1]. This was for a hobby project, not business, so I didn't try out MOSEK, even though it is looks very modestly priced compared to other commercial packages.
What I did find, however, was that some time during the last few years, scipy.optimize grew an LP solver interface, and even better, Matt Haberland contributed a python implementation of an interior-point LP solver straight into scipy [2][3]. I found that Haberland & co's open source interior point LP solver produced dual solutions that tended to be more stable and more useful for shadow prices in my problems than a bunch of the other open source LP solvers I tried (including the various other LP backends exposed by scipy.optimize.linprog).
[0] a paper I found very helpful in understand what was going on was Jansen, de Jong, Roos, Terlaky (1997) "Sensitivity analysis in linear programming: just be careful!". In 1997 they got 5 commercial LP solvers to perform a sensitivity analysis on an illustrative toy problem, and although the solvers all agreed on the optimal objective value, none of them agreed with each other on the sensitivity analysis.
[1] https://docs.mosek.com/9.2/pythonapi/sensitivity-shared.html
[2] https://github.com/scipy/scipy/pull/7123
[3] https://docs.scipy.org/doc/scipy/reference/generated/scipy.o...
Often the mathematical model of the real world problem or the input data used to parametrise the model has a fair bit of approximation error (e.g. assuming parameters are deterministic when actually they are uncertain, linearising things to bash them into the MIP modelling framework, etc) , so pragmatically it doesn't often seem useful to be too bothered about getting an optimal solution to an approximate problem vs getting an approximate solution to perhaps a better model approximation of the true situation.
https://www.localsolver.com/
It’s great, but you have to be able to put your problem into Excel to use it which does not work for all use cases.
In cases where I’m trying to optimise something that doesn’t quite fit into Excel cleanly I’ll usually do some sort of hand-rolled Monte Carlo optimisation. This generally works for me in the types of problems I most often solve.
In the usual Excel Solver case, for a simplified example, I want to create a biased coin where getting heads doubles your money and tails loses your money, with expected payout 90% in the long run. The parameters to change are heads/tails coin weighting, to target a value 90%. A fair coin gives a long run payout of 100%. It turns out that if a biased coin hits heads 45% of the time and tails 55% of the time, we end up with this 90% payout. Excel solver can come up with these two values.
In this example, we can come up with these 45% and 55% values theoretically. With more complex systems, we may want to see the effects of changing a subset of parameters that have an indirect effect on payout.
For example, if we extend the “biased coin game” to instead be “win your money back, 2, or 3 times your wager each with some probability” on a heads result, there are more parameters (and many solutions!) to get to 90% payout. Changing the heads probability has a further, second-order effect on the payout. Using Excel solver it’s straightforward to fix some parameters (heads/tails probability) and allow others to change (1x/2x/3x odds) to get desired results (90% payout).
If we further extend this methodology for a biased coin game, we can end up with a coin game that pays with distribution exactly like a slot machine in a casino, though it would not look like one!
I would have liked some kind of API that I could call out to instead but nothing existed at the time: you pass in the inputs to construct the linear equations and then you get back the results.
After I picked up the project again a year later (around 2019ish), I stumbled across OSQP again. OSQP blew both cvxopt and MOSEK out of the water in terms of speed (up to 10 times faster) and quality of the solutions (not as sensitive to bad conditioning). Plus the C interface was quite easy to use and super easy (as far as numerics C code goes) to integrate into my larger project. I particularly liked that the C code has no external dependencies (more precisely: all external dependencies are vendored).
[1] https://osqp.org/
https://www.optaplanner.org/
https://en.wikipedia.org/wiki/Vehicle_routing_problem
Have you seen our quickstarts repo? https://github.com/kiegroup/optaplanner-quickstarts It features various use cases across various technologies.
For fun I made this Golomb ruler solver using cplex: https://github.com/strateos/golomb-solver
* Minion for IP for scheduling + edge crossing minimization.
* cvxpy (wrapping ECOS, OSQP, and SCS by default) for convex optimization for making nice geometry.
* Z3 and STP for SAT/SMT for program analysis.
All are FLOSS, which is my main criterion in many situations.
Beyond that, I like minion for its focus on only providing efficiently implementable primitives, cvxpy for the awesome lectures and documentation the folks behind it have produced, and z3 + stp for their use in tools I like, such as klee.
For example, I would perhaps not use the same solver for a best-effort problem where I can program strong heuristics, vs a problem that must be optimized and no natural heuristics exist. Sometimes problems have a natural type of formulation, and it is best to use a solver for that type of problem (linear programming, mixed integer programming, SAT, pseudo boolean, constraint programming, ...).
Choosing a solver also very much depends on the deployment situation; how should a model be used and what operational concerns are there.
For example, I first found minion when I was learning about scheduling problems, initially to help a friend who was a Chief Resident on a pediatrics ward and later, to automate the administrative hassle of scheduling incident responders. (I wrote about that a little bit many years ago here if you’re curious: https://mstone.info/posts/scheduling/)
Concurrently with that, while I was working with and supervising security researchers, I spent quite a bit of time implementing various program analyses to answer questions about what certain programs of interest might do, and to find inputs that would make them do interesting things. For this purpose, though, minion is much less immediately relevant than Z3 since the interfaces and research interests of the relevant communities are so different.
Finally, this year, I am focusing on problems that have a more conventionally geometric flavor as opposed to the more discrete search spaces mentioned above. Here, convex optimization is a starting point that cvxpy makes incredibly accessible, especially in combination with Stephen Boyd’s Stanford SEE EE364A lectures (or similar): https://see.stanford.edu/Course/EE364A
After trying different stuff, and under different platforms (e.g. Matlab + CPLEX, Python + GLPK, etc), I settled first on Python or-tools with COIN-LP (about 100x faster than GLPK). Later we got access to FICO Xpress solver which in turn gave us some other gains.
I really liked this benchmarking website: http://plato.asu.edu/bench.html
It seems like they got into some trouble, so I don't know if they are still tracking the main commercial solvers.
Community sentiment seems to be beginning to shift toward favouring the HiGHS solver (https://github.com/ERGO-Code/HiGHS) over CBC. Something I'm keeping a close eye on.
nextmv seems to pitch itself as a generic solving ("decision automation") platform or something (unclear). But it seems that the only fleshed out product offering is for vehicle routing, based on the docs. Are there plans to offer, for instance, a solver binary that can be used to solve generic problems?
Also all the github repos under https://github.com/nextmv-io are private, so links from docs are 404.
Most open-source solvers don't handle parallelization well, and they lack the latest research on techniques like branch-cutting and heuristics that can speed things up significantly.
In my experience, Gurobi is still leader for linear and MiP solving. But, it's really expensive and the licensing terms seem anachronistic.
SimpleRose.com was a startup working on a new solver, too - I'm curious if anybody has tried it yet?
To OP's question, besides JuMP, the other use case I've had for optimization is for optimizing the drawing order of pen plots, for which I used or-tools. A write-up on it is here: https://nb.paulbutler.org/optimizing-plots-with-tsp-solver/
> link to twitter
visible_confusion.png.jpg.exe
Images aren’t ideal for sharing code, of course, but it’s not like this example works as a standalone program.
I remember liking JuMP, but Julia itself didn't feel ready yet. Some of the packages had weird behaviors. For example, Gadfly took several minutes to render some of my charts. IIRC when I looked at the source, it was solving a MIP to compute the best bounding box for display purposes.
I should probably check it out again.
Also: agreed regarding Gurobi licensing.
If I'm solving an optimization problem for personal curiosity, a blog post, etc., JuMP is the tool I reach for. :)
I use JuMP to switch solvers to Mosek or an open source solver is something doesn't go as expected.