4
$\begingroup$

When we use Lagrangian relaxation-based methods to solve mixed integer programming, does the convergence of multipliers to the optimum as well as convergence of primal variables to the optimum happen at the same time?

$\endgroup$
5
$\begingroup$

As its name indicates, a Lagrangian relaxation is a relaxation and therefore only provides a dual bound. If you are interested in getting a primal solution, you have several ways to exploit a Lagrangian relaxation:

  • Designing a procedure to "repair" the infeasible solutions generated at each iteration of the resolution method of the Lagrangian relaxation (bundle method, subgradient method...). Thus, at each iteration of the Lagrangian relaxation resolution, you should get better solutions since the dual information that you get becomes more and more accurate. However, there is no guarantee to get the optimal solution at the end or even just to get a feasible solution. This can be a good choice if solving the Lagrangian relaxation is so costly that it does not terminate within your time limit. An example for the Set Covering Problem: "A lagrangian heuristic for set‐covering problems" (Beasley, 1990)
  • Embedding the Lagrangian relaxation inside a branch-and-bound algorithm. It is similar to a LP-based branch-and-bound, but at each node, you solve a (whole) Lagrangian relaxation instead of a linear relaxation. Therefore, you get optimal multipliers at each node for the corresponding node subproblem. The branch-and-bound provides an improving global dual bound as the search goes and if it terminates, it guarantees to return the optimal solution if there is one. An example for the Generalized Assignment Problem: "An exact method with variable fixing for solving the generalized assignment problem" (Posta et al., 2012)
  • Computing the relaxation and then using the Lagrangian information inside another algorithm, for example inside a local search algorithm. Usually, there is no guarantee to find the optimal solution. An example for the Generalized Assignment Problem: "A path relinking approach with ejection chains for the generalized assignment problem" (Yagiura et al., 2006). Another example for the Set Covering Problem: "A Heuristic Method for the Set Covering Problem" (Caprara et al., 1999)
$\endgroup$

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.