[SCIP] root node dual bound != LP relaxation value
Gregor Hendel
hendel at zib.de
Thu Oct 17 14:35:51 CEST 2019
Hi Marco,
looks as if some propagators do their job and reduce some of the
variables domains before the LP is resolved. By executing "display
statistics" you get an overview which propagator plugin is responsible
for domain reductions, perhaps the root reduced cost propagator.
De rien,
Gregor
Am 17.10.19 um 12:55 schrieb 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
>
>
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20191017/0c3f8b3d/attachment.html>
More information about the Scip
mailing list