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.
Knapsack problems
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 subset of the 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.
OR-Tools provides several solvers for knapsack problems in its algorithms library.
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 physical quantity, such as weight and volume, and the knapsack has a capacity for each quantity. Here, the term dimension does not necessarily refer to the usual spatial dimensions of height, length, and width. However, some problems might involve spatial dimensions, for example, finding the optimal way to pack rectangular boxes into a rectangular storage bin.
Multiple knapsack problems, in which there are multiple knapsacks, and the goal is to maximize the total value of the packed items in all knapsacks.
Note that you can have a multidimensional problem with a single knapsack, or a multiple knapsack problem with just one dimension.
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.