The goal of packing problems is to find the best way to pack a set of items of given sizes into containers with fixed capacities. A typical application is loading boxes onto delivery trucks efficiently. Often, it's not possible to pack all the items, due to the capacity constraints. In that case, the problem is to find a subset of the items with maximum total size that will fit in the containers.
There are many types of packing problems. Two of the most important are knapsack problems and bin packing.
In the simple knapsack problem, there is a single container (a knapsack). The items have values as well as sizes, and the goal is to pack a set of items that has maximum total value.
For the special case in which value is equal to size, the goal is to maximize the total size of the packed items.
There are also more general versions of the knapsack problem. Here are a couple of examples:
Multidimensional knapsack problems, in which the items have more than one dimension, and the knapsack has a capacity for each dimension. The dimensions could be spatial—for example, length, width, and height—or they could be physical quantities, such as weight and volume. In the latter case, a set of items fits in the knapsack if its total weight doesn't exceed the knapsack's weight capacity, and it's total volume doesn't exceed the volume capacity.
Multiple knapsack problem. In this problem, there are multiple knapsacks, the number of which is fixed, and the goal is to maximize the total value of the packed items in all knapsacks.
The bin-packing problem
One of the most well-known packing problems is bin-packing, in which there are multiple containers (called bins) of equal capacity. Unlike the multiple knapsack problem, the number of bins is not fixed. Instead, the goal is to find the smallest number of bins that will hold all the items.
Here's a simple example to illustrate the difference between the multiple knapsack problem and the bin-packing problem. Suppose a company has delivery trucks, each of which has an 18,000 pound weight capacity, and 130,000 pounds of items to deliver.
Multiple knapsack: You have five trucks and you want to load a subset of the items that has maximum weight onto them.
Bin packing: You have 20 trucks (more than enough to hold all the items) and you want to use the fewest trucks that will hold them all.
The following sections show how to solve various types of packing problems with OR-Tools, starting with the knapsack problem.