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

[Xavier Schepler]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20170323/837a1c90/attachment.html>