# Automated Planning Problems Are Cursed With NP Completeness

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 article, I 'll prove that brute force takes billions of years even for small planning problems.

This article from the Drools team blog. You can find more information about Drools Planner on the homepage, download page and in the reference manual.

Geoffrey De Smet is a Java developer from Gent, Belgium. In his spare time, he specializes in solving automated planning problems and develops the Drools Planner project.

{{ nComments() }}