@article{ShinanoAchterbergBertholdetal.2013, author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Vigerske, Stefan and Winkler, Michael}, title = {制約整数計画ソルバ SCIP の並列化}, volume = {61}, journal = {統計数理}, number = {1}, pages = {47 -- 78}, year = {2013}, 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{KochBernalNeiraChenetal.2025, author = {Koch, Thorsten and Bernal Neira, David E. and Chen, Ying and Cortiana, Giorgio and Egger, Daniel J. and Heese, Raoul and Hegade, Narendra N. and Gomez Cadavid, Alejandro and Huang, Rhea and Itoko, Toshinari and Kleinert, Thomas and Maciel Xavier, Pedro and Mohseni, Naeimeh and Montanez-Barrera, Jhon A. and Nakano, Koji and Nannicini, Giacomo and O'Meara, Corey and Pauckert, Justin and Proissl, Manuel and Ramesh, Anurag and Schicker, Maximilian and Shimada, Noriaki and Takeori, Mitsuharu and Valls, Victor and Van Bulck, David and Woerner, Stefan and Zoufal, Christa}, title = {Quantum Optimization Benchmark Library -- The Intractable Decathlon}, arxiv = {http://arxiv.org/abs/2504.03832}, year = {2025}, abstract = {Through recent progress in hardware development, quantum computers have advanced to the point where benchmarking of (heuristic) quantum algorithms at scale is within reach. Particularly in combinatorial optimization -- where most algorithms are heuristics -- it is key to empirically analyze their performance on hardware and track progress towards quantum advantage. To this extent, we present ten optimization problem classes that are difficult for existing classical algorithms and can (mostly) be linked to practically-relevant applications, with the goal to enable systematic, fair, and comparable benchmarks for quantum optimization methods. Further, we introduce the Quantum Optimization Benchmark Library (QOBLIB) where the problem instances and solution track records can be found. The individual properties of the problem classes vary in terms of objective and variable type, coefficient ranges, and density. Crucially, they all become challenging for established classical methods already at system sizes ranging from less than 100 to, at most, an order of 100,000 decision variables, allowing to approach them with today's quantum computers. We reference the results from state-of-the-art solvers for instances from all problem classes and demonstrate exemplary baseline results obtained with quantum solvers for selected problems. The baseline results illustrate a standardized form to present benchmarking solutions, which has been designed to ensure comparability of the used methods, reproducibility of the respective results, and trackability of algorithmic and hardware improvements over time. We encourage the optimization community to explore the performance of available classical or quantum algorithms and hardware platforms with the benchmarking problem instances presented in this work toward demonstrating quantum advantage in optimization.}, language = {en} } @article{AbbasAmbainisAugustinoetal.2024, author = {Abbas, Amira and Ambainis, Andris and Augustino, Brandon and B{\"a}rtschi, Andreas and Buhrman, Harry and Coffrin, Carleton and Cortiana, Giorgio and Dunjko, Vedran and Egger, Daniel J. and Elmegreen, Bruce G. and Franco, Nicola and Fratini, Filippo and Fuller, Bryce and Gacon, Julien and Gonciulea, Constantin and Gribling, Sander and Gupta, Swati and Hadfield, Stuart and Heese, Raoul and Kircher, Gerhard and Kleinert, Thomas and Koch, Thorsten and Korpas, Georgios and Lenk, Steve and Marecek, Jakub and Markov, Vanio and Mazzola, Guglielmo and Mensa, Stefano and Mohseni, Naeimeh and Nannicini, Giacomo and O'Meara, Corey and Tapia, Elena Pe{\~n}a and Pokutta, Sebastian and Proissl, Manuel and Rebentrost, Patrick and Sahin, Emre and Symons, Benjamin C. B. and Tornow, Sabine and Valls, V{\´i}ctor and Woerner, Stefan and Wolf-Bauwens, Mira L. and Yard, Jon and Yarkoni, Sheir and Zechiel, Dirk and Zhuk, Sergiy and Zoufal, Christa}, title = {Challenges and opportunities in quantum optimization}, volume = {6}, journal = {Nature Reviews Physics}, publisher = {Springer Science and Business Media LLC}, issn = {2522-5820}, arxiv = {http://arxiv.org/abs/2312.02279}, doi = {10.1038/s42254-024-00770-9}, pages = {718 -- 735}, year = {2024}, language = {en} } @misc{CharoussetBrignolvanAckooijOudjaneetal.2021, author = {Charousset-Brignol, Sandrine and van Ackooij, Wim and Oudjane, Nadia and Daniel, Dominique and Noceir, Slimane and Haus, Utz-Uwe and Lazzaro, Alfio and Frangioni, Antonio and Lobato, Rafael and Ghezelsoflu, Ali and Iardella, Niccol{\`o} and Galli, Laura and Gorgone, Enrico and dell'Amico, Mauro and Giannelos, Spyros and Moreira, Alex and Strbac, Goran and Borozan, Stefan and Falugi, Paula and Pudjianto, Danny and Wyrwoll, Lothar and Schmitt, Carlo and Franken, Marco and Beulertz, Daniel and Schwaeppe, Henrik and Most, Dieter and Y{\"u}ksel-Erg{\"u}n, Inci and Zittel, Janina and Koch, Thorsten}, title = {Synergistic approach of multi-energy models for a European optimal energy system management tool}, volume = {9}, journal = {The Project Repository Journal}, pages = {113 -- 116}, year = {2021}, language = {en} } @misc{BestuzhevaBesanconChenetal.2021, 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}, year = {2021}, 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{BolusaniBesanconBestuzhevaetal.2024, 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}, year = {2024}, 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} } @article{KotilPelofskeRiedmuelleretal.2025, author = {Kotil, Ayse and Pelofske, Elijah and Riedm{\"u}ller, Stephanie and Egger, Daniel J. and Eidenbenz, Stephan and Koch, Thorsten and Woerner, Stefan}, title = {Quantum Approximate Multi-Objective Optimization}, journal = {Nature Computational Science}, arxiv = {http://arxiv.org/abs/2503.22797}, doi = {10.1038/s43588-025-00873-y}, pages = {1168 -- 1177}, year = {2025}, abstract = {The goal of multi-objective optimization is to understand optimal trade-offs between competing objective functions by finding the Pareto front, i.e., the set of all Pareto optimal solutions, where no objective can be improved without degrading another one. Multi-objective optimization can be challenging classically, even if the corresponding single-objective optimization problems are efficiently solvable. Thus, multi-objective optimization represents a compelling problem class to analyze with quantum computers. In this work, we use low-depth Quantum Approximate Optimization Algorithm to approximate the optimal Pareto front of certain multi-objective weighted maximum cut problems. We demonstrate its performance on an IBM Quantum computer, as well as with Matrix Product State numerical simulation, and show its potential to outperform classical approaches.}, language = {en} }