Lagrangian-informed mixed integer programming reformulations
Integer linear programming is a robust and efficient approach to solve large-scale instances of combinatorial problems.  However, problems constantly gain in complexity and sometimes impose strong constraints on computation times.  We must then develop specialised methods to compute heuristic primal solutions to the problem and derive lower bounds on the optimal value, and thus prove the quality of our primal solutions.  We propose to guide a reformulation approach for mixed integer programs with Lagrangian relaxations.  After the identification of a strong relaxation, a mechanical process leads to a second integer formulation. This reformulation is equivalent to the initial one, but its linear relaxation is equivalent to the strong Lagrangian dual.  We will show that the reformulation approach unifies and generalises prior formulations and lower bounding approaches, and that it exposes a simple mechanism to reduce the size of reformulations in return for weaker bounds.  Nevertheless, our reformulations are large.  We address this issue by solving their linear relaxations with specialised methods.  Finally, we apply the reformulation approach to two location problems. This yields novel formulations for both problems; some are very large but, thanks to the aforementioned specialised methods, still practical.
Operations research Lagrangian relaxation Mixed integer programming Location problems