In the planning and scheduling software I developed for the continuous, batch and dimensional process industries, I retain all of the integer-feasible (logistics) solutions found during one pass of the branch-and-cut search only i.e., no incumbent elimination by adding exclusion cuts. This "solution pool" is then passed on to another optimization (NLP) to solve for the quality details of the manufacturing by enumerating and solving each logistics or integer-feasible solution in an NLP with all binary variables are fixed (what I call a phenomenological decomposition).
Therefore, with callbacks in GLPK you can grap each integer-feasible solution when it is found and then you can save it to a media of your choice. And, if you require to find more of them then add exclusion or local search cuts to continuously search and hopefully find or *mine* more I-F solutions but I don't think it is realistic to have GLPK have a feature to find *all* of them. I think there are other features in GLPK that should be added first. Jeff -----Original Message----- From: [email protected] [mailto:[email protected]] On Behalf Of Klas Markström Sent: Monday, April 11, 2011 1:58 PM To: [email protected] Subject: Re: [Help-glpk] Option to set to generate all solutions 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 _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
