5  Knapsack Example

Knapsack problem is one of the fundamental problems of MILP. Knapsack is a representation of a capacity that should be filled with discrete items with various weights and value. The trick is to find the “optimal” set of items to add to knapsack in order to get the maximum value while adhering to capacity constraint.

An entertaining example would be you are given a cart at a shopping mall and you are allowed to fill it for free. Would you fill it with cereal boxes or chocolate?

A more “real life” example which we experience almost all the time would be packing for the airport which you are constrained with the size of your luggage and total weight of the luggage and its contents.

In practice logistics companies deal with this problem every day in order to fill their trucks with packages of various sizes and weights.

5.1 Problem Description

Suppose there is a “space” (e.g. a knapsack) with a single dimensional capacity of \(W\). Also we have a set of items with value and weight properties. We would like to determine which items to include in the knapsack to get the total maximum value from the items in the knapsack.

5.2 Model Building Steps

  1. Define the decision variables (\(x_i\)) as whether item \(i\) is in the knapsack or not. These decision variables are defined as binary.

  2. Define value (\(v_i\)) and weight (\(w_i\)) parameters for each item \(i\).

  3. Define a capacity parameter (\(W\)) for the knapsack.

  4. Define capacity constraint as the total weight of items should not exceed capacity parameter.

  5. Define objective function as the maximization of total value of items included in the knapsack.

5.3 Mathematical Model

5.3.1 Decision Variables

  • \(x_i\): Whether item \(i\) is included in the knapsack or not (binary variable).

5.3.2 Parameters

  • \(W\): Capacity of the knapsack.
  • \(v_i\): Value of item \(i\).
  • \(w_i\): Weight of item \(i\).

5.3.3 Model

\[\begin{gather} \max z = \sum_i v_ix_i \label{eq:obj.fun} \\ s.t. \nonumber \\ \sum_i w_ix_i \le W \label{eq:knapsack.constraint} \\ x_{i} \in \{0,1\} \label{eq:binary}\\ \end{gather}\]

5.3.4 Constraints

  • (\(\ref{eq:obj.fun}\)) is the objective function to maximize total value for items included in the knapsack.
  • (\(\ref{eq:knapsack.constraint}\)) is the capacity constraint of the knapsack. Each item \(i\) has a weight parameter \(w_i\) so items included in the knapsack should not weigh more than \(W\).
  • (\(\ref{eq:binary}\)) Binary constraint for decision variables.