Branching strategies in Branch-and-Price

After reading up on the topic of B&P, I tried to establish three branching rules and would now like to verify them. I branched based on (1) subproblem variables, (2) master problem variables, and (3) the Ryan-Foster method. My compact model looks like this. This is a set partitioning problem that minimises the completion time of customers in a service centre. Customers \(i\in I\) are processed by employees \(j\in J\) in periods \(p\in P\). Each customer has a period, but when they enter the system \(r_i\), they have a number of service units they need in order to be flagged as a completed customer (\(a_i\)). The completion time variable is \(C_i\). The binary variable \(x_{ijp}\in \{0,1\}\) indicates whether customer \(i\) is processed by employee \(j\) in period \(p\). Each customer can only be processed by one employee in each period. For example, if customer \(i_1\) has a value of \(a_1=4\), then they must remain in the system for at least four periods before they can be released from the system. However, since each employee has only a limited capacity \(Q_{jp}\), it may be that a customer cannot be processed in a given period and can therefore only be released later. Customer-employee continuity is important (this is a hard assumption), which means that once a customer has been assigned to a specific employee, it must always be the same employee. Further constraints are described below. This results in the following compact model:

\begin{align}
\tag{1a}
&\min \sum_{i\in I} C_i\\
\text{s.t}\\\tag{1b}
& \sum_{i\in I}x_{ijp} \leq Q_{jp}&\forall i\in I, p\in P\\\tag{1c}
& \sum_{j\in J}x_{ijp}\leq 1 & \forall i\in I,p\in P \\\tag{1d}
&\sum_{j \in \mathcal{J}} z_{ij} = 1&\forall i\in I\\\tag{1e}
&x_{ijp} \leq z_{ij}&\forall i\in I, j\in J, p\in P\\\tag{1f}
&C_i = \sum_{p \in {P}} p\cdot  d_{ip}- r_i + 1&\forall i\in I\\\tag{1g}
&a_id_{ip}\leq \sum_{k=r_i}^p\sum_{j\in J}x_{ijk}&\forall i\in I, p\in P\\\tag{1h}
&\sum_{p\in P}d_{ip}=1&\forall i\in I\\\tag{1i}
&\sum_{j \in {J}} x_{ijr_i} = 1&\forall i\in I
\end{align}

(1b) is the capacity constraint. (1c) ensures one service per period at most. (1d)-(1e) enforce the continuity relation. (1f) determines the service duration. (1g) determines the completion based on \(a_i\). (1h) ensures exactly one completion period. (1i) makes sure that on release date, there is an assignment.

