!  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