[Scip] Fractional solution, pruned node
Cristina Núñez del Toro
cristina.nunez at upc.edu
Tue Mar 10 17:03:17 CET 2015
Hello Gerald,
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?
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?
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20150310/bdfa42c4/attachment.html>
-------------- next part --------------
SCIP Status : problem is solved [optimal solution found]
Total Time : 73.59
solving : 73.59
presolving : 0.00 (included in solving)
reading : 0.00
copying : 0.01 (1 #copies) (minimal 0.01, maximal 0.01, average 0.01)
Original Problem :
Problem name : BP_AC
Variables : 686 (676 binary, 0 integer, 0 implicit integer, 10 continuous)
Constraints : 1625 initial, 1625 maximal
Objective sense : minimize
Presolved Problem :
Problem name : t_BP_AC
Variables : 1487 (676 binary, 0 integer, 0 implicit integer, 811 continuous)
Constraints : 1625 initial, 1625 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 0 0 0 0 0 0 0 0 0 0
dualinfer : 0.00 0.00 0 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 0 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 0 0 0 0 0 0 0 0 0 0
dualfix : 0.00 0.00 0 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
St_constrhldr : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
linear : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
root node : - - - 41 - - 41 - - - - -
Constraints : Number MaxNumber #Separate #Propagate #EnfoLP #EnfoPS #Check #ResProp Cutoffs DomReds Cuts Applied Conss Children
St_constrhldr : 0+ 8 0 299 0 0 0 0 0 712 0 0 0 0
integral : 0 0 0 0 43 0 8 0 0 0 0 0 0 86
linear : 1625 1625 0 1316 0 0 7 0 0 0 0 0 0 0
countsols : 0 0 0 0 0 0 2 0 0 0 0 0 0 0
Constraint Timings : TotalTime SetupTime Separate Propagate EnfoLP EnfoPS Check ResProp SB-Prop
St_constrhldr : 0.11 0.00 0.00 0.11 0.00 0.00 0.00 0.00 0.00
integral : 0.03 0.00 0.00 0.00 0.03 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 0.00
countsols : 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
Propagators : #Propagate #ResProp Cutoffs DomReds
dualfix : 1 0 0 0
genvbounds : 0 0 0 0
obbt : 0 0 0 0
probing : 0 0 0 0
pseudoobj : 0 0 0 0
redcost : 125 0 0 1240
rootredcost : 1 0 0 0
vbounds : 1359 0 0 0
Propagator Timings : TotalTime SetupTime Presolve Propagate ResProp SB-Prop
dualfix : 0.00 0.00 0.00 0.00 0.00 0.00
genvbounds : 0.01 0.00 0.00 0.01 0.00 0.00
obbt : 0.00 0.00 0.00 0.00 0.00 0.00
probing : 0.00 0.00 0.00 0.00 0.00 0.00
pseudoobj : 0.00 0.00 0.00 0.00 0.00 0.00
redcost : 0.01 0.00 0.00 0.01 0.00 0.00
rootredcost : 0.01 0.00 0.00 0.01 0.00 0.00
vbounds : 0.00 0.00 0.00 0.00 0.00 0.00
Conflict Analysis : Time Calls Success DomReds 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.00 - - 0 0 0.0 - - -
applied locally : - - - 0 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.06 - 516 6219
MCSP_Pricer : 69.09 0.00 275 801
Branching Rules : ExecTime SetupTime BranchLP BranchExt BranchPS Cutoffs DomReds Cuts Conss Children
St_BranchingRule : 0.03 0.00 43 0 0 0 0 0 0 86
allfullstrong : 0.00 0.00 0 0 0 0 0 0 0 0
cloud : 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 0 0 0 0 0 0
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 - - 1
pseudo solutions : 0.00 - - 0
strong branching : 0.00 - - 0
actconsdiving : 0.00 0.00 0 0
clique : 0.00 0.00 0 0
coefdiving : 0.05 0.00 2 0
crossover : 0.00 0.00 0 0
dins : 0.00 0.00 0 0
dualval : 0.00 0.00 0 0
feaspump : 0.21 0.00 1 0
fixandinfer : 0.00 0.00 0 0
fracdiving : 0.03 0.00 2 0
guideddiving : 0.02 0.00 2 0
intdiving : 0.00 0.00 0 0
intshifting : 0.01 0.00 1 0
linesearchdiving : 0.04 0.00 2 0
localbranching : 0.00 0.00 0 0
mutation : 0.00 0.00 0 0
nlpdiving : 0.00 0.00 0 0
objpscostdiving : 0.12 0.00 1 0
octane : 0.00 0.00 0 0
oneopt : 0.00 0.00 1 0
proximity : 0.00 0.00 0 0
pscostdiving : 0.04 0.00 2 0
randrounding : 0.01 0.00 2 0
rens : 0.02 0.00 1 0
rins : 0.00 0.00 0 0
rootsoldiving : 0.08 0.00 1 0
rounding : 0.01 0.00 44 0
shiftandpropagate: 0.01 0.00 1 0
shifting : 0.00 0.00 2 0
simplerounding : 0.02 0.00 275 0
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.01 0.00 2 0
zeroobj : 0.00 0.00 0 0
zirounding : 0.01 0.00 43 0
other solutions : - - - 0
LP : Time Calls Iterations Iter/call Iter/sec Time-0-It Calls-0-It
primal LP : 2.18 390 9229 31.18 4233.49 0.27 94
dual LP : 1.30 143 10236 102.36 7873.85 0.28 43
lex dual LP : 0.00 0 0 0.00 -
barrier LP : 0.00 0 0 0.00 - 0.00 0
diving/probing LP: 0.57 90 5771 64.12 10124.56
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 : 87 (43 internal, 44 leaves)
nodes (total) : 87 (43 internal, 44 leaves)
nodes left : 0
max depth : 8
max depth (total): 8
backtracks : 50 (57.5%)
delayed cutoffs : 0
repropagations : 70 (30 domain reductions, 0 cutoffs)
avg switch length: 3.61
switching time : 0.01
Root Node :
First LP value : -
First LP Iters : 0
First LP Time : 0.00
Final Dual Bound : +2.18666666666667e+00
Final Root Iters : 4754
Solution :
Solutions found : 1 (1 improvements)
First Solution : +3.40000000000000e+00 (in run 1, after 1 nodes, 0.01 seconds, depth 0, found by <relaxation>)
Gap First Sol. : infinite
Gap Last Sol. : infinite
Primal Bound : +3.40000000000000e+00 (in run 1, after 1 nodes, 0.01 seconds, depth 0, found by <relaxation>)
Dual Bound : +3.40000000000000e+00
Gap : 0.00 %
Avg. Gap : 36.01 % (2650.22 primal-dual integral)
More information about the Scip
mailing list