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

121–130 of 158 posts

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

#121

Post by prvak »

mzl wrote: post #104
prvak wrote: post #97

I use Minizinc in a personal toy project ( https://gitlab.com/dustin-space/meal-scheduler ), and GECODE or Google's ortools solver at the backend. It's used for meal planning. Unfortunately it's way way slower than I'd hope. I suspect I just have the domain not modeled efficiently. Maybe if I had a few days to put into it, and learn how to properly debug the CSP solver step by step, it might help...

Fun problem. When solving with Gecode, you might want to add the annotation `:: domain_propagation` to the `all_different` constraint ( https://www.minizinc.org/doc-2.6.2/en/lib-stdlib-annotations... ). Sometimes a good idea, sometimes not. If you can extract some instances you could send in your problem to the MiniZinc challenge ( https://www.minizinc.org/challenge2022/challenge.html ), preferably with several insta…

Thanks for the tips!

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

#122

Post by shaklee3 »

ta92834832 wrote: post #89

The history of state-of-the-art MIP solvers is fascinating. There are very few people in the world who can develop them, and there is a strong history of developers jumping ship from one company to another, tilting performance accordingly. Initially, CPLEX and Xpress were founded in the eighties. In the nineties, CPLEX was acquired by ILOG (a French CP company), which in turn was purchased by IBM around 2009. Around…

you could also write a similar story about the predatory licensing of cplex and gurobi. when gurobi started their model was "we're the opposite of cplex, and we don't count cores". but they realized that wasn't making them enough money.

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

#123

Post by cm2187 »

Google OR tools (along lpsolve). Can be used with c#, free, common api for multiple solvers. I find that on certain problems, even linear solvers can be instable and it is useful for the user to be able to use another solver with a simple drop down. I never fully understood what caused the instability (showing problems that are perfectly solvable as infeasible/abnormal). I suspect it has to do with the many orders of magnitude between the range of certain variables and the range of objectives/constraints. The only downside of Google OR Tools is that you need to recompile it yourself to use glpk (licensing).

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

#124

Post by chime »

sampo wrote: post #42
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…

> so I ended up having to write a simulated annealing algo I think there are much better algorithms in metaheuristic search than just simulated annealing.

Certainly but I didn't and still don't have the resources to write solving algo on top of the business logic that goes into the algo. I would much rather user my 20+ manufacturing ERP experience to setup the problem specific to our use-case than read research papers and implement generic CS algos.

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

#125

Post by chime »

sandGorgon wrote: post #87
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…

curious to know - how do you solve this today ? what is your abstraction/solver-speak today ? I also have faced this (though im not a power user like you) - so im curious what did u end up using today ? 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/ )

I don't 'solve' it using linear optimization today. I use https://en.wikipedia.org/wiki/Simulated_annealing which basically amounts to (1) calculate score based on the dataset (2) randomly change some data that affects the score (3) discard the score if it much worse, keep if slightly better or worse (4) repeat until new score is much better than original score. I allow it to get a little worse over time but if it is much worse, I basically restart from the last-best score.

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.

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

#126

Post by exikyut »

cfontes wrote: post #118

I've used custom made implementation in Java ( proprietary based on the owner thesis ) to optimize train crossings for big mining companies like Vale, BHP and Rio tinto, it was stressful but super fun work! Lot's of money to be made on it too if you guys are interested, but it's super niche and hard to get into. There is a huge resistence from train controllers and other workers. I actually understand it because of t…

That's awesome.

A comment on a recent thread about a train IT failure went on a bit of an interesting tangent about ahead-of-time network scheduling in (IIUC) the Netherlands' TURNI system - https://news.ycombinator.com/item?id=30902585

(The whole thread was a bit of a wide-spectrum ramble, as one might expect for a downtime event.)

So you're saying you were actually doing JIT routing as opposed to AOT? The linked system apparently precomputed the tripdriver/conductor schedules overnight. I wonder if they're still using that approach today. It does feel like a JIT approach is much more amenable to handling the unpredictable non-spherical real world (eg electricity issues, track breakage, crashes at crossings, train malfunctions that block tracks (right on junctions >:D), etc).

This sorta thing is definitely beyond my own mental level :) but for reference, how would someone interested get their foot in the door in this area?

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

#127

Post by exikyut »

ryan-nextmv wrote: post #3
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…

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…

Reading this from the perspective of a naive outside observer, I'm wondering (just thinking out loud) about the potential value of a hybrid approach of a) providing customers who know what they want a self-service API, b) supporting customers who just want their problems solved with consulting, and a+b) offering joint R&D scenarios in select circumstances that would progressively add support for novel workloads over time (like what's described here) in the pursuit of differentiation. Obviously this would be aligned with use cases that don't require immediate solutions/consulting. The resulting data might be worth it. And this all obviously depends on where ease-of-use sits, given that's basically NP-hard to resolve fully in this domain.

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

#128

Post by ai_enthusiast »

I did use Gurobi a few years ago for route optimization within a distro center but results were slow with load. I am now playing around with nvidia's reopt ...i think they now call it cuopt. Very curious to see solver results accelerated by GPU. The results shared were quite impressive - anyone tired it yet?

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

#130

Post by wolfgangK »

If I may hijack a bit this thread, I am currently looking for an optimization solver for a specific goal : I wish to constraint the values of variables so that tuples of variables are unique within sets of tuples.

Cf. https://stackoverflow.com/questions/71878354/constraint-prog...

For now, I could not find anything satisfactory, so any recommendation would be most welcome. Otherwise, I guess I'll have to generate a variable for each tuple and use and all_different (e.g. https://cpmpy.readthedocs.io/en/latest/api/expressions/globa... ) on those.

Post reply on HN