Decomposition and Reformulation in Mixed-Integer Programming
Thursday, August 11, 2016 - 2:00pm - 3:30pm
In this lecture, we present two related methods, Lagrangian relaxation and Dantzig-Wolfe reformulation for exploiting structure of mixed-integer programming models to obtain better relaxations or solve large-scale instances. A Lagrangian relaxation is obtained by relaxing some constraints, ideally leaving only constraints that have special structure that can be exploited computationally. The problem of finding the best such relaxation is known as the Lagrangian dual, and we discuss the strength of this dual bound and how to compute it. We also present the technique of Dantzig-Wolfe reformulation and discuss its relationship to Lagrangian relaxation. Finally, we give an overview of how a Dantzig-Wolfe reformulation might be solved by delayed column generation and branch-and-price.