[Osi] Several integers solutions

[Craig Schmidt]

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.

At best, the solver could remember the integer feasible solutions it  
found during search, but other than the optimal one, these are not  
necessarily good ones.

If you want to enumerate all the integer solutions of a small problem,  
you can stop the solver after the first integer solution is found, and  
then add the integer cut.  Here's an example:

http://www.gams.com/modlib/libhtml/icut.htm

-Craig