Since the model results in a natural decomposition along the capacity constraint and customer-specific subproblems, this yields the following DW decomposition, where the set \(A(i)\) specifies the set of columns, with the master variable \(\lambda_{ia}\in \{0,1\}\) indicating whether column \(a\) is selected for customer \(i\). \(\zeta_i^a\) is the parameter associated with the service duration and \(\chi_{ijp}^a\) is the allocation parameter. The master problem is:
\begin{align}
&MP~~~~\min \sum_{i\in I}\sum_{a\in A(i)}\zeta_i^a\lambda_{ia}\\
\text{s.t.}\\
&\sum_{i\in I}\sum_{a\in A(i)}\chi_{ijp}^a\lambda_{ia}\leq Q_{JP}&\forall j\in J, p\in P & ~~~~\text{(Duals \(\pi_{jp}\)}\\
&\sum_{a\in A(i)}\lambda_{ia}=1&\forall i\in I& ~~~~\text{(Duals \(\eta_i\)}\\
&\lambda_{ia}\in \{0,1\}&\forall i\in I, a\in A(i)
\end{align}

With the individual subproblems \(SP_i\):
\begin{align}
&SP_i~~\min C_i - \sum_{j \in {J}} \sum_{p\in P} \pi_{jp}  x_{ijp} - \gamma_i\\
\text{s.t.}\\
&\text{Constraints (1c)-(1i)}
\end{align}

Currently, \(\lambda \in \{0,1\}\). However, since there are customers with identical profiles (with regard to \(r_i,a_i\)), these are aggregated. This results in \(i\in I \rightarrow n\in N\) as the customer set, and the parameter \(M_n\) specifies how many customers there are per profile. This also results in the modified set \(A(n)\). The master problem looks as follows concerning aggregation.
\begin{align}
&MP~~~~\min \sum_{n\in N}\sum_{a\in A(n)}\zeta_n^a\Lambda_{na}\\
\text{s.t.}\\
&\sum_{n\in N}\sum_{a\in A(n)}\chi_{njp}^a\Lambda_{na}\leq Q_{JP}&\forall j\in J, p\in P\\
&\sum_{a\in A(n)}\Lambda_{na}=M_n&\forall n\in N\\
&\Lambda_{na}\in \mathbb{N}^+_{\geq 0}&\forall n\in N, a\in A(n)
\end{align}
In the subproblems, \(n\) is now used instead of \(i\), but nothing else changes. Note that in both MPs, the bounds of \(\lambda, \Lambda \geq 0\) should be set.

Now I will briefly explain all three branching strategies:

(i) Branching on subproblem variables: Here we take advantage of the fact that there exists a \(\beta_{n j_{1} p_{1}}\) for which \(\beta_{n j_{1} p_{1}} \equiv \sum_{a\in {A}(n)} \chi_{n j_{1} p_{1}}^ {a} \Lambda_{na} \notin \mathbb{Z}^1\). This results in the following successor node constraints for left and right:
\begin{align}
{\sum_{a \in {A}(n)} \chi_{nj_{1} p_{1}}^{a} \Lambda_{na} \leq\left\lfloor\beta_{nj_{1} p_{1}}\right\rfloor}, \quad {\sum_{a\in {A}(n)} X_{n j_{1} p_{1}}^{a} \Lambda_{na} \geq\left\lceil\beta_{n j_{1} p_{1}}\right\rceil}\label{eq:branch:sub2}
\end{align}
with the constraints \(x_{n j_{1} p_{1}}=0\) for the left node and \(x_{n j_{1} p_{1}}=1\) for the right node. Since we have new dual variables, the subproblem objective function is modified as follows.
\[C_i - \sum_{j \in {J}} \sum_{p\in P} \pi_{jp}  x_{ijp} -\sum_{s \in {S}(n)}\left(\tau_{n l}^{L}-\tau_{n l}^{R} \right)- \gamma_i,\]
where the set \(S\) represents the levels of the tree and \(L,R\) indicates whether one is in the right or left branch.

(ii) Branching on master problem variables: Since branching on integer master variables would be too restrictive, we return to the disaggregated version here. For this purpose, the following constraints are added to the master problem.
\begin{align}
{\Lambda_{ia} \leq 0}, \quad {\Lambda_{ia} \geq 1}\label{branch_mp1}
\end{align}
Now we must prevent the same column from being regenerated in the right branch. Since the problem is a set partitioning problem and the columns have variable lengths due to \(C_i\), a no-good cut must be used in the right child node. This looks as follows.
\begin{align}
\sum_{j \in {J}} \sum_{p \in P} \left| x_{ijp} - \chi_{ijp}^a  \right| \geq 1 \equiv \sum_{{(j,p) \in {J} \times P : \chi_{ijp}^a = 1}} ~(1 - x_{ijp}) ~~~+ ~~~~\sum_{{(j,p) \in {J} \times P: \chi_{ijt}^a = 0}}~ x_{ijp} \geq 1.
\end{align}
Since the new constraints in the MP are only variable bounds, there are no new dual variables that need to be taken into account in the objective function of the subproblems.

(iii) Ryan Foster branching:
First, we determine a few \((j_1,p_1),(j_2,p_2)\) for which the solution in MP is fractional. 
This is done using \(\beta_{i,(j_1,p_1),(j_2,p_2)} := \sum_{a \in {A}(i)} \chi_{ij_1p_1}^a \chi_{ij_2p_2}^a \Lambda_{ia}\). In the master problem, the following constraints are added for the left and right branches.
\begin{align} \sum_{a \in {A}(i)} \chi_{ij_1p_1}^a \chi_{ij_2p_2}^a \Lambda_{ia} \leq \lfloor \beta_{i,(j_1,p_1),(j_2,p_2)} \rfloor
,\quad \sum_{a \in {A}(i)} \chi_{ij_1p_1}^a \chi_{ij_2p_2}^a \Lambda_{ia} \geq \lceil \beta_{i,(j_1,p_1),(j_2,p_2)} \rceil \end{align}
The following constraints are inserted for the left and right sides in the subproblems.
\begin{align} x_{ij_1p_1} + x_{ij_2p_2} \leq 1, \quad x_{ij_1p_1} + x_{ij_2p_2} \geq 2 \end{align}

Finally, my questions: 1) Are the strategies correct, 2) can (ii) and (iii) be used in some way with aggregation, (3) is it correct that no modification to the SP objective is necessary for (ii) and (iii), and (4) a general question which fractal \(\lambda \text{ or } \Lambda\) to choose?

Also posted here: