Programação linear vs programação linear inteira

Question

Dado $A,b$, deixei $Ax \le b$ ser uma instância de programação linear nas variáveis $x=(x_1,\dots,x_n)$. Suponha que as restrições$0 \le x_i$ e $x_i \le 1$ estão incluídos em $A,b$.

Suponha que haja uma solução viável $x \in \mathbb{R}^n$ para o problema de programação linear onde $x_1 = 1$. Além disso, suponha que exista uma solução para o programa linear inteiro correspondente, ou seja, existe$x' \in \{0,1\}^n$ de tal modo que $Ax' \le b$. Temos a garantia de que existe uma solução com$x'_1=1$, ou seja, existe $x' \in \{0,1\}^n$ de tal modo que $Ax' \le b$ e $x'_1=1$?

Colocando de outra forma: se resolvermos o programa linear associado a uma instância ILP zero ou um, e descobrirmos que uma das variáveis ​​é atribuída a 1 em alguma solução do programa linear, segue-se que existe uma solução para a instância ILP onde definimos essa variável para 1?

Eu sou cético, mas não consegui encontrar uma prova ou um contra-exemplo.

Answer 1

O programa $x_1 + 2x_2 = 2$ tem a solução inteira $(0,1)$ e a solução fracionária $(1,1/2)$ mas não uma solução inteira da forma $(1,\cdot)$.

Answer 2

Yuval Filmus sugere um contra - exemplo :$x_1 + 2x_2 = 2$, $0 \le x_1 \le 1$, $0 \le x_2 \le 1$.

Aqui há uma solução viável para a instância LP com $x_1=1$, ou seja, $x_1=1$, $x_2=1/2$.

No entanto, a única solução viável para a instância ILP é $x_1=0$, $x_2=1$.