Pemrograman linier vs pemrograman linier integer

Question

Diberikan $A,b$, biarkan $Ax \le b$ menjadi contoh pemrograman linier pada variabel $x=(x_1,\dots,x_n)$. Asumsikan bahwa kendala$0 \le x_i$ dan $x_i \le 1$ termasuk dalam $A,b$.

Misalkan ada solusi yang layak $x \in \mathbb{R}^n$ ke masalah pemrograman linier di mana $x_1 = 1$. Juga, misalkan ada solusi untuk program linier bilangan bulat yang sesuai, yaitu, ada$x' \in \{0,1\}^n$ seperti yang $Ax' \le b$. Apakah kami dijamin bahwa ada solusi dengan$x'_1=1$, yaitu, ada $x' \in \{0,1\}^n$ seperti yang $Ax' \le b$ dan $x'_1=1$?

Dengan kata lain: jika kita menyelesaikan program linier yang terkait dengan turunan ILP nol-atau-satu, dan menemukan bahwa salah satu variabel ditetapkan ke 1 dalam beberapa solusi untuk program linier, apakah itu berarti ada solusi ke contoh ILP di mana kita menetapkan variabel itu ke 1?

Saya skeptis tetapi tidak dapat menemukan bukti atau contoh yang berlawanan.

Answer 1

Program $x_1 + 2x_2 = 2$ memiliki solusi integer $(0,1)$ dan solusi pecahan $(1,1/2)$ tetapi bukan solusi integer dari bentuk $(1,\cdot)$.

Answer 2

Yuval Filmus menyarankan contoh balasan :$x_1 + 2x_2 = 2$, $0 \le x_1 \le 1$, $0 \le x_2 \le 1$.

Di sini ada solusi yang layak untuk instance LP dengan $x_1=1$, yaitu, $x_1=1$, $x_2=1/2$.

Namun satu-satunya solusi yang layak untuk contoh ILP adalah $x_1=0$, $x_2=1$.