1
$\begingroup$

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. enter image description here

$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$
    – RobPratt
    Commented Feb 5 at 22:31
  • $\begingroup$ 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. $\endgroup$
    – prubin
    Commented Feb 5 at 22:43
  • $\begingroup$ 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. $\endgroup$
    – NCyeah
    Commented Feb 5 at 22:53
  • $\begingroup$ 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 $\endgroup$
    – NCyeah
    Commented Feb 5 at 22:56
  • 2
    $\begingroup$ 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. $\endgroup$
    – RobPratt
    Commented Feb 5 at 23:34

1 Answer 1

3
$\begingroup$

That sounds like a good choice for a relaxation, but you haven't explicitly shown how you compute the bounds. From your description so far, I suspect that you have two errors.

  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.
$\endgroup$
1
  • $\begingroup$ Yes you are right. By upper bound I meant an upper bound on the Lagrangian bound, and by the lower bound I meant a lower bound on the Lagrangian bound. Once these two values are equal, then you have the Lagrangian bound. After that, I use the x and z from the first subproblem and using a Lagrangian heuristic I calculate an upper bound on the original problem. If my Lagrangian bound and the upper bound obtained by the heuristic are equal, I have obtained the optimal value of the original problem. $\endgroup$
    – NCyeah
    Commented Feb 6 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.