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 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
Ozzah |