Oops, sorry... Gmail changed it for no good reason and without the slightest warning ;-)<br><br>I'll be writing to the Cbc list then ! <br><br>Thank you ! ;-)<br><br>Nathann<br><br><div class="gmail_quote">2009/8/2 Matthew Saltzman <span dir="ltr"><<a href="mailto:mjs@clemson.edu">mjs@clemson.edu</a>></span><br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="im">On Sun, 2009-08-02 at 13:24 +0200, Nathann Cohen wrote:<br>
> I was indeed interested by enumerating all the *optimal* solutions to<br>
> a problem.. But is there a "clean" way to change the large inequality<br>
> tp a strict inequality, perhaps by changing a parameter of the model<br>
> object ( I'm afraid I may be dreaming ;-) ), or am I bound to modify<br>
> CBC's original source code ?<br>
<br>
</div>I'm not sure (not familiar with CBC internals), but I suspect you'll<br>
need to touch the code. I don't think it should be hard, though.<br>
<div class="im"><br>
<br>
><br>
> It does not seem too complicated for someone knowing beforehand how<br>
> CBC works, perhaps my best bet is to ask for a new feature in CBC --<br>
> namely the enumeration of all the integer solution.. ;-)<br>
<br>
</div>You'll want to raise that issue on the Cbc list.<br>
<br>
BTW, you sent your message from an account that wasn't subscribed to the<br>
list, so it bounced. Your subscription address is your inrea one.<br>
<div><div></div><div class="h5"><br>
><br>
> Thank you again !<br>
><br>
> Nathann<br>
><br>
> 2009/8/2 Matthew Saltzman <<a href="mailto:mjs@clemson.edu">mjs@clemson.edu</a>><br>
><br>
> On Fri, 2009-07-31 at 21:16 +0200, Stefan Vigerske wrote:<br>
> > Hi,<br>
> ><br>
> > Craig Schmidt wrote:<br>
> > > On Jul 31, 2009, at 1:46 PM, Nathann Cohen wrote:<br>
> > ><br>
> > >> Don't you think there may be some special way to do it<br>
> with Cbc,<br>
> > >> though ? It seems a huge waste to begin again the<br>
> computations from<br>
> > >> scratch, or just to modify the problem when all the<br>
> necessary<br>
> > >> informations to enumerate the solutions seems to be<br>
> available to the<br>
> > >> solver :-/<br>
> > >><br>
> > >> Thanks for you help, though ! ;-)<br>
> > >><br>
> > >> Nathann<br>
> > ><br>
> > > Nathann,<br>
> > ><br>
> > > Integer cuts are the only way to go.<br>
> > ><br>
> > > Unfortunately, any branch and bound based solver doesn't<br>
> have the<br>
> > > necessary information to find next-best solutions. If you<br>
> think about<br>
> > > how the "bound" part of the algorithm works, so can see<br>
> why. Once an<br>
> > > integer feasible solution is found, it uses that as a<br>
> bound to exclude<br>
> > > subproblems which cannot contain the optimal solution.<br>
> The second<br>
> > > best solution could be contained in any of the excluded<br>
> parts of the<br>
> > > search tree, which it never examined.<br>
> ><br>
> > Thus, one way could be to let the solver explore the search<br>
> tree further<br>
> > down even when it found a integer feasible solution. Thus<br>
> pruning using<br>
> > such a solution would have to be disabled, maybe just by<br>
> declaring an<br>
> > integer feasible solutions as infeasible if not all integers<br>
> are fixed.<br>
> > I'm not sure, but shouldn't it be possible to implement this<br>
> using<br>
> > CbcObject's?<br>
><br>
><br>
> If you just want all *optimal* integer solutions, you can<br>
> modify the<br>
> bounding procedure in CBC to require that a lower bound<br>
> strictly exceed<br>
> the incumbent value, rather than just matching it (assuming<br>
> minimization) before the node is fathomed. Then the search<br>
> would<br>
> continue for subtrees that could contain a solution with value<br>
> equal to<br>
> the incumbent.<br>
><br>
> I suppose the bound could be adjusted to find all integer<br>
> solutions<br>
> within some delta from the incumbent value, but that would<br>
> require<br>
> managing the list of incumbents found so far, and it doesn't<br>
> guarantee<br>
> any particular number of solutions or whether they are<br>
> generated in<br>
> order by objective value.<br>
><br>
> Generating the K best solutions in order by value could be<br>
> done with a<br>
> "meta" branch and bound procedure that branches on cuts like<br>
> those<br>
> described in earlier replies, but that's not in CBC at this<br>
> point, and<br>
> would require some serious work.<br>
><br>
> ><br>
> > CPLEX offers such a feature under the name solution pool.<br>
> > And for the sake of citing the gams modlib again:<br>
> > <a href="http://www.gams.com/modlib/libhtml/solnpool.htm" target="_blank">http://www.gams.com/modlib/libhtml/solnpool.htm</a><br>
> > Also SCIP has such a feature<br>
> (<a href="http://opus.kobv.de/zib/volltexte/2008/1092" target="_blank">http://opus.kobv.de/zib/volltexte/2008/1092</a>).<br>
> ><br>
> > Best,<br>
> > Stefan<br>
> ><br>
> --<br>
><br>
> Matthew Saltzman<br>
><br>
> Clemson University Math Sciences<br>
> mjs AT clemson DOT edu<br>
> <a href="http://www.math.clemson.edu/%7Emjs" target="_blank">http://www.math.clemson.edu/~mjs</a><br>
><br>
><br>
> _______________________________________________<br>
> Osi mailing list<br>
> <a href="mailto:Osi@list.coin-or.org">Osi@list.coin-or.org</a><br>
> <a href="http://list.coin-or.org/mailman/listinfo/osi" target="_blank">http://list.coin-or.org/mailman/listinfo/osi</a><br>
><br>
><br>
</div></div>--<br>
<div><div></div><div class="h5"> Matthew Saltzman<br>
<br>
Clemson University Math Sciences<br>
mjs AT clemson DOT edu<br>
<a href="http://www.math.clemson.edu/%7Emjs" target="_blank">http://www.math.clemson.edu/~mjs</a><br>
</div></div></blockquote></div><br>