! 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
|