Originally posted by: SystemAdmin
[prubin said:]
Finding all the optimal solutions to an IP problem is NP-hard in general, but if your problem has small dimension, it should be possible. There are two approaches, one using callbacks and the other solving the problem repeatedly.
[size=12pt]Using Callbacks[/size]
Use an incumbent callback to catch each new incumbent as it is reported by CPLEX. Your code must maintain records of the current incumbent objective value and the list of solutions producing that value. If the new solution ties the current incumbent value, add it to the list. If it exceeds the current incumbent value, update the incumbent value, purge the list of solutions, and start a new list with just this solution. Either way, the incumbent callback rejects this solution.
You don't want CPLEX bothering with solutions inferior to this one, but since you rejected it, CPLEX doesn't know it sets a new threshold. Therefore, you have to do something to tell CPLEX that solutions with objective values worse than this one's are not welcome. One way to do this (there may be others) is to use a cut callback to add a global constraints of the form "sum of the B_i >= z" where z is the value of this solution (or maybe the value - 0.5 -- good enough to block inferior solutions but leaves a little room for rounding error).
At termination, CPLEX will think the problem was infeasible (since you rejected all the incumbents), but that's ok -- you'll know it had solutions, and you'll have a list of all of them in your program memory.
[size=12pt]Solve - modify - solve[/size]
This approach eats more CPU cycles but is less taxing on the brain (no callbacks). Solve the model the first time and get the optimal objective value and optimal solution. Add a constraint to the model saying "sum of B_i >= z" as above. You'll only need to do this once. Now let B* denote the optimal value of the B variables. Add a constraint that says
sum_{i|B*_i=0} B_i + sum_{i|B*_i = 1} (1-B_i) >= 1.
Note that B* makes the left side of the constraint 0, so it's no longer feasible. Each time you get a new solution, you'll add a constraint like this (cumulatively). Now solve the model again (and again and again) until CPLEX decides you've made it infeasible.
This gets all optimal values of B; it doesn't get all optimal values of D that produce the same B. Getting all D combinations is more annoying because they're general integer rather than binary variables. If different D vectors can produce the same (optimal) B vector, and if you want all the D's for a given B, then my best advice is to convert D to binary (the usual trick is to write each D_j as a binary expansion, with a binary variable for each bit). Now all variables are binary and we reduce to the previous case.
[size=12pt]CPLEX 11[/size]
CPLEX 11.0 takes all the challenge out of this. If that's what you're running, read the documentation on solution pools:
[i]ILOG CPLEX 11.0 User's Manual > Discrete Optimization > Solution Pool: Generating and Keeping Multiple Solutions > What Is the Solution Pool?[/i]
/Paul
#CPLEXOptimizers#DecisionOptimization