undefined | Better HN

0 pointschime4y ago0 comments

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.

0 comments

3 comments · 3 top-level

mzl4y ago

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.

sandGorgon4y ago

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

nirinor4y ago

Now this sounds like a proper fun problem! :)

j / k navigate · click thread line to collapse