[SCIP] Bug in the branching rule of the bin packing example ?

[Gerald Gamrath]

Dear Xavier,

I would guess that there is a bug in your pricing problem.

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.

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.

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.

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.

Best,
Gerald

On 23.03.2017 16:09, Xavier Schepler wrote:
> Dear SCIP developers,
>
> 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.
>
> 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.
> 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.
>
> 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.
>
> The code which computes the fractional values of the pair is now as 
> follows :
>
> /* compute weigthts for each order pair */
> for  (v  =  0;  v  <  nlpcands;  ++v)  {
> 	assert(lpcands[v]  !=  NULL);
> 	/* get variable data which contains the information to which 
> constraints/items the variable belongs */
> 	vardata  =  SCIPvarGetData(lpcands[v]);
> 	consids  =  SCIPvardataGetConsids(vardata);
> 	nconsids  =  SCIPvardataGetNConsids(vardata);
> 	assert(nconsids  >  0);
> 	/* loop over all constraints/items the variable belongs to */
> 	for  (i  =  0;  i  <  nconsids;  ++i)  {
> 		id1  =  consids[i];
> 		for  (j  =  i  +  1;  j  <  nconsids;  ++j)  {
> 			id2  =  consids[j];
> 			assert(id1  <  id2);
> 			if  (branchpairs[id2][id1])  {
> 				continue;
> 			}
> 			pairweights[id2][id1]  +=  lpcandsfrac[v];
> 			assert(SCIPisFeasLE(scip,  pairweights[id2][id1],  1.0));
> 			assert(SCIPisFeasGE(scip,  pairweights[id2][id1],  0.0));
> 		}
> 	}
> }
> branchpairs[id2][id1] 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.
>
> If a branching was done on the pair id2, id1, then 
> pairweights[id2][id1] will be equal to zero, so this pair will not be 
> selected for branching.
>
> Am I right ?
>
> Kind regards,
>
> Xavier Schepler
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20170323/486cf42b/attachment.html>