[Coin-discuss] Finding all solutions to IP

[John J Forrest]

Martin,

acronyms - SOS - Special Ordered Sets.  Set of variables with some order
where for a valid solution only one variable can be nonzero OR (if SOS type
2) two variables where the two are adjacent in order.
OA - Outer Approximation.  Technique used in Mixed Integer Non Linear
Programming.

If your IP is binary with coefficients which can be made integer then opbdp
(Just use to search on web) does efficient implicit enumeration.  To get
all solutions then one line has to be modified - see OsiOpbdpSolve.hpp.
That is probably code you were thinking of.

John Forrest


                                                                           
             Martin von Gagern                                             
             <Martin.vGagern at g                                             
             mx.net>                                                    To 
             Sent by:                  coin-discuss at list.coin-or.org       
             coin-discuss-boun                                          cc 
             ces at list.coin-or.                                             
             org                                                   Subject 
                                       [Coin-discuss] Finding all          
                                       solutions to IP                     
             05/08/07 07:23 AM                                             
                                                                           
                                                                           
             Please respond to                                             
             Discussions about                                             
                open source                                                
               software for                                                
                Operations                                                 
                 Research                                                  
             <coin-discuss at lis                                             
              t.coin-or.org>                                               
                                                                           
                                                                           




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

_______________________________________________
Coin-discuss mailing list
Coin-discuss at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/coin-discuss