How do you write the dual of the following problem - I know the basics behind the Lagrangian function but I'm getting a little confused with how to handle the Lagrangian multipliers when we are dealing with two dimensions (i and j)?
Min $\sum_{i,j} x_{ij}$ Subject to \begin{align*} \sum_j x_{ij} = 1 \forall i \\ \sum_i x_{ij} = 1 \forall j \\ x_{ij} + \sum_{k: w_k < w_j} x_{ik} + \sum_{l: m_l < m_i} x_{lj} \leq 1 \forall i,j \\ x_{ij} \geq 0 \forall i,j \end{align*}
Arthur Benjamin's S-O-B method is useful for obtaining the dual LP. Here's your primal problem with the dual variables in parentheses:
\begin{align} \text{minimize} \sum_{i,j} x_{ij} & \\ \sum_j x_{ij} &= 1 &&(\text{$\alpha_i$ free}) \\ \sum_i x_{ij} &= 1 &&(\text{$\beta_j$ free}) \\ x_{ij} + \sum_{k: w_k < w_j} x_{ik} + \sum_{l: m_l < m_i} x_{lj} &\leq 1 &&(\text{$\gamma_{ij} \le 0$}) \\ x_{ij} &\geq 0 \end{align}
The dual is then: \begin{align} \text{maximize} \sum_i \alpha_i + \sum_j \beta_j + \sum_{i,j} \gamma_{ij} & \\ \alpha_i + \beta_j + \gamma_{ij} + \sum_{k: w_k > w_j} \gamma_{ik} + \sum_{l: m_l > m_i} \gamma_{lj} &\le 1 &&(\text{$x_{ij}\ge 0$}) \\ \gamma_{ij} &\le 0 \end{align}