I'm using the Ryan-Foster branching in my Branch and Price algorithm for a pickup and delivery problem, but I'm having trouble keeping track of all the pairs as I go down the search tree.
Let's say that at a given point, I create a new node with the rule that elements 1 and 2 should be chosen together. Further down, in the same branch, a new node is created with the rule that 1 and 3 should not be chosen together. Given this new rule, it's clear that elements 2 and 3 should not be chosen together as well, and I could add this new rule to my set. I believe that whenever a new rule is generated I could create a graph G with the elements as nodes and the rules as weighted edges: w(a,b) = 1 if a and b should be together, and -1 if they can't be together. Some traversal in G would allow the generation of new rules or even the detection of a infeasibility. The image below translates my example in G with the dotted edge being the possible new generated edge.
My question is: Is there a known algorithm that does this kind of generation of new edges mentioned above?
UPDATE:
I've implemented the following search, that seems to be working with all my instances. If there's a known algorithm I would love to know if it's better than this or if I'm doing something wrong here:
// M is the adjacency matrix for the graph above. s is the
// initial node (it can be any of the elements of the new rule)
void expand_conflicts(vector<vector<short>>& M, short s){
using namespace std;
const short n = M.size();
queue<short> Q;
vector<bool> visited(n, false);
Q.push(s);
while(!Q.empty()){
short u = Q.front(); Q.pop();
visited[u] = true;
queue<short> Q_u;
for(short v = 0; v < n; ++v){
if(u != v && M[u][v] != 0){
Q_u.push(v);
}
}
while(!Q_u.empty()){
short v = Q_u.front(); Q_u.pop();
short c_uv = M[u][v];
for(short w = 0; w < n; ++w){
auto c_vw = M[v][w];
if(v != w && M[u][w] == 0 &&
((c_uv == -1 && c_vw == 1) ||
(c_uv == 1 && c_vw == -1))){
M[u][w] = M[w][u] = -1;
Q_u.push(w);
}else if(v != w && c_uv == 1 && c_vw == 1 &&
M[u][w] == 0){
M[u][w] = M[w][u] = 1;
Q_u.push(w);
}
}
if(!visited[v]){
Q.push(v);
}
}
}
}