[Scip] Pricer regenerates the same column
Marco Casula
casula.marco at gmail.com
Tue May 6 18:59:55 CEST 2014
Dear all,
I am working on a branch and price algorithm for the VRP with time windows
and stochastic travel times. While on many instances the algorithm
terminates correctly, with a number of instances/parameters (delay
distributions, penalties) combinations, the algorithm gets stuck as the
pricer keeps regenerating the same column.
I have found a similar case in the mailing list archives, and I tried every
suggestion I found there, without success:
the delay flag of the pricer is set to TRUE, as is the initial flag for the
new variables (I had previously set this to FALSE, with the same result);
the variables are added via SCIPaddPricedVar;
I checked SCIPvarIsInLP for the variable added in the previous iteration of
the pricer, and it is true;
the reduced cost of the variable added in the previous iteration (via
SCIPgetVarRedCost) coincides with the one i compute for the variable in the
current iteration;
I changed the upper bound on the variables from 1.0 to SCIPinfinity, with
no effect.
I was hoping for some more insight on the matter.
Please find attached a logfile for a non working instance (terminated
early), and the Pricer code.
For completeness, here's a link to a full-working folder (including all
source files) https://www.dropbox.com/sh/664n10xssiicd4o/G0xtWoLH2T
Thanks for any help
Marco Casula
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140506/7bca6d9d/attachment.html>
-------------- next part --------------
1.5
150
1
x= 40, y= 50
x= 52, y= 75
x= 45, y= 70
x= 62, y= 69
x= 60, y= 66
x= 42, y= 65
x= 16, y= 42
x= 58, y= 70
x= 34, y= 60
x= 28, y= 70
x= 35, y= 66
x= 35, y= 69
x= 25, y= 85
x= 22, y= 75
x= 22, y= 85
x= 20, y= 80
x= 20, y= 85
x= 18, y= 75
x= 15, y= 75
x= 15, y= 80
x= 30, y= 50
x= 30, y= 56
x= 28, y= 52
x= 14, y= 66
x= 25, y= 50
x= 22, y= 66
Number of nodes: 26
Number of arcs: 650
Max demand per tour: 700
presolving:
presolving (1 rounds):
0 deleted vars, 0 deleted constraints, 0 added constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
0 implications, 0 cliques
presolved problem has 0 variables (0 bin, 0 int, 0 impl, 0 cont) and 25 constraints
25 constraints of type <linear>
Presolving Time: 0.00
time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
0.0s| 1 | 0 | 1 | - | 176k| 0 | - | 1 | 25 | 1 | 25 | 0 | 0 | 0 | -- | -- | Inf
r 0.0s| 1 | 0 | 25 | - | 211k| 0 | - | 25 | 25 | 25 | 25 | 0 | 0 | 0 | -- | 1.275055e+03 | Inf
r 2.0s| 1 | 0 | 45 | - | 214k| 0 | - | 26 | 25 | 26 | 25 | 0 | 0 | 0 | -- | 2.529410e+02 | Inf
4.4s| 1 | 0 | 544 | - | 459k| 0 | 24 | 107 | 25 | 45 | 25 | 0 | 0 | 0 | -- | 2.529410e+02 | Inf
r 6.0s| 1 | 0 | 880 | - | 697k| 0 | - | 167 | 25 | 70 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
6.4s| 1 | 0 | 940 | - | 755k| 0 | - | 188 | 25 | 94 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
8.3s| 1 | 0 | 1030 | - |1005k| 0 | - | 288 | 25 | 194 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
10.1s| 1 | 0 | 1030 | - |1244k| 0 | - | 388 | 25 | 294 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
12.0s| 1 | 0 | 1030 | - |1482k| 0 | - | 488 | 25 | 394 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
13.8s| 1 | 0 | 1030 | - |1723k| 0 | - | 588 | 25 | 494 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
15.7s| 1 | 0 | 1030 | - |1962k| 0 | - | 688 | 25 | 594 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
17.5s| 1 | 0 | 1030 | - |2192k| 0 | - | 788 | 25 | 694 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
19.4s| 1 | 0 | 1030 | - |2418k| 0 | - | 888 | 25 | 794 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
21.2s| 1 | 0 | 1030 | - |2666k| 0 | - | 988 | 25 | 894 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
23.1s| 1 | 0 | 1030 | - |2908k| 0 | - |1088 | 25 | 994 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
25.0s| 1 | 0 | 1030 | - |3131k| 0 | - |1188 | 25 |1094 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
26.9s| 1 | 0 | 1030 | - |3395k| 0 | - |1288 | 25 |1194 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
28.7s| 1 | 0 | 1030 | - |3613k| 0 | - |1388 | 25 |1294 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
30.6s| 1 | 0 | 1030 | - |3825k| 0 | - |1488 | 25 |1394 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
32.5s| 1 | 0 | 1030 | - |4119k| 0 | - |1588 | 25 |1494 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
34.4s| 1 | 0 | 1030 | - |4304k| 0 | - |1688 | 25 |1594 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
36.4s| 1 | 0 | 1030 | - |4586k| 0 | - |1788 | 25 |1694 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
38.3s| 1 | 0 | 1030 | - |4836k| 0 | - |1888 | 25 |1794 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
40.2s| 1 | 0 | 1030 | - |5021k| 0 | - |1988 | 25 |1894 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
42.1s| 1 | 0 | 1030 | - |5206k| 0 | - |2088 | 25 |1994 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
44.0s| 1 | 0 | 1030 | - |5587k| 0 | - |2188 | 25 |2094 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
45.9s| 1 | 0 | 1030 | - |5771k| 0 | - |2288 | 25 |2194 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
47.8s| 1 | 0 | 1030 | - |5956k| 0 | - |2388 | 25 |2294 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
49.7s| 1 | 0 | 1030 | - |6141k| 0 | - |2488 | 25 |2394 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
51.7s| 1 | 0 | 1030 | - |6561k| 0 | - |2588 | 25 |2494 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
53.6s| 1 | 0 | 1030 | - |6746k| 0 | - |2688 | 25 |2594 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
55.5s| 1 | 0 | 1030 | - |6931k| 0 | - |2788 | 25 |2694 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
57.4s| 1 | 0 | 1030 | - |7115k| 0 | - |2888 | 25 |2794 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
59.2s| 1 | 0 | 1030 | - |7300k| 0 | - |2988 | 25 |2894 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
61.2s| 1 | 0 | 1030 | - |7767k| 0 | - |3088 | 25 |2994 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
63.0s| 1 | 0 | 1030 | - |7952k| 0 | - |3188 | 25 |3094 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
64.9s| 1 | 0 | 1030 | - |8137k| 0 | - |3288 | 25 |3194 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
66.8s| 1 | 0 | 1030 | - |8322k| 0 | - |3388 | 25 |3294 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
68.8s| 1 | 0 | 1030 | - |8506k| 0 | - |3488 | 25 |3394 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
70.7s| 1 | 0 | 1030 | - |8725k| 0 | - |3588 | 25 |3494 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
72.6s| 1 | 0 | 1030 | - |9215k| 0 | - |3688 | 25 |3594 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
74.5s| 1 | 0 | 1030 | - |9399k| 0 | - |3788 | 25 |3694 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
76.5s| 1 | 0 | 1030 | - |9584k| 0 | - |3888 | 25 |3794 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
78.4s| 1 | 0 | 1030 | - |9769k| 0 | - |3988 | 25 |3894 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
80.3s| 1 | 0 | 1030 | - |9954k| 0 | - |4088 | 25 |3994 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
82.3s| 1 | 0 | 1030 | - | 10M| 0 | - |4188 | 25 |4094 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
84.2s| 1 | 0 | 1030 | - | 10M| 0 | - |4288 | 25 |4194 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
86.2s| 1 | 0 | 1030 | - | 10M| 0 | - |4388 | 25 |4294 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
88.1s| 1 | 0 | 1030 | - | 11M| 0 | - |4488 | 25 |4394 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
90.0s| 1 | 0 | 1030 | - | 11M| 0 | - |4582 | 25 |4488 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
(node 1) LP solver hit time limit in LP 232 -- using pseudo solution instead
90.0s| 1 | 2 | 1030 | - | 11M| 0 | - |4582 | 25 |4488 | 25 | 0 | 0 | 0 | -- | 2.155462e+02 | Inf
SCIP Status : solving was interrupted [time limit reached]
Solving Time (sec) : 90.01
Solving Nodes : 1
Primal Bound : +2.15546223279240e+02 (74 solutions)
Dual Bound : -1.00000000000000e+20
Gap : infinite
SCIP Status : solving was interrupted [time limit reached]
Total Time : 90.01
solving : 90.01
presolving : 0.00 (included in solving)
reading : 0.00
copying : 0.00 (0 times copied the problem)
Original Problem :
Problem name : VRP
Variables : 0 (0 binary, 0 integer, 0 implicit integer, 0 continuous)
Constraints : 25 initial, 25 maximal
Objective sense : minimize
Presolved Problem :
Problem name : t_VRP
Variables : 4582 (0 binary, 4582 integer, 0 implicit integer, 0 continuous)
Constraints : 25 initial, 25 maximal
Presolvers : ExecTime SetupTime Calls FixedVars AggrVars ChgTypes ChgBounds AddHoles DelCons AddCons ChgSides ChgCoefs
boundshift : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
components : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
convertinttobin : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
domcol : 0.00 0.00 1 0 0 0 0 0 0 0 0 0
dualfix : 0.00 0.00 1 0 0 0 0 0 0 0 0 0
gateextraction : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
implics : 0.00 0.00 1 0 0 0 0 0 0 0 0 0
inttobinary : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
trivial : 0.00 0.00 1 0 0 0 0 0 0 0 0 0
genvbounds : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
probing : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
pseudoobj : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
linear : 0.00 0.00 1 0 0 0 0 0 0 0 0 0
root node : - - - 0 - - 0 - - - - -
Constraints : Number MaxNumber #Separate #Propagate #EnfoLP #EnfoPS #Check #ResProp Cutoffs DomReds Cuts Applied Conss Children
integral : 0 0 0 0 0 0 78 0 0 0 0 0 0 0
linear : 25 25 0 1 0 1 77 0 0 0 0 0 0 0
countsols : 0 0 0 0 0 1 75 0 0 0 0 0 0 0
Constraint Timings : TotalTime SetupTime Separate Propagate EnfoLP EnfoPS Check ResProp
integral : 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
linear : 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
countsols : 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
Propagators : #Propagate #ResProp Cutoffs DomReds
genvbounds : 0 0 0 0
obbt : 0 0 0 0
probing : 0 0 0 0
pseudoobj : 0 0 0 0
redcost : 0 0 0 0
rootredcost : 0 0 0 0
vbounds : 0 0 0 0
Propagator Timings : TotalTime SetupTime Presolve Propagate ResProp
genvbounds : 0.00 0.00 0.00 0.00 0.00
obbt : 0.00 0.00 0.00 0.00 0.00
probing : 0.00 0.00 0.00 0.00 0.00
pseudoobj : 0.00 0.00 0.00 0.00 0.00
redcost : 0.00 0.00 0.00 0.00 0.00
rootredcost : 0.00 0.00 0.00 0.00 0.00
vbounds : 0.00 0.00 0.00 0.00 0.00
Conflict Analysis : Time Calls Success Conflicts Literals Reconvs ReconvLits LP Iters
propagation : 0.00 0 0 0 0.0 0 0.0 -
infeasible LP : 0.00 0 0 0 0.0 0 0.0 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 : - - - 0 0.0 - - -
applied locally : - - - 0 0.0 - - -
Separators : ExecTime SetupTime Calls Cutoffs DomReds Cuts Applied Conss
cut pool : 0.00 0 - - 0 - - (maximal pool size: 0)
cgmip : 0.00 0.00 0 0 0 0 0 0
clique : 0.00 0.00 0 0 0 0 0 0
closecuts : 0.00 0.00 0 0 0 0 0 0
cmir : 0.00 0.00 0 0 0 0 0 0
flowcover : 0.00 0.00 0 0 0 0 0 0
gomory : 0.00 0.00 0 0 0 0 0 0
impliedbounds : 0.00 0.00 0 0 0 0 0 0
intobj : 0.00 0.00 0 0 0 0 0 0
mcf : 0.00 0.00 0 0 0 0 0 0
oddcycle : 0.00 0.00 0 0 0 0 0 0
rapidlearning : 0.00 0.00 0 0 0 0 0 0
strongcg : 0.00 0.00 0 0 0 0 0 0
zerohalf : 0.00 0.00 0 0 0 0 0 0
Pricers : ExecTime SetupTime Calls Vars
problem variables: 0.22 - 4516 42
VRP_Pricer : 88.09 0.00 4568 4582
Branching Rules : ExecTime SetupTime BranchLP BranchExt BranchPS Cutoffs DomReds Cuts Conss Children
EdgeBranching : 0.00 0.00 0 0 0 0 0 0 0 0
allfullstrong : 0.00 0.00 0 0 0 0 0 0 0 0
fullstrong : 0.00 0.00 0 0 0 0 0 0 0 0
inference : 0.00 0.00 0 0 1 0 0 0 0 2
leastinf : 0.00 0.00 0 0 0 0 0 0 0 0
mostinf : 0.00 0.00 0 0 0 0 0 0 0 0
pscost : 0.00 0.00 0 0 0 0 0 0 0 0
random : 0.00 0.00 0 0 0 0 0 0 0 0
relpscost : 0.00 0.00 0 0 0 0 0 0 0 0
Primal Heuristics : ExecTime SetupTime Calls Found
LP solutions : 0.00 - - 0
pseudo solutions : 0.00 - - 0
actconsdiving : 0.00 0.00 0 0
clique : 0.00 0.00 0 0
coefdiving : 0.00 0.00 0 0
crossover : 0.00 0.00 0 0
dins : 0.00 0.00 0 0
feaspump : 0.00 0.00 0 0
fixandinfer : 0.00 0.00 0 0
fracdiving : 0.00 0.00 0 0
guideddiving : 0.00 0.00 0 0
intdiving : 0.00 0.00 0 0
intshifting : 0.00 0.00 0 0
linesearchdiving : 0.00 0.00 0 0
localbranching : 0.00 0.00 0 0
mutation : 0.00 0.00 0 0
nlpdiving : 0.00 0.00 0 0
objpscostdiving : 0.00 0.00 0 0
octane : 0.00 0.00 0 0
oneopt : 0.00 0.00 0 0
pscostdiving : 0.00 0.00 0 0
rens : 0.00 0.00 0 0
rins : 0.00 0.00 0 0
rootsoldiving : 0.00 0.00 0 0
rounding : 0.00 0.00 0 0
shiftandpropagate: 0.00 0.00 0 0
shifting : 0.00 0.00 0 0
simplerounding : 0.00 0.00 113 74
subnlp : 0.00 0.00 0 0
trivial : 0.00 0.00 2 0
trysol : 0.00 0.00 0 0
twoopt : 0.00 0.00 0 0
undercover : 0.00 0.00 0 0
vbounds : 0.00 0.00 0 0
veclendiving : 0.00 0.00 0 0
zeroobj : 0.00 0.00 0 0
zirounding : 0.00 0.00 0 0
LP : Time Calls Iterations Iter/call Iter/sec Time-0-It Calls-0-It
primal LP : 0.77 4569 1005 4.83 1305.19 0.75 4361
dual LP : 0.00 43 25 1.04 - 0.00 19
lex dual LP : 0.00 0 0 0.00 -
barrier LP : 0.00 0 0 0.00 - 0.00 0
diving/probing LP: 0.00 0 0 0.00 -
strong branching : 0.00 0 0 0.00 -
(at root node) : - 0 0 0.00 -
conflict analysis: 0.00 0 0 0.00 -
B&B Tree :
number of runs : 1
nodes : 1
nodes (total) : 1
nodes left : 2
max depth : 0
max depth (total): 0
backtracks : 0 (0.0%)
delayed cutoffs : 0
repropagations : 0 (0 domain reductions, 0 cutoffs)
avg switch length: 1.00
switching time : 0.00
Solution :
Solutions found : 74 (3 improvements)
First Solution : +1.27505450416797e+03 (in run 1, after 1 nodes, 0.03 seconds, depth 0, found by <simplerounding>)
Primal Bound : +2.15546223279240e+02 (in run 1, after 1 nodes, 5.96 seconds, depth 0, found by <simplerounding>)
Dual Bound : -
Gap : infinite
Root Dual Bound : -
Root Iterations : 1030
objective value: 215.54622327924
T_4_3_7_1_2_5 1 (obj:70.7174266390292)
T_20_22_24_6_23_18_19_16_14_12_15_17_13_25_9_11_10_8_21 1 (obj:144.828796640211)
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Pricer.cpp
Type: text/x-c++src
Size: 29275 bytes
Desc: not available
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140506/7bca6d9d/attachment.bin>
More information about the Scip
mailing list