Has $\max\{cx:Ax\le b\}$ an optimal solution $x_1=\sqrt 2$ with $A\in \{-1,0,1\}^{m*n}$ with exactly one $1$ and one $-1$?

Question

Let be

• $A\in \{-1,0,1\}^{m*n}$ with exactly one $1$ and one $-1$ and zeroes at each line.

• $c\in\mathbb{Z}^n$ such that $\sum\limits_{j=1}^{j=n}c_j=0$.

• $b\in\mathbb{Z}^m$ positive.

How to start to show that the linear program $\max\{c^Tx:Ax\le b\}$ has an optimal solution $x_1=\sqrt 2$?

Answer 1

I'm not sure I've understood you correctly, but the solution to an LP with rational data $(A,b,c)$ is always rational.