Stay organized with collections
Save and categorize content based on your preferences.
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.
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-28 UTC."],[[["\u003cp\u003ePacking problems involve finding the best way to pack items into containers, often with capacity constraints.\u003c/p\u003e\n"],["\u003cp\u003eKnapsack problems focus on maximizing the value of packed items within a single or multiple containers with limited capacity.\u003c/p\u003e\n"],["\u003cp\u003eBin packing aims to minimize the number of containers needed to pack all items, using bins of equal capacity.\u003c/p\u003e\n"],["\u003cp\u003eMultidimensional and multiple knapsack problems are variations that consider additional item properties or multiple containers.\u003c/p\u003e\n"],["\u003cp\u003eOR-Tools provides solvers and algorithms for tackling various packing problem types, including knapsack and bin packing.\u003c/p\u003e\n"]]],["Packing problems aim to pack items into containers with fixed capacities, often maximizing the total size or value of packed items. Key problem types include knapsack problems, where items have values and the goal is to maximize the total value in a single container, and bin-packing, which minimizes the number of containers needed to hold all items. Variations like multidimensional and multiple knapsack problems exist, with additional constraints or containers. OR-Tools offers solvers for these problems.\n"],null,["# Packing\n\nThe goal of *packing* problems is to find the best way to pack a set of\nitems of given sizes into containers with\nfixed *capacities*. A typical application is loading boxes onto delivery trucks\nefficiently.\nOften, it's not possible to pack all the items, due to the capacity\nconstraints. In that case, the problem is to find a subset of the items with\nmaximum total size that will fit in the containers.\n\nThere are many types of packing problems. Two of the most important are\n*knapsack problems* and *bin packing*.\n\nKnapsack problems\n-----------------\n\nIn the simple knapsack problem, there is a single container (a knapsack).\nThe items have *values* as well as sizes, and\nthe goal is to pack a subset of the items that has maximum total value.\n\nFor the special case in which value is equal to size, the\ngoal is to maximize the total size of the packed items.\n\nOR-Tools provides several solvers for knapsack problems in its\n[algorithms library](/optimization/reference/algorithms).\n\nThere are also more general versions of the knapsack problem. Here are a couple\nof examples:\n\n- *Multidimensional knapsack problems* , in which the items have\n more than one physical quantity, such as weight and volume,\n and the knapsack has a capacity for each quantity. Here,\n the term *dimension*\n does not necessarily refer to the usual spatial\n dimensions of height, length, and width.\n However, some problems might involve spatial dimensions,\n for example, finding the optimal way to pack rectangular boxes into a\n rectangular storage bin.\n\n- [*Multiple knapsack problems*](/optimization/pack/multiple_knapsack),\n in which there are multiple knapsacks, and\n the goal is to maximize the total value of the packed items in all knapsacks.\n\nNote that you can have a multidimensional problem\nwith a single knapsack, or a multiple knapsack problem with just one\ndimension.\n\nThe bin-packing problem\n-----------------------\n\nOne of the most well-known packing problems is\n*bin-packing* , in which there are multiple containers (called *bins*) of\nequal capacity. Unlike the multiple knapsack problem, the number of bins is not\nfixed. Instead, the\ngoal is to find the smallest number of bins that will hold all the items.\n\nHere's a simple example to illustrate the difference between the\nmultiple knapsack problem and the bin-packing problem. Suppose a company has\ndelivery trucks, each of which has an 18,000 pound weight capacity, and 130,000\npounds of items to deliver.\n\n- Multiple knapsack: You have five trucks and you want to load a subset of the\n items that has maximum weight onto them.\n\n- Bin packing: You have 20 trucks (more than enough to hold all the items)\n and you want to use the fewest trucks that will hold them all.\n\nThe following sections show how to solve various types of packing problems with\nOR-Tools, starting with the [knapsack problem](/optimization/pack/knapsack)."]]
