Lagrangian Relaxation

Lagrangian relaxation turns a hard constrained problem into a sequence of easier ones: move constraints into the objective with penalty multipliers (Lagrange multipliers), then solve the relaxed problem. Adjust multipliers to push the solution toward feasibility. When the original problem has tight coupling (e.g. scheduling, routing, capacity), the relaxed version often decomposes into subproblems that are tractable. You trade exactness for speed—the relaxed optimum gives a bound (dual bound); with good multipliers you get near-feasible, near-optimal solutions. Central to integer programming, resource allocation, and network design.

When the full constrained problem is too hard, identify which constraints can be dualised (moved into the objective with multipliers). Solve the relaxed problem; use its solution and multiplier updates (subgradient, cutting-plane) to close the gap. Use the dual bound to judge solution quality. In product or ops: treat rigid constraints as soft penalties, optimise, then tighten until you're "close enough" to feasible—same conceptual move.

Lagrangian relaxation dualises hard constraints into the objective with multipliers, yielding easier (often decomposable) subproblems and a dual bound. Iterate on multipliers to approach feasibility and near-optimality. Use it when the full constrained problem is intractable.