Lagrangian Relaxation for Two-Stage Stochastic Program

Question

I have a two-stage stochastic program as follows: \begin{align}\max&\quad f^\top y+\sum_{s}p_sc_s^\top x_s\\\text{s.t.}&\quad Ay=b\\&\quad W_sX_s+Ty \le h_s \quad \forall s \in S \\&\quad P_sx_s \le q_s \quad \forall s \in S \\&\quad x_s \ge 0\\&\quad y\in \{0,1\}&\quad\end{align} and I want to solve it with Lagrangian relaxation. I relaxed the constraints $$W_sX_s+Ty \le h_s \quad \forall s \in S,$$ and it is decomposed to a first-stage problem and $|S|$ sub-problems related to the second stage. I solved the problem but there is a huge gap between lower and upper bounds. I think I correctly applied the algorithm (Gurobi+Python), but I do not know why it happens.

Also, I have used Benders decomposition to solve this problem and because the coupling constraints are related to capacity constraints and because these constraints are not active in the optimal solution, the dual variables corresponding to these constraints are mostly zero and in generated cuts, most $y$ variables have coefficients $0$ and it does not converge (or at least in a reasonable number of iterations).

I also used combinatorial Benders decomposition but it just excludes each solution and works like enumeration.

I would be thankful if someone has a similar experience and let me know what I can do.

Answer 1

I'll comment on the Lagrangian relaxation question and leave the Benders question for someone else to comment on. (You might want to consider splitting your question into two, one for LR and one for BD.)

In my experience, this sort of gap is common. (And frustrating.) There are a few avenues you could go down in order to try to diagnose and maybe fix the problem.

First, remember that there is no guarantee that the Lagrangian bound will be tight, i.e., will equal the optimal objective function value of the original problem, even if you have the optimal Lagrange multipliers. There is a duality gap, and it might be non-zero. So, it's possible you did everything right but the bounds are just inherently far apart.

Second, it looks like you're running for ~50 iterations. In my experience it usually requires a few hundred to several hundred iterations before you can be confident that the bounds are close to where they should be. That's one reason why it's important to have subproblems that are easy to solve. (Are you solving your subproblem using Gurobi? If so, that might be a signal that LR is going to take too long to converge.)

Third, how are you updating the Lagrange multipliers? If you're using subgradient optimization, there are several parameters you can play around with. In addition, you can consider using other types of methods (bundle methods, etc.) in place of subgradient optimization.

Fourth, the initial multipliers that you feed the algorithm can have a large effect on convergence. If you can find a way to easily identify multipliers that might be in the ballpark, you can use these as your initial multipliers.

In the end, this sort of thing just requires a lot of experimentation and trial-and-error.

Answer 2

Larry Snyder explained very well. Few items to check/add for the Lagrangean Relaxaiton part:

• Make sure your lowerbounds- i.e. the feasible solution (most probably depending on fixed first stage variables)- are computed correctly. I usually do it with a very small instance and double check it with hand calculations
• Similarly double-check you upperbound computations (optimal LR solution).
• Are you using subgradient optimization to update LR multipliers? If so you should double check the subgradient computations and then the multiplier computations. Usually it is where most of the mistakes occur.
• As Larry highlighted, you should have larger number of iterations. Actually the best way is, for a very small instance, set your stopping criteria to a very tight value like 0.00000001 and also set your iteration limits to thousands. So that you can be almost sure that you find the optimal solution (LB). Of course if you can compare this with the exact solution it would be even better.
• You can check if the LR problem has integrality property by either proving/disproving it or by solving the LP relaxation of your original problem. If your UBs converge to the LP relaxation (again you should run many iterations) then you have the curse of integrality property, where your UB can never be better than the LP relaxation.