11
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Are you asking about the use of Lagrangian relaxation as an algorithmic method for MILP, or about the use of the multipliers specifically, e.g., their interpretation as dual values? $\endgroup$ – LarrySnyder610 Jun 20 '19 at 2:57
  • $\begingroup$ More the former, though I would be happy to learn about anything relevant. I wonder also whether a Lagrangian approach could be used in the pre-MILP phase. Often we need to "pick and choose" which binary variable possibilities to include in a MILP, as to include all possibilities would make the problem size too large. I wonder whether a Lagrangian analysis could provide more sophistication in this choosing? $\endgroup$ – Mark H Jun 20 '19 at 3:04
  • $\begingroup$ I was about to post an answer about the use of LR In facility location, but maybe that’s not what you’re after? $\endgroup$ – LarrySnyder610 Jun 20 '19 at 3:06
  • $\begingroup$ @LarrySnyder610 Probably not precisely, but I am still interested in it. $\endgroup$ – Mark H Jun 20 '19 at 3:53
  • $\begingroup$ OK I will post something tomorrow. You might want to edit your question if there’s something more specific you’re interested in (eg, pre-MILP). $\endgroup$ – LarrySnyder610 Jun 20 '19 at 3:55
6
$\begingroup$

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.

| improve this answer | |
$\endgroup$
6
$\begingroup$

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.

| improve this answer | |
$\endgroup$
5
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The interpretation of Lagrangian multipliers is akin to that of dual variables for LPs: it gives the cost/difficulty to satisfy the corresponding constraint. $\endgroup$ – Matteo Fischetti Jun 20 '19 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.