As per this quote (and Tobias's suggestions):
"Since only nonbasic variables with reduced costs of 0 (zero) can change when the application moves from one alternate optimal solution to another, you can also enumerate alternate optimal solutions by using the routines CPXgetdj and CPXgetpi to identify the nonbasic structural variables and slacks with nonzero reduced costs. Then, fix these structural variables to their current values using CPXchgbds, and fix the slack variables with CPXchgsense. Set the simplex iteration limit to 1 (one); change the objective as before; and you can enumerate some, but not all, alternate optimal solutions."
I was able to successfully obtain some of the optimal solutions. I understand that you can't get all of them. Is it because that the above method could only give optimal solutions related to the given basis (set by fixing non-zero reduced costs variables/slacks)? So we could get different set of optimal solutions starting from some other optimal basis?
NOTICE: developerWorks Community will be offline May 29-30, 2015 while we upgrade to the latest version of IBM Connections. For more information, read our upgrade FAQ.
This topic has been locked.
2 replies Latest Post - 2012-12-29T13:11:31Z by SystemAdmin
Pinned topic Enumerating all optimal solutions
Answered question This question has been answered.
Unanswered question This question has not been answered yet.
Updated on 2012-12-29T13:11:31Z at 2012-12-29T13:11:31Z by SystemAdmin
Re: Enumerating all optimal solutions2012-12-27T00:37:05Z in response to SystemAdminAt the risk of belaboring the obvious, for an LP, you can at best enumerate all optimal basic feasible solutions; the number of optimal solutions is either 1 or uncountably infinite.
The problem of enumerating all optimal BFSes (vertex solutions) is NP-annoying. You're essentially correct that the hint in the docs is intended to get solutions that are "near" (in a sort of Hamming distance sense) the current solution.
If you search the forum (and maybe the sibling general math programming forum), you'll find other posts asking how to enumerate all optimal vertices, and responses that site one or more papers containing algorithms. It's a moderately frequently asked question.
Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)