[Scip] Fractional solution, pruned node
Gerald Gamrath
gamrath at zib.de
Tue Mar 10 17:52:23 CET 2015
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
> <mailto: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
>> <mailto: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 list
>>> Scip at zib.de <mailto:Scip at zib.de>
>>> http://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/cd011079/attachment.html>
More information about the Scip
mailing list