Knapsack problem

From Glossary

Jump to: navigation, search

An integer program of the form,

LaTeX: \max \{c^Tx : x \in \mathbb{Z}^n, \, x \ge 0,\, \mbox{ and } a^Tx \le b \},

where LaTeX: a > 0. The original problem models the maximum value of a knapsack that is limited by volume or weight LaTeX: (b), where LaTeX: x_j is the number of items of type LaTeX: j put into the knapsack at unit return LaTeX: c_j, that uses LaTeX: a_j units per item.

The group knapsack problem has this form, except that it pertains to Gomory's corner polyhedron problem for general integer programming.

The multi-dimensional knapsack problem has more constraints (e.g., volume and weight), LaTeX: Ax <= b, where LaTeX: A >= 0 with LaTeX: Ae > 0 and LaTeX: e^TA > 0.

Personal tools