[SCIP] Bug in the branching rule of the bin packing example ?
Gerald Gamrath
gamrath at zib.de
Mon Mar 27 23:03:54 CEST 2017
Dear Xavier,
you are absolutely right! I missed that you are only looping over the LP
branching candidates in the example, and as you said, this ignores
variables with value 1. So the bug was really in the example code, sorry
for the confusion.
Do you have an instance where this can be reproduced (with the example
code)?
I did a short fix that might be a bit easier than your fix, and also
made a few other things in the code somewhat easier. I will send it to
you in a separate mail, perhaps you can test that it works?
Best,
Gerald
Am 24.03.2017 um 12:26 schrieb Xavier Schepler:
> Dear Gerald,
>
> I tryed again and got the same error, after removing my fix.
> It looks like there is really an error in the code of the example,
> probably because the function SCIPgetLPBranchCands return only
> fractional variables.
>
> What may happen is that a variable standing for a pair may have a
> value equal to 1, so it won't be taken into account when computing the
> sum, which will be between 0 and 1.
>
> What do you think ?
>
> Kind regards,
>
> Xavier
>
>
>
> 2017-03-24 12:12 GMT+01:00 Xavier Schepler <xavier.schepler at gmail.com
> <mailto:xavier.schepler at gmail.com>>:
>
> 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
> <mailto: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
>> <mailto: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
>>> <mailto: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 <mailto: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 list
>>>> Scip at zib.de <mailto:Scip at zib.de>
>>>> http://listserv.zib.de/mailman/listinfo/scip
>>>> <http://listserv.zib.de/mailman/listinfo/scip>
>>> _______________________________________________
>>> Scip mailing list Scip at zib.de
>>> <mailto:Scip at zib.de>
>>> http://listserv.zib.de/mailman/listinfo/scip
>>> <http://listserv.zib.de/mailman/listinfo/scip>
>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20170327/99599201/attachment.html>
More information about the Scip
mailing list