Re: [Help-glpk] Option to set to generate all solutions

[Andrew Makhorin]

On Mon, 2011-04-11 at 19:58 +0200, Klas Markström wrote:
> Adding the ability to find all optimal solutions to an IP would be much
>  wanted improvement to glpk.  
> 
> It is true that their may be exponentially many solutions to an IP, but
>  it is also true that the worst time complexity of all analyzed
>  versions of the simplex algorithm have exponential or close to
>  exponential running times. However for typical LP this is not the
>  case, so it is meaningful to implement simplex methods. In much the
>  same way there a many IPs which have only a moderate number of
>  solutions, and I believe a random IP will actually have a unique
>  solution.
> 
> I have generated all solutions to many IPs in my own research by doing
>  an iterative solution procedure, adding new constraints which exclude
>  the old solutions and solving again until all solutions have been
>  found.   In my case each solution gives an experimental design and the
>  designs can be further analyzed in terms of properties which cannot be
>  formulated as MIPs. So having the full set of optimal solutions is
>  very useful.
> 
> Of course there are other development work which might have higher
>  priority for glpk, but in principle I don't think there are any strong
>  arguments against this feature.
> 

In principle, I agree with you. However, I think that a more correct way
would be modeling additional properties within mip. Could you give an
example of a property which cannot be modeled? If you are able to choose
a "best" solution among optimal solutions algorithmically, I belive that
it is always possible to model that with binary variables, at least, in
principle. (Can't any Turing machine be modeled as mip?)