|
|
|
|
|
|
by chime
1526 days ago
|
|
|
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. |
|
|
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.