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 ?

  • $\begingroup$ 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$. $\endgroup$ – mlc Mar 17 '17 at 16:47
  • $\begingroup$ sorry. there was a mistake. I corrected it now. $\endgroup$ – Shew Mar 17 '17 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.