7.2 Lagrangian Relaxation

Computational methods based on Lagrangian relaxation have been popularly used for solving many optimisation problems, especially for mixed integer linear programming problems and combinatorial optimisation problems. The key idea behind the algorithm is typically that we relax hard constraints to make the relaxed problems relatively easier to solve. While we solve these easy problems multiple times, we update the values of Lagrangian multipliers adequately.

• Chapter 9, Julia Programming for Operations Research

7.2.1 Augmented Lagrangian Method ??

Augmented Lagrangian methods are a certain class of algorithms for solving constrained optimisation problems. They have similarities to penalty methods in that they replace a constrained optimisation problem by a series of unconstrained problems and add a penalty term to the objective; the difference is that the augmented Lagrangian method adds yet another term, designed to mimic a Lagrange multiplier. The augmented Lagrangian is not the same as the method of Lagrange multipliers. (???)