# 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.

11 questions
Filter by
Sorted by
Tagged with
206 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 =...
74 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 \\ &...
110 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 "...
101 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$. ...
111 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. ...
135 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 ...
169 views

202 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 ...
255 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.}&\...