The primal assignment problem that I have is:

$\begin{align} & \max \sum\limits_{i=i}^N\sum\limits_{j=1}^N c_{ij}x_{ij} \\ &\text{subject to} \\ &\sum_{i=1}^N x_{ij} = 1,~~j=1,\dots,N \\ &\sum_{j=1}^N x_{ij} = 1, ~~i=1,\dots,N \\ &x_{i,j} ~\in \{ 0,1 \} \end{align} $

and I would like to obtain its dual, which should be

$$ \min_{p_j} \bigg\{ \sum_{i=1}^N p_j + \sum_{i=1}^N \max \{ a_{ij} - p_j \} \bigg\} $$

Can you give me any hints on how to approach this derivation? I have tried with Lagrange multipliers but I have not been able to reach this expression.


I don't know why you want to transform a standard LP problem, as the dual of the AP is, into a min-max problem.

Anyway the transformation should be as follows.

Let $\alpha_j, \ j=1,\ldots, N$ be the dual multipliers associated to the first set of constraints and $\beta_i, \ i=1,\ldots ,N$ those associated to the second set of constraints. Then, the ordinary dual is $$ \begin{align*} \min_{\alpha , \beta}\ &\sum_{j=1}^N \alpha_j + \sum_{i=1}^N \beta_i\\ & \alpha_j + \beta_i \geq c_{ij} \ \ \ \forall i,j=1,\ldots, N \end{align*} $$

Observe now that $$\beta_i \geq c_{ij}-\alpha_j\ \ \forall i,j=1,\ldots, N \Longrightarrow \ \ \beta_i=\max_{1\leq j\leq N}\{c_{ij}-\alpha_j\}\ \ \forall i =1,\ldots,N$$

Hence we get

$$ \begin{align*} \min_{\alpha}\ \sum_{j=1}^N \alpha_j + \sum_{i=1}^N \max_{1\leq j\leq N}\{c_{ij}-\alpha_j\} \end{align*} $$

  • $\begingroup$ Thank you very much for your answer! $\endgroup$ – Dunkel Aug 29 '17 at 23:43

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.