[Scip] Determinism
Timo Berthold
berthold at zib.de
Mon Oct 19 17:07:09 MEST 2009
Hi Alejandro.
I played a little bit with your instance.
Indeed, you need a lot of B&B nodes for this small number of variables and the
root LP optimum is quite far away from the integer optimum. By the way, Cplex
12 also takes 300'000 nodes to prove optimality.
The attached settings file proved to work well (on my desktop, using
SCIP-1.2). It consists of settings/heuristics/aggressive.set,
settings/cuts/aggressive.set plus some changes to perform conflict based
restarts. In particular, the parameter conflict/restartnum is interesting as
it determines when SCIP should abort and restart the search.
Best, Timo
Am Monday 19 October 2009 14:17:51 schrieb Alejandro Burzyn:
> Ok, thank you again, recently I've found what the difference was between
> the runs: I had changed the SCIP version from 1.1 to 1.2. In the attach
> I've put the lp problem, and the stats of the runs of both versions of scip
> (precompiled binary for windows with soplex in both cases, default
> settings). The runs were made on an athlon xp 1.8 ghz, with 1 gb ram. I
> think the principal difference is in the root cuts, but I don't know if I
> should keep with 1.1 or tune 1.2 a little. I'll be grateful for any advice.
> Thank you very much,
> Alejandro
>
>
>
> --- El lun 19-oct-09, Tobias Achterberg <achterberg at zib.de> escribió:
>
> De: Tobias Achterberg <achterberg at zib.de>
> Asunto: Re: [Scip] Determinism
> A: "Alejandro Burzyn" <aleburzyn at yahoo.com>
> Cc: scip at zib.de
> Fecha: lunes, 19 octubre, 2009, 6:30 am
>
> Alejandro Burzyn wrote:
> > Thank you all for your answers, I think I've made a mistake somewhere
> > with the lp
> > (I think I've modified it somewhere between runs). However, I did test
> > on different computers
> > with same lp and same binary, and there I saw differences in stats no
> > related to time, is this behaviour expected?
>
> Yes, if you run SCIP on different machines or on different operating
> systems, you will most likely see differences in the solving process.
>
> The reason is that many decisions in a mathematical programming solver are
> based on the results of floating point arithmetic calculations. Since there
> are small differences across machines and compilers on how to deal with
> round-off in floating point calculations, the decisions are affected by
> machine type, compiler, and also compiler options. In particular for MIP, a
> small difference in some decision can lead to a very large difference in
> solving behavior.
>
>
> Tobias
>
>
>
>
> ___________________________________________________________________________
>_________ ¡Obtén la mejor experiencia en la web!
> Descarga gratis el nuevo Internet Explorer 8.
> http://downloads.yahoo.com/ieak8/?l=e1
-------------- next part --------------
SCIP Status : problem is solved [optimal solution found]
Solving Time : 880.29
Original Problem :
Problem name : eq.lp
Variables : 1789 (0 binary, 1788 integer, 0 implicit integer, 1 continuous)
Constraints : 15179 initial, 15179 maximal
Presolved Problem :
Problem name : t_eq.lp
Variables : 757 (757 binary, 0 integer, 0 implicit integer, 0 continuous)
Constraints : 2129 initial, 8230 maximal
Presolvers : Time FixedVars AggrVars ChgTypes ChgBounds AddHoles DelCons ChgSides ChgCoefs
trivial : 0.00 0 0 0 0 0 0 0 0
dualfix : 0.00 12 0 0 0 0 0 0 0
boundshift : 0.00 0 0 0 0 0 0 0 0
inttobinary : 0.00 0 0 0 0 0 0 0 0
implics : 0.00 0 0 0 0 0 0 0 0
probing : 0.02 0 0 0 0 0 0 0 0
knapsack : 0.01 0 0 0 0 0 240 240 1442
setppc : 0.00 0 0 0 0 0 240 0 0
linear : 0.04 63 957 0 64 0 13296 482 0
logicor : 0.05 0 0 0 0 0 54 0 0
root node : - 1 - - 1 - - - -
Constraints : Number #Separate #Propagate #EnfoLP #EnfoPS Cutoffs DomReds Cuts Conss Children
integral : 0 0 0 38167 0 78 946 0 0 75440
knapsack : 565 9873 228813 7 0 786 651484 501 0 0
setppc : 48 21 227259 2 0 8988 557951 0 0 0
logicor : 1516+ 9873 136881 7 0 1650 137060 17831 0 0
countsols : 0 0 0 7 0 0 0 0 0 0
Constraint Timings : TotalTime Separate Propagate EnfoLP EnfoPS
integral : 182.53 0.00 0.00 182.53 0.00
knapsack : 7.58 1.79 5.79 0.00 0.00
setppc : 2.57 0.00 2.57 0.00 0.00
logicor : 10.59 1.06 9.53 0.00 0.00
countsols : 0.00 0.00 0.00 0.00 0.00
Propagators : Time Calls Cutoffs DomReds
rootredcost : 0.03 13 0 0
pseudoobj : 3.89 230633 174 6340
Conflict Analysis : Time Calls Success Conflicts Literals Reconvs ReconvLits LP Iters
propagation : 0.32 11598 11475 57430 22.7 1274 11.4 -
infeasible LP : 0.14 613 613 3350 24.3 34 9.4 0
bound exceed. LP : 0.00 0 0 0 0.0 0 0.0 0
strong branching : 0.00 0 0 0 0.0 0 0.0 0
pseudo solution : 0.00 0 0 0 0.0 0 0.0 -
applied globally : - - - 39548 20.2 - - -
applied locally : - - - 0 0.0 - - -
Separators : Time Calls Cutoffs DomReds Cuts Conss
cut pool : 2.53 9572 - - 11309 - (maximal pool size: 1400)
redcost : 5.65 56618 0 2003156 0 0
impliedbounds : 0.06 2689 0 0 0 0
intobj : 0.00 0 0 0 0 0
gomory : 19.02 529 0 0 32599 0
strongcg : 17.37 529 0 0 33779 0
cmir : 0.93 344 0 0 4 0
flowcover : 0.71 20 0 0 2 0
clique : 0.00 21 0 0 34 0
zerohalf : 0.55 15 0 0 242 0
mcf : 0.00 2 0 0 0 0
Pricers : Time Calls Vars
problem variables: 0.00 0 0
Branching Rules : Time Calls Cutoffs DomReds Cuts Conss Children
relpscost : 182.48 38160 78 946 0 0 75440
pscost : 0.00 0 0 0 0 0 0
inference : 0.00 0 0 0 0 0 0
mostinf : 0.00 0 0 0 0 0 0
leastinf : 0.00 0 0 0 0 0 0
fullstrong : 0.00 0 0 0 0 0 0
allfullstrong : 0.00 0 0 0 0 0 0
random : 0.00 0 0 0 0 0 0
Primal Heuristics : Time Calls Found
LP solutions : 0.00 - 7
pseudo solutions : 0.00 - 0
intshifting : 0.01 0 0
feaspump : 0.49 1 0
oneopt : 0.04 15 2
crossover : 1.31 29 5
objpscostdiving : 4.16 110 52
fracdiving : 2.37 220 1
veclendiving : 2.96 220 0
pscostdiving : 2.64 220 1
guideddiving : 1.99 220 1
coefdiving : 2.59 220 0
linesearchdiving : 2.33 220 3
rootsoldiving : 2.65 111 56
trivial : 0.00 0 0
simplerounding : 0.18 45302 0
rounding : 0.52 2907 0
shifting : 4.81 2174 0
fixandinfer : 0.00 0 0
intdiving : 0.00 0 0
actconsdiving : 0.00 0 0
octane : 0.60 74 0
rens : 0.45 2 0
rins : 0.42 14 0
localbranching : 0.00 0 0
mutation : 0.00 0 0
dins : 20.01 65 0
nlp : 0.00 0 0
trysol : 0.00 0 0
LP : Time Calls Iterations Iter/call Iter/sec
primal LP : 1.96 0 0 0.00 0.00
dual LP : 520.11 67199 3328560 49.53 6399.72
lex dual LP : 0.00 0 0 0.00 -
barrier LP : 0.00 0 0 0.00 -
diving/probing LP: 19.78 6345 126168 19.88 6378.56
strong branching : 181.15 8833 777774 88.05 4293.54
(at root node) : - 44 27715 629.89 -
conflict analysis: 0.00 0 0 0.00 -
B&B Tree :
number of runs : 2
nodes : 65759
nodes (total) : 69981
nodes left : 0
max depth : 47
max depth (total): 47
backtracks : 16654 (25.3%)
delayed cutoffs : 2599
repropagations : 9149 (96051 domain reductions, 2564 cutoffs)
avg switch length: 8.68
switching time : 18.45
Solution :
Solutions found : 128 (15 improvements)
Primal Bound : +1.23886000000000e+05 (in run 2, after 16287 nodes, 511.28 seconds, depth 21, found by <relaxation>)
Dual Bound : +1.23886000000000e+05
Gap : 0.00 %
Root Dual Bound : +5.01795484041204e+04
More information about the Scip
mailing list