[Scip] ERROR: pricing was aborted, but no branching could be created!

[Jose Walteros]

Hi all, 

Thanks to the hints given by Gerald I was able to solve the previous problem. It was indeed a typo that I had in the Farkas pricing. Now, most of the experiments that I ran are working perfectly. Although, in a couple of those I am getting the following error: 

[src/scip/solve.c:3538] ERROR: pricing was aborted, but no branching could be created!
[src/scip/solve.c:3855] ERROR: Error <-10> in function call
[src/scip/scip.c:7564] ERROR: Error <-10> in function call
[src/scip/scipshell.c:135] ERROR: Error <-10> in function call
[src/scip/scipshell.c:341] ERROR: Error <-10> in function call
[src/cmain.c:83] ERROR: Error <-10> in function call
SCIP Error (-10): method returned an invalid result code

and I am not sure why. My guess is that it has to be related with the subproblem feasibility. 

I think this is the last thing I'll bother you about.

Thanks for your time.

-Jose.

On May 18, 2012, at 12:03 PM, Jose Walteros wrote:

> Hi Gerald and everybody else, 
> 
> Thanks for you response, I hope I am not bothering you too much with my questions.
> 
>> If you do branch-and-price, no node should be pruned by bound without calling the pricer first (unless a new primal bound was found that cuts off parts of the tree). If the LP value is too bad and would lead to a cutoff, the pricer is called, anyway, because by adding new variables it might decrease the LP value.
>> What can happen is that your branching leaves you with an LP that is infeasible.
> 
> I completely agree with this, that is exactly why I wanted to know if the node was cut by bound or by infeasibility to narrow down the search of the bug. If that was the case, cut by infeasibility, I wanted to know if the bug was in my implementation of pricerFarkasCCP,or in the way I am propagating the branching constraints. 
> 
> I manage to deal with the event_boundwriting file and I found that with the DEFAULT_WRITESUBMIPDUALBOUND option set as TRUE, I am getting an objective of +1.e+20, on those nodes, which is an indicator that the nodes where indeed cut by infeasibility.  
> 
>> In this case, you do not have dual values, so "normal" reduced cost pricing cannot be applied. Therefore, a pricer should implement the additional Farkas pricing callback. This one is called for an infeasible LP and works on the values of the dual ray proving infeasibility instead of the dual solution values. You can access these values by, e.g., SCIPgetDualfarkasLinear().
> 
> I was aware of this and, as I mentioned before, I had coded the Farkas pricer. Now, based on my experiments an what I mentioned before, I am almost sure the bug that I have is there. I am currently checking this. I will let you know if something else comes up
> 
> Thanks a lot for your response.
> 
> Best regards,
> 
> -Jose
> 
> On May 18, 2012, at 11:30 AM, Gerald Gamrath wrote:
> 
>> Hi Jose,
>> 
>> as you said, the event_boundwriting example copies the subproblem of the current node. After that, the sub-SCIP is solved until the end of the root node, which means that presolving is performed and cutting planes are generated. This would not be done if we would just solve the current node in the tree. So the value of the LP relaxation in the sub-SCIP should be better (or equal) than the LP relaxation value at the current node.
>> 
>> If you do branch-and-price, no node should be pruned by bound without calling the pricer first (unless a new primal bound was found that cuts off parts of the tree). If the LP value is too bad and would lead to a cutoff, the pricer is called, anyway, because by adding new variables it might decrease the LP value.
>> What can happen is that your branching leaves you with an LP that is infeasible. In this case, you do not have dual values, so "normal" reduced cost pricing cannot be applied. Therefore, a pricer should implement the additional Farkas pricing callback. This one is called for an infeasible LP and works on the values of the dual ray proving infeasibility instead of the dual solution values. You can access these values by, e.g., SCIPgetDualfarkasLinear().
>> 
>> Best,
>> Gerald and Michael
>> 
>> Am 18.05.2012 09:02, schrieb Jose Walteros:
>>> 
>>> Hi all, 
>>> 
>>> I was able to adapt the event_boundwriting example that you have in order to catch information when each node is processed. There are a couple of questions that I have about it:
>>> 
>>> 1. As I see it base on the code in the file event_boundwriting.c when DEFAULT_WRITESUBMIPDUALBOUND option is as true, you construct a new model, copy the bounds, and then, solve it to find the value of the LP relaxation at that node. Is this correct?
>>> 
>>> 2. As I mentioned before, something that I am noting is that SCIP is pruning nodes in the B&B tree that are not supposed to be pruned. SCIP is not even calling the pricer in those node (and because of this reason I don't even know if the LP relaxation is solved in this nodes). I would like to know if it is possible to use this handler do find why the node was pruned (if it was by bound or by infeasibility)? 
>>> 
>>> -Jose
>>> 
>>> On May 17, 2012, at 6:52 PM, Jose Walteros wrote:
>>> 
>>>> Hi all, 
>>>> 
>>>> I coded a Branch and price using the binpacking example as a a starting point. So far everything is working and the code is running, I was able to solve the previous problems that I had before. 
>>>> 
>>>> I am currently running some tests and I found that the pricer problem is not being called while solving some nodes in the b&b tree (my impression is that maybe the nodes are cut by infeasibility, but I want to be sure about the reason). What I have seen, at least for the instances that I am using, is that SCIP by default solves the tree using a depth first search (it might not be the case always, but for the instance that I am running, it explores the tree in this             fashion). I am using as a branching rule a very similar rule compared to the Ryan Foster's, that comes with the binpacking example. I was wondering if there is a simple way to access the value of the objective function at each node and also to find out if the node was cut off (and the reason why it was cut off, i.e., cut by bound, or by infeasibility )? 
>>>> 
>>>> I think that doing this can be done by writing an event handler or something like that, but I have not seen a file like that in the examples that you have. 
>>>> 
>>>> Thanks for your help.
>>>> 
>>>> -Jose
>>> 
>>> 
>>> 
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de
>>> http://listserv.zib.de/mailman/listinfo/scip
>> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20120519/5282e866/attachment.html