Name of graph algorithm arising while using the Ryan Foster Branching

Question

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);
            }
        }
    }
}

Answer 1

Let $U$ be the universe (e.g. total set of elements). Then, if I understand your post correctly, you are looking for a function which given two elements $e_1,e_2\in U, e_1\neq e_2$, tells you if they should be chosen together (I will call this a SAME constraint), chosen different (DIFFER constraint) or are unrestricted.

First, consider only SAME constraints. As this is a transitive operation (e.g. if $x_1$ and $x_2$ are chosen together and $x_1$ and $x_3$ are chosen together, then also $x_2$ and $x_3$ are chosen together), we can partition $U$ into sets of items $S_1,\dots S_k$ where all elements in each set should be chosen together. For your example you would get that $S_1=\{1,2\}, S_2=\{3\}$. At the initialization of the branch-and-price algorithm, you would then have a partition with only single element sets $S_i=\{e_i\}$ for all elements $e_i\in U$. If you then require that two elements $e_1$ and $e_2$ are chosen together, you can keep track of this in the partition by taking the two sets in which they belong $S_1,S_2$, and replacing them by $S_1\cup S_2$.

In order to keep track of the DIFFER constraints, let $G$ be an undirected graph which has the sets $S_i$ as nodes. Then, a DIFFER constraint for $e_1\in S_1, e_2\in S_2$ is applied by adding an edge between $S_1$ and $S_2$. When you apply a SAME constraint to two nodes $e_1\in S_1$ and $e_2\in S_2$, then contract $S_1$ and $S_2$ in $G$ to become a single node, merging their neighbourhoods. Then, infeasibility can be observed if we either try to apply SAME to contract two nodes $S_1,S_2$ which are already connected by an edge in $G$ or if the two nodes from a DIFFER constraint are in the same set S.

In order to find the 'extra edges' for a SAME constraint on $e_1\in S_1$ and $e_2\in S_2$, iterate over all pairs $(S_1\setminus \{e_1\}) \times (S_2\setminus\{e_2\})$. Similarly, for a DIFFER constraint with $e_1\in S_1$ and $e_2\in S_2$, you can find the extra edges by iterating over $(S_1\setminus \{e_1\}) \times (S_2\setminus\{e_2\})$ and requiring that they are different.

The above is basically a Disjoint-Set or (Union-Find) datastructure, where you can efficiently implement the partitioning of sets by ensuring each set $S$ has a 'representative element', and by storing the representative element for each element in the set, which can be queried by a function $\mathrm{FIND}(e_i)$. Initially, each element is its own representative. Then, we have that $\mathrm{FIND}(e_1)= \mathrm{FIND}(e_2)$ if and only if $e_1$ and $e_2$ are to be chosen together. You can efficiently store all edges in $G$ by only storing them for the representatives. In order to check if two element $e_1$ $e_2$ are different, you can then check if the sets of $\mathrm{FIND}(e_1)$ and $\mathrm{FIND}(e_2)$ share an edge. If not, then the pair is unrestricted.