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

[Kelly, Jeff (ON0F)]

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: address@hidden [mailto:address@hidden On Behalf Of Klas Markström
Sent: Monday, April 11, 2011 1:58 PM
To: address@hidden
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 <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/ 
 ===================================================


_______________________________________________
Help-glpk mailing list
address@hidden
http://lists.gnu.org/mailman/listinfo/help-glpk