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

Keenan Conway

Answered question

2022-09-19

I have a knapsack problem
max x { 0 , 1 } n i = 1 n v i x i s.t. i = 1 n w i x i c .
The Lagrangian relaxation is as follows
min λ 0 max x { 0 , 1 } n i = 1 n v i x i λ ( i = 1 n w i x i c ) .
Suppose I solved the relaxed problem and got an optimal x l a g s.t. f ( x ) < f ( x l a g ) where x is the optimal solution of the original problem and f is the objective function. Even though x l a g 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 λ and the maximization part with fixed λ is just activating x i associated with the largest term ( v i λ w i )?

Answer & Explanation

Adelaide Barr

Adelaide Barr

Beginner2022-09-20Added 9 answers

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 λ is O ( m 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 λ to be consideblack) is in general polynomial in problem size, although I suppose it could be.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Multivariable calculus

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?