Knapsack problems

Describes examples that involve a container (the ‘knapsack’) with a fixed capacity and a number of items as contents.

Knapsack problems are a typical application of integer programming (IP). In knapsack problems, there is a container (the ‘knapsack’) with a fixed capacity (an integer) and a number of items. Each item has an associated weight (an integer) and an associated value (another integer). The problem consists of filling the knapsack without exceeding its capacity, while maximizing the overall value of its contents.

A set of knapsack examples

The examples are based on a multiknapsack problem, which is similar to a knapsack problem, except that there are multiple features of the object (such as weight and volume) and multiple capacity constraints.

The examples are:

  • The basic knapsack project: examples/opl/knapsack. This is accessed using the run configuration Default Configuration.

  • The same model modified to use CPLEX priorities. This is accessed using the run configuration Solve using CPLEX priorities.

  • An external knapsack algorithm implemented in Java and called by means of IBM ILOG Script external functions to solve the cutstock subproblem: javaknapsack.mod

See also Cutting stock problems in this manual and Integer programming: the knapsack problem in the Language User’s Manual.