[Coin-discuss] Finding all solutions to IP

[Martin von Gagern]

Hello!

Trying to avoid reinventing the wheel, I want to know if there is some
efficient way to enumerate all MIP-feasible solutions of an IP, i.e. all
lattice points inside a finite simplex, building on COIN-OR components.

I would think Cbc best suited for this. Here is what I found so far:

The sudoku.cpp example suggests model.setCutoffIncrement(-1.0e6); to
find all solutions, but I understand neither how this works nor how I
could get at those solutions. Is there any more documentation on this?

I believe there was an example somewhere that claimed to find all
solutions to some binary problem, but it had to modify some part of Cbc
itself in what seemed a strange way to me, and right now I can't find
that example any more.

repeat.cpp is easily adapted to find all solutions. However it does so
by adding a cut only after branchAndBound returns, which is when the
tree has already been emptied. Seems like redoing a lot of work. I
believe that it should be enough to loop over a single leaf of the
branch tree, recording solutions and cutting them away until the leaf
becomes infeasible. I can't get the same solution again in another
branch, so I won't need any additional cuts there.

Looking at the CbcModel::branchAndBound code, I noted a method called
OsiBabSolver::solutionAddsCuts that sounds interesting. After all, I
want to add a cut whenever I find a solution. However I could not find
any class using this in the whole Cbc + externals svn tree. So I'm not
even sure this has ever been tested. Would this be the way to go?

Can anyone point me to an example or document about how to do this?
Or give me some hints how best to plug my ideas into the Framework?

Oh yes, and I would be grateful if someone could expand these acronyms:
SOS as in CbcModel::resetToReferenceSolver "SOS will have to be redone"
OA as in CbcModel::branchAndBound source comments about "OA based bab"

Thanks in advance,
 Martin