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

[Jordan Atlas]

Hi Sebastian,

   Thank you for your suggestion.  I like it a lot.  I'm working with a 
MIP that has all the variables constrained to being integers >= 0.  Can 
you suggest a cut that might work for this sort of problem?  One 
analogous to the one you suggested doesn't seem to work because it can 
eliminate valid solutions --> I'm having trouble thinking of a way to 
eliminate only the single solution point.

Thanks,

--Jordan

Sebastian Pokutta wrote:

> 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.