Lagrangian dual with zero duality gap that admits decomposition

Understand

For mixed integer programs (MIPs) with block structures and coupling constraints, on dualizing the coupling constraints the resulting Lagrangian relaxation becomes decomposable into blocks which allows for the use of parallel computing.

• However, the resulting Lagrangian dual can have non-zero duality gap due to the inherent non-convexity of MIPs.
• In this paper, we propose two reformulations of such MIPs by adding redundant constraints, such that the Lagrangian dual obtained by dualizing the coupling constraints and the redundant constraints have zero duality gap while still remaining decomposable.
• One of these reformulations is similar, although not the same as the RLT hierarchy.