21 votes
Accepted

What's the difference between Lagrangian relaxation and Lagrangian decomposition?

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 ...
user avatar
9 votes

"Partial" Lagrangian Dual in LP

This is called Lagrangian relaxation, no matter what subset of constraints you choose to dualize.
user avatar
  • 21.8k
8 votes
Accepted

"Partial" Lagrangian Dual in LP

Based on the mentioned references, suppose the primal problem is: \begin{align} \begin{array}{cl} \underset{}{\text{minimize}} & c x \\ \text{subject to} & Ax = a \\ & Dx \leq e \\ & x ...
user avatar
  • 5,725
6 votes
Accepted

Difficulties with Finding a Proper Penalty Value for the Progressive Hedging Algorithm

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-...
user avatar
  • 1,957
5 votes

Using LR-based method to solve mixed integer programming

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 ...
user avatar
  • 1,421
5 votes
Accepted

Lagrangian Relaxation bound greater than optimal solution

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 ...
user avatar
  • 513
4 votes
Accepted

How to Speed Up the subgradient optimization procedure in a Lagrangian Relaxation Scheme

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 ...
user avatar
4 votes

Lagrangian Relaxation The Weak Lower Bound

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 ...
user avatar
  • 5,347
4 votes

Lagrangian Relaxation for Two-Stage Stochastic Program

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 ...
user avatar
3 votes

The variable splitting scheme in the context of Lagrangian relaxation

I am familiar with variable splitting (also known as Lagrangian decomposition) being applied to facility location problems. We used it in our paper: Snyder and Daskin, Stochastic $p$-robust location ...
user avatar
3 votes

The variable splitting scheme in the context of Lagrangian relaxation

The only occurrences of this decomposition that I am aware of are from: Jörnsten K, Näsberg M (1986) A new Lagrangian relaxation approach to the generalized assignment problem. European Journal of ...
user avatar
  • 1,421
2 votes

Lagrangian Relaxation for Two-Stage Stochastic Program

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 ...
user avatar
1 vote

Is there any academic reference which suggests/uses dual values as initialization of Lagrangian multipliers?

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,...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible