Wednesday, May 23, 2012

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.

1. Hi Paul,

thanks for the idea of showing how to use the solution pool of cplex for finding alternative MIP solutions. Hope you don't mind, but I adapted it to show how the same feature of CPLEX can be used within AIMMS.

You can find my adapted version at: http://blog.aimms.com/2012/05/alternative-mip-solutions-with-cplex-solution-pool/

Just to be sure, the solution pool does not need to provide the K best solutions? It just provides the optimal solution and some alternative sub-optimal solutions or not?

2. @Guido: I'm delighted to see your post for AIMMS users. Most especially, thanks for the question, which motivated the addendum I just added.

Yes, the solution pool approach need not actually find the K best solutions unless you crank the settings rather high. I'm not sure, but I think the intensity parameter may need to be 4 (highest setting) to have reasonable assurance of finding the actual K best solutions, although on any given problem a lower setting might work. (There is also the usual disclaimer with MIP models that time limits, memory limits or the eventual heat death of the universe might preclude finding the K best solutions ona sufficiently difficult problem.)

Due to the unfortunate prevalence of comment spam, users who do not authenticate will need to answer a Captcha challenge. Sorry about that!