7
$\begingroup$

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.

Given edges (1,2) and (1,3). The edge (2,3) could be generated with w(2,3) = -1

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);
            }
        }
    }
}
$\endgroup$
2
  • $\begingroup$ Hi. As far as I can see, you are trying to generate new subsets of variables to be fixed in your branching algorithm. However, you have to select these subsets wisely, in order to avoid unfeasibility, as you mentioned in the sentence "... it's clear that elements 2 and 3 should not be chosen together as well, ...". Thus, you have to keep track of the subsets selected in the branching rules applied by the ancestor nodes of the current branch and bound node. Is my reasoning right? $\endgroup$ Dec 5, 2022 at 8:48
  • $\begingroup$ @MatheusDiógenesAndrade Yes Matheus, in my implementation I propagate the branching rules along the branches, so each node knows the rules applied to their ancestors. $\endgroup$ Dec 8, 2022 at 13:18

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.