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
6
votes
1answer
101 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
0answers
97 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$. ...
3
votes
1answer
99 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. ...
4
votes
1answer
132 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 ...
5
votes
2answers
161 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 \\&\...
10
votes
1answer
187 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 ...
14
votes
1answer
242 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.}&\...
11
votes
1answer
187 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 ...
18
votes
1answer
703 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?