# Termination criterion for the Phase 1 algorithm in column generation

To initialize column generation, I obtain a feasible set of columns via the following Phase 1 algorithm. The restricted master problem for this algorithm is formulated as follows.

$$$$min \: \: F = \{w^0 + \sum_{i,k,e} w^1_{ike} + \sum_{k,e}w^2_{ke}\}$$$$

subjected to:

$$$$(1-\lambda) \times \sum_{s}\chi_s +w^0 = 1$$$$

$$$$\sum_{s} (Y_{sike} \times \chi_s) +w^1_{ike} \geq a_{ike} \hspace{1cm} \forall i,k,e$$$$

$$$$\sum_{s} (Z_{ske} \times \chi_s) +w^2_{ke} \geq b_{ke} \hspace{1cm} \forall k,e$$$$

$$$$\chi_s, w^0, w^1_{ike}, w^2_{ke} \geq 0$$$$

The restricted master problem is solved iteratively. I terminate the Phase 1 algorithm when the objective function of the restricted master problem reaches zero (slack variables are zero, indicating no constraint violations). Instead, I'd like to solve the dual of this model, which I have formulated as follows:

$$$$max \: \: F' = \{\phi^0 + \sum_{i,k,e} \phi^1_{ike} + \sum_{k,e} \phi^2_{ke}\}$$$$

subjected to:

$$$$\phi^0 \leq 1$$$$

$$$$\phi^1_{ike} \leq 1 \hspace{1cm} \forall i,k,e$$$$

$$$$\phi^2_{ke} \leq 1 \hspace{1cm} \forall k,e$$$$

$$$$\phi^0 \times (1-\lambda) + \sum_{i,k,e} Y_{sike} \times \phi^1_{ike} + \sum_{k,e} Z_{ske} \times \phi^2_{ke} \leq 0 \hspace{1cm} \forall s$$$$

$$$$\phi^0 \in R$$$$

$$$$\phi^1_{ike}, \phi^2_{ke} \geq 0$$$$

If I solve the dual instead of the primal restricted master problem, what should be the termination criterion for the Phase 1 algorithm? Also, please let me know if the dual is not formulated correctly.

The termination criterion is the same because the primal objective value is $$0$$ if and only if the dual objective value is $$0$$.
Your dual formulation is almost correct, but you are missing $$a$$ and $$b$$ in the objective.