Questions tagged [lagrangian-relaxation]
For questions related to Lagrangian relaxation, a method used to generate bounds on optimization problems by removing one or more constraints and including a penalty in the objective function for violating the removed constraints.
18
questions
0
votes
0
answers
45
views
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 ...
- 1
0
votes
1
answer
55
views
Finding lower bound (maximization problem) in Lagrangian Relaxation with subgradient method
I have tried to implement a toy problem (MIP) from the literature using Lagrangian Relaxation with the subgradient method, I implemented it correctly and I got the upper bound which is updated at each ...
- 1
1
vote
2
answers
83
views
Combination of lagrangian relaxation and column generation
I am solving an integrated scheduling problem and have dealt with coupling constraints using Lagrangian relaxation to decompose the problem into two separate problems. However, it is still difficult ...
- 11
3
votes
2
answers
121
views
Partial Lagrangian in the Max-Flow problem
In the question:
"Partial" Lagrangian Dual in LP
It is argued that considering a partial Lagrangian $L_{partial}$, where we Dualize only some of the constraints, results in a tighter ...
- 143
3
votes
2
answers
264
views
Related to Lagrangian dual
In my research class our professor discuss a paper wherein the solution is obtained via a Lagrangian duality. The original problem is given below:
minimize $t$
subject to $\sum_{j \in \mathcal{M_i}}\...
- 33
3
votes
2
answers
98
views
Augmented Lagrangian Function for Semidefinite Programming Problems
I am currently reading the paper "Alternating direction augmented Lagrangian methods for semidefinite programming" and was wondering about how one comes up with the Augmented Lagrangian ...
- 33
5
votes
2
answers
300
views
The variable splitting scheme in the context of Lagrangian relaxation
I am interested to know solving the generalized assignment problem (GAP) using the variable splitting scheme, specifically, in the context of Lagrangian relaxation. The problem is stated as follows: (...
- 8,450
9
votes
2
answers
954
views
"Partial" Lagrangian Dual in LP
Consider the optimization problem
\begin{align}\label{opt-lp}\tag{Primal}
\begin{array}{cl}
\underset{x \in \mathbb{R}^n}{\text{minimize}} & c^\top x \\
\text{subject to} & Ax = a \\
& Bx =...
- 3,980
2
votes
0
answers
88
views
How to figure out integer variables in the relaxation set?
Suppose, there is mixed-integer programming as follows:
$(1)$
$$\begin{aligned}
\min&\quad c^{\top} x\\
\text{s.t.}& \quad A x \geq b \\
&\quad B x \geq d \\
&\quad x \geq 0 \\
&...
- 8,450
7
votes
1
answer
212
views
Is there any academic reference which suggests/uses dual values as initialization of Lagrangian multipliers?
The Lagrangian relaxation approach is used to generate lower (upper) bounds for minimization (maximization) problems by moving some constraints to the objective function and multiplying them by "...
7
votes
0
answers
120
views
Estimate lagrangian multiplier based on instance characteristics
Assume we have a simple resource allocation problem, where all players have the same cost, but a different utility $a_s$. The resources assigned to a certain player must be between $L$ and $M$. ...
- 123
3
votes
1
answer
175
views
Lagrangian Relaxation The Weak Lower Bound
I am applying Lagrangian Relaxation with Subgradient Optimization Method and trying to solve a MIP model. Before testing the large-scale instances, I wanted to see how it performs on small-size ones. ...
- 31
4
votes
1
answer
263
views
Using LR-based method to solve mixed integer programming
When we use Lagrangian relaxation-based methods to solve mixed integer programming, does the convergence of multipliers to the optimum as well as convergence of primal variables to the optimum happen ...
- 41
6
votes
2
answers
314
views
Lagrangian Relaxation for Two-Stage Stochastic Program
I have a two-stage stochastic program as follows:
\begin{align}\max&\quad f^\top y+\sum_{s}p_sc_s^\top x_s\\\text{s.t.}&\quad
Ay=b\\&\quad
W_sX_s+Ty \le h_s \quad \forall s \in S \\&\...
- 2,150
10
votes
1
answer
337
views
Lagrangian Relaxation bound greater than optimal solution
I am working on a Lagrangian relaxation for a minimization MIP.
Everything seemed to be working fine before I started to run a batch of instances.
Checking the log results for one of the instances ...
- 513
14
votes
1
answer
368
views
How to Speed Up the subgradient optimization procedure in a Lagrangian Relaxation Scheme
I'm currently working on the following problem (a variant of maximal k-covering problem):
\begin{align}
\max&\quad z =\sum\limits_{\omega\in \Omega}x_{\omega}
\label{imbip3a} \\
\text{s.t.}&\...
- 852
11
votes
1
answer
254
views
Difficulties with Finding a Proper Penalty Value for the Progressive Hedging Algorithm
Recently, I've been working on some two-stage stochastic programming problems. Due to the presence of integer second-stage variables in the model, I've preferred to use the Progressive Hedging ...
- 2,438
20
votes
1
answer
2k
views
What's the difference between Lagrangian relaxation and Lagrangian decomposition?
What is the difference between Lagrangian relaxation and Lagrangian decomposition? Are they the same thing?
- 13.1k