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

131–140 of 158 posts

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

#131

Post by tilun »

shoo wrote: post #13

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…

+1 on being interested in seeing how LocalSolver performs. They seem very self-confident in their benchmarks (https://www.localsolver.com/benchmarks) and so it would be very interesting hearing from someone with hands-on experience from real-life applications using LocalSolver.

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

#132

Post by sampo »

chime wrote: post #124
sampo wrote: post #42

Earlier quoted context omitted.

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

> don't have the resources to write solving algo on top of the business logic that goes into the algo

You already did that once, for your simulated annealing code.

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

#133

Post by anoncept »

actually_a_dog wrote: post #44
anoncept wrote: post #27

After several years of exploring, my current gotos are: * 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 primitive…

I'm curious what kind of person has 3 favorite constraint optimizers. What do you do that has you making use of so many different ones?

Doing all sorts of things will introduce you to all sorts of problems; from there, it’s just a matter of habitually looking around to try to see who/what has already worked on whatever problem is currently in front of you.

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

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

#134

Post by nirinor »

chime wrote: post #125
sandGorgon wrote: post #87

Earlier quoted context omitted.

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…

Now this sounds like a proper fun problem! :)

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

#135

Post by sandGorgon »

chime wrote: post #125
sandGorgon wrote: post #87

Earlier quoted context omitted.

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…

this is super interesting - what is a "Score" ? i'm trying to model your problem as a neural net problem in my mind. how do you transform a classic linear optimization problem (which is a bunch of equations) into a score ?

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

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

#136

Post by snowAbstraction »

zokier wrote: post #21

Optaplanner facinates me, but I have no idea what I could be using it for and the learning curve seems quite heavy https://www.optaplanner.org/

You can use it for Vehicle Route Problems. I did so once as an interview project but never in production. If you start from some example problem, the learning curve isn't so steep.

https://en.wikipedia.org/wiki/Vehicle_routing_problem

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

#137

Post by mzl »

chime wrote: post #125
sandGorgon wrote: post #87

Earlier quoted context omitted.

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…

Sounds like you have a good solution for your problem. Whatever solves the problem and is already done is naturally a good solution!

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.

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

#138

Post by ge0ffrey »

Most constraints solvers require math equations based input. If you're more a fan of an Object Orientated Programming and Function Programming coding style, take a look at our solvers:

- OptaPlanner (Java, Kotlin, open source, Apache license) https://www.optaplanner.org/

- OptaPy (Python, open source, Apache license) https://www.optapy.org

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

#139

Post by ge0ffrey »

zokier wrote: post #21

Optaplanner facinates me, but I have no idea what I could be using it for and the learning curve seems quite heavy https://www.optaplanner.org/

We've done a lot lately to reduce the learning curve for OptaPlanner (open source).

Have you seen our quickstarts repo? https://github.com/kiegroup/optaplanner-quickstarts It features various use cases across various technologies.

Post reply on HN