Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ask HN: Do you use an optimization solver? Which one? Do you like it?

news.ycombinator.com

Post reply on HN
Print view View original

11–20 of 158 posts

Re: Ask HN: Do you use an optimization solver? Which one? Do you like it?

#11

Post by shoo »

chime wrote: post #5
ryan-nextmv wrote: post #3

Earlier quoted context omitted.

Thanks for looking at our docs in light of your problem domain. That's way beyond what I anticipated, and much appreciated! 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 diagr…

> 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 everyt…

> 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

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.

Re: Ask HN: Do you use an optimization solver? Which one? Do you like it?

#12

Post by shoo »

The last time I tried to optimise something I ended up with a column generation formulation. I.e. I was wanting to rapidly iterate between LP solves of the (restricted) master problem & solves of auxiliary problems through hand written problem-specific algorithms taking shadow prices from the master problem dual solution as inputs. Then the auxiliary solution would contribute new variables into the master problem & we'd iterate until hitting a fixed point.

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

Re: Ask HN: Do you use an optimization solver? Which one? Do you like it?

#13

Post by shoo »

If I were doing another serious large-scale commercial optimisation application where it was more valuable to get a pretty good feasible solution rapidly rather than potentially wait a long time attempting to find a provably optimal solution, I would be very interested in seeing how localsolver performs.

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/

Re: Ask HN: Do you use an optimization solver? Which one? Do you like it?

#14

Post by eduardosalaz »

For MIP and LP I have used CPLEX, Gurobi and to a lesser extent Cbc. I used those three using JuMP (Julia package for mathematical programming) and Gurobi via pulp and pyomo. Of all three, I think Gurobi has a very accessible documentation, note that I am not saying better or more complete which in that case it would go to CPLEX, and the integration with Python straight out of the box is very useful. Cbc is a lifesaver when we couldn't access the academic licenses of the other two. Overall, I think CPLEX/Gurobi are my favorites with a slight edge to Gurobi. I have tried formulating problems using .lp and GAMS but JuMP is so much more ergonomic even if it's strictly tied to Julia (which I find to be a good thing).

Re: Ask HN: Do you use an optimization solver? Which one? Do you like it?

#15

Post by arsenide »

The only optimisation solver I use is Excel Solver Add-In.

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.

Re: Ask HN: Do you use an optimization solver? Which one? Do you like it?

#16

Post by bjourne »

chime wrote: post #2

I would love to use one or more but the process to convert business logic to solver is painful so I ended up having to write a simulated annealing algo in Rust instead. I tried solver.com, Google OR-Tools, and a few other utilities. It 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 impro…

What you are describing is a scheduling problem. It is not that difficult to solve using standard CP techniques. Create an Nx168 matrix of natural numbers for each room containing N machines, where each column represents the activity for a machine for a week. Constrain the sum of the rows to <= 1. Constrain the sum of the columns to <= 100. CP is all about "tricks" like these and takes a while to get used to. I can recommend the Python interface to OR-tools which I found very easy to work with.

Re: Ask HN: Do you use an optimization solver? Which one? Do you like it?

#17

Post by ryan-nextmv »

arsenide wrote: post #15

The only optimisation solver I use is Excel Solver Add-In. 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.

Is it safe to say those optimizations are performed ad hoc? That is, you're manually in control of the optimization process instead of wiring it up to some kind of automation?

Re: Ask HN: Do you use an optimization solver? Which one? Do you like it?

#18

Post by swanson »

I used OR-Tools via the Python bindings a few years ago. It was nice to work with once I got setup but it was a pain to get it installed (both locally and when deploying to a cloud server).

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.

Re: Ask HN: Do you use an optimization solver? Which one? Do you like it?

#19

Post by arsenide »

ryan-nextmv wrote: post #17
arsenide wrote: post #15

The only optimisation solver I use is Excel Solver Add-In. 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.

Is it safe to say those optimizations are performed ad hoc? That is, you're manually in control of the optimization process instead of wiring it up to some kind of automation?

Yes! In particular, it is usually to create some concrete data/parameters to be used towards creating the final product.

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!

Re: Ask HN: Do you use an optimization solver? Which one? Do you like it?

#20

Post by aurelian15 »

I have been using OSQP [1] quite a bit in a project where I needed to solve many quadratic programs (QPs). When I started with the project back in early 2017, OSQP was still in early stages. I ended up using both cvxopt and MOSEK; both were frustratingly slow.

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/

Post reply on HN