Knapsack-like Problems
If all the profits are 1, we can try to minimize the number of items which exactly fill the knapsack:
| minimize | ||
| subject to | ||
If we have a number of containers (of the same size), and we wish to pack all n items in as few containers as possible, we get the bin packing problem, which is modelled by having indicator variables container i is being used:
| minimize | ||
| subject to | ||
The cutting stock problem is identical to the bin packing problem, but since practical instances usually have far fewer types of items, another formulation is often used. Item j is needed Bj times, each "pattern" of items which fit into a single knapsack have a variable, xi (there are m patterns), and pattern i uses item j bij times:
| minimize | ||
| subject to | for all | |
| for all | ||
If, to the multiple choice knapsack problem, we add the constraint that each subset is of size n and remove the restriction on total weight, we get the assignment problem, which is also the problem of finding a maximal bipartite matching:
| maximize | ||
| subject to | for all | |
| for all | ||
| for all and all | ||
In the Maximum Density Knapsack variant there is an initial weight, and we maximize the density of selected of items which do not violate the capacity constraint:
| maximize | ||
| subject to | ||
Although less common than those above, several other knapsack-like problems exist, including:
- Nested knapsack problem
- Collapsing knapsack problem
- Nonlinear knapsack problem
- Inverse-parametric knapsack problem
The last three of these are discussed in Kellerer et al's reference work, Knapsack Problems.
Read more about this topic: List Of Knapsack Problems
Famous quotes containing the word problems:
“While the onset of puberty can vary by as much as six years, every adolescent wants to be right on the 50-yard line, right in the middle of the field. One is always too tall, too short, too thin, too fat, too hairy, too clear-skinned, too early, too late. Understandably, problems of self-image are rampant.”
—Joan Lipsitz (20th century)