Stephen Maher (Lancaster University)

Improving the heuristic performance of Benders' decomposition
Wednesday 27 March 2019 at 15.00, JCMB 6206

Abstract

Benders decomposition is a very popular solution technique for solving structured mixed integer programs. Benders' decomposition is theoretically appealing for many applications, but unfortunately it typically exhibits poor convergence to the optimal solution in practice. While many enhancement techniques have been developed to improve the effectiveness of Benders' decomposition, most are ad hoc methods that require problem specific implementations. This talk will present a brief overview of different Benders' decomposition schemes and describe a general implementation of Benders' decomposition that has been developed within the MIP solver SCIP. Through the use of the Benders' decomposition implementation within SCIP, a general enhancement approach using large neighbourhood search heuristics will be presented. The results demonstrate the potential enhancement to the Benders' decomposition algorithm that is achieved through a tighter integration with large neighbourhood search heuristics within a MIP solver.

Seminars by year

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