1
$\begingroup$

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!

$\endgroup$

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.