Hello fellow OptaPlanner enthusiasts,
At my company we are trying to build a product based on OptaPlanner but we are running into a maddening situation. We have about 15 constraints, with various penalties and weightings.
Our main problem is, it seems that sometimes, especially in blindingly obvious situations, OP does not move the entities into positions that will satisfy our scoring system. We examine each case manually, and we always ask ourselves: "Why can't it put entity X here???".
In each problematic case, all constraints would be satisfied, and the score would be 0/0/0 or better, if OP would just move certain entities into the right place. It seems that it decides early on, in its planning, that certain entities can never move to, or move back, to certain positions.
Another complicating factor is that sometimes if we change the input order, the problem will be solved.
Overall, it seems that there is a magic under the hood that OP uses that we can't fathom. Could anyone offer some comments before I start dumping code into this question?
Thank-you so much, JO
This question is very vague, therefore so is the answer.
The most important point: there is no way to guarantee that OptaPlanner will find any particular solution, good or bad. If we knew how to reach into the search space and pull out a solution, we would not need OptaPlanner in the first place.
That "magic" under the hood that you mention is randomness. Unless you use REPRODUCIBLE environment mode (or the assert modes when not in production), OptaPlanner will never take the same path through the myriad possible solutions. OptaPlanner has no way of knowing if a better solution is just around the corner. It will simply try a random change, and see what happens. And it will use some smart heuristics to guess which is the best way to go from there.
OptaPlanner's way through the search space will be largely random, only guided by the constraints. And you need to take care and design your constraints very carefully. Most important in my opinion is to make sure you do not introduce score traps. A score trap is a situation where two vastly different solutions result in the same score. If the scores are the same, then the solutions are considered to be of equivalent quality. If you, as a human, can see that two solutions are qualitatively different yet their scores are the same, I suggest you figure out how to convert your insight into a constraint.
Once your constraints describe your problem as best as can be, the next goal is performance of the scoring function. OptaPlanner will find good solutions, assuming it has enough time to search. One way is to give it hours or days. Another way is to speed up the scoring function. This is a major topic on its own, and it is not really possible to give advice here without knowing the specifics of the problem. One general guideline: if your average score calculation count is on the order of hundreds or lower thousands per second, you have some work to do to help OptaPlanner help you. The more random changes you can process per second, the bigger your chance is of finding a good solution given the same amount of computation time.
And lastly, I am going to touch on your point of the input order. Yes, every time you change the input order, OptaPlanner will give different results. Even if you choose the REPRODUCIBLE environment mode - because your problem is suddenly different due to the input order. To avoid that, you should either make your order consistent, or you should look into planning entity difficulty and planning value strength to do the same for you.
EDIT: It is a downside of OptaPlanner that, on small data sets, we can (due to the nature of randomness) miss seemingly obvious good solutions, and a human would spot that. On these small data sets, using brute force is an obvious way to go - see branch and bound for example. But as the data sets grow larger, this will not scale and OptaPlanner's local search will significantly outperform anything any human can do. That is where OptaPlanner shines, and that is where it should be used.