Skip to main content

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.

Filter by
Sorted by
Tagged with
1 vote
1 answer

Lagrangian Relaxation Lower Bound exceeds the Upper bound and the Optimal solution

I'm trying to minimize an MIP model employing a Lagrangian relaxation approach. However, I've encountered an issue where, in certain instances, the lower bound (resulting from the Lagrangian sub-...
NCyeah's user avatar
  • 19
0 votes
0 answers

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 ...
ABDE's user avatar
  • 1
0 votes
1 answer

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 ...
ABDE's user avatar
  • 1
1 vote
2 answers

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 ...
XXia's user avatar
  • 49
3 votes
2 answers

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 ...
Cris's user avatar
  • 143
3 votes
2 answers

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}}\...
chaaru's user avatar
  • 33
3 votes
2 answers

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 ...
benebrue's user avatar
5 votes
2 answers

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: (...
A.Omidi's user avatar
  • 8,950
9 votes
2 answers

"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 =...
independentvariable's user avatar
2 votes
0 answers

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 \\ &...
A.Omidi's user avatar
  • 8,950
7 votes
1 answer

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 "...
Mehdi Iranpoor's user avatar
7 votes
0 answers

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$. ...
Pete S's user avatar
  • 123
3 votes
1 answer

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. ...
Learner444's user avatar
4 votes
1 answer

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 ...
user14153's user avatar
6 votes
2 answers

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 \\&\...
Amin's user avatar
  • 2,160
10 votes
1 answer

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 ...
seimetz's user avatar
  • 513
14 votes
1 answer

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.}&\...
Evren Guney's user avatar
11 votes
1 answer

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 ...
Ehsan's user avatar
  • 2,463
20 votes
1 answer

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?
LarrySnyder610's user avatar