0

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.

ABDE
  • 1
  • 3
  • Welcome to OR.SE. Would you see these links 1, 2, 3? – A.Omidi Sep 16 '23 at 17:12
  • Thank you for sharing the links, unfortunately, non of them answered my concern! – ABDE Sep 16 '23 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. – A.Omidi Sep 17 '23 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. – A.Omidi Sep 17 '23 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 '23 at 16:06
  • As far as I see, at least in my experience, in the LR with some of the scheduling problems, some of them can be solved in the few iterations with a good LB even for the large data set, while the others cannot. I think it heavily depends on the problem formulation and the dualized constraint(s). – A.Omidi Sep 18 '23 at 07:52
  • As a rule of thumb, this method works well on the problem as long as only one of the constraints is being dualized. (Removing the constraints definitely destructs the feasible space). Also, for example, when you have some kinds of disjunctive constraints, especially in the BigM form, relaxing this constraint usually yields a worse LB. – A.Omidi Sep 18 '23 at 07:53

0 Answers0