[Cbc] Unusually slow time taken at a node of branch-and-bound tree

[John Forrest]

Aleksandr,

In this problem, during normal solves the code is spending too much time 
before declaring a branch to be infeasible - I may try and see if I can 
improve.

However this error is to do with strong branching.  Then the code is 
trying to be as fast as possible and may miss some checks. This does not 
matter too much as it will just declare that tentative branch to be 
unfinished.  This is because it is only doing a hundred  or so 
iterations.  This maximum number of iterations
is preset to a high value, but the standalone solver and other 
implementations reduce this to a reasonable value by

         solver->setIntParam(OsiMaxNumIterationHotStart, 100);

I will look into why a strong branch "looped" - and did 9999999 
iterations!  For now use above setting or similar.

John Forrest
On 09/12/17 23:12, Aleksandr M. Kazachkov wrote:
> Hello all,
>
> On my computer, Cbc-2.9 (latest stable, compiled with lapack, blas, 
> and enable_debug on) takes an unusually long time (~15 minutes) on a 
> particular node of the branch-and-bound tree for a version of the 
> instance pigeon-13 from MIPLIB (after applying some preprocessing to 
> it). The instance is here:
>
> https://drive.google.com/file/d/17CWEN1A5ZefhAEZsUwnU1gJl_EPM9d5b/view?usp=sharing 
> <https://urldefense.proofpoint.com/v2/url?u=https-3A__drive.google.com_file_d_17CWEN1A5ZefhAEZsUwnU1gJl-5FEPM9d5b_view-3Fusp-3Dsharing&d=DwMFaQ&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=js2M0T-3OIMIVDvokcKjokJbk0F8QOCd0mT4FsVFE88&m=4sql7feDwXVnADRe81wH9Kinl4oVnVLekMxeZUOQrx8&s=4kM-ZvXu57rNQKxU50jfoQ66IprD2kkjH0k3oyZALY8&e=>
>
> I am reporting this in case the behavior is the result of a bug, 
> though it may simply be a case in which I should be using different 
> settings. On my system, the following lines of code reproduce the 
> behavior:
>
> OsiClpSolverInterface* solver = new OsiClpSolverInterface;
> solver->readMps("pigeon-13_presolved.mps.gz");
> CbcModel* cbc_model = new CbcModel;
> cbc_model->swapSolver(solver);
> cbc_model->setModelOwnsSolver(true); // solver will be deleted with 
> cbc object
> cbc_model->setLogLevel(3);
> cbc_model->messagesPointer()->setDetailMessages(10, 10000, (int *) NULL);
> cbc_model->setPrintFrequency(1);
> cbc_model->setMaximumNodes(656); // at least on my system, this will 
> show the slow node
> cbc_model->branchAndBound(3);
>
> As indicated in the log (excerpt below), Cbc stalls for quite a while 
> after 654 nodes.
>
> Cbc0010I After 654 nodes, 44 on tree, 1e+50 best solution, best 
> possible -13000 (84.18 seconds)
> Clp0006I 0 Obj -13000 Primal inf 0.1871137 (1)
> Clp0006I 2 Obj -13000
> Clp0000I Optimal - objective value -13000
> ---- long stall here ---
> Cbc0007I Strong branching on 145 (184), down 0 (20) up 6.4595608e+14 
> (19) value 0.5
> Cbc0007I Strong branching on 179 (218), down 3.6850268e+13 (12) up 0 
> (20) value 0.5
> Node 655 depth 45 unsatisfied 22 sum 1.40366e+15 obj -13000 guess 
> -12708 branching on 184
> Cbc0015I Node 655 Obj -13000 Unsat 22 depth 45
> Cbc0010I After 655 nodes, 44 on tree, 1e+50 best solution, best 
> possible -13000 (1015.90 seconds)
> Clp0006I 0 Obj -13000 Primal inf 0.10206197 (1)
> Clp0006I 5 Obj -13000
> Clp0000I Optimal - objective value -13000
>
> If there is any other information that would be helpful that I can 
> provide, please let me know,
> Aleksandr Kazachkov
>
>
> _______________________________________________
> Cbc mailing list
> Cbc at list.coin-or.org
> https://urldefense.proofpoint.com/v2/url?u=https-3A__list.coin-2Dor.org_mailman_listinfo_cbc&d=DwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=js2M0T-3OIMIVDvokcKjokJbk0F8QOCd0mT4FsVFE88&m=4sql7feDwXVnADRe81wH9Kinl4oVnVLekMxeZUOQrx8&s=UN254OH8oZgIzzyFz8os_qvVyFq4ov7dGCJyt4e1j1c&e=


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20171210/429f5e86/attachment.html>