Institute of Mathematics for Industry

Seminar



List All(1084) Today and tomorrow's seminars(0)

Benders' decomposition: Fundamentals, implementation and applications


Hold Date 2019-12-02 17:00~2019-12-02 18:00

Place Lecture Room L W1-C-501, West Zone 1, Ito campus, Kyushu University

Object person  

Speaker Stephen J. Maher (EPSRC Research Fellow University of Exeter, United Kingdom)

Abstract:
Benders' decomposition is a popular mathematical programming technique used to solve large-scale optimisation problems. While popular, Benders' decomposition is commonly seen as a problem specific application and hence few general purpose software frameworks for this algorithm exist. This view is changing with general purpose solvers providing frameworks for the application of decomposition methods, including Benders' decomposition. This talk will provide an overview of the Benders' decomposition algorithm, from its fundamental mathematical concepts through to its implementation in SCIP as a general purpose framework. Applications arising from airline planning, location planning and HIV vaccine target identification will be used to demonstrate the key features of the Benders' decomposition framework in SCIP. We will highlight the most important implementation features and discuss the computational performance of various algorithmic enhancement techniques.