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

Fri Mar 24 12:12:14 CET 2017

Dear Gerald,

Ok, I get it, there is something wrong with my part of the code :o)

Thank  you very much for your help !

Kind regards,

Xavier

2017-03-24 12:00 GMT+01:00 Gerald Gamrath <gamrath at zib.de>:

> Dear Xavier,
>
> I agree that this is confusing, but I guess the example is doing the right
> thing. Because after summing up the LP values for the pairs of variables,
> you do not check this for fractionality, but take
>
> value = MIN(pairweights[i][j], 1-pairweights[i][j]);
> and compare this to the bestvalue which is initialized to 0.0. So if the
> pairweight is larger than 1, the min is always negative and this variable
> will not be chosen as a branching candidate. I'm not sure this case was
> taken into account when writing this code, but it seems to work anyway. :-)
>
> Best,
> Gerald
>
>
>
> On 24.03.2017 09:45, Xavier Schepler wrote:
>
> Dear Gerald,
>
> Yes, my problem has this property, that each subset of a valid packing is
> again a valid packing. Each item must be covered once in the end.
>
> You are totally right : I 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.
>
> What looks like a bug to me is that in the file branch_ryanfoster.c of the
> bin-packing example, the only thing that is checked to select the branching
> candidate is that the sum over the pair of items is fractional, but it is
> not checked if at the same time there is a packing that contains exactly
> one of the items with a fractional value.
>
> There would be at least two ways to correct that : check if a branching
> was done before on the pair (what I do), or check if at the same time there
> is packing that contains exactly one of the items with a fractional value.
>
> Kind regards,
>
> Xavier Schepler
>
> 2017-03-23 23:00 GMT+01:00 Gerald Gamrath <gamrath at zib.de>:
>
>> Dear Xavier,
>>
>> 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?
>> 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.
>> 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.
>>
>> I hope this makes sense.
>>
>> Best,
>> Gerald
>>
>>
>>
>> Am 23.03.2017 um 18:50 schrieb 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/20170324/70f11ab6/attachment.html>