分野別セミナー

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.