Programación lineal vs programación lineal entera

Question

Dado $A,b$, dejar $Ax \le b$ ser una instancia de programación lineal en las variables $x=(x_1,\dots,x_n)$. Suponga que las restricciones$0 \le x_i$ y $x_i \le 1$ están incluidos en $A,b$.

Supongamos que existe una solución factible $x \in \mathbb{R}^n$ al problema de la programación lineal donde $x_1 = 1$. Además, suponga que existe una solución para el programa lineal entero correspondiente, es decir, existe$x' \in \{0,1\}^n$ tal que $Ax' \le b$. ¿Tenemos la garantía de que existe una solución con$x'_1=1$, es decir, existe $x' \in \{0,1\}^n$ tal que $Ax' \le b$ y $x'_1=1$?

Para decirlo de otra manera: si resolvemos el programa lineal asociado con una instancia de ILP cero o uno, y encontramos que una de las variables se asigna a 1 en alguna solución del programa lineal, ¿se sigue que existe una solución? a la instancia de ILP donde establecemos esa variable en 1?

Soy escéptico pero no pude encontrar ni una prueba ni un contraejemplo.

Answer 1

El programa $x_1 + 2x_2 = 2$ tiene la solución entera $(0,1)$ y la solución fraccionada $(1,1/2)$ pero no una solución entera de la forma $(1,\cdot)$.

Answer 2

Yuval Filmus sugiere un contraejemplo :$x_1 + 2x_2 = 2$, $0 \le x_1 \le 1$, $0 \le x_2 \le 1$.

Aquí hay una solución factible para la instancia LP con $x_1=1$, a saber, $x_1=1$, $x_2=1/2$.

Sin embargo, la única solución viable para la instancia de ILP es $x_1=0$, $x_2=1$.