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?) _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
