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

[Xavier Schepler]

I meant :

After re-optimization, the sum over the variables which cover items 1 and 3
is still fractional, and its value is *1.5.* (not 0.5)



2017-03-23 18:45 GMT+01:00 Xavier Schepler <xavier.schepler at gmail.com>:

> Dear Gerald,
>
> Thank you for your response.
>
> 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 ?
> 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.
> 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.
>
> Does it make sense ?
>
> Kind regards,
>
> Xavier
>
>
> 2017-03-23 16:38 GMT+01:00 Gerald Gamrath <gamrath at zib.de>:
>
>> 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 listScip at zib.dehttp://listserv.zib.de/mailman/listinfo/scip
>>
>>
>>
>> _______________________________________________
>> 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/ceeecd59/attachment.html>