Lindo Systems

!  Generate the k best solutions to a 
  knapsack problem. 
   For some problems there may be an obvious,
  easy to compute objective, but also less
  easily quantified considerations. Thus,
  we may want to look at the k best 
  solutions according to the quantified
  objective, and then manually choose
  the most attractive solution, taking into
  account the unquantified considerations.
   If all the decision variables are 0/1,
  then generating the k best is easy to do;
 ! Keywords: Alternate Optima, K Best Solutions, Knapsack Model;
SETS:
 ITEM: WGT, VAL, Y; !Each item has a wgt, value, yes/no var;
 SOLN: RHS; !Each new soln has a RHS to help cut it off;
 SXI(SOLN,ITEM): COF; ! Coefficients of the cuts;
ENDSETS
DATA:
  ITEM       WGT    VAL =
 ANT_REPEL    1      2
 SIX_PACK     3      9
 BLANKET      4      3
 BRATWURST    3      8
 BROWNIE      3     10
 FRISBEE      1      6
 SALAD        5      5
 WATERMELON  10     20;
  CAP =  15;
  SOLN = 1..7; ! Number solutions we want;
ENDDATA

SUBMODEL KNAPSACK:
 MAX = OBJ;
  OBJ= @SUM( ITEM(j): VAL(j)*Y(j));       ! Objective;
       @SUM( ITEM(j): WGT(j)*Y(j)) <= CAP;! Wgt constraint;
       @FOR( ITEM(j): @BIN( Y(j)));       ! All vars 0/1;
 ! Cut off previous solutions;
  @FOR( SOLN(k)| k #LT# ksofar:
    @SUM( ITEM(j): COF(k,j)*Y(j)) >= RHS(k);
      );
 ! Do not waste time proving there is no better soln;
   OBJ <= THRESHOLD;
ENDSUBMODEL

CALC:
  NSOLN = @SIZE(SOLN);
  !Initially, no known k best solution;
  THRESHOLD = 9999999;
  @SET( "TERSEO", 2); ! Set solver to very terse;
  @WRITE(@NEWLINE(1),' The ',NSOLN,' Best Solutions to a Knapsack Problem.',@NEWLINE(1));
  @WRITE('           ');
  @FOR( ITEM(j): @WRITE('   ',ITEM(j)));
  @WRITE(@NEWLINE(1));
  @WRITE(' Soln  Obj  Items in(1)',@NEWLINE(1) );

  @FOR( SOLN(ks):
   KSOFAR = ks; ! Make index variable visible to world;
   @SOLVE( KNAPSACK);
   THRESHOLD = OBJ;  ! No remaining soln > THRESHOLD;
 ! Generate cut to cut off latest solution;
   RHS(ks) = 1;
 ! Generate cut coefficients and print current solution;
   @WRITE('  ',ks,'    ',@FORMAT( OBJ,'#3.0f'),':');
   @FOR( ITEM(j):
     @IFC( Y(j) #GT# .5:   !Either;
        COF(KS,j) = -1;    ! One of the 1's must decrease;
        RHS(ks) = RHS(ks)- 1;
        @WRITE('         1');
      @ELSE
        COF(KS,j) = 1;     ! or one of the 0's must increase;
        @WRITE('          ');
         );
   ); ! End FOR;

   @WRITE( @NEWLINE(1));
  );
ENDCALC