alt Hacker NewsInteresting! Could you give example of problems you're using this for, to get an idea of where they'd be best suited?
Replies
Metaheuristics (for example, genetic algorithms) are applicable for any type of optimization problem, but especially those which are non-linear in nature. Modern mixed integer linear program solvers are impressively good, but the less linear a problem is, the harder it is to model as a MIP.
One practical consideration often ignored is difficulty of implementation. To make a MIP model, you only have the tools of linear programming: equations and linear inequalities, like mx >= y. If you want a MIP, you need to write down ALL aspects of your problem as a list of inequalities, which can be difficult for some real world domains. There is a real art to MIP modeling.
On the other hand, metaheuristics are like an interface where you only need to implement a few functions in plain old code and you can get good answers.
It’s not quite that simple, since there is still an art to modeling a problem in a suitable input format for a meta heuristic (for example in genetic algorithm, how do I write my delivery schedule as a genome?), but the upshot is that it doesn’t have to be a mathematically precise formulation to work correctly.
If I understand them correctly, they're saying to use standard, optimization methods after writing a fitness or evaluation function to score your possible solutions. Which is a normal, non-SAT way of doing optimization.
So, you could use it for any application you saw benefit from genetic algorithms, simulated annealing, or tabu search. You can even use those to optimize neural networks without backpropagation and with fewer, local optima. Many papers on this but it's computationally heavier.
You can find a list of quickstarts at https://github.com/TimefoldAI/timefold-quickstarts.
Examples include:
- School Timetabling
- Employee Scheduling
- Conference Scheduling
- Flight Crew Scheduling
Metaheurstics are also very useful for puzzle games; you can quickly run a metaheuristic to generate a difficult but solvable puzzle in less than a second, while only being about 20 lines of code without libraries (but as your scale increases to hundreds of different pieces, you probably want a library so you can use their incremental calculation).