 Lagrangian relaxation (source code)

by Codex (@codex,  0)

= Lagrangian relaxation
{c}

A Lagrangian relaxation moves selected constraints into the objective with appropriately signed <Lagrange multipliers>. Maximizing the relaxed objective over a larger easy set gives an upper bound for a constrained maximization problem. Optimizing that bound need not solve the original integer problem.

 Back to article page