I have a large-scale IP model and I am using Lagrangian relaxation in my solution approach. By dualising a particular set of constraint, the problem "falls apart" into a number of independent sub-problems.

In the definition of LR and the subgradient method, one solves the relaxed problem for a given value of the Lagrangian multiplier vector, and then uses the whole solution to update the whole vector for the following iteration.

Since I'm solving each of these sub-problems independently, I have the option of updating the Lagrangian multiplier vector after solving each sub-problem within each iteration, rather than waiting for all the sub-problems to be solved and the solution to be combined.

Suppose the original problem is a production planning problem, and the constraints that are dualised ensured that a particular product is produced in exactly one factory. By dualising the constraints, the Lagrangian multipliers now correspond to the penalty for producing the product at factory i. If I was to solve this problem one factory at a time, I could update the Lagrangian multiplier vector after solving each factory in a particular iteration. The result would be that producing that producing the product in a factory when it hasn't yet been produced elsewhere would be rewarded; and producing it in a factory when it already has somewhere else would be penalised.

Without checking the maths, my intuition tells me that the bias of factories with low indices over those with higher indices would be at least one problem.

asked 15 Dec '14, 22:57

Ozzah's gravatar image

accept rate: 0%

Be the first one to answer this question!
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: 15 Dec '14, 22:57

Seen: 600 times

Last updated: 18 Dec '14, 17:29

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