[SCIP] Early branching in SCIP

[Benjamin Müller]

Dear Anna,

I have not much experience with early branching in SCIP and thus I hope 
that someone from the mailing list could correct me if I say something 
wrong.

As far as I understand it, the only problem with returning 
SCIP_DIDNOTRUN in your pricer plug-in is that you need to ensure that at 
least one constraint handler marks the current LP solution of the 
restricted master problem to be infeasible and branches. If there is no 
branching candidate then you want to continue with pricing, right?

So couldn't you check the LP solution of the restricted master problem 
in your pricer plug-in for feasibility? If the point is feasible (but 
not optimal!) then you need to continue with pricing. If the point is 
infeasible then this should mean that either cons_integer or your 
constraint handler is going to branch (assuming that you are not doing 
Farkas pricing right now).

I don't know exactly what happens if you return SCIP_DIDNOTRUN. 
Probably, SCIP is checking the feasibility of the current LP solution 
and if necessary calls the enforcement methods of the constraint handlers.

Best,
Benjamin

On 4/9/19 1:45 PM, Anna Melchiori wrote:
> Good morning SCIP team,
> 
> I have implemented a Branch and Price approach with a dedicated pricing 
> routine and a branching strategy (in addition to the standard 0-1 
> branching rule).
> To speed up the pricing I want to test an early branching strategy so 
> I'm returning the pointer result=SCIP_DIDNOTRUN in my reduced cost 
> methods whenever a certain criteria is hit.
> At this point I would like the constraint handler (mine first then the 
> standard 0-1) to be called to check feasibility of the approximate 
> solution and in case branch. If no candidate is found I'd like to go 
> back and solve to optimality the LP by column generation.
> 
> Could you please explain me what are the next steps SCIP implements 
> whenever a SCIP_DIDNOTRUN is given from the pricer?
> So far this is not completely clear to me as I am getting different 
> behaviors (check method for primal/pseudo solutions, node is directly 
> discarded, no branch call)
> 
> Thank you so much!!
> Have a nice day
> Anna
> 
> 
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
> 

-- 
______________________________
Benjamin Müller
Zuse Institute Berlin
Takustr. 7, 14195 Berlin
benjamin.mueller at zib.de
+49 30 841 85-195