We have only one set in this model—the set of items we are considering carrying in the knapsack. This is a primitive set, and we can define it in the sets section:

SETS:

  ITEMS: INCLUDE, WEIGHT, RATING;

ENDSETS

We have associated the three attributes INCLUDE, WEIGHT, and RATING with the set. INCLUDE will be the binary variables used to indicate if an item is to be included in the knapsack. WEIGHT is used to store the weight of each item, and RATING is used to store each item's rating.

Next, we will need to construct a data section to input the set members of set ITEMS and their associated weights and ratings. Here is a data section that accomplishes the task:

DATA:

  ITEMS          WEIGHT RATING =

   ANT_REPEL        1      2

   BEER             3      9

   BLANKET          4      3

   BRATWURST        3      8

   BROWNIES         3     10

   FRISBEE          1      6

   SALAD            5      4

   WATERMELON      10     10;

 

   KNAPSACK_CAPACITY = 15;

ENDDATA

Note that we have also included the knapsack 's capacity in the data section. This is a good practice in that it isolates data from the constraints of the model.

Given that all the sets and data have been defined, we can turn to building our objective function. We want to maximize the sum of the ratings of the items included in our knapsack. Note that INCLUDE( I) will be 1 if item I is included. Otherwise, it will be 0. Therefore, if we take the inner product of INCLUDE with the RATING attribute, we will get the overall rating of a combination of included items. Putting this into LINGO syntax, we have:

MAX = @SUM( ITEMS: RATING * INCLUDE);

Note that we did not specify a set index variable in the @SUM function. Since all the attributes in the function (RATING and INCLUDE) are defined on the index set (ITEMS), we can drop the set index variable and use implicit indexing.

Our next step is to input our constraints. There is only one constraint in this model. Specifically, we must not exceed the capacity of the knapsack. In a similar manner as the objective, we compute the weight of a given combination of items by taking the inner product of the INCLUDE attribute with the WEIGHT attribute. This sum must be less than or equal to the capacity of the knapsack. In LINGO syntax, we express this as:

@SUM( ITEMS: WEIGHT * INCLUDE) <=

KNAPSACK_CAPACITY;

Finally, we must make the INCLUDE variable binary. We could to this by adding:

@BIN( INCLUDE( @INDEX( ANT_REPEL)));

@BIN( INCLUDE( @INDEX( BEER)));

@BIN( INCLUDE( @INDEX( BLANKET)));

@BIN( INCLUDE( @INDEX( BRATWURST)));

@BIN( INCLUDE( @INDEX( BROWNIES)));

@BIN( INCLUDE( @INDEX( FRISBEE)));

@BIN( INCLUDE( @INDEX( SALAD)));

@BIN( INCLUDE( @INDEX( WATERMELON)));

(Note that the @INDEX function simply returns the index of a primitive set member in its set.) However, a more efficient and data independent way of doing this would be to embed an @BIN function in an @FOR function as follows:

@FOR( ITEMS: @BIN( INCLUDE));