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. Best regards Klas > ---------------------------------------------------------------------- > > Message: 1 > Date: Mon, 11 Apr 2011 09:36:25 +0200 > From: jordan <[email protected]> > Subject: [Help-glpk] Option to set to generate all solutions > To: [email protected] > Message-ID: <[email protected]> > Content-Type: text/plain; charset="UTF-8" > > Hi, > I'm actually using GLPK and I want to know if it is possible to set an > option in the source code for the C API, or in the file for a GMPL file, > in order to say "I want all the solutions". > I heard about re-lunch the programm with adding a constraint which is > the last solution, but I don't think it's a good thing. > Does somebody have the answer ? > > PS : Sorry for English, I'm a french student. > > > > > ------------------------------ > > Message: 2 > Date: Mon, 11 Apr 2011 11:17:35 +0200 > From: Oscar Gustafsson <[email protected]> > Subject: Re: [Help-glpk] Option to set to generate all solutions > To: [email protected], [email protected] > Message-ID: <[email protected]> > Content-Type: text/plain; charset=UTF-8; format=flowed > > Hi Jordan, > > no there is no such feature currently in GLPK (that's why you hear about > multiple runs with additional constraints). > > ( With SCIP you can do that though: > http://scip.zib.de/doc/html/COUNTER.html ) > > Regards > > Oscar > > On 04/11/2011 09:36 AM, jordan wrote: >> Hi, >> I'm actually using GLPK and I want to know if it is possible to set an >> option in the source code for the C API, or in the file for a GMPL file, >> in order to say "I want all the solutions". >> I heard about re-lunch the programm with adding a constraint which is >> the last solution, but I don't think it's a good thing. >> Does somebody have the answer ? >> >> PS : Sorry for English, I'm a french student. >> >> >> _______________________________________________ >> Help-glpk mailing list >> [email protected] >> http://lists.gnu.org/mailman/listinfo/help-glpk > > > > > ------------------------------ > > Message: 3 > Date: Mon, 11 Apr 2011 19:58:34 +0400 > From: Andrew Makhorin <[email protected]> > Subject: Re: [Help-glpk] Option to set to generate all solutions > To: jordan <[email protected]> > Cc: [email protected] > Message-ID: <1302537514.2946.20.camel@corvax> > Content-Type: text/plain > >> I'm actually using GLPK and I want to know if it is possible to set an >> option in the source code for the C API, or in the file for a GMPL file, >> in order to say "I want all the solutions". >> I heard about re-lunch the programm with adding a constraint which is >> the last solution, but I don't think it's a good thing. >> Does somebody have the answer ? > > Such feature is not implemented mainly because there may be > exponentially many basic solutions. Besides, unlike LP case, it would be > quite difficult to enumerate all integer feasible/optimal solutions. > > Nevertheless, imagine that you have obtained all the feasible or optimal > solutions. In which way would you use them? > > > > > ------------------------------ > > _______________________________________________ > Help-glpk mailing list > [email protected] > http://lists.gnu.org/mailman/listinfo/help-glpk > > > End of Help-glpk Digest, Vol 101, Issue 12 > ****************************************** =================================================== Klas Markström Docent, Mathematics Biträdande prefekt, Vice head of department Department of Mathematics and Mathematical Statistics Umeå universitet S-901 87 Umea, Sweden phone: (+46)90 786 97 21 fax: (+46)90 786 52 22 URL: http://abel.math.umu.se/~klasm/ =================================================== _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
