LP relaxation for ILP\IP (integer linear programming)

I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a lower bound for the ILP. Why this is correct?

I do understand that a feasible solution for the ILP is a feasible solution to the LP, and the reversed is not always so, i.e. a feasible solution for the LP is not necessarily a feasible solution for the ILP.

Can one please point out and explain briefly why it is so?

-

As you say, a feasible solution for the ILP is a feasible solution for the LP. So if the LP has an optimal solution with objective value $\alpha$, this implies there is no feasible solution for the LP with objective value $< \alpha$, and in particular no feasible solution for the ILP with objective value $<\alpha$. That's what it means for $\alpha$ to be a lower bound for the ILP.

-
thank you for your answer, but i still do not get it... why it is a lower bound rather than an upper bound? could you please elaborate on it a little bit more? –  user36774 Jul 29 '12 at 19:29
"this implies there is no feasible solution for the LP with objective value < alpha". Doesn't it define a different goal function, which it's optimum might exist? –  user36774 Jul 29 '12 at 19:35
@user36774: it's a lower bound because this is a minimization problem. –  Robert Israel Jul 29 '12 at 22:50
For example, take this simple ILP: minimize $2 x$ subject to $2 x \ge 3$, $x$ an integer. Leaving out the "integer" requirement, the linear programming problem has optimal solution $x=3/2$ with objective value $3$. That says there is no real solution with $2x < 3$, and therefore no integer solution with $2x < 3$, so $3$ is a lower bound on the objective values for the ILP. Of course the actual optimal solution for the ILP has objective value $4$ in this case. –  Robert Israel Jul 29 '12 at 22:56
Maybe I am wrong, but x=2 is a feasible solution for the ILP, so why do you say that the optimal solution for the ILP has an objective value of 4? –  user36774 Jul 30 '12 at 5:17

First we should be all be clear on the definition of a "relaxation":

Suppose you have a problem (P) and its relaxation (R).

(R) is a relaxation of (P), with the same decision variable $x$ iff the feasible set of (R) contains that of (P) (that is, $X_{(P)} \subseteq X_{(R)}$), and over the feasible set of (R), the objective function dominates that of (P) (That is, $f_{(R)}(x) \leq f_{(P)}(x)\quad\forall x\in X$).

So it should clearly follow from these two conditions that (for a minimisation problem), a linear relaxation must always give a lower bound of its corresponding IP.

The IP is bounded by some polyhedron with the additional constraint that only the integral points are feasible. The LR relaxation is the same polyhedron where all points are feasible. Therefore, the first condition is satisfied as the set of all points in a polyhedron must logically include all integral points in the same polyhedron.

The second condition is also met as the objective function of (R) is equal at all points to that of (P).

If you think about it visually, there are two possible cases for an integer program (IP) and its corresponding linear relaxation (LR):

1. You solve (LR) and all variables are integral. Either (IP) has the integrality property (where the optimal solution of the corresponding (LR) will always be integral, such as with LPs with totally unimodular matrices), or you were lucky and the optimal solution of (IP) touches the edge of the polyhedron that bounds the feasible region.
2. You solve (LR) and some or all variables are not integral. You can be certain that (for a minimisation problem), the optimal value to the corresponding (IP) must be at least the optimal solution to (LR), since the set of feasible points of (IP) is contained inside that of (LR), and because the function values of (IP) at any arbitrary point is at least as great as that of (LR) at the same point.

Suppose you have some problem (P) with a set of feasible points $X$. (These points need not necessarily be integral, just any finite set of points). If the feasible region of (P) is $conv(X)$ (the convex hull of $X$), then the optimal solution to the relaxation or $x\in X$ (where we consider ALL points inside the feasible region, not just those in $X$) will be the optimal solution.

-