[Osi] Several integers solutions

[Stefan Vigerske]

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?

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

-- 
Stefan Vigerske
Humboldt University Berlin, Numerical Mathematics
http://www.math.hu-berlin.de/~stefan