Department Seminar: Ted Ralphs, Lehigh University - Wednesday, Nov 2 @ 4:00pm, 1680 IOE

DIP with CHiPPS: Decomposition Methods in Integer Programming

Abstract:
Decomposition is a fundamental technique for solving optimization problems. In integer programming, decomposition methods can be used to generate improved bounds on the optimal value, which are essential to the development of effective solution procedures. Typically, the implementation of decomposition methods is difficult, requiring sophisticated custom implementations. In this talk, we present a unifying theoretical framework and an accompanying software framework that simplifies implementation and allows customization through a modeling language, even offering completely generic, automated decomposition methods through detection of block structure. The unified framework allows explicit experimentation with the tradeoffs among various advanced decomposition approaches, including Dantzig-Wolfe decomposition, Lagrangian relaxation, and cutting plane methods. We will discuss the connections between these methods and how they can be combined in a single computational framework to yield a wide range of algorithms for solving integer programs.

back to top