[SCIP] root node dual bound != LP relaxation value

[Marco Lübbecke]

Wisdom of the crowd:

I use SCIP 6.0.1 to compute the root node dual bound of a MILP (say,
miplib2010/mine-166-5.mps.gz), without any cuts added, so I

set separating emphasis off
set limits nodes 1

To be on the safe side, I also disable conflict analysis, however, I don't
know whether this is necessary

set conflict enable FALSE

I expected that this would solve me the LP relaxation of the presolved
instance, which is not true.


 time | node  | left  |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols
|rows |cuts |confs|strbr|  dualbound   | primalbound  |  gap
V 1.0s|     1 |     0 |     0 |     - |  40M|   0 |   - | 712 |6725 | 712
|6725 |   0 |   0 |   0 |-1.008549e+09 |-1.691274e+08 | 496.33%
  1.2s|     1 |     0 |  1839 |     - |  40M|   0 | 481 | 712 |5947 | 712
|6725 |   0 |   0 |   0 |-7.233357e+08 |-1.691274e+08 | 327.69%
u 1.5s|     1 |     0 |  4840 |     - |  40M|   0 |   - | 712 |5947 | 712
|6725 |   0 |   0 |   0 |-7.233357e+08 |-4.463478e+08 |  62.06%
  1.7s|     1 |     0 |  8009 |     - |  41M|   0 | 480 | 712 |5502 | 712
|6725 |   0 |   0 |   0 |-7.233034e+08 |-4.463478e+08 |  62.05%
  2.8s|     1 |     0 |  8009 |     - |  41M|   0 |   - | 712 |5502 | 712
|6725 |   0 |   0 |  24 |-6.589159e+08 |-4.463478e+08 |  47.62%


I realize that, even though there will not be any branching, branching
appears to be "prepared" already and the information gathered from the
strong branching LPs is used in the dual bound computation. So I

set branching random priority 100000000

My personal opinion is that the choice of branching rule should *not*
influence the root node dual bound, but it does:

 time | node  | left  |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols
|rows |cuts |confs|strbr|  dualbound   | primalbound  |  gap
V 1.1s|     1 |     0 |     0 |     - |  39M|   0 |   - | 712 |6725 | 712
|6725 |   0 |   0 |   0 |-1.008549e+09 |-1.691274e+08 | 496.33%
  1.2s|     1 |     0 |  1839 |     - |  39M|   0 | 481 | 712 |5947 | 712
|6725 |   0 |   0 |   0 |-7.233357e+08 |-1.691274e+08 | 327.69%
u 1.5s|     1 |     0 |  4840 |     - |  39M|   0 |   - | 712 |5947 | 712
|6725 |   0 |   0 |   0 |-7.233357e+08 |-4.463478e+08 |  62.06%
  1.7s|     1 |     0 |  8009 |     - |  39M|   0 | 480 | 712 |5502 | 712
|6725 |   0 |   0 |   0 |-7.233034e+08 |-4.463478e+08 |  62.05%
  1.7s|     1 |     2 |  8009 |     - |  39M|   0 | 480 | 712 |5502 | 712
|6725 |   0 |   0 |   0 |-7.233034e+08 |-4.463478e+08 |  62.05%


OK, I accept that, but you see that last tiny improvement in the dual bound
that makes me suspicious: what happens in addition (primal heuristic?) that
impacts the root node dual bound that I am not aware of?


Merci beaucoup
Marco
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20191017/32a7a295/attachment.html>