Working with arrays

After completing this module the student should:


Video

Transcript

When solving a model, writing out the entire model manually might be prohibitive and repetitive. To solve this problem, OPL Studio provides a set of tools used to generate larger models.

To illustrate this, we are going to be working with a knapsack model.

The knapsack problem

Imagine a thief getting into a king treasure chamber. He only has a knapsack with him, and to make his escape, he can only fill it up to its capacity c. He has a set of objects to choose from, each associated with a weight w and profit p.

The mathematical formulation should look like this when you present it in reports:

The knapsack problem

We now need to translate this into an OPL model.

int n = 4;
range N = 1..n;
int cap = 9;

With these three lines, we have defined that we have 4 items to choose from, and a maximum capacity of 9. The items will be represented by an index in the range 1 to n. For each of these indices we need a profit and a weight.

int p[N] = [2,8,2,6];
int w[N] = [6,3,1,4];

the (ordinary) variables p and w will now both be arrays of integers. Each array will have a value for the indices contained in N. p[1..n] or p[1..4] could also be used, but the first form is preferred for its readability, and so that if we have more items later, we just have to change n and the data in the arrays.

We now need to define the decision variables. Here we also want one for each item. We need to decide if we take the item or not, so the type boolean seems correct.

dvar boolean x[N];

We now need to specify the objective function. We could of course write p[1]*x[1]+... but we would be back to enumerate the entire problem manually. A task more daunting perhaps if we had a wealthier king with thousands of items.

Conveniently OPL Studio has provided us with as way to do sums:

maximize sum(i in N) p[i]*x[i];

Note that x[i]==0 is equivalent to saying the item is not selected. Thus the corresponding p[i] will not be counted. The i is an arbitrarily chosen name for the index, just be sure not to reuse a name already in use (OPL studio will warn you). Be mindful about what exactly you are summing over. Had there been a + something after x[i] only the first part would be part of the sum:

maximize sum(i in N) p[i]*x[i]+w[i]; // Silly, and will not work, w[i] is not part of the sum
maximize sum(i in N) (p[i]*x[i]+w[i]); // Silly, but will work

As you can see, you may fix the problem with parenthesis. Having defined the objective (without the w[i]), we proceed to define the constraint:

subject to {
  sum(i in N) w[i]*x[i] <= cap;
}

The complete model now looks like this:

int n = 4;
range N = 1..n;
int cap = 9;

// Profits and weights
int p[N] = [2,8,2,6];
int w[N] = [6,3,1,4];

// Decision variable, do we take item i?
dvar boolean x[N];

// Maximize the profit of the items we take
maximize sum(i in N) p[i]*x[i];
subject to {
  // We can take no more than items with a combined weight of cap
  sum(i in N) w[i]*x[i] <= cap;
}

Conditional operator

The sum from the previous model was simple, in that it summed over an entire range. Occasionally we want to be more specific. Lets say we would like to modify the objective so that only items of weight more than 1 was considered:

maximize sum(i in N) p[i]*x[i];

Would become:

maximize sum(i in N: w[i]>1) p[i]*x[i];

The : can be read as "for which the following holds true". Multiple of these boolean expressions can be combined using && for and and || for or. You are encouraged to use parenthesis to ensure you are clear about what you are doing. (a && b )|| c is not equal to a && (b || c).

Test

Implement an solve the following model. You may find the modulus operator mod helpful.

$\textrm{maximize } \sum_{i=0}^{20} i \cdot x_i$

$\textrm{subject to }$

$\sum_{i=0}^{15} ( x_i ) \geq 10 $

$\sum_{i \in {1,3,5,7,9,11,13,15,17,19} } x_i \geq 7 $

$\sum_{i=0}^{20} x_i \leq 10 $

$ x \in {0,1}$