# Lagrangian Relaxation Lower Bound exceeds the Upper bound and the Optimal solution

I'm trying to minimize an MIP model employing a Lagrangian relaxation approach. However, I've encountered an issue where, in certain instances, the lower bound (resulting from the Lagrangian sub-problems) surpasses both the upper bound (resulting from the Master problem) and the optimal solution of the original problem. Consequently, no Lagrangian bound is obtained, as the lower bound continues to outpace the upper bound, while the upper bound steadily decrease. I tried to enhance the accuracy of the models, the issue is still there. The MIP model is attached, I relaxed the second constraint which gives me two subproblems one in x (binary) and z (binary) and one in y (continuous). I use a random multiplier to solve the subproblems, then I use their solutions to add cuts to the master problem and update the Lagrangian multipliers and solve the subproblems again and go on like that. The lower bound is obtained by adding the optimal solutions of the subproblems while the upper bound is obtained by solving the master problem.

• Welcome to ORSE. You will need to provide more details for anybody to be able to help diagnose what's going wrong. Please describe the original problem, the master problem, the subproblem, and your bound calculation. Commented Feb 5 at 22:31
• Plug the optimal solution into the Lagrangian relaxation. If the relaxation is done correctly, all the penalty terms should be a positive penalty weight multiplying a zero or negative constraint violation (negative violation meaning a surplus in a $\ge$ constraint or slack in a $\le$ constraint.
– prubin
Commented Feb 5 at 22:43
• Yeah it works when I use the optimal solution. However, I relaxed an equality constraint, so, I set the penalty weight (if that's what you mean by the Lagrangian multiplier) to a free variable for the Master problem. Commented Feb 5 at 22:53
• My original problem is a network design problem, I relaxed the flow balanced constraint and now have two subproblems. I am using the cutting plain algorithm to add cuts to my Master problem to obtain an upper bound by solving it. Please let me know if you need more info Commented Feb 5 at 22:56
• It would be helpful to edit your question to include the algebraic formulations of the problems and the formula you are using for the bound. Commented Feb 5 at 23:34

1. First, the objective value of the master problem does not provide an upper bound. Instead, an upper bound for a minimization problem comes from a feasible solution. That is, you must satisfy all of the original constraints, even the complicating constraints that link $$x$$ and $$y$$.
2. Second, the sum of the subproblem objective values does not provide a lower bound. Instead, you must compute the Lagrangian function $$L(\pi)$$ for the given master dual variables (also known as Lagrange multipliers) $$\pi$$, which are free here because you are relaxing equality constraints.