@inproceedings{YokoyamaShinanoWakayamaaetal., author = {Yokoyama, Ryohei and Shinano, Yuji and Wakayamaa, Yuji and Wakui, Tetsuya}, title = {Optimal Design of a Gas Turbine Cogeneration Plant by a Hierarchical Optimization Method With Parallel Computing}, series = {ASME Turbo Expo 2018: Turbomachinery Technical Conference and Exposition}, volume = {3}, booktitle = {ASME Turbo Expo 2018: Turbomachinery Technical Conference and Exposition}, abstract = {To attain the highest performance of energy supply systems, it is necessary to rationally determine types, capacities, and numbers of equipment in consideration of their operational strategies corresponding to seasonal and hourly variations in energy demands. Mixed-integer linear programming (MILP) approaches have been applied widely to such optimal design problems. The authors have proposed a MILP method utilizing the hierarchical relationship between design and operation variables to solve the optimal design problems of energy supply systems efficiently. In addition, some strategies to enhance the computation efficiency have been adopted: bounding procedures at both the levels and ordering of the optimal operation problems at the lower level. In this paper, as an additional strategy to enhance the computation efficiency, parallel computing is adopted to solve multiple optimal operation problems in parallel at the lower level. In addition, the effectiveness of each and combinations of the strategies adopted previously and newly is investigated. This hierarchical optimization method is applied to an optimal design of a gas turbine cogeneration plant, and its validity and effectiveness are clarified through some case studies.}, language = {en} } @misc{ShinanoAchterbergBertholdetal., 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}, 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} } @misc{KochRalphsShinano, author = {Koch, Thorsten and Ralphs, Ted and Shinano, Yuji}, title = {What could a million CPUs do to solve Integer Programs?}, issn = {1438-0064}, doi = {10.1007/s00186-012-0390-9}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14222}, number = {11-40}, abstract = {Given the steady increase in cores per CPU, it is only a matter of time until supercomputers will have a million or more cores. In this article, we investigate the opportunities and challenges that will arise when trying to utilize this vast computing power to solve a single integer linear optimization problem. We also raise the question of whether best practices in sequential solution of ILPs will be effective in massively parallel environments.}, language = {en} } @inproceedings{ShinanoBertholdHeinz, author = {Shinano, Yuji and Berthold, Timo and Heinz, Stefan}, title = {A First Implementation of ParaXpress: Combining Internal and External Parallelization to Solve MIPs on Supercomputers}, series = {Mathematical Software - ICMS 2016, 5th International Conference Berlin, Germany, July 11-14, 2016 Proceedings}, booktitle = {Mathematical Software - ICMS 2016, 5th International Conference Berlin, Germany, July 11-14, 2016 Proceedings}, doi = {10.1007/978-3-319-42432-3_38}, pages = {308 -- 316}, language = {en} } @inproceedings{BertholdGleixnerHeinzetal.2012, author = {Berthold, Timo and Gleixner, Ambros and Heinz, Stefan and Koch, Thorsten and Shinano, Yuji}, title = {SCIP Optimization Suite を利用した 混合整数(線形/非線形) 計画問題の解法}, series = {Proceedings of the 24th RAMP symposium. The Operations Society of Japan, RAMP: Research Association of Mathematical Programming}, 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{YokoyamaShinanoTaniguchietal.2014, author = {Yokoyama, Ryohei and Shinano, Yuji and Taniguchi, Syusuke and Ohkura, Masashi and Wakui, Tetsuya}, title = {Optimization of energy supply systems by MILP branch and bound method in consideration of hierarchical relationship between design and operation}, issn = {1438-0064}, doi = {10.1016/j.enconman.2014.12.020}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-49413}, year = {2014}, abstract = {To attain the highest performance of energy supply systems, it is necessary to rationally determine types, capacities, and numbers of equipment in consideration of their operational strategies corresponding to seasonal and hourly variations in energy demands. In the combinatorial optimization method based on the mixed-integer linear programming (MILP), integer variables are used to express the selection, numbers, and on/off status of operation of equipment, and the number of these variables increases with those of equipment and periods for variations in energy demands, and affects the computation efficiency significantly. In this paper, a MILP method utilizing the hierarchical relationship between design and operation variables is proposed to solve the optimal design problem of energy supply systems efficiently: At the upper level, the optimal values of design variables are searched by the branch and bound method; At the lower level, the values of operation variables are optimized independently at each period by the branch and bound method under the values of design variables given tentatively during the search at the upper level; Lower bounds for the optimal value of the objective function are evaluated, and are utilized for the bounding operations at both the levels. This method is implemented into open and commercial MILP solvers. Illustrative and practical case studies on the optimal design of cogeneration systems are conducted, and the validity and effectiveness of the proposed method are clarified.}, language = {en} } @article{ShinanoInuiFukagawaetal.2013, author = {Shinano, Yuji and Inui, Nobuo and Fukagawa, Youzou and Takakura, Noburu}, title = {Optimizing Movement Sequences for Step-and-Scan Lithography Equipment}, series = {Journal of Advanced Mechanical Design, Systems, and Manufacturing}, volume = {7}, journal = {Journal of Advanced Mechanical Design, Systems, and Manufacturing}, number = {4}, doi = {10.1299/jamdsm.7.608}, pages = {608 -- 618}, year = {2013}, abstract = {The purpose of this work is to improve the throughput of step-and-scan lithography equipment to shorten the production time of a wafer. For this purpose, we propose a method for solving the MSOP (Movement Sequence Optimization Problem), which is the problem of computing the fastest schedule for visiting all shots on a wafer. It is well-known that the MSOP on step-and-repeat lithography equipment can be modeled as a traveling salesman problem. In contrast to step-and-repeat lithography equipment, a schedule for step-and-scan lithography equipment must also indicate the scanning direction of each shot, in addition to the sequence of the shots. For this reason, the traveling salesman problem formulation for step-and-repeat lithography equipment cannot be applied to solve the MSOP on step-and-scan lithography equipment directly. We overcame this difficulty by introducing auxiliary vertices to model the scanning directions in the traveling salesman problem formulation. By this method, we were able to compute exact optimal sequences considering the scanning directions of shots for several MSOP instances. Our numerical experiments demonstrated that our proposed method was capable of computing exact optimal solutions for real-world MSOP instances having up to 232 shots on a wafer. These optimal solutions gave a 0.25\% to 4.66\% improvement in productivity over solutions computed by previously known methods.}, language = {en} } @misc{RalphsShinanoBertholdetal., author = {Ralphs, Ted and Shinano, Yuji and Berthold, Timo and Koch, Thorsten}, title = {Parallel Solvers for Mixed Integer Linear Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-62239}, abstract = {In this article, we introduce parallel mixed integer linear programming (MILP) solvers. MILP solving algorithms have been improved tremendously in the last two decades. Currently, commercial MILP solvers are known as a strong optimization tool. Parallel MILP solver development has started in 1990s. However, since the improvements of solving algorithms have much impact to solve MILP problems than application of parallel computing, there were not many visible successes. With the spread of multi-core CPUs, current state-of-the-art MILP solvers have parallel implementations and researches to apply parallelism in the solving algorithm also getting popular. We summarize current existing parallel MILP solver architectures.}, language = {en} } @inproceedings{ShinanoAchterbergBertholdetal.2012, author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten}, title = {ParaSCIP: a parallel extension of SCIP}, series = {Competence in High Performance Computing 2010}, booktitle = {Competence in High Performance Computing 2010}, editor = {Bischof, Christian and Hegering, Heinz-Gerd and Nagel, Wolfgang and Wittum, Gabriel}, publisher = {Springer}, doi = {10.1007/978-3-642-24025-6_12}, pages = {135 -- 148}, year = {2012}, language = {en} } @article{KochRalphsShinano2012, author = {Koch, Thorsten and Ralphs, Ted and Shinano, Yuji}, title = {Could we use a million cores to solve an integer program?}, series = {Mathematical Methods of Operations Research}, volume = {76}, journal = {Mathematical Methods of Operations Research}, number = {1}, doi = {10.1007/s00186-012-0390-9}, pages = {67 -- 93}, year = {2012}, language = {en} } @misc{BertholdGleixnerHeinzetal., author = {Berthold, Timo and Gleixner, Ambros and Heinz, Stefan and Koch, Thorsten and Shinano, Yuji}, title = {SCIP Optimization Suite を利用した 混合整数(線形/非線形) 計画問題の解法}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-15598}, 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{BertholdGamrathGleixneretal., author = {Berthold, Timo and Gamrath, Gerald and Gleixner, Ambros and Heinz, Stefan and Koch, Thorsten and Shinano, Yuji}, title = {Solving mixed integer linear and nonlinear problems using the SCIP Optimization Suite}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-15654}, abstract = {This paper introduces the SCIP Optimization Suite and discusses the capabilities of its three components: the modeling language Zimpl, the linear programming solver SoPlex, and the constraint integer programming framework SCIP. We explain how these can be used in concert to model and solve challenging mixed integer linear and nonlinear optimization problems. SCIP is currently one of the fastest non-commercial MIP and MINLP solvers. We demonstrate the usage of Zimpl, SCIP, and SoPlex by selected examples, we give an overview of available interfaces, and outline plans for future development.}, language = {en} } @incollection{YokoyamaShinano, author = {Yokoyama, Ryohei and Shinano, Yuji}, title = {MILP Approaches to Optimal Design and Operation of Distributed Energy Systems}, series = {Optimization in the Real World}, volume = {Volume 13}, booktitle = {Optimization in the Real World}, publisher = {Springer}, isbn = {978-4-431-55419-6}, doi = {10.1007/978-4-431-55420-2_9}, pages = {157 -- 176}, abstract = {Energy field is one of the practical areas to which optimization can contribute significantly. In this chapter, the application of mixed-integer linear programming (MILP) approaches to optimal design and operation of distributed energy systems is described. First, the optimal design and operation problems are defined, and relevant previous work is reviewed. Then, an MILP method utilizing the hierarchical relationship between design and operation variables is presented. In the optimal design problem, integer variables are used to express the types, capacities, numbers, operation modes, and on/off states of operation of equipment, and the number of these variables increases with those of equipment and periods for variations in energy demands, and affects the computation efficiency significantly. The presented method can change the enumeration tree for the branching and bounding procedures, and can search the optimal solution very efficiently. Finally, future work in relation to this method is described.}, language = {en} } @article{YokoyamaShinanoTaniguchietal., author = {Yokoyama, Ryohei and Shinano, Yuji and Taniguchi, Syusuke and Ohkura, Masashi and Wakui, Tetsuya}, title = {Optimization of energy supply systems by MILP branch and bound method in consideration of hierarchical relationship between design and operation}, series = {Energy Conversion and Management}, volume = {92}, journal = {Energy Conversion and Management}, doi = {10.1016/j.enconman.2014.12.020}, pages = {92 -- 104}, abstract = {To attain the highest performance of energy supply systems, it is necessary to rationally determine types, capacities, and numbers of equipment in consideration of their operational strategies corresponding to seasonal and hourly variations in energy demands. In the combinatorial optimization method based on the mixed-integer linear programming (MILP), integer variables are used to express the selection, numbers, and on/off status of operation of equipment, and the number of these variables increases with those of equipment and periods for variations in energy demands, and affects the computation efficiency significantly. In this paper, a MILP method utilizing the hierarchical relationship between design and operation variables is proposed to solve the optimal design problem of energy supply systems efficiently: At the upper level, the optimal values of design variables are searched by the branch and bound method; At the lower level, the values of operation variables are optimized independently at each period by the branch and bound method under the values of design variables given tentatively during the search at the upper level; Lower bounds for the optimal value of the objective function to be minimized are evaluated, and are utilized for the bounding operations at both the levels. This method is implemented into open and commercial MILP solvers. Illustrative and practical case studies on the optimal design of cogeneration systems are conducted, and the validity and effectiveness of the proposed method are clarified.}, language = {en} } @inproceedings{ShinanoAchterbergBertholdetal., author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Winkler, Michael}, title = {Solving Open MIP Instances with ParaSCIP on Supercomputers using up to 80,000 Cores}, series = {Proc. of 30th IEEE International Parallel \& Distributed Processing Symposium}, booktitle = {Proc. of 30th IEEE International Parallel \& Distributed Processing Symposium}, doi = {10.1109/IPDPS.2016.56}, abstract = {This paper describes how we solved 12 previously unsolved mixed-integer program- ming (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} } @inproceedings{YokoyamaShinanoTaniguchietal., author = {Yokoyama, Ryohei and Shinano, Yuji and Taniguchi, Syusuke and Ohkura, Masashi and Wakui, Tetsuya}, title = {Generation of multiple best solutions in multiobjective optimal design of energy supply systems}, series = {Proceedings of the 15th International Conference on Power Engineering. ICOPE 2015}, booktitle = {Proceedings of the 15th International Conference on Power Engineering. ICOPE 2015}, doi = {10.1299/jsmeicope.2015.12._ICOPE-15-_56}, abstract = {Optimization approaches based on the mixed-integer linear programming (MILP) have been utilized to design energy supply systems. In this paper, an MILP method utilizing the hierarchical relationship between design and operation is extended to search not only the optimal solution but also suboptimal ones which follow the optimal one without any omissions, what are called K-best solutions, efficiently in a multiobjective optimal design problem. At the upper level, the values of design variables for the K-best solutions are searched by the branch and bound method. At the lower level, the values of operation variables are optimized independently at each period by the branch and bound method under the values of design variables given tentatively. Incumbents for the K-best solutions and an upper bound for all the values of the objective function for the K-best solutions are renewed if necessary between both the levels. This method is implemented into a commercial MILP solver. A practical case study on the multiobjective optimal design of a cogeneration system is conducted, and the validity and effectiveness of the method are clarified.}, language = {en} } @inproceedings{ShinanoAchterbergBertholdetal., author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Winkler, Michael}, title = {Solving Hard MIPLIP2003 Problems with ParaSCIP on Supercomputers: An Update}, series = {IPDPSW'14 Proceedings of the 2014 IEEE, International Parallel \& Distributed Processing Symposium Workshops}, booktitle = {IPDPSW'14 Proceedings of the 2014 IEEE, International Parallel \& Distributed Processing Symposium Workshops}, editor = {IEEE,}, publisher = {IEEE Computer Society}, address = {Washington, DC, USA}, isbn = {978-1-4799-4117-9}, doi = {10.1109/IPDPSW.2014.174}, pages = {1552 -- 1561}, language = {en} } @inproceedings{ShinanoRehfeldtKoch, author = {Shinano, Yuji and Rehfeldt, Daniel and Koch, Thorsten}, title = {Building Optimal Steiner Trees on Supercomputers by Using up to 43,000 Cores}, series = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2019}, volume = {11494}, booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2019}, publisher = {Springer}, doi = {10.1007/978-3-030-19212-9_35}, pages = {529 -- 539}, 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 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]. This paper describes an updated version of ug [SCIP-JACK, MPI], especially branching on constrains and a customized racing ramp-up. Furthermore, the different stages of the solution process on a supercomputer are described in detail. We also show the latest results on open instances from the STEINLIB.}, language = {en} } @inproceedings{ShinanoRehfeldtGally, author = {Shinano, Yuji and Rehfeldt, Daniel and Gally, Tristan}, title = {An Easy Way to Build Parallel State-of-the-art Combinatorial Optimization Problem Solvers: A Computational Study on Solving Steiner Tree Problems and Mixed Integer Semidefinite Programs by using ug[SCIP-*,*]-libraries}, series = {Proceedings of the 9th IEEE Workshop Parallel / Distributed Combinatorics and Optimization}, booktitle = {Proceedings of the 9th IEEE Workshop Parallel / Distributed Combinatorics and Optimization}, publisher = {IEEE}, doi = {10.1109/IPDPSW.2019.00095}, pages = {530 -- 541}, abstract = {Branch-and-bound (B\&B) is an algorithmic framework for solving NP-hard combinatorial optimization problems. Although several well-designed software frameworks for parallel B\&B have been developed over the last two decades, there is very few literature about successfully solving previously intractable combinatorial optimization problem instances to optimality by using such frameworks.The main reason for this limited impact of parallel solvers is that the algorithmic improvements for specific problem types are significantly greater than performance gains obtained by parallelization in general. Therefore, in order to solve hard problem instances for the first time, one needs to accelerate state-of-the-art algorithm implementations. In this paper, we present a computational study for solving Steiner tree problems and mixed integer semidefinite programs in parallel. These state-of-the-art algorithm implementations are based on SCIP and were parallelized via the ug[SCIP-*,*]-libraries---by adding less than 200 lines of glue code. Despite the ease of their parallelization, these solvers have the potential to solve previously intractable instances. In this paper, we demonstrate the convenience of such a parallelization and present results for previously unsolvable instances from the well-known PUC benchmark set, widely regarded as the most difficult Steiner tree test set in the literature.}, language = {en} } @inproceedings{YokoyamaShinanoWakayamaetal., 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}, series = {Proceedings of the 31st International Conference on Efficiency, Cost, Optimization, Simulation and Environmental Impact of Energy Systems (ECOS 2018)}, booktitle = {Proceedings of the 31st International Conference on Efficiency, Cost, Optimization, Simulation and Environmental Impact of Energy Systems (ECOS 2018)}, abstract = {Mixed-integer linear programming (MILP) methods have been applied widely to optimal design of energy supply systems. A hierarchical MILP method has been proposed to solve such optimal design problems effi- ciently. 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 solu- tion. The method can decrease the number of design variables and constraints at the upper level, and thus 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} } @article{GleixnerHendelGamrathetal., author = {Gleixner, Ambros and Hendel, Gregor and Gamrath, Gerald and Achterberg, Tobias and Bastubbe, Michael and Berthold, Timo and Christophel, Philipp M. and Jarck, Kati and Koch, Thorsten and Linderoth, Jeff and L{\"u}bbecke, Marco and Mittelmann, Hans and Ozyurt, Derya and Ralphs, Ted and Salvagnin, Domenico and Shinano, Yuji}, title = {MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library}, series = {Mathematical Programming Computation}, volume = {13}, journal = {Mathematical Programming Computation}, number = {3}, doi = {10.1007/s12532-020-00194-3}, pages = {443 -- 490}, abstract = {We report on the selection process leading to the sixth version of the Mixed Integer Programming Library. Selected from an initial pool of over 5,000 instances, the new MIPLIB 2017 collection consists of 1,065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, the compilation of these sets was done using a data-driven selection process supported by the solution of a sequence of mixed integer optimization problems, which encoded requirements on diversity and balancedness with respect to instance features and performance data.}, language = {en} } @inproceedings{ShinanoTateiwaNakamuraetal., 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}, series = {2020 SC20: International Conference for High Performance Computing, Networking, Storage and Analysis (SC)}, booktitle = {2020 SC20: International Conference for High Performance Computing, Networking, Storage and Analysis (SC)}, doi = {10.1109/SC41405.2020.00064}, pages = {834 -- 848}, 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} } @incollection{KochRehfeldtShinano, author = {Koch, Thorsten and Rehfeldt, Daniel and Shinano, Yuji}, title = {An exact high performance solver for Steiner tree problems in graphs and related problems}, series = {Modeling, Simulation and Optimization of Complex Processes HPSC 2018}, booktitle = {Modeling, Simulation and Optimization of Complex Processes HPSC 2018}, publisher = {Springer}, language = {en} } @inproceedings{YokoyamaKamadaShinanoetal.2020, author = {Yokoyama, Ryohei and Kamada, Hiroki and Shinano, Yuji and Wakui, Tetsuya}, title = {A Hierarchical Optimization Approach to Robust Design of Energy Supply Systems Based on a Mixed-Integer Linear Model}, series = {Conference}, booktitle = {Conference}, pages = {601 -- 613}, year = {2020}, abstract = {In designing energy supply systems, designers should heighten the robustness in performance criteria against the uncertainty in energy demands. In this paper, a robust optimal design method using a hierarchi- cal mixed-integer linear programming (MILP) method is proposed to maximize the robustness of energy sup- ply systems under uncertain energy demands based on a mixed-integer linear model. A robust optimal design problem is formulated as a three-level min-max-min MILP one by expressing uncertain energy demands by intervals, evaluating the robustness in a performance criterion based on the minimax regret cri- terion, and considering relationships among integer design variables, uncertain energy demands, and inte- ger and continuous operation variables. This problem is solved by evaluating upper and lower bounds for the minimum of the maximum regret of the performance criterion repeatedly outside, and evaluating lower and upper bounds for the maximum regret repeatedly inside. Since these different types of optimization problems are difficult to solve even using commercial MILP solvers, they are solved by applying a hierarchi- cal MILP method developed for ordinary optimal design problems with its modifications. In a case study, the proposed approach is applied to the robust optimal design of a cogeneration system. Through the study, its validity and effectiveness are ascertained, and some features of the obtained robust designs are clarified.}, language = {en} } @inproceedings{YokoyamaTakeuchiShinanoetal., author = {Yokoyama, Ryohei and Takeuchi, Kotaro and Shinano, Yuji and Wakui, Tetsuya}, title = {Effect of Model Reduction by Time Aggregation in Multiobjective Optimal Design of Energy Supply Systems by a Hierarchical MILP Method}, series = {Conference}, booktitle = {Conference}, pages = {627 -- 639}, abstract = {The mixed-integer linear programming (MILP) method has been applied widely to optimal design of energy supply systems. A hierarchical MILP method has been proposed to solve such optimal design problems effi- ciently. As one of the strategies to enhance the computation efficiency furthermore, a method of reducing model by time aggregation has been proposed to search design candidates accurately and efficiently in the relaxed optimal design problem at the upper level. In this paper, the hierarchical MILP method and model reduction by time aggregation are applied to the multiobjective optimal design. In applying the model reduc- tion, the methods of clustering periods by the order of time series, based on an operational strategy, and by the k-medoids method are applied. As a case study, the multiobjective optimal design of a gas turbine cogeneration system with a practical configuration is investigated by adopting the annual total cost and pri- mary energy consumption as the objective functions to be minimized simultaneously, and the clustering methods are compared with one another in terms of the computation efficiency. It turns out that the model reduction by any clustering method is effective to enhance the computation efficiency when importance is given to minimizing the first objective function. It also turns out that the model reduction only by the k- medoids method is effective very limitedly when importance is given to minimizing the second objective function.}, language = {en} } @article{MunguiaOxberryRajanetal., author = {Munguia, Lluis-Miquel and Oxberry, Geoffrey and Rajan, Deepak and Shinano, Yuji}, title = {Parallel PIPS-SBB: Multi-Level Parallelism For Stochastic Mixed-Integer Programs}, series = {Computational Optimization and Applications}, journal = {Computational Optimization and Applications}, doi = {10.1007/s10589-019-00074-0}, abstract = {PIPS-SBB is a distributed-memory parallel solver with a scalable data distribution paradigm. It is designed to solve MIPs with a dual-block angular structure, which is characteristic of deterministic-equivalent Stochastic Mixed-Integer Programs (SMIPs). In this paper, we present two different parallelizations of Branch \& Bound (B\&B), implementing both as extensions of PIPS-SBB, thus adding an additional layer of parallelism. In the first of the proposed frameworks, PIPS-PSBB, the coordination and load-balancing of the different optimization workers is done in a decentralized fashion. This new framework is designed to ensure all available cores are processing the most promising parts of the B\&B tree. The second, ug[PIPS-SBB,MPI], is a parallel implementation using the Ubiquity Generator (UG), a universal framework for parallelizing B\&B tree search that has been successfully applied to other MIP solvers. We show the effects of leveraging multiple levels of parallelism in potentially improving scaling performance beyond thousands of cores.}, language = {en} } @misc{RalphsShinanoBertholdetal., author = {Ralphs, Ted and Shinano, Yuji and Berthold, Timo and Koch, Thorsten}, title = {Parallel Solvers for Mixed Integer Linear Optimization}, series = {Handbook of Parallel Constraint Reasoning}, journal = {Handbook of Parallel Constraint Reasoning}, editor = {Hamadi, Youssef}, publisher = {Springer Nature}, doi = {10.1007/978-3-319-63516-3_8}, pages = {283 -- 336}, language = {en} } @misc{ShinanoRehfeldtGalley, author = {Shinano, Yuji and Rehfeldt, Daniel and Galley, Tristan}, title = {An Easy Way to Build Parallel State-of-the-art Combinatorial Optimization Problem Solvers: A Computational Study on Solving Steiner Tree Problems and Mixed Integer Semidefinite Programs by using ug[SCIP-*,*]-libraries}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-72804}, abstract = {Branch-and-bound (B\&B) is an algorithmic framework for solving NP-hard combinatorial optimization problems. Although several well-designed software frameworks for parallel B\&B have been developed over the last two decades, there is very few literature about successfully solving previously intractable combinatorial optimization problem instances to optimality by using such frameworks.The main reason for this limited impact of parallel solvers is that the algorithmic improvements for specific problem types are significantly greater than performance gains obtained by parallelization in general. Therefore, in order to solve hard problem instances for the first time, one needs to accelerate state-of-the-art algorithm implementations. In this paper, we present a computational study for solving Steiner tree problems and mixed integer semidefinite programs in parallel. These state-of-the-art algorithm implementations are based on SCIP and were parallelized via the ug[SCIP-*,*]-libraries---by adding less than 200 lines of glue code. Despite the ease of their parallelization, these solvers have the potential to solve previously intractable instances. In this paper, we demonstrate the convenience of such a parallelization and present results for previously unsolvable instances from the well-known PUC benchmark set, widely regarded as the most difficult Steiner tree test set in the literature.}, language = {en} } @inproceedings{Shinano, author = {Shinano, Yuji}, title = {The Ubiquity Generator Framework: 7 Years of Progress in Parallelizing Branch-and-Bound}, series = {Operations Research Proceedings 2017}, booktitle = {Operations Research Proceedings 2017}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-89920-6_20}, pages = {143 -- 149}, abstract = {Mixed integer linear programming (MIP) is a general form to model combinatorial optimization problems and has many industrial applications. The performance of MIP solvers has improved tremendously in the last two decades and these solvers have been used to solve many real-word problems. However, against the backdrop of modern computer technology, parallelization is of pivotal importance. In this way, ParaSCIP is the most successful parallel MIP solver in terms of solving previously unsolvable instances from the well-known benchmark instance set MIPLIB by using supercomputers. It solved two instances from MIPLIB2003 and 12 from MIPLIB2010 for the first time to optimality by using up to 80,000 cores on supercomputers. ParaSCIP has been developed by using the Ubiquity Generator (UG) framework, which is a general software package to parallelize any state-of-the-art branch-and-bound based solver. This paper discusses 7 years of progress in parallelizing branch-and-bound solvers with UG.}, language = {en} } @article{ShinanoBertholdHeinz, author = {Shinano, Yuji and Berthold, Timo and Heinz, Stefan}, title = {ParaXpress: An Experimental Extension of the FICO Xpress-Optimizer to Solve Hard MIPs on Supercomputers}, series = {Optimization Methods \& Software}, volume = {33}, journal = {Optimization Methods \& Software}, number = {3}, doi = {10.1080/10556788.2018.1428602}, pages = {530 -- 539}, abstract = {The Ubiquity Generator (UG) is a general framework for the external parallelization of mixed integer programming (MIP) solvers. In this paper, we present ParaXpress, a distributed memory parallelization of the powerful commercial MIP solver FICO Xpress. Besides sheer performance, an important feature of Xpress is that it provides an internal parallelization for shared memory systems. When aiming for a best possible performance of ParaXpress on a supercomputer, the question arises how to balance the internal Xpress parallelization and the external parallelization by UG against each other. We provide computational experiments to address this question and we show computational results for running ParaXpress on a Top500 supercomputer, using up to 43,344 cores in parallel.}, language = {en} } @article{ShinanoHeinzVigerskeetal., author = {Shinano, Yuji and Heinz, Stefan and Vigerske, Stefan and Winkler, Michael}, title = {FiberSCIP - A shared memory parallelization of SCIP}, series = {INFORMS Journal on Computing}, volume = {30}, journal = {INFORMS Journal on Computing}, number = {1}, doi = {10.1287/ijoc.2017.0762}, pages = {11 -- 30}, abstract = {Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a mixed-integer linear programming solver and constraint integer programming framework available in source code. There is a parallel extension of SCIP named ParaSCIP, which parallelizes SCIP on massively parallel distributed memory computing environments. This paper describes FiberSCIP, which is yet another parallel extension of SCIP to utilize multi-threaded parallel computation on shared memory computing environments, and has the following contributions: First, we present the basic concept of having two parallel extensions, and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator), including an implementation of deterministic parallelization. Second, we discuss the difficulties in achieving a good performance that utilizes all resources on an actual computing environment, and the difficulties of performance evaluation of the parallel solvers. Third, we present a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions. Finally, we demonstrate the current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer nonlinear programs (MINLPs) in parallel.}, language = {en} } @inproceedings{YokoyamaShinanoWakayamaetal., author = {Yokoyama, Ryohei and Shinano, Yuji and Wakayama, Yuki and Wakui, Tetsuya}, title = {Multiobjective Optimal Design of a Gas Turbine Cogeneration Plant by a Revised Hierarchical Optimization Method}, series = {ASME Turbo Expo 2017: Turbomachinery Technical Conference and Exposition}, volume = {3}, booktitle = {ASME Turbo Expo 2017: Turbomachinery Technical Conference and Exposition}, doi = {doi:10.1115/GT2017-64296}, pages = {1 -- 14}, abstract = {To attain the highest performance of energy supply systems, it is necessary to rationally determine design specifications in consideration of operational strategies corresponding to energy demands. Mixed-integer linear programming (MILP) approaches have been applied widely to such optimal design problems. A MILP method utilizing the hierarchical relationship between design and operation variables have been proposed to solve them efficiently. However, it cannot necessarily be effective to multi-objective optimal design problems because of the existence of a large number of competing design candidates. In this paper, the hierarchical MILP method is revised from the viewpoint of computation efficiency so that it can be applied practically to multi-objective optimal design problems. At the lower level, the order of the optimal operation problems to be solved is changed based on incumbents obtained previously to increase a lower bound for the optimal value of the combined objective function and reduce the number of the optimal operation problems to be solved. At the upper level, a lower bound for the optimal value of the combined objective function is incorporated into the solution method to reduce the number of the design candidates to be generated. This revised hierarchical MILP method is applied to a multiobjective optimal design of a gas turbine cogeneration plant, and its validity and effectiveness are clarified.}, language = {en} } @inproceedings{YokoyamaNakamuraWakuietal., author = {Yokoyama, Ryohei and Nakamura, Ryo and Wakui, Tetsuya and Shinano, Yuji}, title = {Evaluation of Performance Robustness of a Gas Turbine Cogeneration Plant Based on a Mixed-Integer Linear Model}, series = {ASME Turbo Expo 2016: Turbomachinery Technical Conference and Exposition}, volume = {3}, booktitle = {ASME Turbo Expo 2016: Turbomachinery Technical Conference and Exposition}, doi = {doi:10.1115/GT2016-56217}, pages = {1 -- 9}, abstract = {In designing energy supply systems, designers are requested to rationally determine equipment types, capacities, and numbers in consideration of equipment operational strategies corresponding to seasonal and hourly variations in energy demands. However, energy demands have some uncertainty at the design stage, and the energy demands which become certain at the operation stage may differ from those estimated at the design stage. Therefore, designers should consider that energy demands have some uncertainty, evaluate the performance robustness against the uncertainty, and design the systems to heighten the robustness. Especially, this issue is important for cogeneration plants, because their performances depend significantly on both heat and power demands. Although robust optimal design methods of energy supply systems under uncertain energy demands were developed, all of them are based on linear models for energy supply systems. However, it is still a hard challenge to develop a robust optimal design method even based on a mixed-integer linear model. At the first step for this challenge, in this paper, a method of evaluating the performance robustness of energy supply systems under uncertain energy demands is proposed based on a mixed-integer linear model. This problem is formulated as a bilevel mixed-integer linear programming one, and a sequential solution method is applied to solve it approximately by discretizing uncertain energy demands within their intervals. In addition, a hierarchical optimization method in consideration of the hierarchical relationship between design and operation variables is applied to solve large scale problems efficiently. Through a case study on a gas turbine cogeneration plant for district energy supply, the validity and effectiveness of the proposed method and features of the performance robustness of the plant are clarified.}, language = {en} } @misc{TateiwaShinanoYamamuraetal., author = {Tateiwa, Nariaki and Shinano, Yuji and Yamamura, Keiichiro and Yoshida, Akihiro and Kaji, Shizuo and Yasuda, Masaya and Fujisawa, Katsuki}, title = {CMAP-LAP: Configurable Massively Parallel Solver for Lattice Problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82802}, abstract = {Lattice problems are a class of optimization problems that are notably hard. There are no classical or quantum algorithms known to solve these problems efficiently. Their hardness has made lattices a major cryptographic primitive for post-quantum cryptography. Several different approaches have been used for lattice problems with different computational profiles; some suffer from super-exponential time, and others require exponential space. This motivated us to develop a novel lattice problem solver, CMAP-LAP, based on the clever coordination of different algorithms that run massively in parallel. With our flexible framework, heterogeneous modules run asynchronously in parallel on a large-scale distributed system while exchanging information, which drastically boosts the overall performance. We also implement full checkpoint-and-restart functionality, which is vital to high-dimensional lattice problems. Through numerical experiments with up to 103,680 cores, we evaluated the performance and stability of our system and demonstrated its high capability for future massive-scale experiments.}, language = {en} } @article{YokoyamaTakeuchiShinanoetal., author = {Yokoyama, Ryohei and Takeuchi, Kotaro and Shinano, Yuji and Wakui, Tetsuya}, title = {Effect of model reduction by time aggregation in multiobjective optimal design of energy supply systems by a hierarchical MILP method}, series = {Energy}, volume = {228}, journal = {Energy}, doi = {https://doi.org/10.1016/j.energy.2021.120505}, abstract = {The mixed-integer linear programming (MILP) method has been applied widely to optimal design of energy supply systems. A hierarchical MILP method has been proposed to solve such optimal design problems efficiently. In addition, a method of reducing model by time aggregation has been proposed to search design candidates accurately and efficiently at the upper level. In this paper, the hierarchical MILP method and model reduction by time aggregation are applied to the multiobjective optimal design. The methods of clustering periods by the order of time series, by the k-medoids method, and based on an operational strategy are applied for the model reduction. As a case study, the multiobjective optimal design of a gas turbine cogeneration system is investigated by adopting the annual total cost and primary energy consumption as the objective functions, and the clustering methods are compared with one another in terms of the computation efficiency. It turns out that the model reduction by any clustering method is effective to enhance the computation efficiency when importance is given to minimizing the first objective function, but that the model reduction only by the k-medoids method is effective very limitedly when importance is given to minimizing the second objective function.}, language = {en} } @article{YokoyamaKamadaShinanoetal., author = {Yokoyama, Ryohei and Kamada, Hiroki and Shinano, Yuji and Wakui, Tetsuya}, title = {A hierarchical optimization approach to robust design of energy supply systems based on a mixed-integer linear model}, series = {Energy}, volume = {229}, journal = {Energy}, doi = {https://doi.org/10.1016/j.energy.2021.120343}, abstract = {In designing energy supply systems, designers should heighten the robustness in performance criteria against the uncertainty in energy demands. In this paper, a robust optimal design method using a hierarchical mixed-integer linear programming (MILP) method is proposed to maximize the robustness of energy supply systems under uncertain energy demands based on a mixed-integer linear model. A robust optimal design problem is formulated as a three-level min-max-min MILP one by expressing uncertain energy demands by intervals, evaluating the robustness in a performance criterion based on the minimax regret criterion, and considering relationships among integer design variables, uncertain energy demands, and integer and continuous operation variables. This problem is solved by evaluating upper and lower bounds for the minimum of the maximum regret of the performance criterion repeatedly outside, and evaluating lower and upper bounds for the maximum regret repeatedly inside. Different types of optimization problems are solved by applying a hierarchical MILP method developed for ordinary optimal design problems without and with its modifications. In a case study, the proposed approach is applied to the robust optimal design of a cogeneration system. Through the study, its validity and effectiveness are ascertained, and some features of the obtained robust designs are clarified.}, language = {en} } @misc{Shinano, author = {Shinano, Yuji}, title = {UG - Ubiquity Generator Framework v0.9.1}, doi = {10.12752/8508}, 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} } @article{BertholdKochShinano2021, author = {Berthold, Timo and Koch, Thorsten and Shinano, Yuji}, title = {MILP. Try. Repeat.}, series = {Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling - PATAT 2021}, volume = {2}, journal = {Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling - PATAT 2021}, year = {2021}, language = {en} } @misc{RehfeldtKochShinano, 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}, language = {en} } @article{HosadaMaherShinanoetal., 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}, series = {EURO Journal on Transportation and Logistics}, volume = {11}, journal = {EURO Journal on Transportation and Logistics}, publisher = {Elsevier}, doi = {10.1016/j.ejtl.2022.100091}, language = {en} } @misc{ItoShinano, 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}, 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{ShinanoHeinzVigerskeetal., author = {Shinano, Yuji and Heinz, Stefan and Vigerske, Stefan and Winkler, Michael}, title = {FiberSCIP - A shared memory parallelization of SCIP}, issn = {1438-0064}, doi = {10.1287/ijoc.2017.0762}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42595}, abstract = {Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a MIP solver and constraint integer programming framework available in source code. There is a parallel extension of SCIP named ParaSCIP, which parallelizes SCIP on massively parallel distributed memory computing environments. This paper describes FiberSCIP, which is yet another parallel extension of SCIP to utilize multi-threaded parallel computation on shared memory computing environments, and has the following contributions: First, the basic concept of having two parallel extensions and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator) is presented, including an implementation of deterministic parallelization. Second, the difficulties to achieve a good performance that utilizes all resources on an actual computing environment and the difficulties of performance evaluation of the parallel solvers are discussed. Third, a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions is presented. Finally, current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer non-linear programs (MINLPs) in parallel is demonstrated.}, language = {en} } @misc{ShinanoAchterbergBertholdetal., 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}, 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} } @misc{ShinanoAchterbergBertholdetal., 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}, 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} } @misc{GamrathKochRehfeldtetal., author = {Gamrath, Gerald and Koch, Thorsten and Rehfeldt, Daniel and Shinano, Yuji}, title = {SCIP-Jack - A massively parallel STP solver}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-52293}, abstract = {In this article we describe the impact from embedding a 15 year old model for solving the Steiner tree problem in graphs in a state-of-the-art MIP-Framework, making the result run in a massively parallel environment and extending the model to solve as many variants as possible. We end up with a high-perfomance solver that is capable of solving previously unsolved instances and, in contrast to its predecessor, is freely available for academic research.}, language = {en} } @misc{ShinanoAchterbergBertholdetal., author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Winkler, Michael}, title = {Solving Open MIP Instances with ParaSCIP on Supercomputers using up to 80,000 Cores}, issn = {1438-0064}, doi = {10.1109/IPDPS.2016.56}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-56404}, abstract = {This paper describes how we solved 12 previously unsolved mixed-integer program- ming (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} } @misc{FujiiItoKimetal., author = {Fujii, Koichi and Ito, Naoki and Kim, Sunyoung and Kojima, Masakazu and Shinano, Yuji and Toh, Kim-Chuan}, title = {Solving Challenging Large Scale QAPs}, issn = {1438-0064}, doi = {10.12752/8130}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-81303}, abstract = {We report our progress on the project for solving larger scale quadratic assignment problems (QAPs). Our main approach to solve large scale NP-hard combinatorial optimization problems such as QAPs is a parallel branch-and-bound method efficiently implemented on a powerful computer system using the Ubiquity Generator(UG) framework that can utilize more than 100,000 cores. Lower bounding procedures incorporated in the branch-and-bound method play a crucial role in solving the problems. For a strong lower bounding procedure, we employ the Lagrangian doubly nonnegative (DNN) relaxation and the Newton-bracketing method developed by the authors' group. In this report, we describe some basic tools used in the project including the lower bounding procedure and branching rules, and present some preliminary numerical results. Our next target problem is QAPs with dimension at least 50, as we have succeeded to solve tai30a and sko42 from QAPLIB for the first time.}, language = {en} } @misc{Shinano, author = {Shinano, Yuji}, title = {The Ubiquity Generator Framework: 7 Years of Progress in Parallelizing Branch-and-Bound}, issn = {1438-0064}, doi = {10.1007/978-3-319-89920-6_20}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-65545}, abstract = {Mixed integer linear programming (MIP) is a general form to model combinatorial optimization problems and has many industrial applications. The performance of MIP solvers has improved tremendously in the last two decades and these solvers have been used to solve many real-word problems. However, against the backdrop of modern computer technology, parallelization is of pivotal importance. In this way, ParaSCIP is the most successful parallel MIP solver in terms of solving previously unsolvable instances from the well-known benchmark instance set MIPLIB by using supercomputers. It solved two instances from MIPLIB2003 and 12 from MIPLIB2010 for the first time to optimality by using up to 80,000 cores on supercomputers. ParaSCIP has been developed by using the Ubiquity Generator (UG) framework, which is a general software package to parallelize any state-of-the-art branch-and-bound based solver. This paper discusses 7 years of progress in parallelizing branch-and-bound solvers with UG.}, language = {en} } @misc{FujiiItoKimetal., author = {Fujii, Koichi and Ito, Naoki and Kim, Sunyoung and Kojima, Masakazu and Shinano, Yuji and Toh, Kim-Chuan}, title = {大規模二次割当問題への挑戦}, series = {統計数理研究所共同研究リポート 453 最適化:モデリングとアルゴリズム33 2022年3月 「大規模二次割当問題への挑戦」 p.84-p.92}, journal = {統計数理研究所共同研究リポート 453 最適化:モデリングとアルゴリズム33 2022年3月 「大規模二次割当問題への挑戦」 p.84-p.92}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-86779}, abstract = {二次割当問題は線形緩和が弱いことが知られ,強化のため多様な緩和手法が考案されているが,その一つである二重非負値計画緩和( DNN 緩和)及びその解法として近年研究が進んでいるニュートン・ブラケット法を紹介し,それらに基づく分枝限定法の実装及び数値実験結果について報告する.}, language = {ja} } @misc{ShinanoRehfeldtKoch, author = {Shinano, Yuji and Rehfeldt, Daniel and Koch, Thorsten}, title = {Building Optimal Steiner Trees on Supercomputers by using up to 43,000 Cores}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71118}, 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 par- allel 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 instances from the bench- mark libary STEINLIB. After the DIMACS Challenge, SCIP-JACK has been con- siderably improved. However, the improvements were not reflected on ug [SCIP- JACK, MPI]. This paper describes an updated version of ug [SCIP-JACK, MPI], especially branching on constrains and a customized racing ramp-up. Furthermore, the different stages of the solution process on a supercomputer are described in detail. We also show the latest results on open instances from the STEINLIB.}, language = {en} } @misc{HosodaMaherShinanoetal., author = {Hosoda, Junko and Maher, Stephen J. and Shinano, Yuji and Villumsen, Jonas Christoffer}, title = {A parallel branch-and-bound heuristic for the integrated long-haul and local vehicle routing problem on an adaptive transportation network}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-89700}, abstract = {Consolidation of commodities and coordination of vehicle routes are fundamental features of supply chain management problems. While locations for consolidation and coordination are typically known a priori, in adaptive transportation networks this is not the case. The identification of such consolidation locations forms part of the decision making process. Supply chain management problems integrating the designation of consolidation locations with the coordination of long haul and local vehicle routing is not only challenging to solve, but also very difficult to formulate mathematically. In this paper, the first mathematical model integrating location clustering with long haul and local vehicle routing is proposed. This mathematical formulation is used to develop algorithms to find high quality solutions. A novel parallel framework is developed that combines exact and heuristic methods to improve the search for high quality solutions and provide valid bounds. The results demonstrate that using exact methods to guide heuristic search is an effective approach to find high quality solutions for difficult supply chain management problems.}, language = {en} } @article{YokoyamaHiramatsuShinanoetal., author = {Yokoyama, Ryohei and Hiramatsu, Yuto and Shinano, Yuji and Wakui, Tetsuya}, title = {Evaluation of robustness in multiple performance criteria for designing energy supply systems based on a mixed-integer linear model}, series = {Proceedings of the 35th International Conference on Efficiency, Cost, Optimization, Simulation and Environmental Impact of Energy Systems (ECOS 2022)}, journal = {Proceedings of the 35th International Conference on Efficiency, Cost, Optimization, Simulation and Environmental Impact of Energy Systems (ECOS 2022)}, pages = {1937 -- 1948}, abstract = {In designing energy supply systems, it is important to consider the uncertainty in energy demands, evaluate the robustness in some performance criteria, and heighten the robustness. A robust optimal design method has been previously proposed to maximize the robustness in a single performance criterion against the uncertainty in energy demands based on a mixed-integer linear model. In this paper, as a preliminary step toward multiobjective robust optimal design, a method of evaluating robustness in multiple performance criteria against the uncertainty in energy demands is proposed based on a mixed-integer linear model. The problems of evaluating the robustness in the performance criteria are formulated as bilevel mixed-integer linear programming (MILP) ones. They are solved by evaluating lower and upper bounds for the maximum regrets in the performance criteria alternately and repeatedly with the aid of a solution method based on reformulation and decomposition. In addition, for the purpose of applying the proposed method to practical problems, a hierarchical MILP method is used to efficiently solve some MILP problems in the solution process. Through a case study on a cogeneration system, the robustness in the annual total cost and primary energy consumption is evaluated and its trade-off relationship is clarified.}, language = {en} } @article{YokoyamaShinanoWakui, author = {Yokoyama, Ryohei and Shinano, Yuji and Wakui, Tetsuya}, title = {Day and time aggregations for optimal design of energy supply systems with storage units by a hierarchical MILP method}, series = {PROCEEDINGS OF ECOS 2022 - THE 35 TH INTERNATIONAL CONFERENCE ON EFFICIENCY, COST, OPTIMIZATION, SIMULATION AND ENVIRONMENTAL IMPACT OF ENERGY SYSTEMS}, journal = {PROCEEDINGS OF ECOS 2022 - THE 35 TH INTERNATIONAL CONFERENCE ON EFFICIENCY, COST, OPTIMIZATION, SIMULATION AND ENVIRONMENTAL IMPACT OF ENERGY SYSTEMS}, pages = {1891 -- 1902}, abstract = {Mixed-integer linear programming (MILP) methods have been applied widely to optimal design of energy supply systems. A hierarchical MILP method has been proposed to solve such optimal design problems efficiently. In addition, some strategies have been proposed to enhance the computation efficiency furthermore. As one of the strategies, a method of reducing model by time aggregation has been proposed to search design candidates efficiently in the relaxed optimal design problem at the upper level. In this paper, the hierarchical MILP method with the strategies is extendedly applied to the optimal design of energy supply systems with storage units. Especially, the method of reducing model is extended by aggregating both representative days and sampling times separately in consideration of the characteristics of energy storage units. A case study is conducted on the optimal design of a cogeneration system with a thermal storage tank. Through the study, it turns out the hierarchical MILP method is effective to derive the optimal solutions in short computation times. It also turns out that the model reduction with day and time aggregations is effective to shorten the computation times furthermore when the number of candidates for equipment capacities is relatively small.}, language = {en} } @misc{GamrathKochMaheretal., author = {Gamrath, Gerald and Koch, Thorsten and Maher, Stephen J. and Rehfeldt, Daniel and Shinano, Yuji}, title = {SCIP-Jack - A solver for STP and variants with parallelization extensions}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-54648}, abstract = {The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problem specific. In contrast, this paper introduces a general purpose solver that can be used to solve both the classical Steiner tree problem and many of its variants without modification. This is achieved by transforming various problem variants into a general form and solving them using a state-of-the-art MIP-framework. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances.}, language = {en} } @misc{Shinano, author = {Shinano, Yuji}, title = {UG - Ubiquity Generator Framework v1.0.0beta}, doi = {10.12752/8521}, 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. v1.0.0: new documentation and cmake, generalization of ug framework, implementation of selfsplitrampup for fiber- and parascip, better memory and time limit handling.}, language = {en} } @misc{MunguiaOxberryRajanetal., author = {Munguia, Lluis-Miquel and Oxberry, Geoffrey and Rajan, Deepak and Shinano, Yuji}, title = {Parallel PIPS-SBB: Multi-Level Parallelism For Stochastic Mixed-Integer Programs}, number = {ZIB-Report 17-58}, issn = {1438-0064}, doi = {10.1007/s10589-019-00074-0}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-65517}, abstract = {PIPS-SBB is a distributed-memory parallel solver with a scalable data distribution paradigm. It is designed to solve MIPs with a dual-block angular structure, which is characteristic of deterministic-equivalent Stochastic Mixed-Integer Programs (SMIPs). In this paper, we present two different parallelizations of Branch \& Bound (B\&B), implementing both as extensions of PIPS-SBB, thus adding an additional layer of parallelism. In the first of the proposed frameworks, PIPS-PSBB, the coordination and load-balancing of the different optimization workers is done in a decentralized fashion. This new framework is designed to ensure all available cores are processing the most promising parts of the B\&B tree. The second, ug[PIPS-SBB,MPI], is a parallel implementation using the Ubiquity Generator (UG), a universal framework for parallelizing B\&B tree search that has been successfully applied to other MIP solvers. We show the effects of leveraging multiple levels of parallelism in potentially improving scaling performance beyond thousands of cores.}, language = {en} } @misc{FujiiKimKojimaetal., 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}, 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{RehfeldtFujisawaKochetal., author = {Rehfeldt, Daniel and Fujisawa, Katsuki and Koch, Thorsten and Nakao, Masahiro and Shinano, Yuji}, title = {Computing single-source shortest paths on graphs with over 8 trillion edges}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-88180}, abstract = {This paper introduces an implementation for solving the single-source shortest path problem on distributed-memory machines. It is tailored to power-law graphs and scales to trillions of edges. The new implementation reached 2nd and 10th place in the latest Graph500 benchmark in June 2022 and handled the largest and second-largest graphs among all participants.}, language = {en} } @misc{MaherRalphsShinano, author = {Maher, Stephen J. and Ralphs, Ted and Shinano, Yuji}, title = {Assessing the Effectiveness of (Parallel) Branch-and-bound Algorithms}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74702}, abstract = {Empirical studies are fundamental in assessing the effectiveness of implementations of branch-and-bound algorithms. The complexity of such implementations makes empirical study difficult for a wide variety of reasons. Various attempts have been made to develop and codify a set of standard techniques for the assessment of optimization algorithms and their software implementations; however, most previous work has been focused on classical sequential algorithms. Since parallel computation has become increasingly mainstream, it is necessary to re-examine and modernize these practices. In this paper, we propose a framework for assessment based on the notion that resource consumption is at the heart of what we generally refer to as the "effectiveness" of an implementation. The proposed framework carefully distinguishes between an implementation's baseline efficiency, the efficacy with which it utilizes a fixed allocation of resources, and its scalability, a measure of how the efficiency changes as resources (typically additional computing cores) are added or removed. Efficiency is typically applied to sequential implementations, whereas scalability is applied to parallel implementations. Efficiency and scalability are both important contributors in determining the overall effectiveness of a given parallel implementation, but the goal of improved efficiency is often at odds with the goal of improved scalability. Within the proposed framework, we review the challenges to effective evaluation and discuss the strengths and weaknesses of existing methods of assessment.}, language = {en} } @inproceedings{GottwaldMaherShinano, author = {Gottwald, Robert Lion and Maher, Stephen J. and Shinano, Yuji}, title = {Distributed Domain Propagation}, series = {16th International Symposium on Experimental Algorithms (SEA 2017)}, volume = {75}, booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)}, doi = {10.4230/LIPIcs.SEA.2017.6}, pages = {6:1 -- 6:11}, abstract = {Portfolio parallelization is an approach that runs several solver instances in parallel and terminates when one of them succeeds in solving the problem. Despite its simplicity, portfolio parallelization has been shown to perform well for modern mixed-integer programming (MIP) and boolean satisfiability problem (SAT) solvers. Domain propagation has also been shown to be a simple technique in modern MIP and SAT solvers that effectively finds additional domain reductions after the domain of a variable has been reduced. In this paper we introduce distributed domain propagation, a technique that shares bound tightenings across solvers to trigger further domain propagations. We investigate its impact in modern MIP solvers that employ portfolio parallelization. Computational experiments were conducted for two implementations of this parallelization approach. While both share global variable bounds and solutions, they communicate differently. In one implementation the communication is performed only at designated points in the solving process and in the other it is performed completely asynchronously. Computational experiments show a positive performance impact of communicating global variable bounds and provide valuable insights in communication strategies for parallel solvers.}, language = {en} } @misc{GamrathKochMaheretal., author = {Gamrath, Gerald and Koch, Thorsten and Maher, Stephen J. and Rehfeldt, Daniel and Shinano, Yuji}, title = {SCIP-Jack - A solver for STP and variants with parallelization extensions}, issn = {1438-0064}, doi = {10.1007/s12532-016-0114-x}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-60170}, abstract = {The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problem-specific. In contrast, this paper introduces a general-purpose solver that can be used to solve both the classical Steiner tree problem and many of its variants without modification. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances.}, language = {en} } @misc{GottwaldMaherShinano, author = {Gottwald, Robert Lion and Maher, Stephen J. and Shinano, Yuji}, title = {Distributed domain propagation}, issn = {1438-0064}, doi = {10.4230/LIPIcs.SEA.2017.6}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61380}, abstract = {Portfolio parallelization is an approach that runs several solver instances in parallel and terminates when one of them succeeds in solving the problem. Despite it's simplicity portfolio parallelization has been shown to perform well for modern mixed-integer programming (MIP) and boolean satisfiability problem (SAT) solvers. Domain propagation has also been shown to be a simple technique in modern MIP and SAT solvers that effectively finds additional domain reductions after a variables domain has been reduced. This paper investigates the impact of distributed domain propagation in modern MIP solvers that employ portfolio parallelization. Computational experiments were conducted for two implementations of this parallelization approach. While both share global variable bounds and solutions they communicate differently. In one implementation the communication is performed only at designated points in the solving process and in the other it is performed completely asynchronously. Computational experiments show a positive performance impact of communicating global variable bounds and provide valuable insights in communication strategies for parallel solvers.}, language = {en} } @article{GamrathKochMaheretal., author = {Gamrath, Gerald and Koch, Thorsten and Maher, Stephen J. and Rehfeldt, Daniel and Shinano, Yuji}, title = {SCIP-Jack - A solver for STP and variants with parallelization extensions}, series = {Mathematical Programming Computation}, volume = {9}, journal = {Mathematical Programming Computation}, number = {2}, doi = {10.1007/s12532-016-0114-x}, pages = {231 -- 296}, abstract = {The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problem-specific. In contrast, this paper introduces a general-purpose solver that can be used to solve both the classical Steiner tree problem and many of its variants without modification. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances.}, language = {en} } @article{YokoyamaShinanoWakui, author = {Yokoyama, Ryohei and Shinano, Yuji and Wakui, Tetsuya}, title = {Evaluation of Design Alternatives for a Gas Turbine Cogeneration Plant Based on Multiobjective K-Best Solutions}, series = {International Conference on Power Engineering-2019}, journal = {International Conference on Power Engineering-2019}, pages = {1112 -- 1117}, abstract = {To realize the best performance in energy supply, it is an important task to determine types, capacities, and numbers of energy conversion equipment appropriately. It is also necessary to take account of seasonal and hourly variations in energy demands and corresponding operational strategies of equipment. The mixed-integer linear programming (MILP) method has been utilized widely to derive the optimal solution for such a design problem. From the design viewpoint, it is important to generate not only the optimal solution but also suboptimal ones which follow the optimal one without omission, what are called K-best solutions. In this paper, an MILP method utilizing the hierarchical relationship between design and operation variables is applied along with some strategies to efficiently drive K-best solutions of a multiobjective optimal design problem of a gas turbine cogeneration system for district energy supply. The annual total cost and primary energy consumption are adopted as the objective functions to be minimized. A case study is conducted, and K-best solutions with an allowable increase in the value of the combined objective function are derived for each value of the weight for the annual total cost. Through the study, it is clarified how the weight affects the computation time, the number of the K-best solutions, and the design specifications and the values of the objective functions for the K-best solutions.}, language = {en} } @article{YokoyamaHiramatsuShinanoetal., author = {Yokoyama, Ryohei and Hiramatsu, Yuto and Shinano, Yuji and Wakui, Tetsuya}, title = {Evaluation of robustness in multiple performance criteria for designing energy supply systems based on a mixed-integer linear model}, series = {The 35th International Conference on Efficiency, Cost, Optimization, Simulation and Environmental Impact of Energy Systems (ECOS 2022)}, journal = {The 35th International Conference on Efficiency, Cost, Optimization, Simulation and Environmental Impact of Energy Systems (ECOS 2022)}, pages = {1937 -- 1948}, abstract = {In designing energy supply systems, it is important to consider the uncertainty in energy demands, evaluate the robustness in some performance criteria, and heighten the robustness. A robust optimal design method has been previously proposed to maximize the robustness in a single performance criterion against the uncertainty in energy demands based on a mixed-integer linear model. In this paper, as a preliminary step toward multiobjective robust optimal design, a method of evaluating robustness in multiple performance criteria against the uncertainty in energy demands is proposed based on a mixed-integer linear model. The problems of evaluating the robustness in the performance criteria are formulated as bilevel mixed-integer linear programming (MILP) ones. They are solved by evaluating lower and upper bounds for the maximum regrets in the performance criteria alternately and repeatedly with the aid of a solution method based on reformulation and decomposition. In addition, for the purpose of applying the proposed method to practical problems, a hierarchical MILP method is used to efficiently solve some MILP problems in the solution process. Through a case study on a cogeneration system, the robustness in the annual total cost and primary energy consumption is evaluated and its trade-off relationship is clarified. As a result, it turns out how the values of these performance criteria are close to the optimal ones in relation to the uncertainty in energy demands. This work will be an important step toward developing a multiobjective robust optimal design method.}, language = {en} } @article{YokoyamaShinanoTaniguchietal., author = {Yokoyama, Ryohei and Shinano, Yuji and Taniguchi, Syusuke and Wakui, Tetsuya}, title = {Search for K-best solutions in optimal design of energy supply systems by an extended MILP hierarchical branch and bound method}, series = {Energy}, volume = {184}, journal = {Energy}, doi = {https://doi.org/10.1016/j.energy.2018.02.077}, pages = {45 -- 57}, abstract = {For the purpose of making a decision in the optimal design of an energy supply system, it is important to investigate not only the optimal solution but also suboptimal ones which follow the optimal one without any omissions, what are called K-best solutions. In this paper, a mixed-integer linear programming method utilizing the hierarchical relationship between design and operation variables proposed previ- ously is extended to search the K-best solutions very efficiently. In addition, methods for updating the incumbents are incorporated into the extended method for three options for the criterion set newly in deriving the K-best solutions. This extended method is implemented into open and commercial MILP solvers, and is applied to illustrative and practical case studies, respectively, on the optimal design of cogeneration systems. Through the studies, it turns out that the proposed method is much superior in terms of solution optimality and computation efficiency to a conventional method, and that the computation efficiency to derive one of the K-best solutions by the proposed method increases with the number of K-best solutions. In addition, features of the K-best solutions in the value of objective function are clarified.}, language = {en} } @article{YokoyamaShinanoWakayamaetal., 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}, series = {Energy}, volume = {181}, journal = {Energy}, doi = {https://doi.org/10.1016/j.energy.2019.04.066}, pages = {782 -- 792}, 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} } @article{YokoyamaShinanoTakeuchietal., author = {Yokoyama, Ryohei and Shinano, Yuji and Takeuchi, Kotaro and Wakui, Tetsuya}, title = {Operation-based time-period clustering for optimal design of energy supply systems by a hierarchical MILP method}, series = {THE 32ND INTERNATIONAL CONFERENCE ON EFFICIENCY, COST, OPTIMIZATION, SIMULATION AND ENVIRONMENTAL IMPACT OF ENERGY SYSTEMS(ECOS 2019)}, journal = {THE 32ND INTERNATIONAL CONFERENCE ON EFFICIENCY, COST, OPTIMIZATION, SIMULATION AND ENVIRONMENTAL IMPACT OF ENERGY SYSTEMS(ECOS 2019)}, pages = {527 -- 539}, abstract = {Mixed-integer linear programming (MILP) methods have been applied widely to optimal design of energy supply systems. A hierarchical MILP method has been proposed to solve such optimal design problems efficiently. In addition, some strategies have been proposed to enhance the computation efficiency furthermore. As one of the strategies, a method of reducing model by time aggregation has been proposed to search design candidates efficiently in the relaxed optimal design problem at the upper level. In this paper, a method of clustering periods has been proposed based on the optimal operational strategies of the systems to avoid a large decrease in the lower bound for the optimal value of the objective function by model reduction. This method has been realized only by solving the relaxed optimal design problem at the upper level in advance. The method can decrease the number of operation variables and constraints at the upper level, and thus can 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 proposed clustering method is effective to enhance the computation efficiency in comparison with the conventional one which clusters periods regularly in time series.}, language = {en} } @article{YokoyamaShinanoWakui, author = {Yokoyama, Ryohei and Shinano, Yuji and Wakui, Tetsuya}, title = {Day and time aggregations for optimal design of energy supply systems with storage units by a hierarchical MILP method}, series = {The 35th International Conference on Efficiency, Cost, Optimization, Simulation and Environmental Impact of Energy Systems (ECOS 2022)}, journal = {The 35th International Conference on Efficiency, Cost, Optimization, Simulation and Environmental Impact of Energy Systems (ECOS 2022)}, pages = {1891 -- 1902}, abstract = {Mixed-integer linear programming (MILP) methods have been applied widely to optimal design of energy supply systems. A hierarchical MILP method has been proposed to solve such optimal design problems efficiently. In addition, some strategies have been proposed to enhance the computation efficiency furthermore. As one of the strategies, a method of reducing model by time aggregation has been proposed to search design candidates efficiently in the relaxed optimal design problem at the upper level. In this paper, the hierarchical MILP method with the strategies is extendedly applied to the optimal design of energy supply systems with storage units. Especially, the method of reducing model is extended by aggregating both representative days and sampling times separately in consideration of the characteristics of energy storage units. A case study is conducted on the optimal design of a cogeneration system with a thermal storage tank. Through the study, it turns out the hierarchical MILP method is effective to derive the optimal solutions in short computation times. It also turns out that the model reduction with day and time aggregations is effec- tive to shorten the computation times furthermore when the number of candidates for equipment capacities is relatively small.}, language = {en} } @article{YokoyamaShinanoWakayamaetal., 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}, series = {Energy}, volume = {181}, journal = {Energy}, pages = {782 -- 792}, abstract = {Mixed-integer linear programming (MILP) methods have been applied widely to optimal design of en- ergy 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 pro- posed 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 accor- dance 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} } @article{WakayamaYokoyamaShinanoetal., author = {Wakayama, Yuki and Yokoyama, Ryohei and Shinano, Yuji and Wakui, Tetsuya}, title = {エネルギー供給システムの設計および運用の階層的関係を考慮した最適化(時間集約によるモデル縮約とその効果)}, series = {エネルギー・資源学会第34回エネルギーシステム・経済・環境コンファレンス講演論文集}, journal = {エネルギー・資源学会第34回エネルギーシステム・経済・環境コンファレンス講演論文集}, pages = {401 -- 404}, abstract = {A hierarchical mixed-integer linear programming method to solve optimal design problems of energy supply systems efficiently has been proposed. The original problem is solved by dividing it into a relaxed optimal design problem at the upper level and optimal operation problems which are independent of each other at the lower level. In this paper, a method of reducing model by time aggregation is proposed to search design solution candidates efficiently in the relaxed optimal design problem at the upper level. This method is realized only by clustering periods and averaging energy demands for clustered periods, while it guarantees to derive the optimal solution. On one hand, the method may decrease the number of design variables and costraints at the upper level, and thus the computation time at the upper level. On the other hand, it may increase the numbers of generated design solution candidates and solved optimal operation problems, and thus the computation time at both the levels. Though a case study on the optimal design of a cogeneration system, it is clarified how the model reduction is effective to enhance the computation efficiency.}, language = {ja} } @article{TakeuchiYokoyamaShinanoetal., author = {Takeuchi, Kotaro and Yokoyama, Ryohei and Shinano, Yuji and Wakui, Tetsuya}, title = {エネルギー供給システムの 設計と運用の階層的関係を考慮した最適化 (運用を考慮した期間クラスタリングによるモデル縮約)}, series = {エネルギー・資源学会第35回エネルギーシステム・経済・環境コンファレンス講演論文集}, journal = {エネルギー・資源学会第35回エネルギーシステム・経済・環境コンファレンス講演論文集}, pages = {169 -- 174}, abstract = {To attain the highest performance of energy supply systems, it is necessary to determine design specifications optimally in consideration of operational strategies corresponding to seasonal and hourly variations in energy demands. Mixed-integer linear programming (MILP) methods have been applied widely to such multi-period optimal design problems. A hierarchical MILP method has been proposed to solve the problems very efficiently. In addition, by utilizing features of the hierarchical MILP method, a method of reducing model by clustering periods has also been proposed to search design solution candidates efficiently in the relaxed optimal design problem at the upper level. In this paper, by utilizing features of the hierarchical MILP method, a method of clustering periods is proposed based on the optimal operational strategies of energy supply systems obtained by solving the relaxed optimal design problem. As a case study, the method is applied to the optimal design of a gas turbine cogeneration system, and it is clarified that the method is effective to enhance the computation efficiency in comparison with a conventional method of clustering periods regularly.}, language = {ja} } @article{KamadaYokoyamaShinanoetal., author = {Kamada, Hiroki and Yokoyama, Ryohei and Shinano, Yuji and Wakui, Tetsuya}, title = {混合整数線形モデルによる エネルギー供給システムのロバスト最適設計 (階層的最適化手法の適用)}, series = {エネルギー・資源学会第35回エネルギーシステム・経済・環境コンファレンス講演論文集}, journal = {エネルギー・資源学会第35回エネルギーシステム・経済・環境コンファレンス講演論文集}, pages = {163 -- 168}, abstract = {A robust optimal design method of energy supply systems under uncertain energy demands has been proposed using a mixed- integer linear model for constituent equipment. A robust optimal design problem has been formulated as a three-level min-max- min optimization one by expressing uncertain energy demands by intervals, evaluating the robustness in a performance criterion based on the minimax regret criterion, and considering hierarchical relationships among design variables, uncertain energy demands, and operation variables. However, this method takes a long computation time, and thus it can be applied only to small-scale problems. In this paper, mixed-integer linear programming method in consideration of the hierarchical relationship between design and operation variables is applied to parts of the robust optimal design method which take long computation times to solve problems efficiently. In a case study, this revised method is applied to the robust optimal design of a cogeneration system with a simple configuration, and the validity and effectiveness of the method are ascertained.}, language = {ja} } @article{YokoyamaShinanoTaniguchietal., author = {Yokoyama, Ryohei and Shinano, Yuji and Taniguchi, Syusuke and Ohkura, Masashi and Wakui, Tetsuya}, title = {エネルギー供給システムの設計および運用の階層的関係を考慮した最適化(手法の提案)}, series = {第33回エネルギー・資源学会研究発表会講演論文要旨集・講演論文集}, journal = {第33回エネルギー・資源学会研究発表会講演論文要旨集・講演論文集}, pages = {183 -- 188}, abstract = {A mixed-integer linear programming (MILP) method utilizing the hierarchical relationship between design and op- eration variables is proposed to solve the optimal design problem of energy supply systems efficiently: At the upper level, the optimal values of design variables are searched by the branch and bound method; At the lower level, the values of operation variables are optimized by the branch and bound method under the values of design variables given tentatively during the search at the upper level; Lower bounds for the optimal value of the objective function are evaluated, and are utilized for the bounding operations at both the levels. This method is implemented into open and commercial MILP solvers. Illustrative and practical case studies on the optimal design of cogeneration systems are conducted, and the validity and effectiveness of the proposed method are clarified.}, language = {ja} } @article{YokoyamaShinanoTaniguchietal., author = {Yokoyama, Ryohei and Shinano, Yuji and Taniguchi, Syusuke and Ohkura, Masashi and Wakui, Tetsuya}, title = {エネルギー供給システムの設計および運用階層的関係を考慮した最適化(K-ベスト解の探索)}, series = {日本機械学会第11回最適化シンポジウム2014講演論文集}, journal = {日本機械学会第11回最適化シンポジウム2014講演論文集}, pages = {1 -- 4}, abstract = {A mixed-integer linear programming methodutilizing the hierarchical relationship between design and operation variables proposed ot solve the optimal design problem of energy supply systems efficiently is extended ot search K-best solutions: At the upper level, the optimal values ofdesign variables are searched with operation variables relaxed to continuous ones; At the lower level, the values of operation variables are optimized with the values of design variables given tentatively; The obtained solution is used to renew K-best incumbent solutions, and the upper bound for the value of the objective function for K-best solutions is replaced correspondingly. A practical case study is conducted, and the validity and effectiveness of the proposed method are clarified.}, language = {ja} } @article{WakayamaYokoyamaShinanoetal., author = {Wakayama, Yuki and Yokoyama, Ryohei and Shinano, Yuji and Wakui, Tetsuya}, title = {階層的最適化によるエネルギ ー供給システムの最適設計・運用 (期間のクラスタリングに よるモデル縮約とその効果)}, series = {日本機械学会関西支部第93期定時総会講演会講演論文集}, journal = {日本機械学会関西支部第93期定時総会講演会講演論文集}, pages = {259 -- 260}, abstract = {Ahierarchical mixed-integer linear programmingmethod has been proposed to solve optimal design problems of energy supply systems efficiently. In this paper, a method of reducing model by clustering periods is proposed to search design solution candidates efficiently in the relaxed optimal design problem at the upper level. This method is realized only by clustering periods and averaging energy demands for clustered periods, while it guarantees to derive the optimal solution. Through acase study on the optimaldesign of a cogeneration system, ti is clarified how the model reduction si effective ot enhance the computation efficiency.}, language = {ja} } @article{KamadaYokoyamaShinanoetal., author = {Kamada, Hiroki and Yokoyama, Ryohei and Shinano, Yuji and Wakui, Tetsuya}, title = {階層的最適化手法を用いた エネルギー供給システムのロバスト性評価}, series = {日本機械学会関西支部第95期定時総会講演会講演論文集}, journal = {日本機械学会関西支部第95期定時総会講演会講演論文集}, pages = {1 -- 4}, abstract = {A robust optimal design method of energy supply systems under uncertain energy demands has been proposed using a mixed-integer linear model for constituent equipment. However, this method takes a long computation time, and thus it can be applied only to small-scale problems. In this paper, a hierarchical optimization method is applied to two types of optimization problems for evaluating robustness to solve them efficiently. In a case study, the proposed method is applied to a cogeneration system with a complex configuration, and the validity and effectiveness of the method are ascertained.}, language = {ja} } @article{TaniguchiYokoyamaShinanoetal., author = {Taniguchi, Shusuke and Yokoyama, Ryohei and Shinano, Yuji and Ohkura, Masashi and Wakui, Tetsuya}, title = {エネルギー供給システムの設計および運用の階層的関係を考慮した最適化(多目的最適化におけるK-ベスト解の探索)}, series = {エネルギー・資源学会第31回エネルギーシステム・経済・環境コンファレンス講演論文集}, journal = {エネルギー・資源学会第31回エネルギーシステム・経済・環境コンファレンス講演論文集}, pages = {267 -- 272}, abstract = {A mixed-integer linear programming method utilizing the hierarchical relationship between design and operation variables proposed to solve the optimal design problem of energy supply systems efficiently is extended to search K-best solutions in multiobjective optimization: At the upper level, the optimal values of design variables are searched by the branch and bound method with operation variables relaxed to continuous ones; At the lower level, the values of operation variables are optimized independently at the respective periods set for variations in energy demands by the branch and bound method with the values of design variables given tentatively during the search at the upper level. A weighting method is employed for multiobjective optimization, and a weighted sum of the annual total cost and primary energy consumption is adopted as the objective function to be minimized. A practical case study on the optimal design of a cogeneration system is conducted. The validity and effectiveness of the proposed method are clarified, and the trade-off relationship between the annual total cost and primary energy consumption is confirmed.}, language = {ja} } @article{TakeuchiYokoyamaShinanoetal., author = {Takeuchi, Kotaro and Yokoyama, Ryohei and Shinano, Yuji and Wakui, Tetsuya}, title = {エネルギー供給システムの 設計および運用の階層的関係を考慮した最適化 (多目的最適設計へのモデル縮約の適用)}, series = {エネルギー・資源学会第36回エネルギーシステム・経済・環境コンファレンス講演論文集}, journal = {エネルギー・資源学会第36回エネルギーシステム・経済・環境コンファレンス講演論文集}, pages = {724 -- 729}, abstract = {To attain the highest performance of energy supply systems, it is necessary to determine design specifications optimally in consideration of operational strategies corresponding to seasonal and hourly variations in energy demands. Mixed-integer linear programming (MILP) methods have been applied widely to such optimal design problems. A hierarchical MILP method has been proposed to solve the problems very efficiently. In addition, by utilizing features of the hierarchical MILP method, a method of reducing model by clustering periods based on the optimal operational strategies of equipment has been proposed to search design solution candidates efficiently in the relaxed optimal design problem at the upper level. In this paper, these methods are applied to the multiobjective optimal design of a cogeneration system by considering the annual total cost and primary energy consumption as the objective functions to be minimized. Through a case study, it turns out that the model reduction by the operation-based time-period clustering is effective in terms of the computation efficiency when importance is given to the first objective function, while it is not when importance is given to the second objective function.}, language = {ja} } @article{YokoyamaShinanoTakeuchietal., author = {Yokoyama, Ryohei and Shinano, Yuji and Takeuchi, Kotaro and Wakui, Tetsuya}, title = {エネルギー供給システムの設計および運用の 階層的関係を考慮した最適化 (モデル縮約のための期間クラスタリング手法の比較)}, series = {第38回エネルギー・資源学会研究発表会講演論文集}, journal = {第38回エネルギー・資源学会研究発表会講演論文集}, pages = {109 -- 114}, abstract = {Mixed-integer linear programming (MILP) methods have been applied widely to optimal design of energy supply systems. A hierarchical MILP method has been proposed to solve such optimal design problems efficiently. In addition, some strategies have been proposed to enhance the computation efficiency furthermore. As one of the strategies, a method of reducing model by time aggregation has been proposed to search design candidates efficiently in the relaxed optimal design problem at the upper level. In this paper, three clustering methods are applied to time aggregation and compared with one another in terms of the computation efficiency. Especially, the k-medoids method is applied newly in addition to the time-series and operation-based methods applied previously. A case study is conducted on the optimal design of a gas turbine cogeneration system for district energy supply. Through the study, it turns out the k-medoids method is effective to shorten the computation time as compared with the time-series method, although it is necessary to set the number of clusters artifically in both the methods. It also turns out that the operation-based method is more effective than the k-medoids method in terms of the computation efficiency even with the number of clusters set automatically.}, language = {ja} } @article{YokoyamaShinanoWakui, author = {Yokoyama, Ryohei and Shinano, Yuji and Wakui, Tetsuya}, title = {エネルギー供給システムの設計および運用の 階層的関係を考慮した最適化 (蓄エネルギー機器を有するシステムへの適用)}, series = {第40回エネルギー・資源学会研究発表会講演論文集}, journal = {第40回エネルギー・資源学会研究発表会講演論文集}, pages = {398 -- 403}, abstract = {Mixed-integer linear programming (MILP) methods have been applied widely to optimal design of energy supply systems. A hierarchical MILP method has been proposed to solve such optimal design problems efficiently. In addition, some strategies have been proposed to enhance the computation efficiency furthermore. As one of the strategies, a method of reducing model by time aggregation has been proposed to search design candidates efficiently in the relaxed optimal design problem at the upper level. In this paper, the hierarchical MILP method with the strategies has been extendedly applied to the optimal design of energy supply systems with storage units. Especially, the method of re- ducing model is extended by aggregating representative days and sampling times differently in consideration of the characteristics of storage units. A case study is conducted on the optimal design of a gas turbine cogeneration system with a thermal storage unit for district energy supply. Through the study, it turns out the hierarchical MILP method is effective to derive the optimal solution as compared with a conventional method. It also turns out that the model reduction with the special time aggregation is effective to shorten the computation time as compared with that without time aggregation in case that the number of candidates for equipment capacities is relatively small.}, language = {ja} } @article{YokoyamaShinanoWakui, author = {Yokoyama, Ryohei and Shinano, Yuji and Wakui, Tetsuya}, title = {時間集約によるエネルギー供給システムの 近似最適設計解の導出および評価 (階層的最適化を援用した設計解の評価)}, series = {エネルギー・資源学会第38回エネルギーシステム・経済・環境コンファレンス講演論文集}, journal = {エネルギー・資源学会第38回エネルギーシステム・経済・環境コンファレンス講演論文集}, pages = {468 -- 473}, abstract = {For the purpose of attaining the highest performance of energy supply systems, it is important to design the systems optimally in consideration of their operational strategies for seasonal and hourly variations in energy demands. An ap- proach to solve such an optimal design problem with a large number of periods efficiently is to derive an approximate optimal design solution by aggregating periods with a clustering method. However, such an approach does not provide any information on the accuracy for the optimal value of the objective function. The purpose of this paper is to provide a time aggregation method for deriving aprroximate optimal design solutions and evaluting their values of the objective function. Especially, a method of evaluating design solutions is presented here using both methods of evaluating the robustness under uncertain energy demands and solving optimal design problems by a hierarchical approach. A case study is conducted for a cogeneration system with a practical configuration, and it turns out that the proposed approach enables one to evaluate effective lower bounds for the optimal value of the objective function as compared with those obtained by a conventional approach.}, language = {ja} } @article{KamadaYokoyamaShinanoetal., author = {Kamada, Hiroki and Yokoyama, Ryohei and Shinano, Yuji and Wakui, Tetsuya}, title = {階層的最適化手法の援用による エネルギー供給システムのロバスト最適設計}, series = {エネルギー・資源学会第36回エネルギーシステム・経済・環境コンファレンス講演論文集}, journal = {エネルギー・資源学会第36回エネルギーシステム・経済・環境コンファレンス講演論文集}, pages = {730 -- 735}, abstract = {A robust optimal design method of energy supply systems under uncertain energy demands has been proposed using a mixed- integer linear model for constituent equipment. A robust optimal design problem has been formulated as a three-level min-max- min optimization one by expressing uncertain energy demands by intervals, evaluating the robustness in a performance criterion based on the minimax regret criterion, and considering hierarchical relationships among design variables, uncertain energy demands, and operation variables. Since this problem must be solved by a special algorithm and is too difficult to solve even using a commercial solver, a hierarchical optimization approach has been applied to solve the problem but its application is limited only to small scale toy problems. In this paper, some strategies are introduced into the hierarchical optimization approach to enhance the computation efficiency for the purpose of applying the approach to large scale practical problems. In a case study, the proposed approach is applied to the robust optimal design of a cogeneration system with a complex configuration, and the validity and effectiveness of the method are ascertained.}, language = {ja} } @article{YokoyamaShinanoWakui, author = {Yokoyama, Ryohei and Shinano, Yuji and Wakui, Tetsuya}, title = {時間集約によるエネルギー供給システムの 近似最適設計解の導出および評価 (階層的最適化を援用した近似最適設計)}, series = {第41回エネルギー・資源学会研究発表会講演論文集}, journal = {第41回エネルギー・資源学会研究発表会講演論文集}, pages = {144 -- 148}, abstract = {For the purpose of attaining the highest performance of energy supply systems, it is important to design the systems optimally in consideration of their operational strategies for seasonal and hourly variations in energy demands. An ap- proach to efficiently solve such an optimal design problem with a large number of periods for variations in energy de- mands is to derive an approximate optimal design solution by aggregating periods with a clustering method. However, such an approach does not provide any information on the accuracy for the optimal value of the objective function. The purpose of this paper is to propose a time aggregation approach for deriving suitable aprroximate optimal design solutions and evaluting their values of the objective function accurately. This time aggregation approach is realized by combining a robust optimal design method under uncertain energy demands and a hierarchical approach for solving large scale optimal design problems. A case study is conducted for a cogeneration system with a practical configuration, and it turns out that the proposed approach enables one to evaluate effective upper and lower bounds for the optimal value of the objective function as compared with those obtained by a conventional approach.}, language = {ja} } @article{TakeuchiYokoyamaShinanoetal., author = {Takeuchi, Kotaro and Yokoyama, Ryohei and Shinano, Yuji and Wakui, Tetsuya}, title = {エネルギー供給システムの設計および運用の階層的関係を考慮した最適化 (k-メドイド法に基づく期間クラスタリングの適用)}, series = {日本機械学会関西支部第95期定時総会講演会講演論文集}, journal = {日本機械学会関西支部第95期定時総会講演会講演論文集}, pages = {1 -- 4}, abstract = {To attain the highest performance of energy supply systems, it is necessary to determine design specifications optimally in consideration of operational strategies corresponding to seasonal and hourly variations in energy demands. A hierarchical mixed-integer linear programming method has been proposed to solve such an optimal design problem efficiently. In this paper, a method of reducing model by clustering periods with the k-medoids method is applied to the relaxed optimal design problem at the upper level. Through a case study, it is clarified how the proposed method is effective to enhance the computation efficiency in a large scale optimal design problem.}, language = {ja} } @misc{ShinanoAchterbergBertholdetal., author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Vigerske, Stefan and Winkler, Michael}, title = {制約整数計画ソルバ SCIP の並列化}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-18130}, abstract = {制約整数計画(CIP: Constraint Integer Programming)は,制約プログラミング(CP: Constraint Programming),混合整数計画(MIP: Mixed Integer Programming), 充足可能性問題(SAT: Satisfiability Problems)の研究分野におけるモデリング技術と解法を統合している.その結果,制約整数計画は,広いクラスの最適化問題を扱うことができる.SCIP (Solving Constraint Integer Programs)は,CIPを解くソルバとして実装され,Zuse Institute Berlin (ZIB)の研究者を中心として継続的に拡張が続けられている.本論文では,著者らによって開発されたSCIP に対する2種類の並列化拡張を紹介する. 一つは,複数計算ノード間で大規模に並列動作するParaSCIP である. もう一つは,複数コアと共有メモリを持つ1台の計算機上で(スレッド)並列で動作するFiberSCIP である. ParaSCIP は,HLRN IIスーパーコンピュータ上で, 一つのインスタンスを解くために最大7,168 コアを利用した動作実績がある.また,統計数理研究所のFujitsu PRIMERGY RX200S5上でも,最大512コアを利用した動作実績がある.統計数理研究所のFujitsu PRIMERGY RX200S5上 では,これまでに最適解が得られていなかったMIPLIB2010のインスタンスであるdg012142に最適解を与えた.}, language = {ja} } @article{ShinanoAchterbergBertholdetal., author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Vigerske, Stefan and Winkler, Michael}, title = {制約整数計画ソルバ SCIP の並列化}, series = {統計数理}, volume = {61}, journal = {統計数理}, number = {1}, pages = {47 -- 78}, abstract = {制約整数計画(CIP: Constraint Integer Programs)は,制約プログラミング(CP: Constraint Programming),混合整数計画(MIP: Mixed Integer Programming),充足可能性問題(SAT: Satisfability Problem)の研究分野におけるモデリング技術と解法を統合している.その結果,制約整数計画は,広いクラスの最適化問題を扱うことができる.SCIP(Solving Constraint Integer Programs)は,CIP を解くソルバとして実装され,Zuse Institute Berlin(ZIB)の研究者を中心として継続的に拡張が続けられている.本論文では,著者らによって開発された SCIP に対する2 種類の並列化拡張を紹介する.一つは,複数計算ノード間で大規模に並列動作する ParaSCIPである.もう一つは,複数コアと共有メモリを持つ 1 台の計算機上で(スレッド)並列で動作する FiberSCIP である.ParaSCIP は,HLRN II スーパーコンピュータ上で,一つのインスタンスを解くために最大 7,168 コアを利用した動作実績がある.また,統計数理研究所の Fujitsu PRIMERGY RX200S5 上でも,最大 512 コアを利用した動作実績がある.統計数理研究所のFujitsu PRIMERGY RX200S5 上では,これまでに最適解が得られていなかった MIPLIB2010のインスタンスである dg012142 に最適解を与えた.}, language = {ja} } @article{YokoyamaShinanoWakui, author = {Yokoyama, Ryohei and Shinano, Yuji and Wakui, Tetsuya}, title = {An effective approach for deriving and evaluating approximate optimal design solutions of energy supply systems by time series aggregation}, series = {Frontiers in Energy Research}, volume = {11}, journal = {Frontiers in Energy Research}, doi = {10.3389/fenrg.2023.1128681}, pages = {1 -- 14}, abstract = {It is important to design multi-energy supply systems optimally in consideration of their operations for variations in energy demands. An approach for efficiently solving such an optimal design problem with a large number of periods for variations in energy demands is to derive an approximate optimal design solution by time series aggregation. However, such an approach does not provide any information on the accuracy for the optimal value of the objective function. In this paper, an effective approach for time series aggregation is proposed to derive an approximate optimal design solution and evaluate a proper gap between the upper and lower bounds for the optimal value of the objective function based on a mixed-integer linear model. In accordance with aggregation, energy demands are relaxed to uncertain parameters and the problem for deriving an approximate optimal design solution and evaluating it is transformed to a three-level optimization problem, and it is solved by applying both the robust and hierarchical optimization methods. A case study is conducted on a cogeneration system with a practical configuration, and it turns out that the proposed approach enables one to derive much smaller gaps as compared with those obtained by a conventional approach.}, language = {en} } @misc{HosodaMaherShinanoetal., author = {Hosoda, Junko and Maher, Stephen J. and Shinano, Yuji and Villumsen, Jonas Christoffer}, title = {Location, transshipment and routing: An adaptive transportation network integrating long-haul and local vehicle routing}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-83438}, abstract = {The routing of commodities is a tactical problem in supply chain management that aims to synchronise transportation services connecting a network of warehouses and consolidation locations. This paper considers the routing of commodities in a transportation network that is flexible in response to demand through changes to regional warehouse clustering and the designation of consolidation locations. Traditionally, warehouse clustering and consolidation locations are determined as part of strategic planning that is performed months to years in advance of operations---limiting the flexibility in transportation networks to respond to changes in demand. A mathematical programming-based algorithmic framework is proposed to integrate the strategic decisions of location planning with tactical decisions of vehicle routing and synchronisation. A multi-armed bandit problem is developed to explore warehouse clustering decisions and exploit those that lead to small transportation costs. An extensive computational study will show that the proposed algorithmic framework effectively integrates strategic and tactical planning decisions to reduce the overall transportation costs.}, language = {en} } @inproceedings{RehfeldtShinanoKoch, author = {Rehfeldt, Daniel and Shinano, Yuji and Koch, Thorsten}, title = {SCIP-Jack: An exact high performance solver for Steiner tree problems in graphs and related problems}, series = {Modeling, Simulation and Optimization of Complex Processes HPSC 2018}, booktitle = {Modeling, Simulation and Optimization of Complex Processes HPSC 2018}, publisher = {Springer}, doi = {10.1007/978-3-030-55240-4_10}, abstract = {The Steiner tree problem in graphs is one of the classic combinatorial optimization problems. Furthermore, many related problems, such as the rectilinear Steiner tree problem or the maximum-weight connected subgraph problem, have been described in the literature—with a wide range of practical applications. To embrace this wealth of problem classes, the solver SCIP-JACK has been developed as an exact framework for classic Steiner tree and 11 related problems. Moreover, the solver comes with both shared- and distributed memory extensions by means of the UG framework. Besides its versatility, SCIP-JACK is highly competitive for most of the 12 problem classes it can solve, as for instance demonstrated by its top ranking in the recent PACE 2018 Challenge. This article describes the current state of SCIP-JACK and provides up-to-date computational results, including several instances that can now be solved for the first time to optimality.}, language = {en} } @misc{TateiwaShinanoYasudaetal., author = {Tateiwa, Nariaki and Shinano, Yuji and Yasuda, Masaya and Kaji, Shizuo and Yamamura, Keiichiro and Fujisawa, Katsuki}, title = {Massively parallel sharing lattice basis reduction}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-85209}, abstract = {For cryptanalysis in lattice-based schemes, the performance evaluation of lattice basis reduction using high-performance computers is becoming increasingly important for the determination of the security level. We propose a distributed and asynchronous parallel reduction algorithm based on randomization and DeepBKZ, which is an improved variant of the block Korkine-Zolotarev (BKZ) reduction algorithm. Randomized copies of a lattice basis are distributed to up to 103,680 cores and independently reduced in parallel, while some basis vectors are shared asynchronously among all processes via MPI. There is a trade-off between randomization and information sharing; if a substantial amount of information is shared, all processes will work on the same problem, thereby diminishing the benefit of parallelization. To monitor this balance between randomness and sharing, we propose a metric to quantify the variety of lattice bases. We empirically find an optimal parameter of sharing for high-dimensional lattices. We demonstrate the efficacy of our proposed parallel algorithm and implementation with respect to both performance and scalability through our experiments.}, language = {en} } @article{RehfeldtKochShinano, author = {Rehfeldt, Daniel and Koch, Thorsten and Shinano, Yuji}, title = {Faster exact solution of sparse MaxCut and QUBO problems}, series = {Mathematical Programming Computation}, volume = {15}, journal = {Mathematical Programming Computation}, doi = {10.1007/s12532-023-00236-6}, pages = {445 -- 470}, abstract = {The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems—by using mathematical programming techniques. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse maximum-cut and quadratic unconstrained binary optimization instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.}, language = {en} } @article{TateiwaShinanoYasudaetal., author = {Tateiwa, Nariaki and Shinano, Yuji and Yasuda, Masaya and Kaji, Shizuo and Yamamura, Keiichiro and Fujisawa, Katsuki}, title = {Development and analysis of massive parallelization of a lattice basis reduction algorithm}, series = {Japan Journal of Industrial and Applied Mathematics}, volume = {40}, journal = {Japan Journal of Industrial and Applied Mathematics}, number = {1}, doi = {10.1007/s13160-023-00580-z}, abstract = {The security of lattice-based cryptography relies on the hardness of solving lattice problems. Lattice basis reduction is a strong tool for solving lattice problems, and the block Korkine-Zolotarev (BKZ) reduction algorithm is the de facto standard in cryptanalysis. We propose a parallel algorithm of BKZ-type reduction based on randomization. Randomized copies of an input lattice basis are independently reduced in parallel, while several basis vectors are shared asynchronously among all processes. There is a trade-off between randomization and information sharing; if a substantial amount of information is shared, all processes might work on the same problem, which diminishes the benefit of parallelization. To monitor the balance between randomness and sharing, we propose a new metric to quantify the variety of lattice bases, and we empirically find an optimal parameter of sharing for high-dimensional lattices. We also demonstrate the effectiveness of our parallel algorithm and metric through experiments from multiple perspectives.}, language = {en} } @inproceedings{TateiwaShinanoYamamuraetal., author = {Tateiwa, Nariaki and Shinano, Yuji and Yamamura, Keiichiro and Yoshida, Akihiro and Kaji, Shizuo and Yasuda, Masaya and Fujisawa, Katsuki}, title = {CMAP-LAP: Configurable Massively Parallel Solver for Lattice Problems}, series = {HiPC 2021 proceedings}, booktitle = {HiPC 2021 proceedings}, abstract = {Lattice problems are a class of optimization problems that are notably hard. There are no classical or quantum algorithms known to solve these problems efficiently. Their hardness has made lattices a major cryptographic primitive for post-quantum cryptography. Several different approaches have been used for lattice problems with different computational profiles; some suffer from super-exponential time, and others require exponential space. This motivated us to develop a novel lattice problem solver, CMAP-LAP, based on the clever coordination of different algorithms that run massively in parallel. With our flexible framework, heterogeneous modules run asynchronously in parallel on a large-scale distributed system while exchanging information, which drastically boosts the overall performance. We also implement full checkpoint-and-restart functionality, which is vital to high-dimensional lattice problems. Through numerical experiments with up to 103,680 cores, we evaluated the performance and stability of our system and demonstrated its high capability for future massive-scale experiments.}, language = {en} } @misc{FujisawaShinanoWaki, author = {Fujisawa, Katsuki and Shinano, Yuji and Waki, Hayato}, title = {Optimization in the Real World}, series = {Mathematics for Industry (MFI)}, 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}, language = {en} } @misc{FujiiKimKojimaetal., author = {Fujii, Koichi and Kim, Sunyoung and Kojima, Masakazu and Mittelmann, Hans D. and Shinano, Yuji}, title = {An Exceptionally Difficult Binary Quadratic Optimization Problem with Symmetry: a Challenge for The Largest Unsolved QAP Instance Tai256c}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-93072}, abstract = {Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB. It is known that QAP tai256c 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. As the BQOP is much simpler than the original QAP, the conversion increases the possibility to solve the QAP. Solving exactly the BQOP, however, is still very difficult. Indeed, a 1.48\% gap remains between the best known upper bound (UB) and lower bound (LB) of the unknown optimal value. This paper shows that the BQOP admits a nontrivial symmetry, a property that makes the BQOP very hard to solve. The symmetry induces equivalent subproblems in branch and bound (BB) methods. To effectively improve the LB, we propose an efficient BB method that incorporates a doubly nonnegative relaxation, the standard orbit branching and a technique to prune equivalent subproblems. With this BB method, a new LB with 1.25\% gap is successfully obtained, and computing an LB with 1.0\% gap is shown to be still quite difficult.}, language = {en} } @misc{MaherFischerGallyetal., author = {Maher, Stephen J. and Fischer, Tobias and Gally, Tristan and Gamrath, Gerald and Gleixner, Ambros and Gottwald, Robert Lion and Hendel, Gregor and Koch, Thorsten and L{\"u}bbecke, Marco and Miltenberger, Matthias and M{\"u}ller, Benjamin and Pfetsch, Marc and Puchert, Christian and Rehfeldt, Daniel and Schenker, Sebastian and Schwarz, Robert and Serrano, Felipe and Shinano, Yuji and Weninger, Dieter and Witt, Jonas T. and Witzig, Jakob}, title = {The SCIP Optimization Suite 4.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-62170}, abstract = {The SCIP Optimization Suite is a powerful collection of optimization software that consists of the branch-cut-and-price framework and mixed-integer programming solver SCIP, the linear programming solver SoPlex, the modeling language Zimpl, the parallelization framework UG, and the generic branch-cut-and-price solver GCG. Additionally, it features the extensions SCIP-Jack for solving Steiner tree problems, PolySCIP for solving multi-objective problems, and SCIP-SDP for solving mixed-integer semidefinite programs. The SCIP Optimization Suite has been continuously developed and has now reached version 4.0. The goal of this report is to present the recent changes to the collection. We not only describe the theoretical basis, but focus on implementation aspects and their computational consequences.}, language = {en} } @misc{GamrathFischerGallyetal., author = {Gamrath, Gerald and Fischer, Tobias and Gally, Tristan and Gleixner, Ambros and Hendel, Gregor and Koch, Thorsten and Maher, Stephen J. and Miltenberger, Matthias and M{\"u}ller, Benjamin and Pfetsch, Marc and Puchert, Christian and Rehfeldt, Daniel and Schenker, Sebastian and Schwarz, Robert and Serrano, Felipe and Shinano, Yuji and Vigerske, Stefan and Weninger, Dieter and Winkler, Michael and Witt, Jonas T. and Witzig, Jakob}, title = {The SCIP Optimization Suite 3.2}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-57675}, abstract = {The SCIP Optimization Suite is a software toolbox for generating and solving various classes of mathematical optimization problems. Its major components are the modeling language ZIMPL, the linear programming solver SoPlex, the constraint integer programming framework and mixed-integer linear and nonlinear programming solver SCIP, the UG framework for parallelization of branch-and-bound-based solvers, and the generic branch-cut-and-price solver GCG. It has been used in many applications from both academia and industry and is one of the leading non-commercial solvers. This paper highlights the new features of version 3.2 of the SCIP Optimization Suite. Version 3.2 was released in July 2015. This release comes with new presolving steps, primal heuristics, and branching rules within SCIP. In addition, version 3.2 includes a reoptimization feature and improved handling of quadratic constraints and special ordered sets. SoPlex can now solve LPs exactly over the rational number and performance improvements have been achieved by exploiting sparsity in more situations. UG has been tested successfully on 80,000 cores. A major new feature of UG is the functionality to parallelize a customized SCIP solver. GCG has been enhanced with a new separator, new primal heuristics, and improved column management. Finally, new and improved extensions of SCIP are presented, namely solvers for multi-criteria optimization, Steiner tree problems, and mixed-integer semidefinite programs.}, language = {en} } @misc{BestuzhevaBesanconChenetal., author = {Bestuzheva, Ksenia and Besan{\c{c}}on, Mathieu and Chen, Wei-Kun and Chmiela, Antonia and Donkiewicz, Tim and van Doornmalen, Jasper and Eifler, Leon and Gaul, Oliver and Gamrath, Gerald and Gleixner, Ambros and Gottwald, Leona and Graczyk, Christoph and Halbig, Katrin and Hoen, Alexander and Hojny, Christopher and van der Hulst, Rolf and Koch, Thorsten and L{\"u}bbecke, Marco and Maher, Stephen J. and Matter, Frederic and M{\"u}hmer, Erik and M{\"u}ller, Benjamin and Pfetsch, Marc E. and Rehfeldt, Daniel and Schlein, Steffan and Schl{\"o}sser, Franziska and Serrano, Felipe and Shinano, Yuji and Sofranac, Boro and Turner, Mark and Vigerske, Stefan and Wegscheider, Fabian and Wellner, Philipp and Weninger, Dieter and Witzig, Jakob}, title = {The SCIP Optimization Suite 8.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-85309}, 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 8.0 of the SCIP Optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin type for cut selection, and a complete rework of the way nonlinear constraints are handled. Additionally, SCIP 8.0 now supports interfaces for Julia as well as Matlab. Further, UG now includes a unified framework to parallelize all solvers, a utility to analyze computational experiments has been added to GCG, dual solutions can be postsolved by PaPILO, new heuristics and presolving methods were added to SCIP-SDP, and additional problem classes and major performance improvements are available in SCIP-Jack.}, language = {en} } @misc{GamrathAndersonBestuzhevaetal., author = {Gamrath, Gerald and Anderson, Daniel and Bestuzheva, Ksenia and Chen, Wei-Kun and Eifler, Leon and Gasse, Maxime and Gemander, Patrick and Gleixner, Ambros and Gottwald, Leona and Halbig, Katrin and Hendel, Gregor and Hojny, Christopher and Koch, Thorsten and Le Bodic, Pierre and Maher, Stephen J. and Matter, Frederic and Miltenberger, Matthias and M{\"u}hmer, Erik and M{\"u}ller, Benjamin and Pfetsch, Marc and Schl{\"o}sser, Franziska and Serrano, Felipe and Shinano, Yuji and Tawfik, Christine and Vigerske, Stefan and Wegscheider, Fabian and Weninger, Dieter and Witzig, Jakob}, title = {The SCIP Optimization Suite 7.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-78023}, abstract = {The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming frame- work SCIP. This paper discusses enhancements and extensions contained in version 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies mixed-integer linear op- timization problems and can be used stand-alone or integrated into SCIP via a presolver plugin. SCIP 7.0 provides additional support for decomposition algorithms. Besides im- provements in the Benders' decomposition solver of SCIP, user-defined decomposition structures can be read, which are used by the automated Benders' decomposition solver and two primal heuristics. Additionally, SCIP 7.0 comes with a tree size estimation that is used to predict the completion of the overall solving process and potentially trigger restarts. Moreover, substantial performance improvements of the MIP core were achieved by new developments in presolving, primal heuristics, branching rules, conflict analysis, and symmetry handling. Last, not least, the report presents updates to other components and extensions of the SCIP Optimization Suite, in particular, the LP solver SoPlex and the mixed-integer semidefinite programming solver SCIP-SDP.}, language = {en} } @misc{GleixnerEiflerGallyetal., author = {Gleixner, Ambros and Eifler, Leon and Gally, Tristan and Gamrath, Gerald and Gemander, Patrick and Gottwald, Robert Lion and Hendel, Gregor and Hojny, Christopher and Koch, Thorsten and Miltenberger, Matthias and M{\"u}ller, Benjamin and Pfetsch, Marc and Puchert, Christian and Rehfeldt, Daniel and Schl{\"o}sser, Franziska and Serrano, Felipe and Shinano, Yuji and Viernickel, Jan Merlin and Vigerske, Stefan and Weninger, Dieter and Witt, Jonas T. and Witzig, Jakob}, title = {The SCIP Optimization Suite 5.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-66297}, abstract = {This article describes new features and enhanced algorithms made available in version 5.0 of the SCIP Optimization Suite. In its central component, the constraint integer programming solver SCIP, remarkable performance improvements have been achieved for solving mixed-integer linear and nonlinear programs. On MIPs, SCIP 5.0 is about 41 \% faster than SCIP 4.0 and over twice as fast on instances that take at least 100 seconds to solve. For MINLP, SCIP 5.0 is about 17 \% faster overall and 23 \% faster on instances that take at least 100 seconds to solve. This boost is due to algorithmic advances in several parts of the solver such as cutting plane generation and management, a new adaptive coordination of large neighborhood search heuristics, symmetry handling, and strengthened McCormick relaxations for bilinear terms in MINLPs. Besides discussing the theoretical background and the implementational aspects of these developments, the report describes recent additions for the other software packages connected to SCIP, in particular for the LP solver SoPlex, the Steiner tree solver SCIP-Jack, the MISDP solver SCIP-SDP, and the parallelization framework UG.}, language = {en} } @misc{GleixnerBastubbeEifleretal., 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}, 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} } @inproceedings{KochRehfeldtShinano, author = {Koch, Thorsten and Rehfeldt, Daniel and Shinano, Yuji}, title = {On the state of QUBO solving}, series = {Operations Research Proceedings 2023}, booktitle = {Operations Research Proceedings 2023}, abstract = {It is regularly claimed that quantum computers will bring breakthrough progress in solving challenging combinatorial optimization problems relevant in practice. In particular, Quadratic Unconstrained Binary Optimization (QUBO) problems are said to be the model of choice for use in (adiabatic) quantum systems during the noisy intermediate- scale quantum (NISQ) era. Even the first commercial quantum-based systems are advertised to solve such problems. Theoretically, any Integer Program can be converted into a QUBO. In practice, however, there are some caveats, as even for problems that can be nicely modeled as a QUBO, this might not be the most effective way to solve them. We review the state of QUBO solving on digital and quantum computers and provide insights regarding current benchmark instances and modeling.}, language = {en} } @article{BestuzhevaBesanconChenetal., author = {Bestuzheva, Ksenia and Besan{\c{c}}on, Mathieu and Chen, Wei-Kun and Chmiela, Antonia and Donkiewicz, Tim and Doornmalen, Jasper and Eifler, Leon and Gaul, Oliver and Gamrath, Gerald and Gleixner, Ambros and Gottwald, Leona and Graczyk, Christoph and Halbig, Katrin and Hoen, Alexander and Hojny, Christopher and Hulst, Rolf and Koch, Thorsten and L{\"u}bbecke, Marco and Maher, Stephen J. and Matter, Frederic and M{\"u}hmer, Erik and M{\"u}ller, Benjamin and Pfetsch, Marc and Rehfeldt, Daniel and Schlein, Steffan and Schl{\"o}sser, Franziska and Serrano, Felipe and Shinano, Yuji and Sofranac, Boro and Turner, Mark and Vigerske, Stefan and Wegscheider, Fabian and Wellner, Philipp and Weninger, Dieter and Witzig, Jakob}, title = {Enabling research through the SCIP optimization suite 8.0}, series = {ACM Transactions on Mathematical Software}, volume = {49}, journal = {ACM Transactions on Mathematical Software}, number = {2}, doi = {10.1145/3585516}, pages = {1 -- 21}, abstract = {The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. The focus of this article is on the role of the SCIP Optimization Suite in supporting research. SCIP's main design principles are discussed, followed by a presentation of the latest performance improvements and developments in version 8.0, which serve both as examples of SCIP's application as a research tool and as a platform for further developments. Furthermore, this article gives an overview of interfaces to other programming and modeling languages, new features that expand the possibilities for user interaction with the framework, and the latest developments in several extensions built upon SCIP.}, language = {en} } @misc{BolusaniBesanconBestuzhevaetal., author = {Bolusani, Suresh and Besan{\c{c}}on, Mathieu and Bestuzheva, Ksenia and Chmiela, Antonia and Dion{\´i}sio, Jo{\~a}o and Donkiewicz, Tim and van Doornmalen, Jasper and Eifler, Leon and Ghannam, Mohammed and Gleixner, Ambros and Graczyk, Christoph and Halbig, Katrin and Hedtke, Ivo and Hoen, Alexander and Hojny, Christopher and van der Hulst, Rolf and Kamp, Dominik and Koch, Thorsten and Kofler, Kevin and Lentz, Jurgen and Manns, Julian and Mexi, Gioni and M{\"u}hmer, Erik and E. Pfetsch, Marc and Schl{\"o}sser, Franziska and Serrano, Felipe and Shinano, Yuji and Turner, Mark and Vigerske, Stefan and Weninger, Dieter and Xu, Liding}, title = {The SCIP Optimization Suite 9.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-95528}, abstract = {The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming framework SCIP. This report discusses the enhancements and extensions included in the SCIP Optimization Suite 9.0. The updates in SCIP 9.0 include improved symmetry handling, additions and improvements of nonlinear handlers and primal heuristics, a new cut generator and two new cut selection schemes, a new branching rule, a new LP interface, and several bug fixes. The SCIP Optimization Suite 9.0 also features new Rust and C++ interfaces for SCIP, new Python interface for SoPlex, along with enhancements to existing interfaces. The SCIP Optimization Suite 9.0 also includes new and improved features in the LP solver SoPlex, the presolving library PaPILO, the parallel framework UG, the decomposition framework GCG, and the SCIP extension SCIP-SDP. These additions and enhancements have resulted in an overall performance improvement of SCIP in terms of solving time, number of nodes in the branch-and-bound tree, as well as the reliability of the solver.}, language = {en} }