Hi,

And is there any way to calculate the adjacent extreme points of an optimal solution?

thanks

Hi,

And is there any way to calculate the adjacent extreme points of an optimal solution?

thanks

Hi,

It is certainly possible, but technically quite challenging. One would need to use the low level API (and from Mosel one would need to use a custom dso for that).

Through the API, given an optimal basis for the problem, the API can be used to check if there are any columns outside the current basis with a zero reduced cost that can be brought into the basis. It must be noted that this would only tell you if there are adjacent feasible bases, which in a degenerate situation may describe the same extreme point; in which case it can be really challenging to find an adjacent basis in the geometric sense.

Technically, the reduced costs are provided by XPRSgetlpsol; the columns with a zero reduced cost can be retrieved by XPRSgetcols and the RHS vector by XPRSgetrhs. These can be transformed to the current tableau form by XPRSftran. If the ratio test of the transformed column with the zero reduced costs and the transformed RHS yields a non-degenerate step size, then we have an adjacent extreme point which can be calculated by updating the solution vector with the transformed column times the step size (remembering to update the non-basic variable as well) without carrying out the pivot, so the same solution / transformed RHS can be reused to check the next candidate column.

Hi,

It is certainly possible, but technically quite challenging. One would need to use the low level API (and from Mosel one would need to use a custom dso for that).

Through the API, given an optimal basis for the problem, the API can be used to check if there are any columns outside the current basis with a zero reduced cost that can be brought into the basis. It must be noted that this would only tell you if there are adjacent feasible bases, which in a degenerate situation may describe the same extreme point; in which case it can be really challenging to find an adjacent basis in the geometric sense.

Technically, the reduced costs are provided by XPRSgetlpsol; the columns with a zero reduced cost can be retrieved by XPRSgetcols and the RHS vector by XPRSgetrhs. These can be transformed to the current tableau form by XPRSftran. If the ratio test of the transformed column with the zero reduced costs and the transformed RHS yields a non-degenerate step size, then we have an adjacent extreme point which can be calculated by updating the solution vector with the transformed column times the step size (remembering to update the non-basic variable as well) without carrying out the pivot, so the same solution / transformed RHS can be reused to check the next candidate column.