0

I've come across a problematic LP question and unfortunately it's been a while since I solved these type of problems

the problem:

you have a graph $G$, the edges are $E$, Vertices are $V$, edges are denoted by $(u,v)$ :

\begin{align} \max \sum_{(u,v)\in E}y(u,v) &\\ s.t \\ y(u,v) &\le x_u && \forall (u,v) \in E \\ y(u,v) &\le x_v && \forall (u,v) \in E \\ \sum_{v\in V} x_v &\le 1 \\ y(u,v) &\ge 0 && \forall (u,v) \in E \\ x_v &\ge 0 && \forall v \in V \end{align}

I only want to write the Dual LP of this primal problem at the moment, The thing I'm having trouble with is that I don't understand how to write this LP in a "standard form", I remember that I should bring the problem to a form:

\begin{align} \max c^T x \\ Ax &\le b \\ x &\ge 0 \\ \end{align}

and from there a dual problem is easy to write, but here it seems that its not that straightforward. Any help would be appreciated

RobPratt
  • 45,619
Edward Josef
  • 481

1 Answers1

1

To put in standard form, rewrite the first two constraints so all the variables appear on the left: $y(u,v)-x_u \le 0$ and $y(u,v)-x_v \le 0$. Introduce dual variables $\alpha_{uv}$, $\beta_{uv}$, and $\gamma$ for the three primal $\le$ constraints. The dual problem is to minimize $\gamma$ subject to \begin{align} \alpha_{uv} + \beta_{uv} &\ge 1 && \text{for $(u,v)\in E$} \\ -\alpha_{vu} - \beta_{uv} + \gamma &\ge 0 && \text{for $v\in V$} \\ \alpha_{uv} &\ge 0 && \text{for $(u,v)\in E$} \\ \beta_{uv} &\ge 0 && \text{for $(u,v)\in E$} \\ \gamma &\ge 0 && \text{for $(u,v)\in E$} \end{align}

RobPratt
  • 45,619
  • Thanks for you answer! could you provide me with some insight on the thought process that led you to the decisions to introduce variables alpha beta gamma, and formulating the dual problem ? since I'm familiar with : $max \ C^Tx$ s.t $Ax\le b$ $x \ge 0$ turns to $min \ b^Ty$ $A^Ty \ge c$ $y \ge 0$ I'm having trouble seeing what 'takes the role' of A, x and b in the primal problem after introducing alpha beta and gamma – Edward Josef Mar 13 '24 at 16:38
  • The primal constraints correspond to rows of $A$. Because you have three families of primal constraints, it is natural to consider one family at a time. In matrix terms, think of stacked matrices: $$A=\begin{pmatrix}A_1\A_2\A_3\end{pmatrix}\quad\text{and}\quad b=\begin{pmatrix}b_1\b_2\b_3\end{pmatrix}$$ Similarly, you can think of the dual vector $y$ as being partitioned into three sets of variables: $y=(\alpha, \beta, \gamma)$. – RobPratt Mar 13 '24 at 16:47
  • So if I understood you correctly, in our case b = ( 0..0 0..0 1..1) because in the primal problem we got $\alpha_{uv} \le 0$ $\beta_{uv} \le 0$ $\gamma_{uv} \le 1$.

    Which gives that the problem is (since just $b_3$ is non-zero: $ min\ b^Ty = min\ \gamma$ I understand the non negativity constraints, But I'm still having trouble understanding how to get the first two constraints you've written. Again, thank you!

     – Edward Josef Mar 13 '24 at 17:24
  • Yes, that is the correct idea for $b$, but there is only one $1$. The first dual constraint corresponds to the primal $y$ variable, and the second dual constraint corresponds to the primal $x$ variable, so look at the primal constraint coefficients for those variables – RobPratt Mar 13 '24 at 21:41