Lagrangian Relaxation..

By Suzan Afacan

In my research, I am using Lagrangian relaxation dual to solve the mixed integer problem. This week I would like to explain the basics of Lagrangian Relaxation.

One of the most useful methods to solve combinatorial optimization models, especially for larger instances, is Lagrangian relaxation. Not only can we obtain a lower bound to the original (minimizing) model, but we can also obtain a feasible solution and upper bound to the original model by using Lagrangian relaxation dual. The most important feature of Lagrangian relaxation is making a difficult problem easier by relaxing the hard constraints.

The basic steps of the relaxation are:

  • Take an integer or mixed integer programming formulation,
  • Attach a Lagrangian multiplier to the constraints in the formula (you need to use an educated guess or luck to find the best constraint)
  • Relax these constraints into the objective function,
  • Solve this resulting integer programming optimally,
  • This optimal solution gives us a lower (upper) bound to the original minimization (maximization) problem.

Mathematically speaking, here is a general example:

example

To solve Lagrangian relaxation dual the most often used method is the Subgradient Algorithm. Here is the basic outline of the Subgradient Algorithm:

subgrad

The Subgradient Algorithm requires an upper bound on the original objective as an input. We need to set the starting value for Lagrangian multiplier u, the decreasing parameter Θ to 2 and the best bound to negative infinity.

Here we can choose some of the values problem specifically. For instance,the starting value for u can be set to 0, or better starting values can be found depending on the problem. The important property for the step size is

Screen Shot 2016-03-28 at 11.11.53 PM

We want to reduce the stepsize such that it is not going to stick before finding the optimal value, but also we want to make sure that we are not shrinking the search area too quickly. Even though the formula used in the Subgradient Algorithm (Polyak’s formula) might provide a good solution for the Lagrangian relaxation dual, other choices of step size which satisfy the properties above might be better than Polyak’s formula depending on the problem.

To conclude,

Lagrangian relaxation can be used to solve difficult problems by relaxing the most difficult constraints, but you need to find the best choices for the constraints to relax on and the step size to get best Lagrangian Relaxation solution. If you can find the best choices for your problem, Lagrangian relaxation will be a great method. Even if you cannot find the best choice, Lagrangian relaxation will still give you a lower bound and it is not hard to construct a feasible solution using the Lagrangian relaxation dual solution to get an upper bound on the original problem.

 

References:

Comments on The Lagrangian Relaxation Method for Solving Integer Programming Problems. (2004). 50(12 supplement), 1872-1874.

K. Ahuja, T. L. Magnanti and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.

 

 

Advertisements

2 thoughts on “Lagrangian Relaxation..

    1. Lagrangian Relaxation can be used for linear and also for nonlinear optimization problems. The method is pretty much problem specific so it is hard to say how good it works in general. Though, when we look at the literature Lagrangian relaxation usage has great improvements for lots of important problems such as routing, location, scheduling, assignment and set covering. Indeed, in the literature first Lagrangian Relaxation used successfully by Held and Karp (1970, 1971) on minimum spanning trees. There is great literature review by Fisher (2004) “The Lagrangian Relaxation Method for Solving Integer Programming Problems” gives great overview about the subject.

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s