Applicability of Lagrange Multipliers in the analysis of large-scale MILPs?

Question

Qualitatively, in my experience in the solving of large scale MILPs, it is common that binary variables corresponding to "edge possibility" components are frequently chosen. Intuitively, these seem associated with various "critical values" within the problem domain.

This seems to resonate with the approach of Lagrange Multipliers which identifies such critical values. I have therefore wondered whether a Lagrangian-Multiplier analysis could add significant value in the solving of MILPs. A quick online search seems to confirm that Lagrange Multipliers do indeed have a role to play.

Does anyone have practical hands-on experience about the usefulness of Lagrange-Multipliers in the solving of real-world large-scale MILP problems? If so, what techniques have you found to be the most useful?

Answer 1

I am not aware of specific algorithmic methods for MIPs that use Lagrangian multipliers directly. However, as for the interpretation of the solution of a MIP: probably one of the nicer applications I have seen comes from Martin Greiner from Aarhus university who solves a large-scale MIP of the European electricity prices with a focus on renewable energies.

By converting everything into $CO_2$ equivalents, the Lagrangian multiplier of the constraint on "how green" we want to be gives then the price needed to achieve this, i.e. the Lagrangian multipliers are interpreted in their classical way as shadow prices.

Answer 2

For an application to very large set covering problems you can see e.g. here This approach can be extended (somehow) to general MILPs and allows one to quickly find a “core” set of variables defining heuristically a restricted MILP to be solved by Cplex or alike.

Answer 3

Lagrangian relaxation is extremely common as an algorithmic method to solve facility location problems. Because many "minisum"-type problems ($p$-median, uncapacitated facility location problem, etc.) tend to have very tight LP relaxation bounds, the Lagrangian bound is also very tight.

The use of LR for facility location dates back to the 1970s—the main reference I know of from that time is Cornuejols, Fisher, and Nemhauser (1977), though there might be earlier examples too. Since it was difficult to solve LPs using the hardware and software of that time, LR methods had a big advantage over LP-based methods even though they produce the same bound (in theory).

But even today, LR-based methods for facility location are important. Even though CPLEX and Gurobi can solve very large facility location MIPs exactly, and quickly, there are problems that still cannot be solved well with those solvers. An example is the location–inventory model by Daskin, Coullard, and Shen (2002), which is a mixed-integer concave minimization problem, but can be solved very efficiently by LR.

As far as I know, there isn't a lot of work on interpreting the Lagrange multipliers themselves, but it could be done. It depends on the relaxation, of course. But for the most common relaxation for facility location (in which we relax the constraint of the form $$\sum_j y_{ij}=1\quad \forall i,$$ which says that each customer must be assigned to exactly one facility), a Lagrange multiplier can be interpreted as estimating the cost of having to assign a given customer.