[Coin-discuss] OSI branchAndBound vs CBC
Ted Ralphs
ted at lehigh.edu
Mon May 25 02:29:21 EDT 2009
Just to clarify, the existing branchAndBound() method in Osi is
supposed to be playing the role of the solveMilp() method you are
suggesting. The naming of some methods in OSI is a bit opaque because
it has evolved significantly from the use case it was originally
designed for. As I understand it, the original design was made with
the "cut-and-branch" paradigm in mind, whereby you would first process
the root node by iteratively tightening the LP relaxation of a given
MILP using dynamic cut generation, then pass the tightened relaxation
to branchAndBound() for the enumeration. If you look at the way the
methods are named and even the comments in the header file (the
initialSolve() method is still described as being for "solving the
initial LP relaxation"), you will see remnants of this, even though it
is not really how it is used today.
Even today, though, OSI is really designed for solvers like CPLEX that
can solve both LPs and MILPs. For such a solver, the way to invoke the
MILP solution algorithm is with branchAndBound(). Because Cbc and Clp
are thought of as separate solvers within COIN, they have separate Osi
implementations, but perhaps they could be combined in order to
eliminate the need to support the separate implementations and to
bring the whole thing into line with the way other OSI implementations
work. This would involve either invoking Cbc within the OsiClp
branchAndBound() method (at the moment, this invokes a simple branch
and bound method, as originally conceived), or, alternatively, to
invoke Clp (or whatever solver Cbc happens to be using) in OsiCbc when
initialSolver() or resolve() are called (perhaps this is already the
case).
Of course, I'm sure there are issues with doing this. For instance,
this would create a sort of dependence between Cbc and Clp, which
perhaps should not be there, since Cbc can be integrated with LP
solvers other than Clp. It would also mean that using Clp through Osi
could require downloading Cbc as well, but these problems could be
worked around. For example, the configuration for the combined
OsiClp/Cbc could detect whether Cbc was present and automatically
invoke the simple branch and bound instead of Cbc if Cbc was not
present, for example.
It would be ashame if there was no way of invoking Cbc effectively
through Osi, as it is nice to be able to interchange Cbc with other
MILP solvers in the same way as Clp can be interchanged with other LP
solvers. It might also keep the same questions about the differences
between the various ways of invoking Cbc from getting rehashed on
coin-discuss every few months.
Cheers,
Ted
On Mon, May 25, 2009 at 6:02 AM, Matthew Saltzman <mjs at clemson.edu> wrote:
> Matt-
>
> Good thoughts. Could you file tickets so I don't lose these ideas?
>
> Thanks.
>
> Matt
>
>
> On Sat, 2009-05-23 at 19:45 -0400, Matthew Galati wrote:
>> Thanks All.
>>
>> This
>> const char *args[] = {"Cbc_Test", "-solve", "-quit"};
>> CbcModel model(*solver.getRealSolverPtr());
>> CbcMain0(model);
>> CbcMain1(3, args, model);
>>
>> seems to work much better than OsiCbc::branchAndBound( ) !
>>
>> This is a very odd construction. Maybe I asked this before, but why
>> don't we just have a CbcModel::model.solve( ) method? Why is there not
>> some simple API like this for solving a MILP with CBC?
>>
>> Moreover - for OSI users, why don't we have an OsiCbc::solveMilp( )
>> method? The base class can have solveMilp( ) virtual and for those
>> OsiXxx's that can solve MILPs (OsiCpx, OsiXpr, OsiCbc, ...), it gets
>> derived, else it returns an error. I understand the reluctance to add
>> MILP support in OSI when OSI2 was being discussed -- but that was many
>> years ago. As an "interim" fix, can we at least make OSI work for
>> MILPs - since many people are already using them to define and (try
>> to) solve MILPs.
>>
>> Thanks,
>> Matt
>>
>>
>>
>>
>> Hi,
>>
>> > I have a similar problem, which you helped me with
>> previously:
>> >
>> http://list.coin-or.org/pipermail/cbc/2008-February/thread.html#99
>> >
>> > Just a quick summary: I have a model in OSI and need to get
>> solution
>> > there as well:
>> > OsiCbcSolverInterface solver;
>>
>>
>> Better use "OsiClpSolverInterface solver;" here.
>> I think Cbc do some special stuff if the instance comes as an
>> OsiClp object.
>>
>> > const char *args[] = {"Cbc_Test", "-solve", "-quit"};
>> >
>> > One option is to create a new CbcModel and solve it:
>> > CbcModel model(*solver.getRealSolverPtr());
>> > CbcMain0(model);
>> > CbcMain1(3, args, model);
>> > This works fine, but how do I get copy the solution to the
>> OSI object?
>> > (I tried solver->getModelPtr()->setBestSolution and
>> > solver->getModelPtr()->setObjValue, using the values from
>> model, but it
>> > does not work - it does not update the "best possible
>> solution", so even
>> > if solver knows about the optimal solution, it does not know
>> it is
>> > optimal..)
>>
>>
>> CbcModel creates a copy of the Osi interface that you give to
>> it and
>> works on this one. So maybe using the OsiSolverInterface* from
>> model.solver() will work?
>> Or you fix integer variables to the solution in your Osi, try
>> to copy
>> the basis from model.solver() as well, and do a resolve() in
>> your Osi.
>>
>> > The other option is to work directly on the CbcModel of the
>> OSI object:
>> > CbcMain0(*solver.getModelPtr());
>> > CbcMain1(3, args, *solver.getModelPtr());
>> > In works fine in the sense that solver now has the optimal
>> solution (and
>> > knows it is optimal).
>> > The problem with this version is that the CbcMain1 function
>> takes more
>> > than 3 times longer and in the first option - any idea why
>> and how to
>> > fix it?
>>
>>
>> Maybe the way the CbcModel is setup in OsiCbc is different.
>>
>> Stefan
>>
>> --
>> Stefan Vigerske
>> Humboldt University Berlin, Numerical Mathematics
>> http://www.math.hu-berlin.de/~stefan
>>
>>
>>
>> _______________________________________________
>> Coin-discuss mailing list
>> Coin-discuss at list.coin-or.org
>> http://list.coin-or.org/mailman/listinfo/coin-discuss
>>
>>
>> _______________________________________________
>> Coin-discuss mailing list
>> Coin-discuss at list.coin-or.org
>> http://list.coin-or.org/mailman/listinfo/coin-discuss
> --
> Matthew Saltzman
>
> Clemson University Math Sciences
> mjs AT clemson DOT edu
> http://www.math.clemson.edu/~mjs
>
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-discuss
>
--
Dr. Ted Ralphs
Associate Professor, Lehigh University (permanent)
Visiting Professor, University of Newcastle (current)
(610) 628-1280
ted 'at' lehigh 'dot' edu
coral.ie.lehigh.edu/~ted
Sent from Newcastle, Nsw, Australia
More information about the Coin-discuss
mailing list