Optimization Methods
Lagrangian relaxation The explanation I provide is based on Lagrangian relaxation-Wikipedia and Chapter 12 Lagrangian Relaxation-ens-lyon
Lagrangian relaxation is a relaxation method which approximates a difficult problem of constrained optimization by a simpler problem.
The method penalizes violations of inequality constraints using a Lagrange multiplier, which imposes a cost on violations. These added costs are used instead of the strict inequality constraints in the optimization. In practice, this relaxed problem can often be solved more easily than the original problem.