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.

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

subjected to:

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

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

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

\begin{equation} \chi_s, w^0, w^1_{ike}, w^2_{ke} \geq 0 \end{equation}

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:

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

subjected to:

\begin{equation} \phi^0 \leq 1 \end{equation}

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

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

\begin{equation} \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 \end{equation}

\begin{equation} \phi^0 \in R \end{equation}

\begin{equation} \phi^1_{ike}, \phi^2_{ke} \geq 0 \end{equation}

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.


1 Answer 1


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.


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.