[Coin-bcpdiscuss] Performance

[Laszlo Ladanyi]

As much as I like BCP and praise its power :-), it is NOT efficient as a
general purpose MIP solver. It is a framework that allows you to substitute
your own routines for many steps of the whole B&C procedure, which can lead to
significant gains *if* you have specific knowledge of your problem and you can
exploit it. If you don't have such knowledge I can very well believe that you
get very bad performance, especially on smaller problems, where solving LPs
does not dominate the solution times (the harder the LPs are the more
irrelevant the data copying time becomes). Since you've been using OSL before,
I suppose you want to use a black-box solver, in which case you'd be much
better off using CBC (Coin Branch-and-Cut). CBS can also use any LP solver
that has an OSI interface.

Hope this helps,
--Laci

On Mon, 12 Dec 2005 acw at ascent.com wrote:

> We are in the process of migrating from OSL to COIN/Bcp.  Mostly the 
> process has gone quite well, but recently I received quite a shock 
> concerning performance.
> 
> I have a MIP problem which OSL completes in about 25 seconds; the same 
> problem takes COIN/Bcp about 290 seconds.  This is more than an order of 
> magnitude discrepancy, which would be unacceptable on some of our larger 
> problems.
> 
> I can think of several possible explanations.
> 
> We are using the BranchAndCut example almost unchanged; the only 
> modifications we have made were to interface the code to our LP server. 
> Perhaps BranchAndCut uses cut generation and variable selection that is 
> only appropriate to small problems, and we have to do more research to 
> figure out how to guide the branching process.  Maybe it's as simple as 
> selecting the right values for the branching control parameters.
> 
> Perhaps the main time-sink is communication between the TM and LP modules. 
>  BranchAndCut uses the "BCP_message_single" communications protocol, which 
> has to pack and unpack every LP problem and solution.  Doubtless this 
> could be streamlined, but we don't want to open that can of worms unless 
> the potential gain is great (like a factor of 3 or more).
> 
> And of course there is the possibility that we are doing something else 
> completely stupid that we're not even aware of.
> 
> So I'm appealing to the community.  What experiences have you had 
> regarding performance?  What approaches have worked?  What stupid mistakes 
> should we be careful to avoid?
> 
> If there is interest, I can post an MPS file containing the test problem 
> in question.
> 
> Thanks in advance.