<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
Dear Xavier,<br>
<br>
but does your problem have the property, that each subset of a valid
packing is again a valid packing? And each item must be covered once
in the end?<br>
I would say that you can then ignore pairs of variables for which
the sum over the LP values is larger than 1, because you could
post-process this in the end and reduce this value by removing both
items for some packings.<br>
More specifically, you should choose two items such that those are
together in some of the packings selected by the LP solution and
also some packings are selected that contain exactly one of the
items. This is not the case for your example. If you do Ryan and
Foster branching based in this criterion, each variable should have
a value 0 or 1 in the end.<br>
<br>
I hope this makes sense.<br>
<br>
Best,<br>
Gerald<br>
<br>
<br>
<div class="moz-cite-prefix">Am 23.03.2017 um 18:50 schrieb Xavier
Schepler:<br>
</div>
<blockquote
cite="mid:CA+SwSLwqOXvsFRmEWvO8Wr1t5+vaf8NrOYmirv=Yug9XNXkC2g@mail.gmail.com"
type="cite">
<div dir="ltr">
<div>I meant :<br>
<br>
After re-optimization, the sum over the variables which cover
items 1 and 3 is still fractional, and its value is <b>1.5.</b>
(not 0.5)<br>
<br>
</div>
<br>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">2017-03-23 18:45 GMT+01:00 Xavier
Schepler <span dir="ltr"><<a moz-do-not-send="true"
href="mailto:xavier.schepler@gmail.com" target="_blank">xavier.schepler@gmail.com</a>></span>:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<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="HOEnZb">
<div class="h5">
<div class="gmail_extra"><br>
<div class="gmail_quote">2017-03-23 16:38 GMT+01:00
Gerald Gamrath <span dir="ltr"><<a
moz-do-not-send="true"
href="mailto:gamrath@zib.de" target="_blank"><a class="moz-txt-link-abbreviated" href="mailto:gamrath@zib.de">gamrath@zib.de</a></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="m_-3460604176725813753h5"><br>
<br>
<div
class="m_-3460604176725813753m_3956173086178731958moz-cite-prefix">On
23.03.2017 16:09, Xavier Schepler wrote:<br>
</div>
</div>
</div>
<blockquote type="cite">
<div>
<div class="m_-3460604176725813753h5">
<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_-3460604176725813753m_3956173086178731958gmail-cm">/* compute weigthts for each order pair */</span>
<span class="m_-3460604176725813753m_3956173086178731958gmail-k">for</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-p">(</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">v</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-o">=</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-mi">0</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">;</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">v</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-o"><</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">nlpcands</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">;</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-o">++</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">v</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">)</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-p">{</span>
<a moz-do-not-send="true" name="m_-3460604176725813753_m_3956173086178731958_branch_ryanfoster.c-174"></a> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">assert</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">(</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">lpcands</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">[</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">v</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">]</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-o">!=</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-nb">NULL</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">);</span>
<span class="m_-3460604176725813753m_3956173086178731958gmail-cm">/* get variable data which contains the information to which constraints/items the variable belongs */</span>
<a moz-do-not-send="true" name="m_-3460604176725813753_m_3956173086178731958_branch_ryanfoster.c-177"></a> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">vardata</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-o">=</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">SCIPvarGetData</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">(</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">lpcands</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">[</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">v</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">]);</span>
<span class="m_-3460604176725813753m_3956173086178731958gmail-n">consids</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-o">=</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">SCIPvardataGetConsids</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">(</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">vardata</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">)<wbr>;</span>
<a moz-do-not-send="true" name="m_-3460604176725813753_m_3956173086178731958_branch_ryanfoster.c-180"></a> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">nconsids</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-o">=</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">SCIPvardataGetNConsids</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">(</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">vardata</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p"><wbr>);</span>
<a moz-do-not-send="true" name="m_-3460604176725813753_m_3956173086178731958_branch_ryanfoster.c-181"></a> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">assert</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">(</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">nconsids</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-o">></span> <span class="m_-3460604176725813753m_3956173086178731958gmail-mi">0</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">);</span>
<span class="m_-3460604176725813753m_3956173086178731958gmail-cm">/* loop over all constraints/items the variable belongs to */</span>
<a moz-do-not-send="true" name="m_-3460604176725813753_m_3956173086178731958_branch_ryanfoster.c-184"></a> <span class="m_-3460604176725813753m_3956173086178731958gmail-k">for</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-p">(</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">i</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-o">=</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-mi">0</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">;</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">i</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-o"><</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">nconsids</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">;</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-o">++</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">i</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">)</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-p">{</span>
<a moz-do-not-send="true" name="m_-3460604176725813753_m_3956173086178731958_branch_ryanfoster.c-185"></a> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">id1</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-o">=</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">consids</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">[</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">i</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">];</span>
<a moz-do-not-send="true" name="m_-3460604176725813753_m_3956173086178731958_branch_ryanfoster.c-186"></a> <span class="m_-3460604176725813753m_3956173086178731958gmail-k">for</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-p">(</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">j</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-o">=</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">i</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-o">+</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-mi">1</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">;</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">j</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-o"><</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">nconsids</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">;</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-o">++</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">j</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">)</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-p">{</span>
<a moz-do-not-send="true" name="m_-3460604176725813753_m_3956173086178731958_branch_ryanfoster.c-187"></a> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">id2</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-o">=</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">consids</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">[</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">j</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">];</span>
<a moz-do-not-send="true" name="m_-3460604176725813753_m_3956173086178731958_branch_ryanfoster.c-188"></a> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">assert</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">(</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">id1</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-o"><</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">id2</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">);</span>
<a moz-do-not-send="true" name="m_-3460604176725813753_m_3956173086178731958_branch_ryanfoster.c-189"></a> <span class="m_-3460604176725813753m_3956173086178731958gmail-k">if</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-p">(</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">branchpairs</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">[</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">id2</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">][</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">id1</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">])</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-p">{</span>
<a moz-do-not-send="true" name="m_-3460604176725813753_m_3956173086178731958_branch_ryanfoster.c-190"></a> <span class="m_-3460604176725813753m_3956173086178731958gmail-k">continue</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">;</span>
<a moz-do-not-send="true" name="m_-3460604176725813753_m_3956173086178731958_branch_ryanfoster.c-191"></a> <span class="m_-3460604176725813753m_3956173086178731958gmail-p">}</span>
<span class="m_-3460604176725813753m_3956173086178731958gmail-n">pairweights</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">[</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">id2</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">][</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">id1</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">]</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-o">+=</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">lpcandsfrac</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">[</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">v</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">];</span>
<span class="m_-3460604176725813753m_3956173086178731958gmail-n">assert</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">(</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">SCIPisFeasLE</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">(</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">scip</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">,</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">pairweights</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">[</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">id2</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">][</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">id1</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">],</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-mf">1.0</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">));</span>
<a moz-do-not-send="true" name="m_-3460604176725813753_m_3956173086178731958_branch_ryanfoster.c-196"></a> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">assert</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">(</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">SCIPisFeasGE</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">(</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">scip</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">,</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-n">pairweights</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">[</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">id2</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">][</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">id1</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">],</span> <span class="m_-3460604176725813753m_3956173086178731958gmail-mf">0.0</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">));</span>
<a moz-do-not-send="true" name="m_-3460604176725813753_m_3956173086178731958_branch_ryanfoster.c-197"></a> <span class="m_-3460604176725813753m_3956173086178731958gmail-p">}</span>
<a moz-do-not-send="true" name="m_-3460604176725813753_m_3956173086178731958_branch_ryanfoster.c-198"></a> <span class="m_-3460604176725813753m_3956173086178731958gmail-p">}</span>
<a moz-do-not-send="true" name="m_-3460604176725813753_m_3956173086178731958_branch_ryanfoster.c-199"></a><span class="m_-3460604176725813753m_3956173086178731958gmail-p">}</span></pre>
</div>
<div><span class="m_-3460604176725813753m_3956173086178731958gmail-n">branchpairs</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">[</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">id2</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">][</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">id1</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">]</span> <span class="m_-3460604176725813753m_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.
</div>
<div>If a branching was done on the pair id2, id1, then <span class="m_-3460604176725813753m_3956173086178731958gmail-n">pairweights</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">[</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">id2</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">][</span><span class="m_-3460604176725813753m_3956173086178731958gmail-n">id1</span><span class="m_-3460604176725813753m_3956173086178731958gmail-p">] will be
equal to zero, so this pair will not be selected for
branching.
</span></div>
<div><span class="m_-3460604176725813753m_3956173086178731958gmail-p">Am I right ?</span>
</div>
<div>Kind regards,
</div>
<div>Xavier Schepler
</div>
</div>
<fieldset class="m_-3460604176725813753m_3956173086178731958mimeAttachmentHeader"></fieldset>
</div></div><pre>______________________________<wbr>_________________
Scip mailing list
<a moz-do-not-send="true" class="m_-3460604176725813753m_3956173086178731958moz-txt-link-abbreviated" href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a>
<a moz-do-not-send="true" class="m_-3460604176725813753m_3956173086178731958moz-txt-link-freetext" href="http://listserv.zib.de/mailman/listinfo/scip" target="_blank">http://listserv.zib.de/mailman<wbr>/listinfo/scip</a>
</pre>
</blockquote>
</div>
______________________________<wbr>_________________
Scip mailing list
<a moz-do-not-send="true" href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a>
<a moz-do-not-send="true" href="http://listserv.zib.de/mailman/listinfo/scip" rel="noreferrer" target="_blank">http://listserv.zib.de/mailman<wbr>/listinfo/scip</a>
</blockquote></div>
</div>
</div></div></blockquote></div>
</div>
</blockquote>
</body></html>