[Scip] Fractional solution, pruned node
Cristina Núñez del Toro
cristina.nunez at upc.edu
Tue Mar 10 18:59:59 CET 2015
Hello Gerald,
I'm sending you the output lines in the attached file.
Regarding the activation of the pricer, before doing SCIP_CALL( SCIPsolve()
), I call a probdata plug-in in which I create the scip the problem,
variables and constraints. In the same callback I also create and activate
the pricer object. Just getting out the SCIPprobdataCreate, I checked
SCIPgetOrigObjscale() and it is equal to 0. Once in the pricing routing,
SCIPgetOrigObjscale() has the same value but SCIPgetTransObjscale() is
equal to one. What could be happening?
2015-03-10 17:52 GMT+01:00 Gerald Gamrath <gamrath at zib.de>:
> Hi Christina,
>
> I have revised the initial parameters settings and, as you said, I had
> the heuristic as disabled (and also the separating and presolving). Now,
> the heuristic is not disabled but the separating and presolving. I'm
> sending you the statistics file. I'm not using the runshell SCIP command
> line interface, so I don't know where can obtain the log file. Is there
> another way to obtain it without including the SCIP command line?
>
> But you get output lines from SCIP don't you? Just pipe them to some file
> and send this to me.
>
> What I have discovered is that the initial cutoff bound (3.0001) is
> lower than my (already known) optimal value (3.2). So, even the LP gets an
> integer solution with value of 3.2, scip never takes this bound into
> account. I have already checked my code and I never set this cutoff bound,
> so I suspect this 3.0001 is set by scip from the very beginning. In fact, I
> have tried starting the B&Price with different initial columns. Even if the
> initial columns yields feasible or infeasible solution, the cutoff bound is
> always 3.0001 after finding the first feasible LP solution. You may think
> that I have something wrong in my problem definition and that 3.2 is
> actually not my optimal solution, but the same cutoff bound of 3.0001
> appears even when the initial columns gives a integer (and obviously
> feasible) LP solution with value equal to 3.2. It is somehow normal?
>
> Do you activate your pricer before calling SCIP solve? If not, SCIP might
> detect that the objective value of each solution will always be a multiple
> of some number, for example 0.2. In that case, if a solution with value 3.2
> was found, SCIP would set a cutoff bound of 3.0 + eps, which would be
> exactly 3.0001. But this should not happen if a pricer is enabled. Perhaps
> you can check that SCIPgetOrigObjscale() and SCIPgetTransObjscale() are
> both 1.0.
>
> Best,
> Gerald
>
>
>
>
> 2015-03-09 18:43 GMT+01:00 Gerald Gamrath <gamrath at zib.de>:
>
>> Dear Christina,
>>
>> it should not be a problem if you do not set a lowerbound. Just to be
>> sure, you could set it to -SCIPinfinity().
>>
>> So we will need to investigate your problem further. Could you send me a
>> log file (including statistics)?
>>
>> About the integer LP solutions: This should automatically be done by the
>> simplerounding heuristic. Did you perhaps disable the heuristic by accident?
>>
>> Best,
>> Gerald
>>
>>
>> On 06.03.2015 17:08, Cristina Núñez del Toro wrote:
>>
>> Dear Gerald,
>>
>> thank you for you response.
>>
>>
>> About 2) yes, I am sure that pricing is performed at this node, and 3)
>> I start the B&P with a with a set of initial variables that gives a
>> feasible primal solution to the integer problem. Both, initial and priced
>> variables are marked as removable and all constraints are marked as
>> modifiable.
>>
>> About 1), I think this could be actually the problem. I do not compute
>> the lower bound at any point. I just followed the binpacking example to
>> create my own implementation but I missed this issue. In fact, I also
>> noticed that whenever an integer LP solution gets into the pricing
>> callback, scip do not update the best upper bound in case of promising one.
>> I read a previous email about this issue and recommended to use
>> SCIPupdateCutoofbound() and/or SCIPsetObjlimit(). However, what I am more
>> concerned about why this integral and feasible solution is not stored as a
>> Primal bound of the original Integer Master Problem thant setting a new
>> cuttoffbound. If you can help me explaining me a little bit more about this
>> because I'm find myself quite lost with that.
>> Best regards,
>>
>>
>>
>> 2015-03-04 19:35 GMT+01:00 Gerald Gamrath <gamrath at zib.de>:
>>
>>> Dear Christina,
>>>
>>> sorry for the late reply, but we were quite busy in the last weeks.
>>>
>>> There might be different reasons for this behavior.
>>>
>>> 1) Does your pricing callback compute a lower bound and sets the
>>> lowerbound pointer accordingly? If this is higher than the cutoff bound,
>>> the node will be cut off.
>>>
>>> 2) Perhaps the propagation already detected infeasibility? Are you sure
>>> that you perform pricing at this node?
>>>
>>> 3) Are all your variables created by pricing and all constraints marked
>>> to be modifiable? Otherwise, the enforcement might also detect
>>> infeasibility of an unmodifiable constraint.
>>>
>>> Best,
>>> Gerald
>>>
>>> Am 19.02.2015 um 15:27 schrieb Cristina Núñez del Toro:
>>>
>>> Dear all,
>>>
>>> I am currently implemented a Branch&Price algorithm. For my problem, I
>>> have 3 types of variables, say "x","y" and "z". I have just finished my on
>>> branching rule that implies to only branch on the "z" variables.
>>> Apparently, everything goes ok; I mean, everytime SCIP enters to the
>>> branchexeclp routine, it looks for the most fractional "z" variable and do
>>> branch on it. However, I have noticed that a certain point of the
>>> algorithm, after finishing the pricing loop, SCIP "skips" (sorry for the
>>> joke) the branching phase (the node is cutted off/pruned), I mean, it does
>>> not enter to any branching callback method and goes directly to the handler
>>> constraint to propagate another node. As far I understand, this would be of
>>> course a normal behaviour if, after finishing the pricing stage :
>>>
>>> a) the objective value of the current LP is greater or equal than the
>>> incumbent,
>>> b) the current LP solution is an integer solution,
>>> c) the current LP solution is an integer solution and it is optimal.
>>>
>>> However, I found a pruned node with a fractional LP solution (inluding
>>> some "z" variables with fractional value) but with the objective value strictly
>>> lower than the incumbent.
>>>
>>> Is there any reason for expecting this?
>>>
>>> Thanks in advances,
>>>
>>> Best regards,
>>>
>>>
>>> --
>>> ---
>>> Cristina Nuñez
>>>
>>>
>>> _______________________________________________
>>> Scip mailing listScip at zib.dehttp://listserv.zib.de/mailman/listinfo/scip
>>>
>>>
>>>
>>
>>
>> --
>> ---
>> Cristina Nuñez
>>
>>
>>
>
>
> --
> ---
> Cristina Nuñez
>
>
>
--
---
Cristina Nuñez
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20150310/46df70b2/attachment.html>
-------------- next part --------------
7.3s| 1 | 2 | 4845 | - |7390k| 0 | 170 | 994 |1625 | 994 |1625 | 0 | 0 | 0 | 2.186667e+00 | -- | Inf
8.7s| 2 | 3 | 5043 | 203.0 |7979k| 1 | 127 |1048 |1625 |1048 |1625 | 0 | 0 | 0 | 2.186667e+00 | -- | Inf
10.8s| 3 | 4 | 5316 | 238.0 |8213k| 2 | 126 |1081 |1625 |1081 |1625 | 0 | 0 | 0 | 2.186667e+00 | -- | Inf
12.1s| 4 | 5 | 5375 | 178.3 |8267k| 3 | 144 |1088 |1625 |1088 |1625 | 0 | 0 | 0 | 2.186667e+00 | -- | Inf
14.9s| 5 | 6 | 5673 | 208.2 |8658k| 4 | 111 |1136 |1625 |1136 |1625 | 0 | 0 | 0 | 2.186667e+00 | -- | Inf
15.4s| 6 | 7 | 5746 | 181.2 |8684k| 5 | 90 |1139 |1625 |1139 |1625 | 0 | 0 | 0 | 2.186667e+00 | -- | Inf
15.5s| 7 | 8 | 5772 | 155.3 |8686k| 6 | 26 |1139 |1625 |1139 |1625 | 0 | 0 | 0 | 2.186667e+00 | -- | Inf
16.9s| 8 | 9 | 5901 | 151.6 |8891k| 7 | 87 |1158 |1625 |1158 |1625 | 0 | 0 | 0 | 2.186667e+00 | -- | Inf
17.1s| 9 | 6 | 5903 | 132.9 |8907k| 8 | 0 |1158 |1625 |1158 |1625 | 0 | 0 | 0 | 2.186667e+00 | 3.400000e+00 | 55.49%
18.6s| 11 | 6 | 6110 | 127.0 |9093k| 8 | 150 |1175 |1625 |1081 |1625 | 0 | 0 | 0 | 2.186667e+00 | 3.400000e+00 | 55.49%
time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
22.7s| 14 | 5 | 7030 | 168.5 |9519k| 8 | 113 |1225 |1625 |1133 |1625 | 0 | 0 | 0 | 2.186667e+00 | 3.400000e+00 | 55.49%
23.9s| 15 | 6 | 7195 | 168.2 |9612k| 8 | 112 |1242 |1625 |1161 |1625 | 0 | 0 | 0 | 2.186667e+00 | 3.400000e+00 | 55.49%
24.9s| 16 | 7 | 7390 | 170.0 |9683k| 8 | 109 |1252 |1625 |1184 |1625 | 0 | 0 | 0 | 2.186667e+00 | 3.400000e+00 | 55.49%
25.9s| 17 | 8 | 7513 | 167.1 |9748k| 8 | 89 |1264 |1625 |1200 |1625 | 0 | 0 | 0 | 2.186667e+00 | 3.400000e+00 | 55.49%
28.3s| 21 | 6 | 7861 | 151.1 |9849k| 8 | 128 |1276 |1625 |1114 |1625 | 0 | 0 | 0 | 2.186667e+00 | 3.400000e+00 | 55.49%
29.5s| 22 | 7 | 8263 | 163.0 |9952k| 8 | 139 |1289 |1625 |1180 |1625 | 0 | 0 | 0 | 2.186667e+00 | 3.400000e+00 | 55.49%
31.1s| 23 | 8 | 8725 | 176.6 | 10M| 8 | 106 |1319 |1625 |1198 |1625 | 0 | 0 | 0 | 2.186667e+00 | 3.400000e+00 | 55.49%
33.0s| 24 | 9 | 8992 | 180.5 | 10M| 8 | 113 |1346 |1625 |1240 |1625 | 0 | 0 | 0 | 2.186667e+00 | 3.400000e+00 | 55.49%
33.7s| 25 | 10 | 9110 | 177.9 | 10M| 8 | 99 |1349 |1625 |1216 |1625 | 0 | 0 | 0 | 2.186667e+00 | 3.400000e+00 | 55.49%
33.9s| 26 | 11 | 9156 | 172.6 | 10M| 8 | 96 |1349 |1625 |1216 |1625 | 0 | 0 | 0 | 2.186667e+00 | 3.400000e+00 | 55.49%
35.8s| 31 | 8 | 9743 | 163.4 | 10M| 8 | 150 |1352 |1625 |1116 |1625 | 0 | 0 | 0 | 2.228571e+00 | 3.400000e+00 | 52.56%
36.7s| 32 | 9 | 10053 | 168.2 | 10M| 8 | 111 |1356 |1625 |1181 |1625 | 0 | 0 | 0 | 2.228571e+00 | 3.400000e+00 | 52.56%
38.7s| 35 | 8 | 10410 | 163.8 | 10M| 8 | 159 |1371 |1625 |1121 |1625 | 0 | 0 | 0 | 2.228571e+00 | 3.400000e+00 | 52.56%
39.8s| 36 | 9 | 11100 | 178.9 | 10M| 8 | 138 |1384 |1625 |1170 |1625 | 0 | 0 | 0 | 2.333333e+00 | 3.400000e+00 | 45.71%
40.5s| 37 | 10 | 13283 | 234.5 | 10M| 8 | 90 |1392 |1625 |1192 |1625 | 0 | 0 | 0 | 2.333333e+00 | 3.400000e+00 | 45.71%
42.5s| 39 | 8 | 13858 | 237.3 | 10M| 8 | 0 |1405 |1625 |1253 |1625 | 0 | 0 | 0 | 2.333333e+00 | 3.400000e+00 | 45.71%
43.5s| 40 | 9 | 14004 | 235.0 | 10M| 8 | 99 |1415 |1625 |1206 |1625 | 0 | 0 | 0 | 2.333333e+00 | 3.400000e+00 | 45.71%
43.9s| 41 | 10 | 14325 | 237.1 | 10M| 8 | 141 |1415 |1625 |1197 |1625 | 0 | 0 | 0 | 2.333333e+00 | 3.400000e+00 | 45.71%
44.2s| 42 | 11 | 14496 | 235.5 | 10M| 8 | 84 |1415 |1625 |1210 |1625 | 0 | 0 | 0 | 2.333333e+00 | 3.400000e+00 | 45.71%
45.4s| 46 | 9 | 14774 | 220.8 | 10M| 8 | 110 |1418 |1625 |1214 |1625 | 0 | 0 | 0 | 2.333333e+00 | 3.400000e+00 | 45.71%
46.1s| 48 | 9 | 15097 | 218.2 | 10M| 8 | 106 |1423 |1625 |1225 |1625 | 0 | 0 | 0 | 2.333333e+00 | 3.400000e+00 | 45.71%
46.8s| 49 | 10 | 15188 | 215.6 | 11M| 8 | 89 |1429 |1625 |1243 |1625 | 0 | 0 | 0 | 2.333333e+00 | 3.400000e+00 | 45.71%
47.3s| 51 | 10 | 15267 | 208.5 | 11M| 8 | 152 |1429 |1625 |1121 |1625 | 0 | 0 | 0 | 2.380952e+00 | 3.400000e+00 | 42.80%
47.8s| 53 | 10 | 15534 | 205.7 | 11M| 8 | 99 |1429 |1625 |1227 |1625 | 0 | 0 | 0 | 2.380952e+00 | 3.400000e+00 | 42.80%
48.0s| 54 | 9 | 15560 | 202.3 | 11M| 8 | 0 |1429 |1625 |1252 |1625 | 0 | 0 | 0 | 2.380952e+00 | 3.400000e+00 | 42.80%
48.7s| 57 | 8 | 15879 | 197.1 | 11M| 8 | 144 |1429 |1625 |1121 |1625 | 0 | 0 | 0 | 2.380952e+00 | 3.400000e+00 | 42.80%
49.4s| 58 | 9 | 16181 | 199.0 | 11M| 8 | 114 |1431 |1625 |1173 |1625 | 0 | 0 | 0 | 2.380952e+00 | 3.400000e+00 | 42.80%
50.5s| 59 | 10 | 16316 | 197.9 | 11M| 8 | 91 |1444 |1625 |1219 |1625 | 0 | 0 | 0 | 2.380952e+00 | 3.400000e+00 | 42.80%
51.9s| 61 | 10 | 16524 | 194.7 | 11M| 8 | 120 |1455 |1625 |1183 |1625 | 0 | 0 | 0 | 2.380952e+00 | 3.400000e+00 | 42.80%
time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
53.0s| 63 | 10 | 16933 | 195.0 | 11M| 8 | 97 |1460 |1625 |1213 |1625 | 0 | 0 | 0 | 2.380952e+00 | 3.400000e+00 | 42.80%
54.3s| 66 | 9 | 17258 | 191.0 | 11M| 8 | 125 |1464 |1625 |1224 |1625 | 0 | 0 | 0 | 2.380952e+00 | 3.400000e+00 | 42.80%
55.6s| 70 | 7 | 17749 | 187.1 | 11M| 8 | 143 |1467 |1625 |1210 |1625 | 0 | 0 | 0 | 2.380952e+00 | 3.400000e+00 | 42.80%
56.0s| 71 | 8 | 18484 | 194.9 | 11M| 8 | 141 |1467 |1625 |1183 |1625 | 0 | 0 | 0 | 2.666667e+00 | 3.400000e+00 | 27.50%
56.2s| 72 | 9 | 18854 | 197.4 | 11M| 8 | 124 |1467 |1625 |1216 |1625 | 0 | 0 | 0 | 2.666667e+00 | 3.400000e+00 | 27.50%
56.5s| 73 | 10 | 18863 | 194.8 | 11M| 8 | 90 |1467 |1625 |1216 |1625 | 0 | 0 | 0 | 2.666667e+00 | 3.400000e+00 | 27.50%
58.7s| 76 | 9 | 19181 | 191.2 | 11M| 8 | 125 |1484 |1625 |1255 |1625 | 0 | 0 | 0 | 2.666667e+00 | 3.400000e+00 | 27.50%
59.0s| 77 | 10 | 19184 | 188.7 | 11M| 8 | 113 |1484 |1625 |1255 |1625 | 0 | 0 | 0 | 2.666667e+00 | 3.400000e+00 | 27.50%
59.9s| 79 | 10 | 19418 | 186.9 | 11M| 8 | 99 |1491 |1625 |1262 |1625 | 0 | 0 | 0 | 2.666667e+00 | 3.400000e+00 | 27.50%
60.1s| 80 | 9 | 19501 | 185.6 | 11M| 9 | 0 |1491 |1625 |1293 |1625 | 0 | 0 | 0 | 2.666667e+00 | 3.400000e+00 | 27.50%
61.7s| 86 | 5 | 20089 | 179.4 | 11M| 9 | 127 |1491 |1625 |1185 |1625 | 0 | 0 | 0 | 2.733333e+00 | 3.400000e+00 | 24.39%
61.9s| 87 | 6 | 20106 | 177.5 | 11M| 9 | 118 |1491 |1625 |1188 |1625 | 0 | 0 | 0 | 2.733333e+00 | 3.400000e+00 | 24.39%
63.9s| 91 | 4 | 20782 | 177.1 | 11M| 9 | 132 |1495 |1625 |1180 |1625 | 0 | 0 | 0 | 2.800000e+00 | 3.400000e+00 | 21.43%
64.2s| 92 | 5 | 20834 | 175.8 | 11M| 9 | 129 |1495 |1625 |1209 |1625 | 0 | 0 | 0 | 2.800000e+00 | 3.400000e+00 | 21.43%
65.8s| 97 | 0 | 21133 | 169.7 | 11M| 9 | - |1496 |1625 | 0 | 0 | 0 | 0 | 0 | 3.400000e+00 | 3.400000e+00 | 0.00%
More information about the Scip
mailing list