Doğrusal programlama vs tamsayı doğrusal programlama

Question

Verilen $A,b$, İzin Vermek $Ax \le b$ değişkenler üzerinde doğrusal programlamanın bir örneği olun $x=(x_1,\dots,x_n)$. Kısıtlamaların$0 \le x_i$ ve $x_i \le 1$ dahildir $A,b$.

Uygulanabilir bir çözüm olduğunu varsayalım $x \in \mathbb{R}^n$ doğrusal programlama problemine $x_1 = 1$. Ayrıca, karşılık gelen doğrusal tamsayı programına bir çözüm olduğunu varsayalım, yani,$x' \in \{0,1\}^n$ öyle ki $Ax' \le b$. İle bir çözüm var mı?$x'_1=1$yani var $x' \in \{0,1\}^n$ öyle ki $Ax' \le b$ ve $x'_1=1$?

Başka bir deyişle: sıfır veya bir ILP örneğiyle ilişkili doğrusal programı çözersek ve değişkenlerden birinin doğrusal programın bazı çözümlerinde 1'e atandığını bulursak, bir çözüm var mıdır? bu değişkeni 1 olarak ayarladığımız ILP örneğine?

Şüpheliyim ama ne bir kanıt ne de karşı örnek bulamadım.

Answer 1

Program $x_1 + 2x_2 = 2$ tamsayı çözümüne sahiptir $(0,1)$ ve kesirli çözüm $(1,1/2)$ ancak formun tamsayı çözümü değil $(1,\cdot)$.

Answer 2

Yuval Filmus bir karşı örnek öneriyor :$x_1 + 2x_2 = 2$, $0 \le x_1 \le 1$, $0 \le x_2 \le 1$.

Burada LP örneğine uygulanabilir bir çözüm var: $x_1=1$, yani, $x_1=1$, $x_2=1/2$.

Bununla birlikte, ILP örneğine yönelik tek uygun çözüm, $x_1=0$, $x_2=1$.