I designed lagrangian relaxation for a MIP problem by dualizing single constraint and got slightly better results than direct CPLEX solution. Now, I would like to know has anyone dualized more than one constraint while designing lagrangian relaxation? I tried to dualize two constraints but it has given me bad results.

With respect to Lagrangian Relaxation, any advice or 'points-to-keep-in-mind' while dualizing more than one constraint will be helpful. Appreciate your response.

asked 12 Jul '14, 12:10

Pavan's gravatar image

accept rate: 0%

edited 12 Jul '14, 12:10


In what sense are the results worse? The bound will naturally be worse but imbedded in branch and bound this might be balanced by maximizing the Lagrangian dual faster. If you are interested in more details about Lagrangian relaxation, I would strongly suggest you to read the survey paper "Lagrangean relaxation" by Monique Guignard.

(13 Jul '14, 02:43) Sune

For a small instance of problem, Lagrangian with two constraints dualized -- the solution procedure (using CPLEX 12.0) kept running even after few hours. The direct CPLEX took only ~12 minutes.

Later I designed a different variant which dualized single constraint -- this produced solutions in 522 seconds with optimality gap of 0.01%.

Thank you for your paper suggestion, looks interesting!

(13 Jul '14, 12:56) Pavan

Relaxing multiple constraints is quite common, and I can't think of any special advice about it. My sense (based on limited experience) is that if you relax too many constraints (make the relaxed problem too easy) it tends to backfire. On the other hand, if the relaxation lets you decompose the model, that may help.


answered 12 Jul '14, 16:31

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

Dr. @Paul Rubin: Is there a set of conditions that would help decide which constraint(s) would be ideal to dualize?

(13 Jul '14, 12:51) Pavan

Not that I know of. In my experience, at least, it's trial and error. The only blanket statement that I can recall is that if the relaxed problem is too easy (which IIRC means the LP relaxation of the Lagrangian relaxation has the integrality property), the bound you get by LR will at best match the ordinary LP bound, and you'll have accomplished nothing. (That's a theorem somewhere -- Fisher's '81 paper?) Other than that and maybe getting a decomposable structure, I can't think of anything useful.

(13 Jul '14, 14:05) Paul Rubin ♦♦

Paul is correct--if the LP relaxation of the relaxed problem has integer optima, then the best possible relaxation bound is the same as the LP relaxation bound. But the relaxed problem might be solved much more efficiently than the LP relaxation.

The best general advice is to try to relax constraints that lead to the tightest possible bound. Even if you don't solve the relaxation dual optimally, you can still get good bounds from a heuristic dual solution. Also look for relaxations where good dual solutions can be found quickly. Decomposition fits here.

(13 Jul '14, 14:55) Matthew Salt... ♦

I've experimented with dualizing >1 set of constraints, though a while ago. I remember trying it two ways: (1) Dualizing 2 sets of constraints simultaneously, and (2) dualizing one set of constraints, and then dualizing the second set of constraints in order to solve the subproblem for the first relaxation (a sort of nested approach). I can't remember which worked better -- I believe method #2, actually -- but that might be very problem specific. In approach (1) you have to be careful in the multiplier update step, especially if the constraints have very different scales. Both approaches can be cumbersome to code. In my experience with Lagrangian relaxation in general, there is a lot of coding and experimentation whenever you're trying something non-standard like this.


answered 18 Jul '14, 12:39

LarrySnyder's gravatar image

accept rate: 0%

The maximum number of constraints that I have ever dualized is 1600 when solving generalized assignment problems. When solving such problems there are two options: dualize assignment constraints that are associated with each job or dualize capacity constraints. In the first case, while the number of multipliers to adjust is large, the resulting lower bound is tighter and the quality of the solutions that can be obtained are much better.


answered 11 Sep '14, 16:20

Mikhail%20Bragin's gravatar image

Mikhail Bragin
accept rate: 0%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 12 Jul '14, 12:10

Seen: 2,759 times

Last updated: 11 Sep '14, 16:20

OR-Exchange! Your site for questions, answers, and announcements about operations research.