Consider the following graph $G = (V,E)$ with costs $w:E\to\mathbb{R}$ on the edges. enter image description here

Denote by $\mathcal{O} = \{U\subseteq V:\left|U\right| \text{ is odd}\}$ the collection of odd subsets of $V$. A vector $y\in\mathbb{R}^{\mathcal{O}}$ is given by the values in the table below and setting $y_U = 0$ for the other sets in $\mathcal{O}$.

$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline U&\{a\}&\{b\}&\{c\}&\{d\}&\{e\}&\{f\}&\{g\}&\{h\}&\{i\}&\{j\} &\{a,d,e\}&\{e,g,h\}&\{a,b,c,d,e,f,g,h,i\}\\\hline y_U& 3&0&3&-1&3&2&3&1&8&11&1&4&1\\\hline\end{array}$

Now, consider the following LP with variables $x\in\mathbb{R}^E$ $$\begin{split}\min w^Tx\\s.t\\x\geq&\, 0\\x(\delta(U)) =\, &1 \text{ for all $U\in\mathcal{O}$ with $\left|U\right| = 1$}\\x(\delta(U))\geq\,&3\text{ for all $U\in\mathcal{O}$ with $\left|U\right| \geq 3$.}\end{split}$$ Here $x(u)$ is the flow on edge $u$, and $\delta(U) = \{\text{$e\in E:e$ has a end in $U$ and an end in $V\backslash U$}\}$.

Exercise: Write down the dual LP and show that $y$ is a feasible solution to the dual LP.

What I've tried: I know that the dual LP has the form $$\begin{split}\max\, &b^Ty\\&s.t\\A^Ty &\geq w^T\end{split}$$ In order to check that $y_U$ is a feasible solution to the dual LP, I need to show that $A^Ty \geq w$. I don't understand how, since $A^T$ looks like this $$A^T = \begin{bmatrix}1&1&\ldots&-1&-1&-1\end{bmatrix}$$ which means that $A^Ty$ is a scalar, while $w$ is a vector.

Question: What would be the correct dual LP in this exercise?

Thanks in advance!


Your Answer

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

Browse other questions tagged or ask your own question.