4
$\begingroup$

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 is this 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?

2 Answers 2

6

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.

  • 0
    Maybe I should try again: it may be too confusing to have the objective appearing in the constraint. Minimize $x+y$ subject to $x+2y \ge 3$, $x \ge 0$, $y\ge 0$. The optimal solution of the LP is $x=0$, $y=1.5$, for an objective value of $1.5$. Therefore there can't be a solution of the ILP with x+y < 1.5, so $1.5$ is a lower bound on the objective value for the ILP. In fact the optimal solution of the ILP is $x=0,y=2$ for objective value $2$.2012-07-30
1

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.