<div dir="ltr"><div><div><div>Dear Gerald,<br><br></div>Thank you for your response.<br></div><br>Assume that a branching constraint was added, enforcing that items 1 and 3 must be in the same bin. The variables that do not satisfy this constraint were deleted. The resulting LP is the one in the attached file. After re-optimization, the sum over the variables which cover items 1 and 3 is still fractional, and its value is 0.5. Assume that no improving variable is priced out, during the column generation phase. What does prevent the same branching constraint to be generated again ?<br></div><div>This is because, in the case of a set covering problem, the sum over the variables which cover items 1 and 3 can be greater than one and fractional, which can not happen with a set partitionning problem.<br></div><div>So, my opinion is that, with the set covering formulation, in the case of a fractional sum value for a pair of a items, it must be checked whether the branching constraint is satisfied (i.e. that it is already exists), and only in the case that is is not, to create it.<br><br></div><div>Does it make sense ?<br></div><div><br></div><div>Kind regards,<br></div><div><br></div><div>Xavier<br></div><br></div><div class="gmail_extra"><br><div class="gmail_quote">2017-03-23 16:38 GMT+01:00 Gerald Gamrath <span dir="ltr"><<a href="mailto:gamrath@zib.de" target="_blank">gamrath@zib.de</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div 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<div><div class="h5"><br>
<br>
<div class="m_3956173086178731958moz-cite-prefix">On 23.03.2017 16:09, Xavier Schepler
wrote:<br>
</div>
</div></div><blockquote type="cite"><div><div class="h5">
<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="m_3956173086178731958gmail-cm">/* compute weigthts for each order pair */</span>
<span class="m_3956173086178731958gmail-k">for</span> <span class="m_3956173086178731958gmail-p">(</span><span class="m_3956173086178731958gmail-n">v</span> <span class="m_3956173086178731958gmail-o">=</span> <span class="m_3956173086178731958gmail-mi">0</span><span class="m_3956173086178731958gmail-p">;</span> <span class="m_3956173086178731958gmail-n">v</span> <span class="m_3956173086178731958gmail-o"><</span> <span class="m_3956173086178731958gmail-n">nlpcands</span><span class="m_3956173086178731958gmail-p">;</span> <span class="m_3956173086178731958gmail-o">++</span><span class="m_3956173086178731958gmail-n">v</span><span class="m_3956173086178731958gmail-p">)</span> <span class="m_3956173086178731958gmail-p">{</span>
<a name="m_3956173086178731958_branch_ryanfoster.c-174"></a> <span class="m_3956173086178731958gmail-n">assert</span><span class="m_3956173086178731958gmail-p">(</span><span class="m_3956173086178731958gmail-n">lpcands</span><span class="m_3956173086178731958gmail-p">[</span><span class="m_3956173086178731958gmail-n">v</span><span class="m_3956173086178731958gmail-p">]</span> <span class="m_3956173086178731958gmail-o">!=</span> <span class="m_3956173086178731958gmail-nb">NULL</span><span class="m_3956173086178731958gmail-p">);</span>
<span class="m_3956173086178731958gmail-cm">/* get variable data which contains the information to which constraints/items the variable belongs */</span>
<a name="m_3956173086178731958_branch_ryanfoster.c-177"></a> <span class="m_3956173086178731958gmail-n">vardata</span> <span class="m_3956173086178731958gmail-o">=</span> <span class="m_3956173086178731958gmail-n">SCIPvarGetData</span><span class="m_3956173086178731958gmail-p">(</span><span class="m_3956173086178731958gmail-n">lpcands</span><span class="m_3956173086178731958gmail-p">[</span><span class="m_3956173086178731958gmail-n">v</span><span class="m_3956173086178731958gmail-p">]);</span>
<span class="m_3956173086178731958gmail-n">consids</span> <span class="m_3956173086178731958gmail-o">=</span> <span class="m_3956173086178731958gmail-n">SCIPvardataGetConsids</span><span class="m_3956173086178731958gmail-p">(</span><span class="m_3956173086178731958gmail-n">vardata</span><span class="m_3956173086178731958gmail-p">)<wbr>;</span>
<a name="m_3956173086178731958_branch_ryanfoster.c-180"></a> <span class="m_3956173086178731958gmail-n">nconsids</span> <span class="m_3956173086178731958gmail-o">=</span> <span class="m_3956173086178731958gmail-n">SCIPvardataGetNConsids</span><span class="m_3956173086178731958gmail-p">(</span><span class="m_3956173086178731958gmail-n">vardata</span><span class="m_3956173086178731958gmail-p"><wbr>);</span>
<a name="m_3956173086178731958_branch_ryanfoster.c-181"></a> <span class="m_3956173086178731958gmail-n">assert</span><span class="m_3956173086178731958gmail-p">(</span><span class="m_3956173086178731958gmail-n">nconsids</span> <span class="m_3956173086178731958gmail-o">></span> <span class="m_3956173086178731958gmail-mi">0</span><span class="m_3956173086178731958gmail-p">);</span>
<span class="m_3956173086178731958gmail-cm">/* loop over all constraints/items the variable belongs to */</span>
<a name="m_3956173086178731958_branch_ryanfoster.c-184"></a> <span class="m_3956173086178731958gmail-k">for</span> <span class="m_3956173086178731958gmail-p">(</span><span class="m_3956173086178731958gmail-n">i</span> <span class="m_3956173086178731958gmail-o">=</span> <span class="m_3956173086178731958gmail-mi">0</span><span class="m_3956173086178731958gmail-p">;</span> <span class="m_3956173086178731958gmail-n">i</span> <span class="m_3956173086178731958gmail-o"><</span> <span class="m_3956173086178731958gmail-n">nconsids</span><span class="m_3956173086178731958gmail-p">;</span> <span class="m_3956173086178731958gmail-o">++</span><span class="m_3956173086178731958gmail-n">i</span><span class="m_3956173086178731958gmail-p">)</span> <span class="m_3956173086178731958gmail-p">{</span>
<a name="m_3956173086178731958_branch_ryanfoster.c-185"></a> <span class="m_3956173086178731958gmail-n">id1</span> <span class="m_3956173086178731958gmail-o">=</span> <span class="m_3956173086178731958gmail-n">consids</span><span class="m_3956173086178731958gmail-p">[</span><span class="m_3956173086178731958gmail-n">i</span><span class="m_3956173086178731958gmail-p">];</span>
<a name="m_3956173086178731958_branch_ryanfoster.c-186"></a> <span class="m_3956173086178731958gmail-k">for</span> <span class="m_3956173086178731958gmail-p">(</span><span class="m_3956173086178731958gmail-n">j</span> <span class="m_3956173086178731958gmail-o">=</span> <span class="m_3956173086178731958gmail-n">i</span> <span class="m_3956173086178731958gmail-o">+</span> <span class="m_3956173086178731958gmail-mi">1</span><span class="m_3956173086178731958gmail-p">;</span> <span class="m_3956173086178731958gmail-n">j</span> <span class="m_3956173086178731958gmail-o"><</span> <span class="m_3956173086178731958gmail-n">nconsids</span><span class="m_3956173086178731958gmail-p">;</span> <span class="m_3956173086178731958gmail-o">++</span><span class="m_3956173086178731958gmail-n">j</span><span class="m_3956173086178731958gmail-p">)</span> <span class="m_3956173086178731958gmail-p">{</span>
<a name="m_3956173086178731958_branch_ryanfoster.c-187"></a> <span class="m_3956173086178731958gmail-n">id2</span> <span class="m_3956173086178731958gmail-o">=</span> <span class="m_3956173086178731958gmail-n">consids</span><span class="m_3956173086178731958gmail-p">[</span><span class="m_3956173086178731958gmail-n">j</span><span class="m_3956173086178731958gmail-p">];</span>
<a name="m_3956173086178731958_branch_ryanfoster.c-188"></a> <span class="m_3956173086178731958gmail-n">assert</span><span class="m_3956173086178731958gmail-p">(</span><span class="m_3956173086178731958gmail-n">id1</span> <span class="m_3956173086178731958gmail-o"><</span> <span class="m_3956173086178731958gmail-n">id2</span><span class="m_3956173086178731958gmail-p">);</span>
<a name="m_3956173086178731958_branch_ryanfoster.c-189"></a> <span class="m_3956173086178731958gmail-k">if</span> <span class="m_3956173086178731958gmail-p">(</span><span class="m_3956173086178731958gmail-n">branchpairs</span><span class="m_3956173086178731958gmail-p">[</span><span class="m_3956173086178731958gmail-n">id2</span><span class="m_3956173086178731958gmail-p">][</span><span class="m_3956173086178731958gmail-n">id1</span><span class="m_3956173086178731958gmail-p">])</span> <span class="m_3956173086178731958gmail-p">{</span>
<a name="m_3956173086178731958_branch_ryanfoster.c-190"></a> <span class="m_3956173086178731958gmail-k">continue</span><span class="m_3956173086178731958gmail-p">;</span>
<a name="m_3956173086178731958_branch_ryanfoster.c-191"></a> <span class="m_3956173086178731958gmail-p">}</span>
<span class="m_3956173086178731958gmail-n">pairweights</span><span class="m_3956173086178731958gmail-p">[</span><span class="m_3956173086178731958gmail-n">id2</span><span class="m_3956173086178731958gmail-p">][</span><span class="m_3956173086178731958gmail-n">id1</span><span class="m_3956173086178731958gmail-p">]</span> <span class="m_3956173086178731958gmail-o">+=</span> <span class="m_3956173086178731958gmail-n">lpcandsfrac</span><span class="m_3956173086178731958gmail-p">[</span><span class="m_3956173086178731958gmail-n">v</span><span class="m_3956173086178731958gmail-p">];</span>
<span class="m_3956173086178731958gmail-n">assert</span><span class="m_3956173086178731958gmail-p">(</span><span class="m_3956173086178731958gmail-n">SCIPisFeasLE</span><span class="m_3956173086178731958gmail-p">(</span><span class="m_3956173086178731958gmail-n">scip</span><span class="m_3956173086178731958gmail-p">,</span> <span class="m_3956173086178731958gmail-n">pairweights</span><span class="m_3956173086178731958gmail-p">[</span><span class="m_3956173086178731958gmail-n">id2</span><span class="m_3956173086178731958gmail-p">][</span><span class="m_3956173086178731958gmail-n">id1</span><span class="m_3956173086178731958gmail-p">],</span> <span class="m_3956173086178731958gmail-mf">1.0</span><span class="m_3956173086178731958gmail-p">));</span>
<a name="m_3956173086178731958_branch_ryanfoster.c-196"></a> <span class="m_3956173086178731958gmail-n">assert</span><span class="m_3956173086178731958gmail-p">(</span><span class="m_3956173086178731958gmail-n">SCIPisFeasGE</span><span class="m_3956173086178731958gmail-p">(</span><span class="m_3956173086178731958gmail-n">scip</span><span class="m_3956173086178731958gmail-p">,</span> <span class="m_3956173086178731958gmail-n">pairweights</span><span class="m_3956173086178731958gmail-p">[</span><span class="m_3956173086178731958gmail-n">id2</span><span class="m_3956173086178731958gmail-p">][</span><span class="m_3956173086178731958gmail-n">id1</span><span class="m_3956173086178731958gmail-p">],</span> <span class="m_3956173086178731958gmail-mf">0.0</span><span class="m_3956173086178731958gmail-p">));</span>
<a name="m_3956173086178731958_branch_ryanfoster.c-197"></a> <span class="m_3956173086178731958gmail-p">}</span>
<a name="m_3956173086178731958_branch_ryanfoster.c-198"></a> <span class="m_3956173086178731958gmail-p">}</span>
<a name="m_3956173086178731958_branch_ryanfoster.c-199"></a><span class="m_3956173086178731958gmail-p">}</span></pre>
</div>
<div><span class="m_3956173086178731958gmail-n">branchpairs</span><span class="m_3956173086178731958gmail-p">[</span><span class="m_3956173086178731958gmail-n">id2</span><span class="m_3956173086178731958gmail-p">][</span><span class="m_3956173086178731958gmail-n">id1</span><span class="m_3956173086178731958gmail-p">]</span> <span class="m_3956173086178731958gmail-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="m_3956173086178731958gmail-n">pairweights</span><span class="m_3956173086178731958gmail-p">[</span><span class="m_3956173086178731958gmail-n">id2</span><span class="m_3956173086178731958gmail-p">][</span><span class="m_3956173086178731958gmail-n">id1</span><span class="m_3956173086178731958gmail-p">] will be
equal to zero, so this pair will not be selected for
branching.<br>
<br>
</span></div>
<div><span class="m_3956173086178731958gmail-p">Am I right ?</span><br>
<br>
</div>
<div>Kind regards,<br>
<br>
</div>
<div>Xavier Schepler<br>
</div>
</div>
<br>
<fieldset class="m_3956173086178731958mimeAttachmentHeader"></fieldset>
<br>
</div></div><pre>______________________________<wbr>_________________
Scip mailing list
<a class="m_3956173086178731958moz-txt-link-abbreviated" href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a>
<a class="m_3956173086178731958moz-txt-link-freetext" href="http://listserv.zib.de/mailman/listinfo/scip" target="_blank">http://listserv.zib.de/<wbr>mailman/listinfo/scip</a>
</pre>
</blockquote>
<br>
</div>
<br>______________________________<wbr>_________________<br>
Scip mailing list<br>
<a href="mailto:Scip@zib.de">Scip@zib.de</a><br>
<a href="http://listserv.zib.de/mailman/listinfo/scip" rel="noreferrer" target="_blank">http://listserv.zib.de/<wbr>mailman/listinfo/scip</a><br>
<br></blockquote></div><br></div>