TY - JOUR A1 - Shinano, Yuji A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Vigerske, Stefan A1 - Winkler, Michael T1 - 制約整数計画ソルバ SCIP の並列化 JF - 統計数理 N2 - 制約整数計画(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 に最適解を与えた. N2 - The paradigm of constraint integer programming (CIP) combines modeling and solving techniques from the fields of constraint programming (CP), mixed-integer programming (MIP) and satisfability problem (SAT). This paradigm allows us to address a wide range of optimization problems. SCIP is an implementation of the idea of CIP and is now being continuously extended by a group of researchers centered at Zuse Institute Berlin (ZIB). This paper introduces two parallel extensions of SCIP. One is ParaSCIP, which is intended to run on a large scale distributed memory computing environment, and the other is FiberSCIP, intended to run on a shared memory computing environment. ParaSCIP has been run successfully on the HLRN II supercomputer utilizing up to 7,168 cores to solve a single difficult MIP. It has also been tested on an ISM supercomputer (Fujitsu PRIMERGY RX200S5 using up to 512 cores). The previously unsolved instance dg012142 from MIPLIB2010 was solved by using the ISM supercomputer. Y1 - 2013 UR - https://www.ism.ac.jp/editsec/toukei/pdf/61-1-047.pdf VL - 61 IS - 1 SP - 47 EP - 78 ER - TY - JOUR A1 - Koch, Thorsten A1 - Bernal Neira, David E. A1 - Chen, Ying A1 - Cortiana, Giorgio A1 - Egger, Daniel J. A1 - Heese, Raoul A1 - Hegade, Narendra N. A1 - Gomez Cadavid, Alejandro A1 - Huang, Rhea A1 - Itoko, Toshinari A1 - Kleinert, Thomas A1 - Maciel Xavier, Pedro A1 - Mohseni, Naeimeh A1 - Montanez-Barrera, Jhon A. A1 - Nakano, Koji A1 - Nannicini, Giacomo A1 - O'Meara, Corey A1 - Pauckert, Justin A1 - Proissl, Manuel A1 - Ramesh, Anurag A1 - Schicker, Maximilian A1 - Shimada, Noriaki A1 - Takeori, Mitsuharu A1 - Valls, Victor A1 - Van Bulck, David A1 - Woerner, Stefan A1 - Zoufal, Christa T1 - Quantum Optimization Benchmark Library -- The Intractable Decathlon N2 - 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. Y1 - 2025 ER - TY - JOUR A1 - Abbas, Amira A1 - Ambainis, Andris A1 - Augustino, Brandon A1 - Bärtschi, Andreas A1 - Buhrman, Harry A1 - Coffrin, Carleton A1 - Cortiana, Giorgio A1 - Dunjko, Vedran A1 - Egger, Daniel J. A1 - Elmegreen, Bruce G. A1 - Franco, Nicola A1 - Fratini, Filippo A1 - Fuller, Bryce A1 - Gacon, Julien A1 - Gonciulea, Constantin A1 - Gribling, Sander A1 - Gupta, Swati A1 - Hadfield, Stuart A1 - Heese, Raoul A1 - Kircher, Gerhard A1 - Kleinert, Thomas A1 - Koch, Thorsten A1 - Korpas, Georgios A1 - Lenk, Steve A1 - Marecek, Jakub A1 - Markov, Vanio A1 - Mazzola, Guglielmo A1 - Mensa, Stefano A1 - Mohseni, Naeimeh A1 - Nannicini, Giacomo A1 - O’Meara, Corey A1 - Tapia, Elena Peña A1 - Pokutta, Sebastian A1 - Proissl, Manuel A1 - Rebentrost, Patrick A1 - Sahin, Emre A1 - Symons, Benjamin C. B. A1 - Tornow, Sabine A1 - Valls, Víctor A1 - Woerner, Stefan A1 - Wolf-Bauwens, Mira L. A1 - Yard, Jon A1 - Yarkoni, Sheir A1 - Zechiel, Dirk A1 - Zhuk, Sergiy A1 - Zoufal, Christa T1 - Challenges and opportunities in quantum optimization JF - Nature Reviews Physics Y1 - 2024 U6 - https://doi.org/10.1038/s42254-024-00770-9 SN - 2522-5820 VL - 6 SP - 718 EP - 735 PB - Springer Science and Business Media LLC ER - TY - GEN A1 - Charousset-Brignol, Sandrine A1 - van Ackooij, Wim A1 - Oudjane, Nadia A1 - Daniel, Dominique A1 - Noceir, Slimane A1 - Haus, Utz-Uwe A1 - Lazzaro, Alfio A1 - Frangioni, Antonio A1 - Lobato, Rafael A1 - Ghezelsoflu, Ali A1 - Iardella, Niccolò A1 - Galli, Laura A1 - Gorgone, Enrico A1 - dell’Amico, Mauro A1 - Giannelos, Spyros A1 - Moreira, Alex A1 - Strbac, Goran A1 - Borozan, Stefan A1 - Falugi, Paula A1 - Pudjianto, Danny A1 - Wyrwoll, Lothar A1 - Schmitt, Carlo A1 - Franken, Marco A1 - Beulertz, Daniel A1 - Schwaeppe, Henrik A1 - Most, Dieter A1 - Yüksel-Ergün, Inci A1 - Zittel, Janina A1 - Koch, Thorsten T1 - Synergistic approach of multi-energy models for a European optimal energy system management tool T2 - The Project Repository Journal Y1 - 2021 VL - 9 SP - 113 EP - 116 ER - TY - GEN A1 - Bestuzheva, Ksenia A1 - Besançon, Mathieu A1 - Chen, Wei-Kun A1 - Chmiela, Antonia A1 - Donkiewicz, Tim A1 - van Doornmalen, Jasper A1 - Eifler, Leon A1 - Gaul, Oliver A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Gottwald, Leona A1 - Graczyk, Christoph A1 - Halbig, Katrin A1 - Hoen, Alexander A1 - Hojny, Christopher A1 - van der Hulst, Rolf A1 - Koch, Thorsten A1 - Lübbecke, Marco A1 - Maher, Stephen J. A1 - Matter, Frederic A1 - Mühmer, Erik A1 - Müller, Benjamin A1 - Pfetsch, Marc E. A1 - Rehfeldt, Daniel A1 - Schlein, Steffan A1 - Schlösser, Franziska A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Sofranac, Boro A1 - Turner, Mark A1 - Vigerske, Stefan A1 - Wegscheider, Fabian A1 - Wellner, Philipp A1 - Weninger, Dieter A1 - Witzig, Jakob T1 - The SCIP Optimization Suite 8.0 N2 - 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. T3 - ZIB-Report - 21-41 KW - Constraint integer programming KW - Linear programming KW - Mixed-integer linear programming KW - Mixed-integer nonlinear programming KW - Optimization solver KW - Branch-and-cut KW - Branch-and-price KW - Column generation KW - Parallelization KW - Mixed-integer semidefinite programming Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-85309 SN - 1438-0064 ER - TY - GEN A1 - Bolusani, Suresh A1 - Besançon, Mathieu A1 - Bestuzheva, Ksenia A1 - Chmiela, Antonia A1 - Dionísio, João A1 - Donkiewicz, Tim A1 - van Doornmalen, Jasper A1 - Eifler, Leon A1 - Ghannam, Mohammed A1 - Gleixner, Ambros A1 - Graczyk, Christoph A1 - Halbig, Katrin A1 - Hedtke, Ivo A1 - Hoen, Alexander A1 - Hojny, Christopher A1 - van der Hulst, Rolf A1 - Kamp, Dominik A1 - Koch, Thorsten A1 - Kofler, Kevin A1 - Lentz, Jurgen A1 - Manns, Julian A1 - Mexi, Gioni A1 - Mühmer, Erik A1 - E. Pfetsch, Marc A1 - Schlösser, Franziska A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Turner, Mark A1 - Vigerske, Stefan A1 - Weninger, Dieter A1 - Xu, Liding T1 - The SCIP Optimization Suite 9.0 N2 - 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. T3 - ZIB-Report - 24-02-29 KW - Constraint integer programming KW - Linear programming KW - Mixed-integer linear programming KW - Mixed-integer nonlinear programming KW - Optimization solver KW - Branch-and-cut KW - Branch-and-price KW - Column generation KW - Parallelization KW - Mixed-integer semidefinite programming Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-95528 SN - 1438-0064 ER - TY - JOUR A1 - Kotil, Ayse A1 - Pelofske, Elijah A1 - Riedmüller, Stephanie A1 - Egger, Daniel J. A1 - Eidenbenz, Stephan A1 - Koch, Thorsten A1 - Woerner, Stefan T1 - Quantum Approximate Multi-Objective Optimization JF - Nature Computational Science N2 - 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. Y1 - 2025 U6 - https://doi.org/10.1038/s43588-025-00873-y SP - 1168 EP - 1177 ER -