Column Generation Algorithm

Since there is an exponential number of possible columns in the Dantzig-Wolfe LP, we will use a column generation algorithm. Let ${\cal F}'_{t} \subseteq {\cal F}'$ represent a subset of the feasible points in ${\cal P}'$, i.e. assignment points. At iteration $t$, the restricted master problem is the Dantzig-Wolfe LP above with ${\cal F}' = {\cal F}'_{t}$. Associate a vector of dual variables $u$ with constraint (4) and $\alpha$ with the convexity constraint (5). Let $(\hat u, \hat \alpha )$ be the optimal dual solution to the restricted master problem. We then solve a subproblem to search for the column from ${\cal F}' \setminus {\cal F}'_{t}$ with the most negative reduced cost. The reduced cost of a variable $x_{ijk}$ is calculated as

$$r_{ijk} = c_{ijk} - \hat u_i - \hat \alpha$$ (9)

Hence, we can write the column generation subproblem as an optimization problem over the AP polytope as

		$$z_{SP}(\hat u, \hat \alpha )) = \min$$	$$\sum_{(j,k) \in J \times K} c'_{jk} x_{jk} \nonumber$$
			$$\sum_{k \in K} x_{jk}$$	$$=$$	$$1$$	$$\forall j \in J \yesnumber$$		(10)
			$$\sum_{j \in J} x_{jk}$$	$$=$$	$$1$$	$$\forall k \in K \yesnumber$$		(11)
			$$x_{jk} \in \{0,1\}$$			$$\forall (j,k) \in J \times K$$		(12)

where $c'_{jk} = \min_{i \in I} \{c_{ijk} - \hat u_i\}$. Then, if $z_{SP}(\hat u, \hat \alpha ) \geq \hat \alpha$, then no columns in ${\cal F}' \setminus {\cal F}'_{t}$ have negative reduced cost and the solution to the restricted master is optimal. Otherwise, we add the column $x_{ijk}$, corresponding to the optimal solution of $z_{SP}(\hat u, \hat \alpha )$, to ${\cal F}'_{t+1}$ and iterate.