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.

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

11 comments:

  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?

    ReplyDelete
  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.)

    ReplyDelete
  3. Hi Paul.
    How do I store the variables (instead of just displaying) that is in the pool. My model is an MIP that contains variables x and t, so how du I store the loaded variables inside a variable,say, x^l t^l.

    ReplyDelete
    Replies
    1. Hi,

      I added a second addendum with code to store the solutions for the knapsack example.

      Delete
  4. Hi Paul! Thank you for your post!
    I have a problem with implementing the code above.
    I am running AMPL on windows and I am using "option solver cplex;". When I run the code above in the .run-file cplex ignores the populate statement and retuns only the optimal solution. what makes things even more inconvenient is when I solve my problem once again in the amplide prompt it works! Do you have any idees on how this problem can occur?

    ReplyDelete
    Replies
    1. Did you get your version of CPLEX from IBM or from AMPL (or maybe both?). When you get CPLEX from IBM, they include an executable named 'cplexamp' that is designed specifically to work with AMPL. If you acquire CPLEX from AMPL, they supply what I think is the same executable but for some reason call it 'cplex'.

      I don't use the AMPL IDE, but it's possible that the AMPL IDE sees "option solver cplex" and runs AMPL's version of CPLEX (equivalent to cplexamp). Meanwhile, if you have a IBM's version installed, running in a terminal may cause "option solver cplex" to use IBM's cplex executable (not cplexamp), which is not specifically designed to work with AMPL. I don't know how (or even if) solver options are passed from AMPL to the non-AMPL version of the cplex executable. If I try to use "options solver cplex" on my system, I don't get anything useful; CPLEX complains about incorrect usage (I don't think it can find the model file AMPL produces), and AMPL complains that CPLEX didn't write a solution file (because it never ran anything).

      Delete
  5. Hello Paul,
    i'm wondering how can i find the k best solutions in cplex (Concert technology) according with an objectif function, when a try to solve the model using "Populate + objectif function" i find only the best solution, the problem is how can i call populate an second time and don't find the same solution from the first call.
    if you have an idea, thank you very much

    ReplyDelete
    Replies
    1. specifically, how to exclude each found solution and solve the problem again

      Delete
    2. If you are using Concert, have you looked at this post: http://orinanobworld.blogspot.com/2013/01/finding-all-mip-optima-cplex-solution.html?

      Delete
    3. Yes i have seen it and i use the parameter SolnPoolAGap = k but sometimes the solutions are not the k best solutions.
      i would like to know how to use the function delSolnPoolSolns in the C++ API for to delete the first optimal solution on the pool and solve the probleme again to find an other optimal solution

      Delete
    4. SolnPoolAGap=k does *not* tell CPLEX to find the k best solutions; it tells CPLEX to eliminate from the pool any solution whose objective value is worse than the best solution so far by more than k units.

      Delete

If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on OR-Exchange.