1
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ A really nice reference for duality is chapter 5 of Boyd and Vanderbergh. There's nothing special about having two indices, if you like, you can consider this is on index in the set $[n^2]$ instead of two in the set $[n]$. $\endgroup$
    – Elle Najt
    May 25, 2020 at 2:18
  • 1
    $\begingroup$ Thanks for the reference, I'll have a look. Do you mind elaborating or writing out a few steps to explain your last sentence? I was trying to write these constraints as matrices bu I am really confused about how to deal with the "forall i" and "for all j" $\endgroup$
    – bilbo
    May 25, 2020 at 2:23
  • 1
    $\begingroup$ Maybe try writing out the case of $n = 2$. $\endgroup$
    – Elle Najt
    May 25, 2020 at 6:10

1 Answer 1

Reset to default
0
$\begingroup$

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}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .