1
$\begingroup$

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.

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

2 Answers 2

2
$\begingroup$

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)$.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.