<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 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 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 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 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 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 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 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 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 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 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 name="branch_ryanfoster.c-190"></a>                            <span class="gmail-k">continue</span><span class="gmail-p">;</span>
<a 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 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 name="branch_ryanfoster.c-197"></a>            <span class="gmail-p">}</span>
<a name="branch_ryanfoster.c-198"></a>    <span class="gmail-p">}</span>
<a 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>