Say we're given the following integer problem:
$\min c^Tx$
s.t
$Ax \leq b$
$x \in \{0,1\}^n$
and its corresponding LP-relaxation:
$\min c^Tx$
s.t
$Ax \leq b$
$x \in [0,1]^n$
Then we can say that the optimal value of the LP-relaxation will be a lower bound on the optimal value of the MIP.
However, does the same hold for subsets of the variables? So, say we're given a optimal solution $x^*$ of the MIP and an optimal fractional solution $\tilde x$ of the LP relaxation as well as a subset of our index set $J \subseteq \{1, \dots, n\}$. Let $v^*_J := \sum_{j\in J}c_jx_j^*$ and $\tilde v_J := \sum_{j\in J}c_j\tilde x_j$ where $c_j$, $x^*_j$ and $\tilde x_j$ are the $j$-th columns of $c$, $x^*$ and $\tilde x$ respectively. Must it then also hold that $v^*_J \geq \tilde v_J$? I have a feeling that no, it must not, but I'm struggling to come up with a good counter example.
Best Answer
Here is a simple example: $$\min\{ x_1 + 1.1x_2 : x_1 + x_2 = 1, x_2 \geq 0.1, x \in \{0,1\}^2 \}.$$ The solution is $(0,1)$ whereas the solution of the relaxation is $(0.9,0.1)$. Take $J=\{1\}$ and notice $v^*_J = 0$ while $\tilde{v}_J = 0.9$.