Benders' decomposition: Fundamentals, implementation and applications Speaker: Stephen J Maher (University of Exeter)
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.
Talk 2
Building optimal solutions to prize-collecting Steiner tree problems on ISM supercomputer Speaker: Yuji Shinano (Konrad-Zuse-Zentrum für Informationstechnik Berlin; IMI, Kyushu University; ISM)
Abstract
SCIP-Jack is a customized, branch-and-cut based solver for Steiner tree and related problems. ug[SCIP-Jack, MPI] extends SCIP-Jack to a massively parallel solver by using the Ubiquity Generator (UG) framework. ug[SCIP-Jack, MPI] was the only solver that could run on a distributed environment at the (latest) 11th DIMACS Challenge in 2014. Furthermore, it could solve three well-known open instances and updated 14 best known solutions to well-known instances from the benchmark libary SteinLib. After the DIMACS Challenge, SCIP-Jack has been considerably improved. However, the improvements were not reflected on ug[SCIP-Jack, MPI]. An updated version of ug[SCIP-Jack, MPI] enabled us to use branching on constrains and a customized racing ramp-up, among others. The new features brought us the capability to use up to 43,000 cores to solve two more open instances from the SteinLib. SCIP-Jack solves not only the classic Steiner tree problem, but also a number of related problems. In this presentation, we show for the first time results of using ug[SCIP-Jack, MPI] on a problem class other than the classic Steiner tree problem, namely for prize-collecting Steiner trees. The prize-collecting Steiner tree problem is a well-known generalization of the Steiner tree problem and entails many real-world applications.
