A typical integer program: the knapsack problem

Presents the model and data files.

A typical example of integer programs is the knapsack problem, which can be intuitively understood as follows. We have a 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 multi-knapsack problem is similar to the knapsack problem, except that there are multiple features for the object (e.g., weight and volume) and multiple capacity constraints. The following example, knapsack.mod, depicts a model for the multi-knapsack problem, while Data for the multi-knapsack problem (knapsack.dat) describes an instance of the problem.

int NbItems = ...;
int NbResources = ...;
range Items = 1..NbItems;
range Resources = 1..NbResources;
int Capacity[Resources] = ...;
int Value[Items] = ...;
int Use[Resources][Items] = ...;
int MaxValue = max(r in Resources) Capacity[r];


dvar int Take[Items] in 0..MaxValue;

maximize
  sum(i in Items) Value[i] * Take[i];
  
subject to {
  forall( r in Resources )
    ct:
      sum( i in Items ) 
        Use[r][i] * Take[i] <= Capacity[r];
}

This model has several novel features. It represents items and resources not by string sets but rather by integers. In other words, the items (respectively the resources) are represented by successive integers starting at 1. The instructions

int NbItems = ...;
int NbResources = ...;
range Items = 1..NbItems;
range Resources = 1..NbResources;

declare the number of items and the number of resources, as well as two ranges, Items and Resources, to represent the set of items and the set of resources.

The next three instructions

int Capacity[Resources] = ...;
int Value[Items] = ...;
int Use[Resources][Items] = ...;

are similar to the data declarations presented in Data declarations and the subsequent sections. The array Capacity represents the capacity of the resources, the array Value the value of each item, and Use[r][i] the use of resource r by item i.

The next instruction

int MaxValue = max(r in Resources) Capacity[r];

is more interesting. It declares an integer MaxValue whose value is given by an expression. OPL and IBM ILOG Script have many features for computing and preprocessing data, since this is fundamental in simplifying and improving the efficiency of many models.

The instruction

dvar int Take[Items] in 0..MaxValue;

declares the problem variables: take[Items] represents the number of times item i is selected in the solution. The variable is of type integer and is restricted to range in 0..MaxValue.

The rest of the statement is rather standard and should raise no difficulty. Data for the multi-knapsack problem (knapsack.dat) describes an instance of the problem.

NbResources = 7;
NbItems = 12;
Capacity = [ 18209, 7692, 1333, 924, 26638, 61188, 13360 ];
Value = [ 96, 76, 56, 11, 86, 10, 66, 86, 83, 12, 9, 81 ];
Use = [
      [ 19,   1,  10,  1,   1,  14, 152, 11,  1,   1, 1, 1 ],
      [  0,   4,  53,  0,   0,  80,   0,  4,  5,   0, 0, 0 ],
      [  4, 660,   3,  0,  30,   0,   3,  0,  4,  90, 0, 0],
      [  7,   0,  18,  6, 770, 330,   7,  0,  0,   6, 0, 0],
      [  0,  20,   0,  4,  52,   3,   0,  0,  0,   5, 4, 0],
      [  0,   0,  40, 70,   4,  63,   0,  0, 60,   0, 4, 0],
      [  0,  32,   0,  0,   0,   5,   0,  3,  0, 660, 0, 9]];

Feasible solution with objective 261890.0000:
  take = [0 0 0 154 0 0 0 912 333 0 6505 1180];

Feasible solution with objective 261916.0000:
  take = [0 0 0 153 0 0 0 912 333 0 6499 1180];

Final solution with objective 261916.0000:
  take = [0 0 0 154 0 0 0 913 333 0 6499 1180];