Lagrangian Relaxation is a technique for obtaining bounds on optimal values by relaxing difficult constraints into the objective function using Lagrange multipliers. For problem: min f(x) subject to g(x) ≤ 0, h(x) = 0, x ∈ X, the Lagrangian is L(x,λ,μ) = f(x) + λᵀg(x) + μᵀh(x). The Lagrangian dual: max_λ≥0,μ min_x∈X L(x,λ,μ) provides lower bounds (for minimization). Solved using subgradient optimization to update multipliers. Strong duality holds for convex problems. Applications: integer programming (relaxing integrality), network design, scheduling, and decomposition methods. Particularly effective when relaxed problem is easily solvable (e.g., becomes a network flow problem).