Programmazione lineare vs programmazione lineare intera

Question

Dato $A,b$, permettere $Ax \le b$ essere un'istanza di programmazione lineare sulle variabili $x=(x_1,\dots,x_n)$. Supponiamo che i vincoli$0 \le x_i$ e $x_i \le 1$ sono inclusi in $A,b$.

Supponiamo che ci sia una soluzione fattibile $x \in \mathbb{R}^n$ al problema della programmazione lineare dove $x_1 = 1$. Inoltre, supponiamo che esista una soluzione al corrispondente programma lineare intero, cioè che esista$x' \in \{0,1\}^n$ tale che $Ax' \le b$. Siamo garantiti che esiste una soluzione con$x'_1=1$, cioè, esiste $x' \in \{0,1\}^n$ tale che $Ax' \le b$ e $x'_1=1$?

Per dirla in un altro modo: se risolviamo il programma lineare associato a un'istanza ILP zero o uno e troviamo che una delle variabili viene assegnata a 1 in qualche soluzione al programma lineare, ne consegue che esiste una soluzione all'istanza ILP in cui abbiamo impostato quella variabile su 1?

Sono scettico ma non sono riuscito a trovare né una prova né un controesempio.

Answer 1

Il programma $x_1 + 2x_2 = 2$ ha la soluzione intera $(0,1)$ e la soluzione frazionaria $(1,1/2)$ ma non una soluzione intera della forma $(1,\cdot)$.

Answer 2

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

Qui c'è una soluzione fattibile per l'istanza LP con $x_1=1$, vale a dire, $x_1=1$, $x_2=1/2$.

Tuttavia, l'unica soluzione fattibile per l'istanza ILP è $x_1=0$, $x_2=1$.