<html dir="ltr">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=windows-1256">
<style type="text/css" id="owaParaStyle"></style>
</head>
<body bgcolor="#ffffff" fpstyle="1" ocsi="0">
<div style="direction: ltr;font-family: Tahoma;color: #000000;font-size: 10pt;">Hi Yongjia,
<div><br>
</div>
<div> Sorry for jumping into the discussion. Got interested in this thread. Maybe I am completely wrong, but it seems to me that if you only do variable branching instead of some fancy constraint branching (say Ryan/Foster), the original pricing routine
should still work even after the branching? Basically you fix a variable in the restricted master formulation, and this will automatically change the dual information. I am not sure how SCIP implement the branching rule, but if it is simply adding a constraint
to the master problem on every new B&B node, maybe the original pricer should still work. </div>
<div><br>
</div>
<div> Sorry for interrupting your discussion. </div>
<div><br>
</div>
<div>Best,</div>
<div>Chiwei <br>
<div style="font-family: Times New Roman; color: #000000; font-size: 16px">
<hr tabindex="-1">
<div id="divRpF389918" style="direction: ltr;"><font face="Tahoma" size="2" color="#000000"><b>From:</b> Scip [scip-bounces@zib.de] on behalf of Yongjia Song [ysong3@vcu.edu]<br>
<b>Sent:</b> Friday, August 07, 2015 10:02 AM<br>
<b>To:</b> Benjamin Müller; SCIP mailing list<br>
<b>Subject:</b> Re: [Scip] Question about branching on master variables in SCIP<br>
</font><br>
</div>
<div></div>
<div>
<div>
<div style="font-family:Calibri,sans-serif; font-size:11pt">Hi Benny,<br>
<br>
Thanks a lot! I actually tried a set partitioning formulation with only master variables, and claim them to be integer so branching has to be done for these variables. I only specify a pricer as the one in the VRP example. Will Scip automatically take care
of the extra complication in pricing because of branching? I actually tried this, and sometimes it gave the correct solution(maybe out of luck) but it also happened that no progress is made at all after the root. Any explanation on this? Thanks a lot!<br>
<br>
Best,</div>
</div>
<div dir="ltr">
<hr>
<span style="font-family:Calibri,sans-serif; font-size:11pt; font-weight:bold">From:
</span><span style="font-family:Calibri,sans-serif; font-size:11pt"><a href="mailto:benjamin.mueller@zib.de" target="_blank">Benjamin Müller</a></span><br>
<span style="font-family:Calibri,sans-serif; font-size:11pt; font-weight:bold">Sent:
</span><span style="font-family:Calibri,sans-serif; font-size:11pt">ı8/ı7/ı2015 3:50 AM</span><br>
<span style="font-family:Calibri,sans-serif; font-size:11pt; font-weight:bold">To:
</span><span style="font-family:Calibri,sans-serif; font-size:11pt"><a href="mailto:ysong3@vcu.edu" target="_blank">Yongjia Song</a>;
<a href="mailto:scip@zib.de" target="_blank">SCIP mailing list</a></span><br>
<span style="font-family:Calibri,sans-serif; font-size:11pt; font-weight:bold">Subject:
</span><span style="font-family:Calibri,sans-serif; font-size:11pt">Re: [Scip] Question about branching on master variables in SCIP</span><br>
<br>
</div>
Hi Yongjia,<br>
<br>
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).
<br>
<br>
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).<br>
<br>
<br>
Best,<br>
<br>
Benny<br>
<br>
<br>
<div class="moz-cite-prefix">On 08/06/2015 08:01 PM, Yongjia Song wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">Hi all,
<div><br>
</div>
<div>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!</div>
<div><br>
</div>
<div>Best,<br clear="all">
<div><br>
</div>
-- <br>
<div class="gmail_signature">
<div dir="ltr">
<div>SONG, Yongjia</div>
<div>Assistant Professor</div>
<div>Department of Statistical Sciences and Operations Research</div>
<div>Virginia Commonwealth University </div>
<div>PO Box 843083 </div>
<div>Richmond, VA 23284-3083 </div>
<div>804-828-1149<br>
</div>
<div><a href="mailto:Ysong3@vcu.edu" target="_blank">Ysong3@vcu.edu</a></div>
</div>
</div>
</div>
</div>
<br>
<fieldset class="mimeAttachmentHeader" target="_blank"></fieldset> <br>
<pre>_______________________________________________
Scip mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a>
<a class="moz-txt-link-freetext" href="http://listserv.zib.de/mailman/listinfo/scip" target="_blank">http://listserv.zib.de/mailman/listinfo/scip</a>
</pre>
</blockquote>
<br>
<pre class="moz-signature" cols="72">--
______________________________
Benjamin Müller
Zuse Institute Berlin
Takustr. 7, 14195 Berlin
<a class="moz-txt-link-abbreviated" href="mailto:benjamin.mueller@zib.de" target="_blank">benjamin.mueller@zib.de</a>
+49 30 841 85-195</pre>
</div>
</div>
</div>
</div>
</body>
</html>