Lagrange relaxation / subgaradient algorithm Sensivity to input data

I am implementing a Lagarange relaxation with subgradient method to find a lower bound for a minization problem, I tried to find the complicating constraints. I found an upper bound with relatively small amount of time(2-4 minutes) with a gap=0.65%. Howerver, when I tried to increase the size of the problem the algorithm did not perform the same, and I had to tune again the initial parameters, most of the time, the upper bound is worse that the first one or even did not report any improvement. Is this issue usual or something is wrong with the implementation ( I should mention that I relaxed three constraint, two of them constains binary variables, and both did not report lamda i.e lamda=0). The problem is formulated in budget uncertainty set, and I am relaxing the robust problem with gamma(set size)=1, is this implementation valid or I have to relax the problem as determinic ie gamma =0. The other thing is that I have found on the literature that they compete with solvers in terms of solving large scale problem, in this case do I have to do the to say the algorithm is valid.

• Welcome to OR.SE. Would you see these links 1, 2, 3? Sep 16, 2023 at 17:12
• Thank you for sharing the links, unfortunately, non of them answered my concern!
– ABDE
Sep 16, 2023 at 18:01
• I am not aware of if using the LR to solve a problem with a budget uncertainty set would be quite different from the classical LR method. But, if your question is, most of the time, the upper bound is worse than the first one or even did not report any improvement. Is this issue usual or something is wrong with the implementation the quick answer would be it is almost usual in the LR context. The LR, as it name also says, only provides a bound. Sep 17, 2023 at 11:12
• And there is NO guarantee to achive a feasible solution or even a better solution than the first you can provide as an initial one. In the mentioned links the ways you can get a feasible solution have been described. Sep 17, 2023 at 11:12
• my major concern is to find a good lower bound using lagrange and subgradient, my question is about data input, for example I run it with small problem and it performs well, but when I scale up the problem, everything changed.
– ABDE
Sep 17, 2023 at 16:06