Over a million developers have joined DZone.

Automated Planning Problems Are Cursed With NP Completeness

· Java Zone

Discover how AppDynamics steps in to upgrade your performance game and prevent your enterprise from these top 10 Java performance problems, brought to you in partnership with AppDynamics.

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.

The Java Zone is brought to you in partnership with AppDynamics. AppDynamics helps you gain the fundamentals behind application performance, and implement best practices so you can proactively analyze and act on performance problems as they arise, and more specifically with your Java applications. Start a Free Trial.

Topics:

The best of DZone straight to your inbox.

SEE AN EXAMPLE
Please provide a valid email address.

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.
Subscribe

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}