How can I retrieve multiple solutions from CPLEX for a linear program?

[Natalie]

I have a linear program and I want to find out if there is a single optimal solution or multiple optimal solutions with the same objective value. I am using the solver CPLEX.

I tried this code, as suggested on another forum:

option cplex_options 'poolstub=dt_solutions';

solve;

# New problem suffix .npool should be returned.

# If it's positive, we can examine the solutions:

for{i in 1 .. Current.npool} {

 solution ("dt_solutions" & i & ".sol");

 display _varname, _var;

}

I got an error message that suffix .npool wasn't recognized. Is there a way to see if multiple optimal solutions exist and (if they do) view alternative solutions?

Thanks!

[Victor Zverovich]

Solution pool only works for MIP problems. If your problem is not MIP, CPLEX will not return an .npool suffix.

HTH,

Victor

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at http://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

[Natalie]

Yeah, that is what I expected since the advice was for MIP problems. Is there a way to view multiple solutions for an LP?

[Robert Fourer]

None of the large-scale LP solvers that I'm familiar with have any feature for finding multiple optimal solutions for one LP. Apparently this feature is neither as easy to implement or as useful to have as it might seem.

One potentially useful thing you could do in AMPL is to define a secondary objective function to push the solution toward a different part of the optimal region. For instance if you have

var Buy {j in FOOD} >= f_min[j], <= f_max[j];

minimize Total_Cost: sum {j in FOOD} cost[j] * Buy[j];

subject to Diet {i in NUTR}:
n_min[i] <= sum {j in FOOD} amt[i,j] * Buy[j] <= n_max[i];

you could add

maximize FoodBought {f in FOOD}: Buy[f];

subject to Optimal:
sum {j in FOOD} cost[j] * Buy[j] = sum {j in FOOD} cost[j] * Buy[j].val;

First you would solve without the Optimal constraint, then you would restore it -- to fix the objective expression at its optimal value -- and you would select a secondary objective to optimize subject to the total cost remaining optimal. For example,

model diet.mod;
data diet.dat;
drop Optimal;
solve;

restore Optimal;
objective FoodBought["SPG"];
solve;

In principle you could be guided by the basis status and reduced costs of the variables, but this quickly becomes messy when you account for upper bounds, slack variables, and degeneracy. Instead this approach is likely to work best when you can choose secondary objectives based on your specific knowledge of the model's structure and solutions.

Bob Fourer
am...@googlegroups.com

=======