Turning local(TreeSearch) on results in non-conforming objective function value.

[ahmtsn]

Hello. I have built Cbc (CBC MILP Solver, Version: 2.10.8, Build Date: Jul 8 2022) from source. When I tried Cbc on solving miplib3 problem mkc with different Cbc params, I encountered a strange behaviour. The http://miplib2017.zib.de/instance_details_mkc.html web source provides an optimal objective function value of -563.8460100132 for the problem mkc.

So I did run the problem (solution 1 below) for a while turning off some of the cuts, and obtained a gap in accordance with the optimum value.

Afterwards I tried turning local(TreeSearch) on (still cuts off) (solution 2 below) and as a result I got the wrong objective function value of -541.82600000. I thought it may be related to having 4 threads so I ran again with just 1 thread, but the resulting gap still does not contain the objective function value given above.

Solution 1: Without local(TreeSearch) cbc.exe mkc threads 4 probing off gomory off knapsack off clique off mixed off flow off twomir off solve solu mkcSoln.txt After some time the gap I obtained: Cbc0010I After 4429800 nodes, 11456 on tree, -550.064 best solution, best possible -572.1169

Solution 2: With local(TreeSearch) cbc.exe mkc probing off gomory off knapsack off clique off mixed off flow off twomir off local on thread 4 solve solu mkcSoln2.txt It finds optimal solution value conflicting with the bounds above (and the results from miplib3 results).

Cbc0010I After 142300 nodes, 1 on tree, -541.826 best solution, best possible -541.83 (3522.83 seconds) Cbc0030I Thread 0 used 35962 times, waiting to start 627.66192, 163712 locks, 17.234734 locked, 6.2167914 waiting for locks Cbc0030I Thread 1 used 35839 times, waiting to start 666.93384, 163250 locks, 16.687968 locked, 5.4236195 waiting for locks Cbc0030I Thread 2 used 36037 times, waiting to start 719.55181, 164197 locks, 16.148723 locked, 5.3377047 waiting for locks Cbc0030I Thread 3 used 34471 times, waiting to start 762.40254, 156868 locks, 15.077676 locked, 5.3262887 waiting for locks Cbc0030I Main thread 2828.1079 waiting for threads, 286236 locks, 6.4534926 locked, 10.191869 waiting for locks Cbc0001I Search completed - best objective -541.8259999999996, took 12208720 iterations and 142309 nodes (3524.02 seconds) Cbc0032I Strong branching done 152836 times (2211681 iterations), fathomed 3097 nodes and fixed 5055 variables Cbc0035I Maximum depth 126, 1744757 variables fixed on reduced cost Cuts at root node changed objective from -611.438 to -611.438 ZeroHalf was tried 5 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.043 seconds)

Result - Optimal solution found

Objective value: -541.82600000

I even ran the command with just 1 thread:

cbc.exe mkc probing off gomory off knapsack off clique off mixed off flow off twomir off local on thread 1 solve solu mkcSoln2_t1.txt

Did not wait long enough for the optimal solution, got the following gap:

Cbc0010I After 261600 nodes, 4893 on tree, -540.726 best solution, best possible -542.154

Sincerely.

[jjhforrest]

It does look as if local tree search is broken. In debug mode, I get assert failures on some problems. I have tried some simple fixes, but it may need rethinking.