[Scip] Fractional solution, pruned node
Gerald Gamrath
gamrath at zib.de
Tue Mar 10 21:32:30 CET 2015
Hi Christina,
ok, this explains the behavior. The original objective scale should be
1, but this itself should not be a problem. However, I don't see how
this can be changed to 0 (which SCIP version do you use?), so perhaps
you want to use valgrind to check that you don't have any memory
corruptions.
Best,
Gerald
Am 10.03.2015 um 19:19 schrieb Cristina Núñez del Toro:
> Hello again,
>
> I have already solve the problem! Because following binpacking
> example, I just left SCIPsetObjIntegral() without noticed that my
> solution does not fullfill this condition. Now, I obtain the optimal
> value of 3.2 recognized. However, SCIPgetOrigObjscale() and
> SCIPgetTransObjscale() are still 0 and 1, respectivelly. Should I
> expect both values equal to 1 ?
>
> Thanks for all,
>
> 2015-03-10 17:52 GMT+01:00 Gerald Gamrath <gamrath at zib.de
> <mailto: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
>> <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
>
>
>
>
> --
> ---
> Cristina Nuñez
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20150310/9b500910/attachment.html>
More information about the Scip
mailing list