Binary variables are very useful for modeling logical conditions. For instance, suppose your physician reviews your picnic plans and, fearing for your health, insists you must take either the salad or the watermelon along on your picnic. You could add this condition to your model by simply appending the constraint:

INCLUDE( @INDEX( SALAD)) +

INCLUDE( @INDEX( WATERMELON)) >= 1;

In order to satisfy this constraint, either the salad, the watermelon, or both must be included in the knapsack. Unfortunately, constraints of this form are not good practice in that they are not data independent. Suppose that your list of picnic items changes. You may need to modify this new constraint to reflect those changes. A well formulated model should require no changes to the constraints as a result of changes to the data. The following model demonstrates a data independent way of incorporating your physician's request (additions to the original model are listed in bold).

MODEL:

 

SETS:

  ITEMS: INCLUDE, WEIGHT, RATING;

  MUST_EAT_ONE( ITEMS);

ENDSETS

 

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;

 

  MUST_EAT_ONE = SALAD WATERMELON;

 

  KNAPSACK_CAPACITY = 15;

ENDDATA

 

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

 

@SUM( ITEMS: WEIGHT * INCLUDE) <=

KNAPSACK_CAPACITY;

 

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

 

@SUM( MUST_EAT_ONE( I): INCLUDE( I)) >= 1;

 

END  

We have derived a set called MUST_EAT_ONE from the original picnic items, and used an explicit list to include the items we must carry as members. Then, at the end of the model, we added a constraint that forces at least one of the "must eat" items into the solution.

For those interested, the solution to the modified model is:

Global optimal solution found.

Objective value:                    37.00000

Objective bound:                    37.00000

Infeasibilities:                    0.000000

Extended solver steps:                     0

Total solver iterations:                   0

Elapsed runtime seconds:                0.03

 

            Variable           Value        Reduced Cost

 INCLUDE( ANT_REPEL)        0.000000           -2.000000

      INCLUDE( BEER)        1.000000           -9.000000

   INCLUDE( BLANKET)        0.000000           -3.000000

 INCLUDE( BRATWURST)        1.000000           -8.000000

  INCLUDE( BROWNIES)        1.000000           -10.00000

   INCLUDE( FRISBEE)        1.000000           -6.000000

     INCLUDE( SALAD)        1.000000           -4.000000

INCLUDE( WATERMELON)        0.000000           -10.00000

In short, we drop the ant repellent and blanket, and replace them with the salad.