<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p>Dear Xavier,</p>
<p>I would guess that there is a bug in your pricing problem.</p>
<p>Normally, if you branch on items i and j and go into, say, the
child node where SAME(i,j) should hold, you fix all packings
locally to 0, which contain exactly one of the two items. But
additionally, you need to adjust your pricing problem, so that no
further packings with that property are priced in in this subtree,
say by adding a constraint x_i = x_j. Note that variables are
always valid globally, so if you jump through the tree and come
back to this sub-tree later on, you need to repropagate the node
again to make sure that variables generated in between also stick
to the branching decision.</p>
<p>This works fine for set partitioning problems or set covering
problems if you can ensure that there is always at least one
optimal solution which would be feasible for the corresponding set
partitioning problem.</p>
<p>If in your problem, this is not the case and there is no optimal
solution which fulfills all constraints with equality, I fear you
cannot use Ryan and Foster branching.</p>
<p>Your fix might cure the symptoms, but I guess the bug itself
persists. Because if you did some branching on SAME(i,j) before,
there should not be any incentive to do the same branching again.
If there is, then the old branching was actually not strictly
enforced, and as such, you might now choose to not do the same
branching again, but you might end up with a situation where you
performed all possible branching but are still not feasible, since
as it seems, your branchings are not (always) respected.</p>
Best,<br>
Gerald<br>
<br>
<div class="moz-cite-prefix">On 23.03.2017 16:09, Xavier Schepler
wrote:<br>
</div>
<blockquote
cite="mid:CA+SwSLxUqxeohTgP+uQq620CvtmNwmLZHLjYy_rUaLp6ZwsgsQ@mail.gmail.com"
type="cite">
<div dir="ltr">
<div>
<div>Dear SCIP developers,<br>
<br>
</div>
I'm working on a variant of the bin-packing problem. I started
from the example of a branch-and-price algorithm for the bin
packing problem provided with SCIP 3.2.1. It uses the Ryan and
Foster branching rule.<br>
<br>
</div>
<div>However, the master problem is a set cover problem, so,
potentially, after branching on a pair of item, it may happen
that this same pair of items comes up again with a fractional
sum value in a child node.<br>
</div>
<div>To avoid this problem, we must ensure that the pair
selected for branching has not been selected before in an
ancestor for branching. If it has, another pair must be
selected.<br>
<br>
</div>
<div>Before adding a piece of code that checks if a pair was
selected before for branching, I had my program branching
again and again on the same pair of variable, for one
particular instance.<br>
<br>
</div>
<div>The code which computes the fractional values of the pair
is now as follows :<br>
<br>
<pre><span class="gmail-cm">/* compute weigthts for each order pair */</span>
<span class="gmail-k">for</span> <span class="gmail-p">(</span><span class="gmail-n">v</span> <span class="gmail-o">=</span> <span class="gmail-mi">0</span><span class="gmail-p">;</span> <span class="gmail-n">v</span> <span class="gmail-o"><</span> <span class="gmail-n">nlpcands</span><span class="gmail-p">;</span> <span class="gmail-o">++</span><span class="gmail-n">v</span><span class="gmail-p">)</span> <span class="gmail-p">{</span>
<a moz-do-not-send="true" name="branch_ryanfoster.c-174"></a> <span class="gmail-n">assert</span><span class="gmail-p">(</span><span class="gmail-n">lpcands</span><span class="gmail-p">[</span><span class="gmail-n">v</span><span class="gmail-p">]</span> <span class="gmail-o">!=</span> <span class="gmail-nb">NULL</span><span class="gmail-p">);</span>
<span class="gmail-cm">/* get variable data which contains the information to which constraints/items the variable belongs */</span>
<a moz-do-not-send="true" name="branch_ryanfoster.c-177"></a> <span class="gmail-n">vardata</span> <span class="gmail-o">=</span> <span class="gmail-n">SCIPvarGetData</span><span class="gmail-p">(</span><span class="gmail-n">lpcands</span><span class="gmail-p">[</span><span class="gmail-n">v</span><span class="gmail-p">]);</span>
<span class="gmail-n">consids</span> <span class="gmail-o">=</span> <span class="gmail-n">SCIPvardataGetConsids</span><span class="gmail-p">(</span><span class="gmail-n">vardata</span><span class="gmail-p">);</span>
<a moz-do-not-send="true" name="branch_ryanfoster.c-180"></a> <span class="gmail-n">nconsids</span> <span class="gmail-o">=</span> <span class="gmail-n">SCIPvardataGetNConsids</span><span class="gmail-p">(</span><span class="gmail-n">vardata</span><span class="gmail-p">);</span>
<a moz-do-not-send="true" name="branch_ryanfoster.c-181"></a> <span class="gmail-n">assert</span><span class="gmail-p">(</span><span class="gmail-n">nconsids</span> <span class="gmail-o">></span> <span class="gmail-mi">0</span><span class="gmail-p">);</span>
<span class="gmail-cm">/* loop over all constraints/items the variable belongs to */</span>
<a moz-do-not-send="true" name="branch_ryanfoster.c-184"></a> <span class="gmail-k">for</span> <span class="gmail-p">(</span><span class="gmail-n">i</span> <span class="gmail-o">=</span> <span class="gmail-mi">0</span><span class="gmail-p">;</span> <span class="gmail-n">i</span> <span class="gmail-o"><</span> <span class="gmail-n">nconsids</span><span class="gmail-p">;</span> <span class="gmail-o">++</span><span class="gmail-n">i</span><span class="gmail-p">)</span> <span class="gmail-p">{</span>
<a moz-do-not-send="true" name="branch_ryanfoster.c-185"></a> <span class="gmail-n">id1</span> <span class="gmail-o">=</span> <span class="gmail-n">consids</span><span class="gmail-p">[</span><span class="gmail-n">i</span><span class="gmail-p">];</span>
<a moz-do-not-send="true" name="branch_ryanfoster.c-186"></a> <span class="gmail-k">for</span> <span class="gmail-p">(</span><span class="gmail-n">j</span> <span class="gmail-o">=</span> <span class="gmail-n">i</span> <span class="gmail-o">+</span> <span class="gmail-mi">1</span><span class="gmail-p">;</span> <span class="gmail-n">j</span> <span class="gmail-o"><</span> <span class="gmail-n">nconsids</span><span class="gmail-p">;</span> <span class="gmail-o">++</span><span class="gmail-n">j</span><span class="gmail-p">)</span> <span class="gmail-p">{</span>
<a moz-do-not-send="true" name="branch_ryanfoster.c-187"></a> <span class="gmail-n">id2</span> <span class="gmail-o">=</span> <span class="gmail-n">consids</span><span class="gmail-p">[</span><span class="gmail-n">j</span><span class="gmail-p">];</span>
<a moz-do-not-send="true" name="branch_ryanfoster.c-188"></a> <span class="gmail-n">assert</span><span class="gmail-p">(</span><span class="gmail-n">id1</span> <span class="gmail-o"><</span> <span class="gmail-n">id2</span><span class="gmail-p">);</span>
<a moz-do-not-send="true" name="branch_ryanfoster.c-189"></a> <span class="gmail-k">if</span> <span class="gmail-p">(</span><span class="gmail-n">branchpairs</span><span class="gmail-p">[</span><span class="gmail-n">id2</span><span class="gmail-p">][</span><span class="gmail-n">id1</span><span class="gmail-p">])</span> <span class="gmail-p">{</span>
<a moz-do-not-send="true" name="branch_ryanfoster.c-190"></a> <span class="gmail-k">continue</span><span class="gmail-p">;</span>
<a moz-do-not-send="true" name="branch_ryanfoster.c-191"></a> <span class="gmail-p">}</span>
<span class="gmail-n">pairweights</span><span class="gmail-p">[</span><span class="gmail-n">id2</span><span class="gmail-p">][</span><span class="gmail-n">id1</span><span class="gmail-p">]</span> <span class="gmail-o">+=</span> <span class="gmail-n">lpcandsfrac</span><span class="gmail-p">[</span><span class="gmail-n">v</span><span class="gmail-p">];</span>
<span class="gmail-n">assert</span><span class="gmail-p">(</span><span class="gmail-n">SCIPisFeasLE</span><span class="gmail-p">(</span><span class="gmail-n">scip</span><span class="gmail-p">,</span> <span class="gmail-n">pairweights</span><span class="gmail-p">[</span><span class="gmail-n">id2</span><span class="gmail-p">][</span><span class="gmail-n">id1</span><span class="gmail-p">],</span> <span class="gmail-mf">1.0</span><span class="gmail-p">));</span>
<a moz-do-not-send="true" name="branch_ryanfoster.c-196"></a> <span class="gmail-n">assert</span><span class="gmail-p">(</span><span class="gmail-n">SCIPisFeasGE</span><span class="gmail-p">(</span><span class="gmail-n">scip</span><span class="gmail-p">,</span> <span class="gmail-n">pairweights</span><span class="gmail-p">[</span><span class="gmail-n">id2</span><span class="gmail-p">][</span><span class="gmail-n">id1</span><span class="gmail-p">],</span> <span class="gmail-mf">0.0</span><span class="gmail-p">));</span>
<a moz-do-not-send="true" name="branch_ryanfoster.c-197"></a> <span class="gmail-p">}</span>
<a moz-do-not-send="true" name="branch_ryanfoster.c-198"></a> <span class="gmail-p">}</span>
<a moz-do-not-send="true" name="branch_ryanfoster.c-199"></a><span class="gmail-p">}</span></pre>
</div>
<div><span class="gmail-n">branchpairs</span><span
class="gmail-p">[</span><span class="gmail-n">id2</span><span
class="gmail-p">][</span><span class="gmail-n">id1</span><span
class="gmail-p">]</span> <span class="gmail-p"></span> is
equal to zero if no branching constraints exists on the pair
{id2, id1} for the current node, and it is equal to one
otherwise.<br>
<br>
</div>
<div>If a branching was done on the pair id2, id1, then <span
class="gmail-n">pairweights</span><span class="gmail-p">[</span><span
class="gmail-n">id2</span><span class="gmail-p">][</span><span
class="gmail-n">id1</span><span class="gmail-p">] will be
equal to zero, so this pair will not be selected for
branching.<br>
<br>
</span></div>
<div><span class="gmail-p">Am I right ?</span><br>
<br>
</div>
<div>Kind regards,<br>
<br>
</div>
<div>Xavier Schepler<br>
</div>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Scip mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Scip@zib.de">Scip@zib.de</a>
<a class="moz-txt-link-freetext" href="http://listserv.zib.de/mailman/listinfo/scip">http://listserv.zib.de/mailman/listinfo/scip</a>
</pre>
</blockquote>
<br>
</body>
</html>