Originally posted by: EXCT_RALF_GOLLMER

Hi all,

just encountered a strange log during the tune tool (default settings part) - a node objective is displayed being bigger than the incumbent's value (see node 4000 in the snippet):

Found incumbent value 1786982.780705 after 208.12 sec. (2370751.95 ticks)
   2000   513  1786761.6131    64  1786982.7807  1786390.2518   139023    0.03%
*  3389+ 1891                      1786826.1603  1786391.7622             0.02%
Found incumbent of value 1786826.160289 after 264.00 sec. (2380859.35 ticks)
*  3636+ 1807                      1786816.9656  1786391.7622             0.02%
Found incumbent of value 1786816.965592 after 273.30 sec. (2382502.60 ticks)
*  3959+ 2050                      1786622.6812  1786391.7622             0.01%
Found incumbent of value 1786622.681222 after 283.66 sec. (2384339.72 ticks)
   4000  2155  1786713.5102    11  1786622.6812  1786391.7622   200268    0.01%
   6000  2805  1786499.4482    46  1786622.6812  1786396.5127   254077    0.01%
   8000  4686  1786426.1889    98  1786622.6812  1786397.3927   301875    0.01%
  10000  6842  1786400.3166   132  1786622.6812  1786398.0282   359831    0.01%

Why isn't a 'cutoff' in that line? Is the displayed objective value not really the relaxation objective? Or was the incumbent value updated after deciding about the cutoff in that thread?

There is another part in that log quite hard to understand:

                                                      Cuts: 4                  
Found incumbent of value 2193393.814966 after 1318.10 sec. (1694736.22 ticks)
* 29075+18762                      2193393.5018  2193087.6020             0.01%
Found incumbent of value 2193393.501783 after 1334.22 sec. (1699734.75 ticks)
  30000 19365  2193306.0441    33  2193393.5018  2193087.6020  1075770    0.01%
  32000  1197  2193139.8297   115  2193393.5018  2193095.7843  1153212    0.01%
                                                      Cuts: 6                  
* 32142+ 1253                      2193384.9733  2193097.9495             0.01%

From node 30000 to node 32000, i.e. within 2000 nodes, the number of nodes is reduced by more than 18000 without a new incumbent. No idea how that can be done without evaluating that many nodes.

Is this a restart in the b&c? But maybe this is just due to the next incumbent being found by one of the threads before printing that line of output, while the new incumbent's node gets no. 32142 and is displayed only later.

Best regards

Ralf Gollmer

Originally posted by: EdKlotz

Regarding the lack of cutoff for the node LP at node 4000, it  looks like this is simply the way
the node logger handles a multithreaded run in parallel det. MIP.   Specifically,
note that the incumbent was found only a few nodes before 4000:

> *  3636+ 1807                      1786816.9656  1786391.7622          0.02%
> Found incumbent of value 1786816.965592 after 273.30 sec. (2382502.60 ticks)
> *  3959+ 2050                      1786622.6812  1786391.7622          0.01%
> Found incumbent of value 1786622.681222 after 283.66 sec. (2384339.72 ticks)
>    4000  2155  1786713.5102    11  1786622.6812  1786391.7622   

The log indicates a 4 thread deterministic run, and we could have found the new incumbent at node
3959 on say thread 4 while the node that ultimately is listed as 4000 was on thread 1.
If the logger then prints out nodes at the next synch. point in ascending order of threads,
we could get the output above.

   Regarding the unexpected drop of 18000 actives nodes in the space of 2000 nodes being processed,
if you use dynamic search (as you did in this run), you may see node logs that differ from what
you would expect to see with traditional branch and cut.   This can happen with the list of
active nodes, as well as the dual bounds and other MIP output.

Originally posted by: EXCT_RALF_GOLLMER

Dear Ed,

many thanks for your answer.

I already thought the missing cutoff is a consequence of the parallel run. I'm sure that node is deleted with the next synchronisation. Just I was curious that it was not done when preparing the oputput line by the node logger.

Regarding dynamic search - this is quite hard to understand for soneone trained in mathemtical optimization outside of IBM, since no hint of a decription is given (even the principle of the algorithm being regarded as a trade secret) - with normal B&C such a drop in the number would be impossible without a new incumbent.

As there are other things which are due to a bug (return code 1217 when using local branching in 12.8.0 or false optimality diagnostics when using repeat presolve 3) that drop in the number of nodes made me think of another problem in CPLEX.

Best regards

Ralf

Originally posted by: EdKlotz

Ralf,

        Yes, I understand your concerns regarding dynamic search and the node log, and maybe at some point our position will change.   But, until then, one thing you can do if you see some node log output that contradicts your B&C training is to run the same model with traditional B&C.   Admittedly, the path will change, so the disappearance of any contradictory node log output does not prove that the "impossible" behavior was due to dynamic search.   But if the "impossible" behavior persists with traditional B&C, then you have found something worth a closer look.

        Furthermore, for the situation in this thread, the main concern about a reduction in the active node list that exceeds the number of nodes processed, the main concern is that nodes are being improperly pruned, and optimal solutions lost.    So if you can run traditional B&C to optimality, you can then confirm that the objectives with traditional B&C and dynamic search are the same.   Again, this is not a proof that all is well given the possibility of multiple alternate optima, but it adds evidence that the unexpected node log output is reasonable for dynamic search.

Ed