[Osi] Several integers solutions

Matthew Saltzman mjs at clemson.edu
Sun Aug 2 11:36:02 EDT 2009


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
>         
>         
>         _______________________________________________
>         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




More information about the Osi mailing list