How good is an optimal solution of the Lagrangian relaxation of an integer linear program?

Question

From what I learned, the Lagrangian relaxation of an integer program is used to find a bound. Is the solution to the relaxed problem considered to be a good approximate solution of the original problem?

Let's say I have a knapsack problem \begin{align} &\max_{x \in \{0,1\}^n} \sum_{i=1}^n v_i x_i\\ &\textrm{s.t.} \sum_{i=1}^n w_i x_i \leq c. \end{align} The Lagrangian relaxation is as follows \begin{align} \min_{\lambda \geq 0} \max_{x \in \{0,1\}^n} \sum_{i=1}^n v_i x_i - \lambda \left( \sum_{i=1}^n w_i x_i - c \right). \end{align} Suppose I solved the relaxed problem and got an optimal $x_{lag}$ s.t. $f(x^*) < f(x_{lag})$ where $x^*$ is the optimal solution of the original problem and $f$ is the objective function. Even though $x_{lag}$ gives a strict bound, is it considered to be a good approximate solution?

Is it true that the relaxation can be solved in polynomial time since the dual problem is convex in $\lambda$ and the maximization part with fixed $\lambda$ is just activating $x_i$ associated with the largest term $(v_i - \lambda w_i)$?

Answer 1

I would not describe the solution to the Lagrangian relaxation as an "approximate solution" to the original problem, since it need not be feasible in the original problem.

In general, the objective value of the LR may or may not be a tight bound for the objective value of the original problem. There is a well-known result that if the extreme points of the convex hull of the solutions to the constraints you did not relax all are integer valued, the Lagrangean bound (from the optimal solution to the LR problem) will be identical to the value of the LP relaxation of the original problem. In the case of the knapsack problem, where you relaxed the only constraint, that convex hull would just be $[0,1]^n$, which definitely satisfies the condition. So I would expect the LR bound for the knapsack to match the LP bound.

When the original problem contains only binary variables (as in your case) and all primal constraints are relaxed in the Lagrangian relaxation (which need not always be true, but is in your case), evaluating the Lagrangian objective for a single choice of $\lambda$ is $O(m\cdot n)$ where $m$ is the number of constraints (1 for the knapsack problem) and $n$ is the number of variables. Note: You do not just set a single $x_i=1$; you set $x_i=1$ for all $i$ such that the coefficient of $x_i$ in the LR is positive.

I'm not aware of any result that the number of such evaluations (the number of different values of $\lambda$ to be considered) is in general polynomial in problem size, although I suppose it could be.