Re: [Help-glpk] problems with multiple solutions in glpk

[Sebastian Pokutta]

Hey Jordan,

IF you have a 0-1 program you can try to cut off the solution (point)  
as follows to check the presence of other solutions with same cost.

Say the solution is x and let I be the support of x, i.e. x_i = 1 iff  
i \in I and let J be the zero-support, i.e. x_i = 0 iff i \in J. Note  
that I \cup J \subseteq [n] where n is the dimension but  equality  
does not necessarily hold as we have a mixed-0-1-program. Now you can  
add the cut
\sum_{i in I} (1-x_i) + \sum_{i ?in J} x_i >= 1/2 to cut-off exactly  
that solution. All other valid solutions y will "survive" because  
there is at least one coordinate y_i \neq x_i. Hence, if i \in I then  
x_i = 1 and so y_i = 0 and the sum above is >= 1/2. Similar holds if i  
\in J.

Now you can re-optimize with this cut added and if you obtain a valid  
solution with the same solution value then there are more than one  
solution. You could (theoretically - it is rather impraticable though)  
even enumerate the solution with same cost using this "trick".

For general mixed-integer program the same procedure works as well,  
though you have to find a cut that cuts-off your solution which might  
be a bit harder in this case.

--Sebastian



On 05.01.2008, at 20:06, Jordan Atlas wrote:

> Hello,
>
>   Can GLPK detect the presence of multiple (same cost) solutions in  
> a Mixed Integer Programming (MIP) problem?  If so, can it find those  
> solutions, up to some limit on the number of solutions?
>
> Thank you,
>
> --Jordan
>
>
>
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/help-glpk