Lineare Programmierung vs. ganzzahlige lineare Programmierung

Question

Gegeben $A,b$, Lassen $Ax \le b$ eine Instanz der linearen Programmierung auf den Variablen sein $x=(x_1,\dots,x_n)$. Angenommen, die Einschränkungen$0 \le x_i$ und $x_i \le 1$ sind enthalten in $A,b$.

Angenommen, es gibt eine praktikable Lösung $x \in \mathbb{R}^n$ zum linearen Programmierproblem wo $x_1 = 1$. Angenommen, es gibt eine Lösung für das entsprechende ganzzahlige lineare Programm, dh es gibt eine$x' \in \{0,1\}^n$ so dass $Ax' \le b$. Sind wir garantiert, dass es eine Lösung mit gibt$x'_1=1$dh es existiert $x' \in \{0,1\}^n$ so dass $Ax' \le b$ und $x'_1=1$?

Anders ausgedrückt: Wenn wir das einer ILP-Instanz Null oder Eins zugeordnete lineare Programm lösen und feststellen, dass eine der Variablen in einer Lösung des linearen Programms 1 zugewiesen wird, folgt daraus, dass es eine Lösung gibt auf die ILP-Instanz, in der wir diese Variable auf 1 setzen?

Ich bin skeptisch, konnte aber weder einen Beweis noch ein Gegenbeispiel finden.

Answer 1

Das Programm $x_1 + 2x_2 = 2$ hat die ganzzahlige Lösung $(0,1)$ und die fraktionierte Lösung $(1,1/2)$ aber keine ganzzahlige Lösung der Form $(1,\cdot)$.

Answer 2

Yuval Filmus schlägt ein Gegenbeispiel vor :$x_1 + 2x_2 = 2$, $0 \le x_1 \le 1$, $0 \le x_2 \le 1$.

Hier gibt es eine praktikable Lösung für die LP-Instanz mit $x_1=1$nämlich. $x_1=1$, $x_2=1/2$.

Die einzig mögliche Lösung für die ILP-Instanz ist jedoch $x_1=0$, $x_2=1$.