以下の通り，第6回研究会を開催いたしました．
日時: 2019年12月4日 (水) 16:00～18:00
場所: 京都大学 数理解析研究所 (RIMS) 2階 204室
参加者: 18名
[講演1]
講演者: Yuji Shinano (Zuse Institute Berlin)
題目: Building optimal solutions to prize-collecting Steiner tree problems on supercomputers
概要: 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.
[講演2]
講演者: Stephen J Maher (University of Exeter)
題目: Experiments with a general Benders' decomposition framework in SCIP
概要: Benders' decomposition is a popular mathematical programming technique for solving large scale optimisation problems. While Benders' decomposition is historically viewed as requiring a problem specific implementation, general frameworks can provide an ideal platform for the investigation of general algorithm enhancement techniques. Such a broad investigation was not possible until only recently when Benders' decomposition frameworks have been implemented in general purpose constraint integer programming solvers. This talk will give an overview of the current features within the Benders' decomposition framework available with SCIP and GCG. In addition, current work on cut enhancement techniques and the handling of integer subproblems will be discussed. This talk will demonstrate the value of a general framework for the development and investigation of enhanced algorithms for Benders' decomposition.