Here is a copy of the knapsack model our application will load into LINGO:

MODEL:

 

SETS:

  ITEMS: INCLUDE, WEIGHT, RATING;

ENDSETS

 

DATA:

  ITEMS  = @POINTER( 1);

  WEIGHT = @POINTER( 2);

  RATING = @POINTER( 3);

  KNAPSACK_CAPACITY = @POINTER( 4);

ENDDATA

 

SUBMODEL SACK:

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

  @SUM( ITEMS: WEIGHT * INCLUDE) <=

   KNAPSACK_CAPACITY;

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

ENDSUBMODEL

 

CALC:

  !keep output to a minimum;

  @SET( 'TERSEO', 1);

  !solve the model;

  @SOLVE( SACK);

  !fix the INCLUDE attribute to it's optimal value;

  @FOR( ITEMS( I): INCLUDE( I) = INCLUDE( I));

ENDCALC

 

SETS:

  !construct a set of the optimal items;

  ITEMSUSED( ITEMS) | INCLUDE( &1) #GT# .5:;

ENDSETS

 

DATA:

  !send optimal items set back to caller;

  @POINTER( 5) = ITEMSUSED;

  !along with the solver status;

  @POINTER( 6) = @STATUS();

ENDDATA

 

END

Model: SACK

In the model's sets section:

SETS:

  ITEMS: INCLUDE, WEIGHT, RATING;

ENDSETS

We define the ITEMS set, which will store the set of potential items for the knapsack.  Each item has the following attributes:

In the data section, we ask LINGO to import all the data for the model via the @POINTER function:

DATA:

  ITEMS  = @POINTER( 1);

  WEIGHT = @POINTER( 2);

  RATING = @POINTER( 3);

  KNAPSACK_CAPACITY = @POINTER( 4);

ENDDATA

Note that in addition to strictly numeric values, we are also importing the set ITEMS.  This set will be passed from our calling application as an ASCII string.

Next, we have the actual knapsack model.  We partition the model as a submodel within our main model (the concept of submodels is discussed further in Chapter 13):

SUBMODEL SACK:

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

  @SUM( ITEMS: WEIGHT * INCLUDE) <=

   KNAPSACK_CAPACITY;

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

ENDSUBMODEL

This submodel contains three expressions.  First, there's the objective that maximizes total utility of the selected items.  Second, there is a constraint that forces total weight to not exceed capacity.  Finally, via the @BIN function, we force the INCLUDE attribute members to be either 0 or 1, given that fractional solution do not make sense for this model.

The next section is a calc section where we perform three steps:

CALC:

  !keep output to a minimum;

  @SET( 'TERSEO', 1);

  !solve the model;

  @SOLVE( SACK);

  !fix the INCLUDE attribute to it's optimal value;

  @FOR( ITEMS( I): INCLUDE( I) = INCLUDE( I));

ENDCALC

The first step sets the TERSEO function to minimize output from LINGO.  Next, we use the @SOLVE function to solve the knapsack submodel.  Finally,. we loop over the ITEMS set, fixing the INCLUDE attribute members to their optimal values in the SACK submodel.  The reason we need to fix their values is that we will need them in the following sets section where we use a set membership condition to generate the optimal set of items in the knapsack (set membership conditions will reject variables that aren't fixed in value).

Next, we derive the set ITEMSUSED from the original set of all potential items, however, we only include those items that have a nonzero value in the optimal solution:

SETS:

  !construct a set of the optimal items;

  ITEMSUSED( ITEMS) | INCLUDE( &1) #GT# .5:;

ENDSETS

As our last step, we construct a data section to send the set of optimal items back to the calling program via @POINTER:

DATA:

  !send optimal items set back to caller;

  @POINTER( 5) = ITEMSUSED;

  !along with the solver status;

  @POINTER( 6) = @STATUS();

ENDDATA