[Osi] Several integers solutions

[Matthew Saltzman]

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