0

I've been biting my teeth out, trying to find an example of the following. Is it even possible?

Consider two LPs

$$ (P1) \ \max \{c^Tx|Ax\leq b, x\geq 0\} \\ (P2)\ \max \{c^Tx|Ax\leq \tilde{b}, x\geq 0\} $$ where $ A \in \mathbb{R}^{m,n}$, $c\in \mathbb R^n$ and $b,\tilde b \in \mathbb R ^m$ for $m,n$ arbitrary.

The task is to prove or disprove, that if (P1) is unbounded, then (P2) is infeasible or unbounded. I have been searching for a counterexample to the claim, so I've been trying to find $A,\ c,\ b$ and $\tilde b$ for which (P1) is unbounded but (P2) is feasible and bounded. Does such an example exist?

Thanks for any help.

Florian Ente
  • 279

1 Answers1

2

If $(P1)$ is unbounded then its dual $$(D1) \quad \min \{b^Ty\, |\, A^Ty\geq c, y\geq 0\}$$ is infeasible by weak duality, see the summary at the end of [1], or [2], or Theorem A.2.2 page 336 in [3]. But this means the dual of $(P2)$, namely $$(D2) \quad \min \{\tilde{b}^Ty\, |\, A^Ty\geq c, y\geq 0\}$$ is also infeasible. By the same references, it follows that $(P2)$ is infeasible or unbounded.

[1] http://theory.stanford.edu/~trevisan/cs261/lecture06.pdf

[2] https://en.wikipedia.org/wiki/Dual_linear_program

[3] Karlin, Anna R., and Yuval Peres. Game theory, alive. Vol. 101. American Mathematical Soc., 2017. https://homes.cs.washington.edu/~karlin/GameTheoryBook.pdf

Yuval Peres
  • 21,955