[Osi] Several integers solutions

[Nathann Cohen]

Oops, sorry... Gmail changed it for no good reason and without the slightest
warning ;-)

I'll be writing to the Cbc list then !

Thank you ! ;-)

Nathann

2009/8/2 Matthew Saltzman <mjs at clemson.edu>

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