Drools Planner (formerly known as Drools Solver) optimizes automated planning. Real world planning problems are almost always NP complete. But what does NP complete mean? And why is it so annoying? And how does Drools Planner deal with it?
Let’s take a look at the bin packaging use case. In this simple 2D bin packaging example we have to put 5 items of different sizes into a 4 by 8 container:
There are 3 solutions presented, but only the last solution is feasible:
- The first algorithm puts in the items with the largest size first. It starts with the purple item of size 9. In the end, the blue item doesn’t fit.
- The second algorithm puts in the items with the largest side first. It starts with the blue item which has a side of 5. In the end, the green item doesn’t fit.
- The last algorithm, one of Drools Planner’s algorithms, manages to fit in all the items and generate a feasible solution.
Why does the yellow item has to be at the bottom (or the top) in a feasible solution for this problem instance? Let’s take a look at 3 more problem instances and a feasible solution for each of them:
The yellow item is in a different location in each of those problem instances. It’s location depends upon the size of the container, all of the items involved and the constraints. They call this phenomenon NP complete:
- It is easy to verify a feasible solution,
- But it is hard to find a feasible solution.
Only by trying many (or all) of the solutions, we find a feasible solution. Actually, we can’t even easily prove if there even is a feasible solution:
Even though the total size of the items is 14 and the container is size 18, we
humans can easily see that there’s no feasible solution for this tiny planning problem.
But what if the planning problem is bigger?
Real world bin packaging has thousands of items, multiple containers, different container sizes and many more other constraints.
So, how do we make the computer automate it? Brute force?
No, because brute force takes too long. Instead, Drools Planner optimizes it with metaheuristic algorithms, such as tabu search and simulated annealing.
In a upcoming blog, I ‘ll prove that brute force takes billions of years even for small planning problems.
