Ted Ralphs (Lehigh University, USA)

DIP with CHiPPS: a generic framework for decomposition methods in integer programming
Tuesday 1 June 2010 at 15.30, JCMB 6206 - Joint with NAIS

Abstract

Methods for generating bounds on the optimal value of a MILP are essential to the development of effective solution procedures. Traditionally, bounding methods based on decomposition, such as Dantzig-Wolfe decomposition and Lagrangian relaxation, have been treated as distinct both from each other and from polyhedral methods that utilize dynamic cut generation for bound improvement. It is possible, however, to view these methods from a common theoretical perspective and to integrate them in order to capitalize on their individual strengths. In this talk, we introduce both a theoretical framework that takes this perspective and a software framework that implements the resulting methodology, allowing for explicit experimentation with the tradeoffs among various decomposition approaches.

Seminars by year

Current 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996