# Linear programming vs integer linear programming

Given $$A,b$$, let $$Ax \le b$$ be an instance of linear programming on the variables $$x=(x_1,\dots,x_n)$$. Assume that the constraints $$0 \le x_i$$ and $$x_i \le 1$$ are included in $$A,b$$.

Suppose that there is a feasible solution $$x \in \mathbb{R}^n$$ to the linear programming problem where $$x_1 = 1$$. Also, suppose there exists a solution to the corresponding integer linear program, i.e., there exists $$x' \in \{0,1\}^n$$ such that $$Ax' \le b$$. Are we guaranteed that there exists a solution with $$x'_1=1$$, i.e., there exists $$x' \in \{0,1\}^n$$ such that $$Ax' \le b$$ and $$x'_1=1$$?

To put it another way: if we solve the linear program associated with a zero-or-one ILP instance, and find that one of the variables gets assigned to 1 in some solution to the linear program, does it follow that there exists a solution to the ILP instance where we set that variable to 1?

I am skeptical but could not find either a proof or a counterexample.

• How about $x_1 + 2x_2 = 2$? Oct 13, 2020 at 17:31
• @YuvalFilmus, perfect! Thank you.
– D.W.
Oct 13, 2020 at 17:51

The program $$x_1 + 2x_2 = 2$$ has the integer solution $$(0,1)$$ and the fractional solution $$(1,1/2)$$ but not an integer solution of the form $$(1,\cdot)$$.
Yuval Filmus suggests a counterexample: $$x_1 + 2x_2 = 2$$, $$0 \le x_1 \le 1$$, $$0 \le x_2 \le 1$$.
Here there is a feasible solution to the LP instance with $$x_1=1$$, namely, $$x_1=1$$, $$x_2=1/2$$.
However the only feasible solution to the ILP instance is $$x_1=0$$, $$x_2=1$$.