Dantzig-Wolfe Formulation

Balas and Saltzman [1] consider the use of the classical Assignment Problem (AP) as a relaxation of AAP in the context of Lagrangian Relaxation. We will use these same ideas in the context of column generation or Dantzig-Wolfe decomposition.

Define the AP polytope by removing constraint (1) as ${\cal P}' = \emph{conv}({\cal F}')$, where ${\cal F}' = \{x \in \mathbb{R}^H: x \textrm{ satisfies } \eqref{aap:2} - \eqref{aap:4}\}$. Observe, that the cost of an assignment is $c_s = \sum_{(i,j,k) \in H} s_{ijk} c_{ijk}, \; \forall s \in {\cal F}'$.

Then, the Dantzig Wolfe (DW) LP can be written as:

		$$z_{DW} = \min$$	$$\sum_{s \in {\cal F}'} c_{s} \lambda_{s} \nonumber$$
			$$\sum_{s \in {\cal F}'} \sum_{(j,k) \in J \times K} s_{ijk} \lambda_s$$	$$=$$	$$1$$	$$\forall i \in I$$		(5)
			$$\sum_{s \in {\cal F}'} \lambda_{s}$$	$$=$$	$$1$$			(6)
			$$\lambda_{s} \geq 0$$			$$\forall s \in {\cal F}'$$		(7)

where

$$x_{ijk} = \sum_{s \in {\cal F}'} s_{ijk} \lambda_s$$ (8)