# Finding lower bound (maximization problem) in Lagrangian Relaxation with subgradient method

I have tried to implement a toy problem (MIP) from the literature using Lagrangian Relaxation with the subgradient method, I implemented it correctly and I got the upper bound which is updated at each iteration, however, for the lower bound (original problem), I optimized it to using a solver inside the algorithm, but in the literature, it has been mentioned that we can make use of relaxed problem solution to find a lower bound (maximization problem), most of them they refer to a heuristic to find such lower bound because in most cases the solution of relaxed problem will be infeasible to the original one, but I did not figure it out, do I have to optimize the lower bound using the solution from LR and solver or just plug the solution of the relaxed problem into the original problem ( in this case it will not work, as I have tried it before).

• Related question: or.stackexchange.com/questions/5426/… Aug 14, 2023 at 16:19
• @fontanf Thank you for redirecting me to that link, it was useful but most of the literature takes the LR algorithm as a lower and upper bound as one algorithm, although without finding the upper bound we will not know how far are we from the optimal solution.
– ABDE
Aug 15, 2023 at 11:34
• Sorry, I don't understand your comment. For a maximization problem, LR directly provides an upper bound. The solution of the LR is in general infeasible. To get a feasible solution (lower bound), another algorithm is needed, such as branch-and-bound Aug 16, 2023 at 7:24
• Sorry, I was talking in general which is typically for minimization problems, my comment should be "finding a lower bound ( original problem) ..." which is related to my question.
– ABDE
Aug 16, 2023 at 9:13

The relaxed constraints will typically be violated, but the rest of the constraints will be satisfied. To get a feasible solution to the original problem, you need to modify the relaxed solution somehow to satisfy all the constraints. Such a "repair" heuristic is usually problem-specific. For example, Section 10.4 of Wolsey's Integer Programming describes a greedy heuristic when the original problem is set covering and all covering constraints are relaxed: ignore the rows that are already covered by the relaxed solution, and greedily change some variables from $$0$$ to $$1$$ to cover the rest.