# Derivation of the dual of the linear assignment problem

I read that the dual of the assignment problem is

\begin{align} \text{maximize } & \sum_{i=1}^n \lambda_i + \sum_{i=1}^n \beta_i \\ & \lambda_i + \beta_j \leq c_{ij} \end{align}

where the primal problem is

\begin{align} \text{minimize } & \sum\limits_{i=i}^n\sum\limits_{j=1}^n c_{ij}x_{ij} \\ &\sum_{i=1}^n x_{ij} = 1\; \forall j \\ &\sum_{j=1}^n x_{ij} = 1\; \forall i \\ &x_{i,j} ~\in (0,1) \end{align}

But unfortunately, I am not able to derive dual from primal using Lagrangian. Anyone can help ?

• Would you please state clearly which are objective functions and which are constraints? I would expect to see $\min$ in the primal and I am puzzled by having $\le c_i$ after $\max \lambda_i + \beta_i$. – mlc Mar 17 '17 at 16:47
• sorry. there was a mistake. I corrected it now. – Shew Mar 17 '17 at 16:52