@misc{ShinanoAchterbergBertholdetal.2020, author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Winkler, Michael}, title = {Solving Previously Unsolved MIP Instances with ParaSCIP on Supercomputers by using up to 80,000 Cores}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-78393}, year = {2020}, abstract = {Mixed-integer programming (MIP) problem is arguably among the hardest classes of optimization problems. This paper describes how we solved 21 previously unsolved MIP instances from the MIPLIB benchmark sets. To achieve these results we used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP computation: up to 80,000 cores in parallel on the Titan supercomputer. In this paper, we describe the basic parallelization mechanism of ParaSCIP, improvements of the dynamic load balancing and novel techniques to exploit the power of parallelization for MIP solving. We give a detailed overview of computing times and statistics for solving open MIPLIB instances.}, language = {en} } @article{HosadaMaherShinanoetal.2022, author = {Hosada, Junko and Maher, Stephen and Shinano, Yuji and Villumsen, Jonas Christoffer}, title = {Location, transshipment and routing: An adaptive transportation network integrating long-haul and local vehicle routing}, volume = {11}, journal = {EURO Journal on Transportation and Logistics}, publisher = {Elsevier}, doi = {10.1016/j.ejtl.2022.100091}, year = {2022}, language = {en} } @misc{HosodaMaherShinano2024, author = {Hosoda, Junko and Maher, Stephen J. and Shinano, Yuji}, title = {Combining Benders' decomposition and parallelisation to solve large-scale adaptive network supply chain management problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-98744}, year = {2024}, abstract = {Integrated supply chain network design—combining warehouse clustering with inter- and intra-cluster vehicle routing—is a fundamental feature of supply chain management problems. In this paper, a Benders' decomposition-based parallel heuristic approach for the integrated long-haul and local vehicle routing problem is proposed. The proposed algorithm comprises lower- and upper-bound search algorithms running in parallel to find high-quality solutions for challenging supply chain management problems. A novel Benders' decomposition approach is proposed to aid the improvement in the lower bound for large-scale problems. The results demonstrate that the Benders' decomposition approach is effective in finding strong lower bounds and is beneficial for obtaining high-quality solutions.}, language = {en} } @misc{FujiiKimKojimaetal.2022, author = {Fujii, Koichi and Kim, Sunyoung and Kojima, Masakazu and Mittelmann, Hans D. and Shinano, Yuji}, title = {The Largest Unsolved QAP Instance Tai256c Can Be Converted into A 256-dimensional Simple BQOP with A Single Cardinality Constraint}, issn = {1438-0064}, doi = {10.12752/8808}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-88086}, year = {2022}, abstract = {Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB; a 1.48\% gap remains between the best known feasible objective value and lower bound of the unknown optimal value. This paper shows that the instance can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which requires the sum of the binary variables to be 92.The converted BQOP is much simpler than the original QAP tai256c and it also inherits some of the symmetry properties. However, it is still very difficult to solve. We present an efficient branch and bound method for improving the lower bound effectively. A new lower bound with 1.36\% gap is also provided.}, language = {en} } @misc{RehfeldtKochShinano2022, author = {Rehfeldt, Daniel and Koch, Thorsten and Shinano, Yuji}, title = {Faster exact solution of sparse MaxCut and QUBO problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-85715}, year = {2022}, language = {en} } @misc{FujisawaShinanoWaki2015, author = {Fujisawa, Katsuki and Shinano, Yuji and Waki, Hayato}, title = {Optimization in the Real World}, volume = {13}, journal = {Mathematics for Industry (MFI)}, publisher = {Springer Tokyo Heidelberg New York Dordrecht London}, isbn = {978-4-431-55419-6}, doi = {10.1007/978-4-431-55420-2}, year = {2015}, language = {en} } @misc{RalphsShinanoBertholdetal.2018, author = {Ralphs, Ted and Shinano, Yuji and Berthold, Timo and Koch, Thorsten}, title = {Parallel Solvers for Mixed Integer Linear Optimization}, journal = {Handbook of Parallel Constraint Reasoning}, editor = {Hamadi, Youssef}, publisher = {Springer Nature}, doi = {10.1007/978-3-319-63516-3_8}, pages = {283 -- 336}, year = {2018}, language = {en} } @misc{ItoShinano2018, author = {Ito, Satoshi and Shinano, Yuji}, title = {Calculation of clinch and elimination numbers for sports leagues with multiple tiebreaking criteria}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-70591}, year = {2018}, abstract = {The clinch (elimination) number is a minimal number of future wins (losses) needed to clinch (to be eliminated from) a specified place in a sports league. Several optimization models and computational results are shown in this paper for calculating clinch and elimination numbers in the presence of predefined multiple tiebreaking criteria. The main subject of this paper is to provide a general algorithmic framework based on integer programming with utilizing possibly multilayered upper and lower bounds.}, language = {en} } @misc{GleixnerBastubbeEifleretal.2018, author = {Gleixner, Ambros and Bastubbe, Michael and Eifler, Leon and Gally, Tristan and Gamrath, Gerald and Gottwald, Robert Lion and Hendel, Gregor and Hojny, Christopher and Koch, Thorsten and L{\"u}bbecke, Marco and Maher, Stephen J. and Miltenberger, Matthias and M{\"u}ller, Benjamin and Pfetsch, Marc and Puchert, Christian and Rehfeldt, Daniel and Schl{\"o}sser, Franziska and Schubert, Christoph and Serrano, Felipe and Shinano, Yuji and Viernickel, Jan Merlin and Walter, Matthias and Wegscheider, Fabian and Witt, Jonas T. and Witzig, Jakob}, title = {The SCIP Optimization Suite 6.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69361}, year = {2018}, abstract = {The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 6.0 of the SCIP Optimization Suite. Besides performance improvements of the MIP and MINLP core achieved by new primal heuristics and a new selection criterion for cutting planes, one focus of this release are decomposition algorithms. Both SCIP and the automatic decomposition solver GCG now include advanced functionality for performing Benders' decomposition in a generic framework. GCG's detection loop for structured matrices and the coordination of pricing routines for Dantzig-Wolfe decomposition has been significantly revised for greater flexibility. Two SCIP extensions have been added to solve the recursive circle packing problem by a problem-specific column generation scheme and to demonstrate the use of the new Benders' framework for stochastic capacitated facility location. Last, not least, the report presents updates and additions to the other components and extensions of the SCIP Optimization Suite: the LP solver SoPlex, the modeling language Zimpl, the parallelization framework UG, the Steiner tree solver SCIP-Jack, and the mixed-integer semidefinite programming solver SCIP-SDP.}, language = {en} } @misc{Shinano2020, author = {Shinano, Yuji}, title = {UG - Ubiquity Generator Framework v0.9.1}, doi = {10.12752/8508}, year = {2020}, abstract = {UG is a generic framework to parallelize branch-and-bound based solvers (e.g., MIP, MINLP, ExactIP) in a distributed or shared memory computing environment. It exploits the powerful performance of state-of-the-art "base solvers", such as SCIP, CPLEX, etc. without the need for base solver parallelization. UG framework, ParaSCIP(ug[SCIP,MPI]) and FiberSCIP (ug[SCIP,Pthreads]) are available as a beta version. For MIP solving, ParaSCIP and FiberSCIP are well debugged and should be stable. For MINLP solving, they are relatively stable, but not as thoroughly debugged. This release version should handle branch-and-cut approaches where subproblems are defined by variable bounds and also by constrains for ug[SCIP,*] ParaSCIP and FiberSCIP). Therefore, problem classes other than MIP or MINLP can be handled, but they have not been tested yet. v0.9.1: Update orbitope cip files.}, language = {en} } @inproceedings{ShinanoTateiwaNakamuraetal.2020, author = {Shinano, Yuji and Tateiwa, N. and Nakamura, S. and Yoshida, A. and Yasuda, M. and Kaji, S. and Fujisawa, K.}, title = {Massive Parallelization for Finding Shortest Lattice Vectors Based on Ubiquity Generator Framework}, booktitle = {2020 SC20: International Conference for High Performance Computing, Networking, Storage and Analysis (SC)}, doi = {10.1109/SC41405.2020.00064}, pages = {834 -- 848}, year = {2020}, abstract = {Lattice-based cryptography has received attention as a next-generation encryption technique, because it is believed to be secure against attacks by classical and quantum computers. Its essential security depends on the hardness of solving the shortest vector problem (SVP). In the cryptography, to determine security levels, it is becoming significantly more important to estimate the hardness of the SVP by high-performance computing. In this study, we develop the world's first distributed and asynchronous parallel SVP solver, the MAssively Parallel solver for SVP (MAP-SVP). It can parallelize algorithms for solving the SVP by applying the Ubiquity Generator framework, which is a generic framework for branch-and-bound algorithms. The MAP-SVP is suitable for massive-scale parallelization, owing to its small memory footprint, low communication overhead, and rapid checkpoint and restart mechanisms. We demonstrate its performance and scalability of the MAP-SVP by using up to 100,032 cores to solve instances of the Darmstadt SVP Challenge.}, language = {en} } @article{YokoyamaShinanoWakayamaetal.2019, author = {Yokoyama, Ryohei and Shinano, Yuji and Wakayama, Yuki and Wakui, Tetsuya}, title = {Model reduction by time aggregation for optimal design of energy supply systems by an MILP hierarchical branch and bound method}, volume = {181}, journal = {Energy}, doi = {https://doi.org/10.1016/j.energy.2019.04.066}, pages = {782 -- 792}, year = {2019}, abstract = {Mixed-integer linear programming (MILP) methods have been applied widely to optimal design of energy supply systems in consideration of multi-period operation. A hierarchical MILP method has been proposed to solve such optimal design problems efficiently. An original problem has been solved by dividing it into a relaxed optimal design problem at the upper level and optimal operation problems which are independent of one another at the lower level. In addition, some strategies have been proposed to enhance the computation efficiency furthermore. In this paper, a method of reducing model by time aggregation is proposed as a novel strategy to search design candidates efficiently in the relaxed optimal design problem at the upper level. In addition, the previous strategies are modified in accordance with the novel strategy. This method is realized only by clustering periods and averaging energy demands for clustered periods, while it guarantees to derive the optimal solution. Thus, it may decrease the computation time at the upper level. Through a case study on the optimal design of a gas turbine cogeneration system, it is clarified how the model reduction is effective to enhance the computation efficiency in comparison and combination with the modified previous strategies.}, language = {en} } @misc{ShinanoAchterbergBertholdetal.2010, author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten}, title = {ParaSCIP - a parallel extension of SCIP}, doi = {10.1007/978-3-642-24025-6_12}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11921}, number = {10-27}, year = {2010}, abstract = {Mixed integer programming (MIP) has become one of the most important techniques in Operations Research and Discrete Optimization. SCIP (Solving Constraint Integer Programs) is currently one of the fastest non-commercial MIP solvers. It is based on the branch-and-bound procedure in which the problem is recursively split into smaller subproblems, thereby creating a so-called branching tree. We present ParaSCIP, an extension of SCIP, which realizes a parallelization on a distributed memory computing environment. ParaSCIP uses SCIP solvers as independently running processes to solve subproblems (nodes of the branching tree) locally. This makes the parallelization development independent of the SCIP development. Thus, ParaSCIP directly profits from any algorithmic progress in future versions of SCIP. Using a first implementation of ParaSCIP, we were able to solve two previously unsolved instances from MIPLIB2003, a standard test set library for MIP solvers. For these computations, we used up to 2048 cores of the HLRN~II supercomputer.}, language = {en} } @inproceedings{BertholdGleixnerHeinzetal.2012, author = {Berthold, Timo and Gleixner, Ambros and Heinz, Stefan and Koch, Thorsten and Shinano, Yuji}, title = {SCIP Optimization Suite を利用した 混合整数(線形/非線形) 計画問題の解法}, booktitle = {Proceedings of the 24th RAMP symposium. The Operations Society of Japan, RAMP: Research Association of Mathematical Programming}, pages = {165 -- 192}, year = {2012}, abstract = {この論文ではソフトウェア・パッケージSCIP Optimization Suite を紹介し,その3つの構成要素:モデリン グ言語Zimpl, 線形計画(LP: linear programming) ソルバSoPlex, そして,制約整数計画(CIP: constraint integer programming) に対するソフトウェア・フレームワークSCIP, について述べる.本論文では,この3つの 構成要素を利用して,どのようにして挑戦的な混合整数線形計画問題(MIP: mixed integer linear optimization problems) や混合整数非線形計画問題(MINLP: mixed integer nonlinear optimization problems) をモデル化 し解くのかを説明する.SCIP は,現在,最も高速なMIP,MINLP ソルバの1つである.いくつかの例により, Zimpl, SCIP, SoPlex の利用方法を示すとともに,利用可能なインタフェースの概要を示す.最後に,将来の開 発計画の概要について述べる.}, language = {ja} } @misc{ShinanoAchterbergBertholdetal.2013, author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Winkler, Michael}, title = {Solving hard MIPLIB2003 problems with ParaSCIP on Supercomputers: An update}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42888}, year = {2013}, abstract = {Contemporary supercomputers can easily provide years of CPU time per wall-clock hour. One challenge of today's software development is how to harness this wast computing power in order to solve really hard mixed integer programming instances. In 2010, two out of six open MIPLIB2003 instances could be solved by ParaSCIP in more than ten consecutive runs, restarting from checkpointing files. The contribution of this paper is threefold: For the first time, we present computational results of single runs for those two instances. Secondly, we provide new improved upper and lower bounds for all of the remaining four open MIPLIB2003 instances. Finally, we explain which new developments led to these results and discuss the current progress of ParaSCIP. Experiments were conducted on HLRNII, on HLRN III, and on the Titan supercomputer, using up to 35,200 cores.}, language = {en} }