23
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 ...
- 13.1k
9
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 ...
- 8,450
9
votes
"Partial" Lagrangian Dual in LP
This is called Lagrangian relaxation, no matter what subset of constraints you choose to dualize.
- 30.5k
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-...
- 2,047
5
votes
Accepted
Augmented Lagrangian Function for Semidefinite Programming Problems
My way of reading it is $\langle X, \mathcal{A}^*(y)+S-C\rangle = \langle X, \mathcal{A}^*(y)-C\rangle + \langle X,S \rangle$. The first term is your standard inner product between dual variable and ...
- 1,702
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 ...
- 513
5
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 ...
- 13.1k
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 ...
- 2,495
4
votes
Augmented Lagrangian Function for Semidefinite Programming Problems
There's a good discussion of this in Convex Optimization by Stephen Boyd and Lieven Vandenberghe. See section 5.9.
With an ordinary scalar inequality constraint:
$f_{i}(x) \leq 0$,
you'll have a term ...
- 801
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 ...
- 6,352
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 ...
- 13.1k
4
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 ...
- 13.1k
4
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 ...
- 2,495
3
votes
Accepted
Related to Lagrangian dual
Dualizing a constraint comes back to the first, the direction of the objective function, and the second, how the dualized constraint would be violated. In your case, the constraint is written as $LHS-...
- 8,450
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 ...
- 852
2
votes
Partial Lagrangian in the Max-Flow problem
Unfortunately, there is NO guarantee to find the primal feasible solution in the context of Lagrangian relaxation, especially when it comes to solving integer programming.
In order to get a feasible ...
- 8,450
2
votes
Accepted
Partial Lagrangian in the Max-Flow problem
The error comes in assuming that, given a zero duality gap, the solution to the relaxed LP (which I agree becomes a shortest path problem) would be the optimal flow solution.
Let $X$ the set of all ...
- 37.9k
2
votes
Related to Lagrangian dual
To ease notation, let me use B as (sum_j Beta_ij.x_ij).
Then the constraint (1) is B-t <=0... You multiply this with lambda_i (let me use L for short of sum_i Lambda_i) and carry to objective ...
- 852
1
vote
Finding lower bound (maximization problem) in Lagrangian Relaxation with subgradient method
The relaxed constraints will typically be violated, but the rest of the constraints will be satisfied. To get a feasible solution to the original problem, you need to modify the relaxed solution ...
- 30.5k
1
vote
Combination of lagrangian relaxation and column generation
In theory, nothing forbids it.
I don't remember seeing any such example in the scientific literature. But here is an example of an algorithm using nested column generation, i.e. the pricing subproblem ...
- 2,495
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,...
Only top scored, non community-wiki answers of a minimum length are eligible