Topic
  • 2 replies
  • Latest Post - ‏2012-12-29T13:11:31Z by SystemAdmin
SystemAdmin
SystemAdmin
7929 Posts

Pinned topic Enumerating all optimal solutions

‏2012-12-26T16:48:32Z |
Hello,

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?

Thanks,
Vivek.
Updated on 2012-12-29T13:11:31Z at 2012-12-29T13:11:31Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Enumerating all optimal solutions

    ‏2012-12-27T00:37:05Z  
    At 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.

    Paul

    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)
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Enumerating all optimal solutions

    ‏2012-12-29T13:11:31Z  
    At 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.

    Paul

    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)
    Thanks Paul! That answers

    Vivek.