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

[John Forrest]

Looking more closely -

a) takes more time to declare normal branch infeasible.  This is because 
normally code has tightened bounds.  In this case some variables were at 
"fake" bounds, which had to be slowly made genuine.  It will be asy to 
add a little bit of code in the next day or so.

b) strong branching problems were because of lack of accuracy in dual 
values.  I will just exit from strong branching if I find lack of accuracy.

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/1040e999/attachment-0001.html>