How to determine if a LP/MIP solution is unique or if/which other solutions exist?

[Cord Wayne]

Hi everybody,

I know that my question is more of a general nature but I am wondering how I can gain information about the existence of possible other optimal solutions for an LP/MIP. For very simple problems this might be visualized in 2D but as soon as it gets more complex this is not possible anymore.

For LPs I have heard (but not tested) that the use of Polyhedron ((https://en.wikipedia.org/wiki/Polyhedron) libraries can deliver other edges. But how about MIPs? And are there other formal concepts (maybe even implemented in gurobi) which are described in literature?

Any hints are welcome!

Best,
Cord

[Daniel Espinoza]

Hi Cord,

The question for LP's is well understood. Al optimal solutions are in the face induced by fixing the variables with non-zero reduced costs, all feasible solutions within that face are optimal too.

To find them, you could do the fixings and use random objectives over the new polyhedron to find others.

To enumerate all extreme points it gets harder.... as there is no polynomial bound on how many of them there are.... I remember that there is some software that can do that, but I have never tested them so I am not sure how robust they are.

For MIP's it gets a lot harder... but a similar algorithmic approach could be used, meaning restricting the polyhedron to solutions with objective value at least as good as the `optimal` and then finding alternative solutions with another objective (e.g. maximize L1 norm from the previous optimal value), but again, you will either prove that there is no alternative, or get just another one.

A further alternative is provided in gurobi with poolsearchmode=2 parameter, take a look at the documentation for more details on that.

http://www.gurobi.com/documentation/8.0/refman/poolsearchmode.html#parameter:PoolSearchMode

Best,

Daniel

[Cord Wayne]

Hi Daniel,

thanks a lot for your quick response! Note that I am an industrial engineer and my questions might be trivial..

Am Dienstag, 14. August 2018 16:32:40 UTC+2 schrieb Daniel Espinoza:

Hi Cord,

The question for LP's is well understood. Al optimal solutions are in the face induced by fixing the variables with non-zero reduced costs, all feasible solutions within that face are optimal too.

To find them, you could do the fixings and use random objectives over the new polyhedron to find others.

To enumerate all extreme points it gets harder.... as there is no polynomial bound on how many of them there are.... I remember that there is some software that can do that, but I have never tested them so I am not sure how robust they are.

To me, it is not clear why the non-zero reduced costs are fixed. Aren't these to be interpreted as "How much must a coefficient for a related variable in the objective be adapted to make them contribute to the objective (in either direction depending on maximization/minimization)?

Why it is valid to change objectives after fixing the variables? Doesn't this also change the original problem and thus all solutions do not belong to the original problem anymore?

For MIP's it gets a lot harder... but a similar algorithmic approach could be used, meaning restricting the polyhedron to solutions with objective value at least as good as the `optimal` and then finding alternative solutions with another objective (e.g. maximize L1 norm from the previous optimal value), but again, you will either prove that there is no alternative, or get just another one.

Which L1 norm has to be chosen? Could you provide an example or some literature on this method?

A further alternative is provided in gurobi with poolsearchmode=2 parameter, take a look at the documentation for more details on that.

http://www.gurobi.com/documentation/8.0/refman/poolsearchmode.html#parameter:PoolSearchMode

This sounds promising.

Thanks already for your answer although I am still trying to understand the exact approach.

Best,
Cord

Best,

Daniel

[Daniel Espinoza]

Hi Cord,

I'll answer between lines

The question for LP's is well understood. Al optimal solutions are in the face induced by fixing the variables with non-zero reduced costs, all feasible solutions within that face are optimal too.

To find them, you could do the fixings and use random objectives over the new polyhedron to find others.

To enumerate all extreme points it gets harder.... as there is no polynomial bound on how many of them there are.... I remember that there is some software that can do that, but I have never tested them so I am not sure how robust they are.

To me, it is not clear why the non-zero reduced costs are fixed. Aren't these to be interpreted as "How much must a coefficient for a related variable in the objective be adapted to make them contribute to the objective (in either direction depending on maximization/minimization)?

Why it is valid to change objectives after fixing the variables? Doesn't this also change the original problem and thus all solutions do not belong to the original problem anymore?

(optimal) Reduce costs are a proof that your current basic solution is optimal, it basically allows you to re-write your problem as

(P) min k + \bar{c}x

s.t. Ax=b, x>=0

where all \bar{c}_j are >= 0, and the primal solution x^* satisfy that x^*_j == 0, so any other feasible solution will have a larger (or equal) objective value.

Now, using the same observation, any feasible solution with x^*_j == 0 for \bar{c}_j > 0 will have the same objective value as your current basic solution, and thus proving that they are alternative optimal solutions.

 

For MIP's it gets a lot harder... but a similar algorithmic approach could be used, meaning restricting the polyhedron to solutions with objective value at least as good as the `optimal` and then finding alternative solutions with another objective (e.g. maximize L1 norm from the previous optimal value), but again, you will either prove that there is no alternative, or get just another one.

Which L1 norm has to be chosen? Could you provide an example or some literature on this method?

if x^* is your previous optimal solution and c your objective vector, you would modify the MIP by adding the constraint

cx <= cx^*

Now, choosing the objective can be tricky, although maximizing the L1 norm is possible by introducing new variables s_j and z_j and defining

x_j - x^*_j + s_j - z_j = 0

SOS1 s_j z_j

maximize sum(s_j+z_j: j=1..n)

the resulting problem can be quite hard, trying random linear objectives can be effective if you want to find any alternative solution (and assuming there are many), but you have to keep trying until you find one (which might never succeed if your problem does not have alternative optimal solutions).

You can also be `systematic` and try the 2n unitary objective vectors +-e_j but then you have 2n MIPs to solve.

 

A further alternative is provided in gurobi with poolsearchmode=2 parameter, take a look at the documentation for more details on that.

http://www.gurobi.com/documentation/8.0/refman/poolsearchmode.html#parameter:PoolSearchMode

This sounds promising.

Thanks already for your answer although I am still trying to understand the exact approach.

The advantage of this last approach is that you are solving only one MIP, but can be quite expensive, that is the nature of the beast.

Hope it helps,

Best,

Daniel

[Cord Wayne]

Thanks for clarification. I'll look into this more closely with your hints.

Best,
Cord