[Scip] Question about branching on master variables in SCIP

[Benjamin Müller]

Hi Yongjia,

you are completely right, branching on the reformulated variables does 
change the nature of your pricing problem. If your model does only 
contain the routing variables and you declare them as integral then SCIP 
will branch on those as SCIP would usually do. The user has to respect 
the branching decisions made by SCIP in his pricer. You could add your 
own branching rule in order to branch on the original variables even 
though they are not in the model (see Ryan/Foster branching in the 
Binpacking example).

Note that, in the VRP example the routine variables are continuous and 
thus branching will only be applied on edge variables. Those branching 
decisions does not influence the pricing problem too much (excluding 
edges from the graph).


Best,

Benny


On 08/06/2015 08:01 PM, Yongjia Song wrote:
> Hi all,
>
> I have a question about how SCIP handles branching when only the 
> master variables present in the model. Taking VRP as an example, 
> suppose we only have the route variables (without the original edge 
> variables or the linking constraints between edge variables and route 
> variables), and we impose the integrality constraints on these 
> variables, it is not clear how branching on these variables are 
> implemented in SCIP. Indeed, when a branching decision is made on some 
> route variable, it complicates the pricing by forcing the pricing 
> algorithm to avoid generating that route. Without specific problem 
> structure, it is not clear to me how SCIP handles this case. Thanks a 
> lot for your help!
>
> Best,
>
> -- 
> SONG, Yongjia
> Assistant Professor
> Department of Statistical Sciences and Operations Research
> Virginia Commonwealth University
> PO Box 843083
> Richmond, VA 23284-3083
> 804-828-1149
> Ysong3 at vcu.edu <mailto:Ysong3 at vcu.edu>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20150807/495ab42e/attachment.html>