If an Integer Linear Programming (ILP) problem is relaxed to a Linear Programming (LP) problem, is the objective value of the LP always less than the same ILP problem? Why?
2
-
2$\begingroup$ Less than or equal. More generally, every relaxation (not just LP) of a minimization problem yields a lower bound on the optimal objective value. $\endgroup$– RobPrattSep 9 at 12:25
-
$\begingroup$ The best solution of the ILP is feasible for the LP. Therefore, the best solution of the LP is necessarily at least better, since it is better than any feasible solution $\endgroup$– fontanfSep 9 at 17:24
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
If the integer linear programming is a minimization problem then whose linear relaxation is a lower bound for the original MILP model, and for the maximization problem it is an upper bound. In the context of branch and bound and for the minimization model, linear relaxation is known as the best bound (lower bound), and every feasible solution would be an incumbent or best feasible solution. In the maximization, the situation is vice versa.
When you enforce integrality constraint, the objective function of MILP is worse than whose linear relaxation. Also, there is an exception when the original problem has an integrality property which is known as the total unimodularity condition.
