Videos

Decomposition and Reformulation in Mixed-Integer Programming

Presenter
August 11, 2016
Keywords:
  • Mixed-integer programming, Lagrangian relaxation, Dantzig-Wolfe reformulation, branch-and-price
MSC:
  • 90C11
Abstract
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.