Engineering
Lagrangean Relaxation for Capacity-Constrained Facility Location
Quick fact
With Lagrangean relaxation, you can often solve a capacitated facility location problem with 100 facilities and 1000 customers in under a second — something that would take minutes or hours with a generic integer-programming solver.
Why this is interesting
You need to decide where to build warehouses so that you can serve all customers cheaply — but each warehouse can only handle so much demand. How do you solve that almost instantly, even for hundreds of cities?
Read the full explanation
Understanding Lagrangean Relaxation for Capacity-Constrained Facility Location
Think of it as the mathematical equivalent of an accountant who knows the hard budget limits but is willing to temporarily ignore them to get a rough estimate, then adjusts the penalty until the rough estimate aligns with reality.
A deeper explanation
The mechanism is iterative: you initialize the multipliers (maybe all zero), solve the decomposed subproblems, compute the resulting bound, then update the multipliers based on constraint violations (the subgradient). This process is the subgradient algorithm. Each iteration improves the lower bound, and you stop when you reach a target gap or after a fixed number of iterations. The key theoretical insight is that the Lagrangean dual is a concave piecewise-linear function, so subgradient optimization finds a good (often optimal) multiplier set. The bound obtained can be much tighter than the LP relaxation, especially when the problem has complicating constraints that make the LP bound weak. In practice, after solving the relaxed problem, you often need to "repair" the solution to make it feasible (e.g., if some facility is over capacity, you reassign customers). This yields a feasible solution, and its cost gives an upper bound on the true optimum. The gap between the lower and upper bounds tells you how close you are to optimal. Often, the gap is less than 1%. This technique is not just for facility location — it is used in many problems where the constraints have a special structure, such as the traveling salesman problem, the vehicle routing problem, and the set covering problem. Its importance lies in turning a monolithic hard problem into a set of manageable subproblems, while providing a rigorous bound on solution quality.