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).

Linear Programming is an optimization technique where both the objective function and constraints are linear. The standard form is: maximize (or minimize) z = c₁x₁ + c₂x₂ + ... + cₙxₙ subject to linear constraints a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁, and xᵢ ≥ 0. LP is used extensively in resource allocation, production planning, transportation, diet optimization, and financial portfolio management. The feasible region forms a convex polyhedron, and optimal solutions occur at vertices.

LP Relaxation transforms an integer program into a linear program by relaxing integrality restrictions, allowing variables to take continuous values. For binary variable x ∈ {0,1}, relaxation gives 0 ≤ x ≤ 1. The LP relaxation provides: (1) lower bound on optimal integer solution value (for minimization); (2) indicator of problem difficulty (large gap suggests hard problem); (3) basis for branch-and-bound algorithms. If LP relaxation solution is integer, it's optimal for the original IP. Strong formulations have tight LP relaxations (small gap). Techniques to strengthen: adding valid inequalities, reformulation, and extended formulations with additional variables. LP relaxation quality fundamentally determines integer programming solver performance.