 # From what I learned, the Lagrangian relaxation of an integer program is used to find a bound. Is the solution to the relaxed problem consideblack to be a good approximate solution of the original problem? Let's say I have a knapsack problem max_(x in {0,1}^n)sum_(i=1)^n v_ix_i s.t.sum_(i=1)^n w_ix_i<=c. The Lagrangian relaxation is as follows min_(lambda>=0) max_(x in {0,1}^n) sum_(i=1)^nv_ix_i−lambda(sum_(i=1)^n w_ix_i−c). 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 consideblack to be a good approximate solution? Is it true that the relaxation can be solved in polynomial time since the dual problem is convex Keenan Conway 2022-09-19 Answered
I have a knapsack problem
$\begin{array}{rl}& \underset{x\in \left\{0,1{\right\}}^{n}}{max}\sum _{i=1}^{n}{v}_{i}{x}_{i}\\ & \text{s.t.}\sum _{i=1}^{n}{w}_{i}{x}_{i}\le c.\end{array}$
The Lagrangian relaxation is as follows
$\begin{array}{r}\underset{\lambda \ge 0}{min}\underset{x\in \left\{0,1{\right\}}^{n}}{max}\sum _{i=1}^{n}{v}_{i}{x}_{i}-\lambda \left(\sum _{i=1}^{n}{w}_{i}{x}_{i}-c\right).\end{array}$
Suppose I solved the relaxed problem and got an optimal ${x}_{lag}$ s.t. $f\left({x}^{\ast }\right) where ${x}^{\ast }$ is the optimal solution of the original problem and $f$ is the objective function. Even though ${x}_{lag}$ gives a strict bound, is it consideblack 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 $\left({v}_{i}-\lambda {w}_{i}\right)$?
You can still ask an expert for help

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it Adelaide Barr
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 $\left[0,1{\right]}^{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\left(m\cdot n\right)$ 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 consideblack) is in general polynomial in problem size, although I suppose it could be.

We have step-by-step solutions for your answer!