[Osi] Several integers solutions
Nathann Cohen
nathann.cohen at sophia.inria.fr
Sun Aug 2 11:43:59 EDT 2009
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>
More information about the Osi
mailing list