K Best Solutions in AMPL/CPLEX

This is a continuation of my earlier post on how to find the K best solutions to a mixed integer linear program. Per a reader request, I'll show how to do it using AMPL+CPLEX. Note that cplexamp is the name of the CPLEX executable that interfaces with AMPL.  The example is that same one from the previous post, a binary knapsack model.

Here's the AMPL code:

#
# K best solutions using AMPL + CPLEX
# Test problem is a binary knapsack
#
# model parameters
#
param n default 20;  # problem size
param k default 3;   # solutions to find
param weight {i in 1..n} := i*sqrt(i);  # item weights
param value {i in 1..n} := i^2;  # item values
param capacity := (2/3)*sum {i in 1..n} weight[i];  # knapsack capacity
#
# parameters controlling the solution process
#
param method in {1,2} default 1;  # method:
                                  # 1=solve MIP, then populate;
                                  # 2=populate only
param intensity in 0..4 default 3;  # CPLEX pool intensity
param limit default 20;     # number of pool solutions to generate
#
# the binary knapsack model
#
var x {1..n} binary;
maximize TotalValue: sum {i in 1..n} value[i]*x[i];
s.t. TotalCapacity: sum {i in 1..n} weight[i]*x[i] <= capacity;
#
# print out solution parameters
#
print "Problem size = ", n, ", seeking ", k, " solutions, method = ",
                      method, ", intensity = ", intensity, ", limit = ",
                      limit;
#
# set up CPLEX
#
option solver cplexamp;
option cplex_options ("populate=" & method & 
                      " poolstub=kbpool poolcapacity=" & k & 
                      " poolintensity=" & intensity & 
                      " poolreplace=1 populatelim=" & limit);
#
# solve the model and show the pool solutions
#
solve;
for {i in 1 .. Current.npool} {
  solution ("kbpool" & i & ".sol");
  display _varname, _var;
}

Most of the CPLEX options can be inferred from the AMPL parameters assigned to them.  There are two I should probably explain:

• poolstub is a file name that CPLEX will use to store each of the solutions in the pool (so in my case I end up with files kbpool1.sol, kbpool2.sol, and kbpool3.sol), which the final loop reads back in; and
• poolreplace tells CPLEX how to decide which solution to boot out of the pool when the pool is full and a new solution is found (value 1 means keep the solutions with the best objective value; other choices are to keep the most recently found solutions or to strive for diversity).

One last note: the .npool suffix (here attached to the current problem) returns the number of solutions in the solution pool at termination (which equals the number of .sol files generated).

Addendum: The last note is apparently not the last note. :-) Guido's comment below reminded me that an important point from the previous post needs to be repeated here (particularly if someone stumbles on this without reading the prior post).  The title of the post notwithstanding, the solution pool approach may not actually produce the K best solutions, unless the population limit is set quite high and the pool intensity is at one of the higher settings.  Both those settings changes are likely to increase solution times.  As was seen in the previous post on this, the moderate settings used in the code example produce several "good" solutions, one of which is optimal, but they do not always produce the second best, third best etc. solutions.

Addendum #2: To answer a question below, we can store the various solutions in a parameter (xx) in the script by adding the following code to the end of the script:

#
# store the solutions
#
param xx {i in 1 .. Current.npool, j in 1 .. n};
for {i in 1 .. Current.npool} {
  for {j in 1 .. n} {
    solution ("kbpool" & i & ".sol");
    let xx[i, j] := _var[j];
  }
}
display xx;  # verify what was stored