3 ms·

I once tried to use MiniZinc as a back-end for a school timetabling app I was working on, and came away with the impression that the OptaPlanner Java API would

I once tried to use MiniZinc as a back-end for a school timetabling app I was working on, and came away with the impression that the OptaPlanner Java API would be a lot easier to use. (Although unlike solvers, OptaPlanner uses heuristic algorithms -- simulated annealing, etc.) Maybe it's just that formally expressing a set of constraints doesn't come naturally to me. I'm sure with a lot of practice, writing MiniZinc code would be easier. The Google OR-Tools Python API also might be easier if you're generating models dynamically. I wouldn't want to generate MiniZinc code...

wsdookadr 3y ago
That an algorithm is heuristic does not preclude it from being provably correct. It precludes it from being optimal! The goal of an heuristic algorithm is to produce a near-optimal or approximate solution in a reasonable amount of time. From here, some heuristics have more or less theory behind them and that theory shows what sort of properties the solution has. [1] https://optimization.cbe.cornell.edu/index.php?title=Heuristic_algorithms https://optimization.cbe.cornell.edu/index.php?title=Heurist... [2] https://en.wikipedia.org/wiki/Heuristic_(computer_science) https://en.wikipedia.org/wiki/Heuristic_(computer_science)
chriswarbo 3y ago
I've used OptaPlanner in production, it was pretty straightforward and coped perfectly well with the few-hundred-variable problems we needed it for (we ran it with a timeout, and its solutions were good). If you're comfortable programming Java, it should be easy enough (note that it relies on mutating objects in-place; which took some getting used to since I was using it from Scala!) I've used MiniZinc too (in a different project), where I wanted some optimal results to compare against some heuristic algorithms I was developing. MiniZinc requires more careful thought when it comes to encoding/representing the problem (i.e. sets of integers, rather than familiar Java objects), but it's not too difficult. Since it's optimal it can take an age to run; I could only scale my problem up to N=11 before it was taking more than 24 hours (that was enough for my comparisons though)
darksaints 3y ago
I have actually found that optaplanner often gets better results on hard problems than a lot of constraint solvers do. Part of that has to do with a genius aspect of how it was designed: constraint evaluation is built on top of the drools rule engine algorithm (an evolution of the Rete algorithm). I think the fact that it is written for the JVM is especially helpful because you can write constraints using JVM libraries, which are a massive boon in some of the very domain specific areas that I’ve worked in. Writing geospatial or RF propagation constraints in a DSL like minizinc is a total nonstarter.
- ge0ffrey 3y ago
  OptaPlanner was forked as Timefold by the team behind it: https://timefold.ai/blog/2023/optaplanner-fork/ https://timefold.ai/blog/2023/optaplanner-fork/ We made it twice as fast (by replacing Drools).
  - TimTheTinker 3y ago
    Thanks for the note! This is helpful to know.

wsdookadr 3y ago

That an algorithm is heuristic does not preclude it from being provably correct. It precludes it from being optimal! The goal of an heuristic algorithm is to produce a near-optimal or approximate solution in a reasonable amount of time. From here, some heuristics have more or less theory behind them and that theory shows what sort of properties the solution has. [1] https://optimization.cbe.cornell.edu/index.php?title=Heuristic_algorithms https://optimization.cbe.cornell.edu/index.php?title=Heurist... [2] https://en.wikipedia.org/wiki/Heuristic_(computer_science) https://en.wikipedia.org/wiki/Heuristic_(computer_science)

chriswarbo 3y ago

I've used OptaPlanner in production, it was pretty straightforward and coped perfectly well with the few-hundred-variable problems we needed it for (we ran it with a timeout, and its solutions were good). If you're comfortable programming Java, it should be easy enough (note that it relies on mutating objects in-place; which took some getting used to since I was using it from Scala!) I've used MiniZinc too (in a different project), where I wanted some optimal results to compare against some heuristic algorithms I was developing. MiniZinc requires more careful thought when it comes to encoding/representing the problem (i.e. sets of integers, rather than familiar Java objects), but it's not too difficult. Since it's optimal it can take an age to run; I could only scale my problem up to N=11 before it was taking more than 24 hours (that was enough for my comparisons though)

darksaints 3y ago

I have actually found that optaplanner often gets better results on hard problems than a lot of constraint solvers do. Part of that has to do with a genius aspect of how it was designed: constraint evaluation is built on top of the drools rule engine algorithm (an evolution of the Rete algorithm). I think the fact that it is written for the JVM is especially helpful because you can write constraints using JVM libraries, which are a massive boon in some of the very domain specific areas that I’ve worked in. Writing geospatial or RF propagation constraints in a DSL like minizinc is a total nonstarter.

ge0ffrey 3y ago
OptaPlanner was forked as Timefold by the team behind it: https://timefold.ai/blog/2023/optaplanner-fork/ https://timefold.ai/blog/2023/optaplanner-fork/ We made it twice as fast (by replacing Drools).
- TimTheTinker 3y ago
  Thanks for the note! This is helpful to know.