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

[Klas Markström]

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 <address@hidden>
> Subject: [Help-glpk] Option to set to generate all solutions
> To: address@hidden
> Message-ID: <address@hidden>
> 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 <address@hidden>
> Subject: Re: [Help-glpk] Option to set to generate all solutions
> To: address@hidden, address@hidden
> Message-ID: <address@hidden>
> 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
>> address@hidden
>> http://lists.gnu.org/mailman/listinfo/help-glpk
> 
> 
> 
> 
> ------------------------------
> 
> Message: 3
> Date: Mon, 11 Apr 2011 19:58:34 +0400
> From: Andrew Makhorin <address@hidden>
> Subject: Re: [Help-glpk] Option to set to generate all solutions
> To: jordan <address@hidden>
> Cc: address@hidden
> Message-ID: <address@hidden>
> 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
> address@hidden
> 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/ 
 ===================================================