# From primal to dual in maximization of the assignment problem

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*}

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