Is there any academic reference which suggests/uses dual values as initialization of Lagrangian multipliers?

Question

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 "Lagrangian multipliers".

The sub-gradient algorithm tries to improve the bounds by updating the Lagrangian multipliers. There are some codes which initialize the Lagrangian multipliers by the dual value of the constraints in the optimal solution of the linear relaxation of the problem (e.g., https://www.gams.com/latest/gamslib_ml/libhtml/gamslib_gapmin.html).

This approach is problem-independent and seems to perform better than initialization by zero vectors. However, I could not find any textbook or paper which suggested or used this initialization. I wondered if you could help by introducing such a reference.

Answer 1

Short answer: Here is a paper that uses the dual values

Akbari, V., & Salman, F. S. (2017). Multi-vehicle prize collecting arc routing for connectivity problem. Computers & Operations Research, 82, 52-68. https://doi.org/10.1016/j.cor.2017.01.007

Some additional points: The sub-gradient method is a heuristic approach to solve the Lagrangian Dual problem. It gives you good but not necessarily optimal set of multipliers, after reaching an arbitrary iteration limit. Depending on the complexity of the sub-problems the method is also expected to be very quick. In literature, the natural choice for the initial multiplier values has been 0, perhaps because over a moderate number of iterations, the choice does not significantly affect the computational time and bound quality in most cases. I have experienced the same while implementing Lagrangian relaxation to solve the Team Orienteering Problem.

However, it is definitely prudent to experiment with different set of initial values and go for the one which gives best result for the particular problem. An example of a different starting point for the Generalized Assignment Problem can be found here:

Fisher, M. L. (2004). The Lagrangian relaxation method for solving integer programming problems. Management science, 50(12_supplement), 1861-1871. https://doi.org/10.1287/mnsc.1040.0263