Tag Info

They are not the same thing. Lagrangian decomposition is a special case of Lagrangian relaxation. (Note: I'm talking specifically about integer programming problems in this answer, though some of this answer applies to continuous optimization as well.) Lagrangian relaxation involves removing (relaxing) one or more constraints and penalizing violations of ...

This problem is addressed in some detail in Section 2.1 of the paper Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems by Watson and Woodruff (a non-paywall version is given here). In general, proper selection can be quite tricky and is highly problem-specific. I recommend trying some of the tricks in the ...

As its name indicates, a Lagrangian relaxation is a relaxation and therefore only provides a dual bound. If you are interested in getting a primal solution, you have several ways to exploit a Lagrangian relaxation: Designing a procedure to "repair" the infeasible solutions generated at each iteration of the resolution method of the Lagrangian ...

After the discussion here and a suggestion on my post at gurobi's community I'll post an answer for the forum records. Concerning the presolve, I found out that in order to check if this is what is getting strange results some parameters to change are: 'Presolve':0, 'Cuts':0, Turns out that on my problem the issue wasn't bad code of the subgradient method,...

In my experience, this sort of thing just requires a lot of trial and error. An SO variant that works well for one problem may not work as well for another, so you just have to implement and test a lot of stuff. Having said that, one important thing to determine is how good the (upper) bound is. That is, if you could find the optimal multipliers, how tight ...

A problem with subgradient optimization is the phenomenon of “zigzagging” in the vicinity of the optimal solution. That is, it is often seen that the direction of search in one step is almost opposite to the search direction in the previous step. This often yields very slow convergence. Many different schemes to prevent this behavior have been proposed in ...

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 ...

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 ...

Short answer: Here is a paper that uses the dual values Akbari, V., & Salman, F. S. (2017). Multi-vehicle prize collecting arc routing for connectivity problem. Computers & Operations Research, 82, 52-68. https://doi.org/10.1016/j.cor.2017.01.007 Some additional points: The sub-gradient method is a heuristic approach to solve the Lagrangian Dual ...