6469
eng
reportzib
0
--
2017-07-25
--
Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem
Borne out of a surprising variety of practical applications, the maximum-weight connected subgraph problem has attracted considerable interest during the past years. This interest has not only led to notable research on theoretical properties, but has also brought about several (exact) solvers-with steadily increasing performance. Continuing along this path, the following article introduces several new algorithms such as reduction techniques and heuristics and describes their integration into an exact solver.
The new methods are evaluated with respect to both their theoretical and practical properties. Notably, the new exact framework allows to solve common problem instances from the literature faster than all previous approaches. Moreover, one large-scale benchmark instance from the 11th DIMACS Challenge can be solved for the first time to optimality and the primal-dual gap for two other ones can be significantly reduced.
1438-0064
urn:nbn:de:0297-zib-64699
10.1137/17M1145963
Daniel Rehfeldt
Daniel Rehfeldt
Thorsten Koch
ZIB-Report
17-45
eng
uncontrolled
maximum-weight connected subgraph
Mathematical Optimization
Mathematical Optimization Methods
Koch, Thorsten
Rehfeldt, Daniel
MIP-ZIBOPT
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6469/mwcs_zib_revision.pdf
6543
eng
reportzib
0
--
2017-10-27
--
Generalized preprocessing techniques for Steiner tree and maximum-weight connected subgraph problems
This article introduces new preprocessing techniques for the Steiner tree problem in graphs and one of its most popular relatives, the maximum-weight connected subgraph problem. Several of the techniques generalize previous results from the literature. The correctness of the new methods is shown, but also their NP-hardness is demonstrated. Despite this pessimistic worst-case complexity, several relaxations are discussed that are expected to allow for a strong practical efficiency of these techniques in strengthening both exact and heuristic solving approaches.
1438-0064
urn:nbn:de:0297-zib-65439
Daniel Rehfeldt
Daniel Rehfeldt
Thorsten Koch
ZIB-Report
17-57
eng
uncontrolled
Steiner tree
eng
uncontrolled
maximum-weight connected subgraph
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Koch, Thorsten
Rehfeldt, Daniel
MIP-ZIBOPT
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6543/note.pdf
5977
eng
reportzib
0
--
2016-01-07
--
Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP
Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this paper transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, we demonstrate the considerable implications for practical solving approaches, including the computation of strong upper and lower bounds.
1438-0064
urn:nbn:de:0297-zib-59777
10.4208/jcm.1709-m2017-0002
Appeared in: Journal of Computational Mathematics, 36(3):459-468, 2018
Daniel Rehfeldt
Daniel Rehfeldt
Thorsten Koch
ZIB-Report
16-36
eng
uncontrolled
graph transformation
eng
uncontrolled
Steiner tree problems
eng
uncontrolled
prize-collecting Steiner tree problem
eng
uncontrolled
maximum-weight connected subgraph problem
COMBINATORICS (For finite fields, see 11Txx)
Mathematical Optimization
Mathematical Optimization Methods
Koch, Thorsten
Rehfeldt, Daniel
MIP-ZIBOPT
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/5977/pcmwtransformations.pdf
6335
2018
eng
459
468
3
36
article
0
--
2018-03-28
--
Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP
Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree
problem in graphs. In this paper transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, we demonstrate the considerable implications for practical solving approaches, including the computation of strong upper and lower bounds.
Journal of Computational Mathematics
10.4208/jcm.1709-m2017-0002
yes
urn:nbn:de:0297-zib-59777
2017/09/20
Daniel Rehfeldt
Daniel Rehfeldt
Thorsten Koch
Mathematical Optimization
Mathematical Optimization Methods
Koch, Thorsten
Rehfeldt, Daniel
MIP-ZIBOPT
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
4906
2013
deu
bachelorthesis
0
--
--
--
Zweistufige Zielfunktionen in gemischt-ganzzahligen Programmen
Martin Grötschel
Daniel Rehfeldt
Engel
Mathematical Optimization
Technische Universität Berlin
6641
eng
reportzib
0
--
2018-01-18
--
SCIP-Jack—a solver for STP and variants with parallelization extensions: An update
The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. Although the different Steiner tree problem variants are usually strongly related, solution approaches employed so far have been prevalently problem-specific. Against this backdrop, the solver SCIP-Jack was created as a general-purpose framework that can be used to solve the classical Steiner tree problem and 11 of its variants. 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. Furthermore, SCIP-Jack includes various newly developed algorithmic components such as preprocessing routines and heuristics. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances. After the introduction of SCIP-Jack at the 2014 DIMACS Challenge on Steiner problems, the overall performance of the solver has considerably improved. This article provides an overview on the current state.
1438-0064
urn:nbn:de:0297-zib-66416
Daniel Rehfeldt
Daniel Rehfeldt
Thorsten Koch
ZIB-Report
18-05
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Koch, Thorsten
Rehfeldt, Daniel
MIP-ZIBOPT
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6641/scipjack-zibreport.pdf
7349
2019
eng
529
539
11494
conferenceobject
Springer
0
--
--
--
Building Optimal Steiner Trees on Supercomputers by Using up to 43,000 Cores
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.
Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2019
10.1007/978-3-030-19212-9_35
yes
urn:nbn:de:0297-zib-71118
LNCS
Yuji Shinano
Daniel Rehfeldt
Daniel Rehfeldt
Thorsten Koch
Mathematical Optimization
Mathematical Optimization Methods
Koch, Thorsten
Rehfeldt, Daniel
Shinano, Yuji
MIP-ZIBOPT
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
7359
2019
eng
530
541
conferenceobject
IEEE
0
--
--
--
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
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.
Proceedings of the 9th IEEE Workshop Parallel / Distributed Combinatorics and Optimization
10.1109/IPDPSW.2019.00095
yes
urn:nbn:de:0297-zib-72804
2019-03-19
Yuji Shinano
Daniel Rehfeldt
Daniel Rehfeldt
Tristan Gally
Mathematical Optimization
Mathematical Optimization Methods
Rehfeldt, Daniel
Shinano, Yuji
MIP-ZIBOPT
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
7432
eng
reportzib
0
--
2019-08-08
--
A massively parallel interior-point solver for linear energy system models with block structure
Linear energy system models are often a crucial component of system
design and operations, as well as energy policy consulting. Such models can lead to large-scale linear programs, which can be intractable even for state-of-the-art commercial solvers|already the available memory on a desktop machine might not be sufficient. Against this backdrop, this article introduces an interior-point solver that exploits common structures of
linear energy system models to efficiently run in parallel on distributed memory systems. The solver is designed for linear programs with doubly bordered
block-diagonal constraint matrix and makes use of a Schur complement
based decomposition. Special effort has been put into handling
large numbers of linking constraints and variables as commonly observed
in energy system models. In order to handle this strong linkage, a distributed
preconditioning of the Schur complement is used. In addition, the
solver features a number of more generic techniques such as parallel matrix
scaling and structure-preserving presolving. The implementation is
based on the existing parallel interior-point solver PIPS-IPM. We evaluate
the computational performance on energy system models with up to 700
million non-zero entries in the constraint matrix, and with more than 200
million columns and 250 million rows. This article mainly concentrates on
the energy system model ELMOD, which is a linear optimization model
representing the European electricity markets by the use of a nodal pricing
market clearing. It has been widely applied in the literature on energy
system analyses during the recent years. However, it will be demonstrated
that the new solver is also applicable to other energy system models.
1438-0064
urn:nbn:de:0297-zib-74321
In the meantime, this report got published as a journal article: https://opus4.kobv.de/opus4-zib/frontdoor/index/index/searchtype/authorsearch/author/Hannes+Hobbie/docId/8191/start/1/rows/10
Please use this journal reference when citing this work.
Daniel Rehfeldt
Daniel Rehfeldt
Hannes Hobbie
David Schönheit
Ambros Gleixner
Thorsten Koch
Dominik Möst
ZIB-Report
19-41
Mathematical Optimization
Mathematical Optimization Methods
Gleixner, Ambros
Koch, Thorsten
Rehfeldt, Daniel
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/7432/ip4energy3.pdf
7407
2020
eng
105
111
XV, 819
1
conferenceobject
Springer International Publishing
0
2020-09-25
--
--
First Experiments with Structure-Aware Presolving for a Parallel Interior-Point Method
In linear optimization, matrix structure can often be exploited algorithmically. However, beneficial presolving reductions sometimes destroy the special structure of a given problem. In this article, we discuss structure-aware implementations of presolving as part of a parallel interior-point method to solve linear programs with block-diagonal structure, including both linking variables and linking constraints. While presolving reductions are often mathematically simple, their implementation in a high-performance computing environment is a complex endeavor. We report results on impact, performance, and scalability of the resulting presolving routines on real-world energy system models with up to 700 million nonzero entries in the constraint matrix.
Operations Research Proceedings 2019
10.1007/978-3-030-48439-2_13
urn:nbn:de:0297-zib-74084
2019-12-13
yes
Nils-Christian Kempke
Ambros Gleixner
Nils-Christian Kempke
Thorsten Koch
Daniel Rehfeldt
Svenja Uslu
eng
uncontrolled
block structure
eng
uncontrolled
energy system models
eng
uncontrolled
interior-point method
eng
uncontrolled
high performance computing
eng
uncontrolled
linear programming
eng
uncontrolled
parallelization
eng
uncontrolled
presolving
eng
uncontrolled
preprocessing
Linear programming
Large-scale problems
Mathematical Optimization
Mathematical Optimization Methods
Gleixner, Ambros
Koch, Thorsten
Rehfeldt, Daniel
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
Applied Algorithmic Intelligence Methods
7408
eng
reportzib
0
--
2019-07-26
--
First Experiments with Structure-Aware Presolving for a Parallel Interior-Point Method
In linear optimization, matrix structure can often be exploited algorithmically. However, beneficial presolving reductions sometimes destroy the special structure of a given problem. In this article, we discuss structure-aware implementations of presolving as part of a parallel interior-point method to solve linear programs with block-diagonal structure, including both linking variables and linking constraints. While presolving reductions are often mathematically simple, their implementation in a high-performance computing environment is a complex endeavor. We report results on impact, performance, and scalability of the resulting presolving routines on real-world energy system models with up to 700 million nonzero entries in the constraint matrix.
1438-0064
urn:nbn:de:0297-zib-74084
10.1007/978-3-030-48439-2_13
Operations Research Proceedings 2019
Ambros Gleixner
Nils-Christian Kempke
Nils-Christian Kempke
Thorsten Koch
Daniel Rehfeldt
Svenja Uslu
ZIB-Report
19-39
eng
uncontrolled
block structure
eng
uncontrolled
energy system models
eng
uncontrolled
interior-point method
eng
uncontrolled
high performance computing
eng
uncontrolled
linear programming
eng
uncontrolled
parallelization
eng
uncontrolled
presolving
eng
uncontrolled
preprocessing
Linear programming
Large-scale problems
Mathematical Optimization
Mathematical Optimization Methods
Gleixner, Ambros
Koch, Thorsten
Rehfeldt, Daniel
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/7408/ZR-19-39-preprint_revised_pub.pdf
7459
2019
deu
6
8
66
article
0
--
2019-07-01
--
BEAM-ME: Ein interdisziplinärer Beitrag zur Erreichung der Klimaziele
OR-News : das Magazin der GOR
2019/07/01
no
Thomas Breuer
Franziska Schlösser
Michael Bussieck
Frederik Fiand
Karl-Kiên Cao
Hans Christian Gils
Manuel Wetzel
Ambros Gleixner
Thorsten Koch
Daniel Rehfeldt
Dmitry Khabi
Mathematical Optimization
Mathematical Optimization Methods
Gleixner, Ambros
Koch, Thorsten
Rehfeldt, Daniel
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
7817
eng
reportzib
0
--
2020-04-11
--
On the exact solution of prize-collecting Steiner tree problems
1438-0064
urn:nbn:de:0297-zib-78174
Daniel Rehfeldt
Daniel Rehfeldt
Thorsten Koch
ZIB-Report
20-11
Mathematical Optimization
Koch, Thorsten
Rehfeldt, Daniel
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
Applied Algorithmic Intelligence Methods
https://opus4.kobv.de/opus4-zib/files/7817/pcstpZIBv2.pdf
7909
eng
reportzib
0
--
2020-08-06
--
Optimal Connected Subgraphs: Formulations and Algorithms
1438-0064
urn:nbn:de:0297-zib-79094
Daniel Rehfeldt
Daniel Rehfeldt
Henriette Franz
Thorsten Koch
ZIB-Report
20-23
Koch, Thorsten
Rehfeldt, Daniel
MODAL-SynLab
MODAL-Gesamt
Applied Algorithmic Intelligence Methods
https://opus4.kobv.de/opus4-zib/files/7909/connectedsubgraphs.pdf
8189
2021
eng
article
0
2021-10-06
--
--
On the exact solution of prize-collecting Steiner tree problems
INFORMS Journal on Computing
10.1287/ijoc.2021.1087
yes
2021/03/17
publish
urn:nbn:de:0297-zib-78174
Daniel Rehfeldt
Daniel Rehfeldt
Thorsten Koch
Koch, Thorsten
Rehfeldt, Daniel
MODAL-SynLab
MODAL-Gesamt
Applied Algorithmic Intelligence Methods
MODAL-EnergyLab
8190
2021
eng
473
487
conferenceobject
0
--
--
--
Implications, conflicts, and reductions for Steiner trees
Integer Programming and Combinatorial Optimization: 22th International Conference, IPCO 2021
10.1007/978-3-030-73879-2_33
yes
2021/01/25
publish
urn:nbn:de:0297-zib-80039
Daniel Rehfeldt
Rehfeldt
Thorsten Koch
Koch, Thorsten
Rehfeldt, Daniel
MODAL-SynLab
MODAL-Gesamt
Applied Algorithmic Intelligence Methods
MODAL-EnergyLab
8072
2020
eng
bookpart
Springer
0
--
--
--
An exact high performance solver for Steiner tree problems in graphs and related problems
Modeling, Simulation and Optimization of Complex Processes HPSC 2018
Lecture Notes in Computer Science
no
2020
Thorsten Koch
Katharina Lachmann
Daniel Rehfeldt
Yuji Shinano
Koch, Thorsten
Rehfeldt, Daniel
no-project
Mathematical Algorithmic Intelligence
Applied Algorithmic Intelligence Methods
8003
eng
reportzib
0
--
2020-11-12
--
Implications, conflicts, and reductions for Steiner trees
1438-0064
urn:nbn:de:0297-zib-80039
Daniel Rehfeldt
Daniel Rehfeldt
Thorsten Koch
ZIB-Report
20-28
Koch, Thorsten
Rehfeldt, Daniel
MODAL-GasLab
MODAL-SynLab
MODAL-Gesamt
Applied Algorithmic Intelligence Methods
https://opus4.kobv.de/opus4-zib/files/8003/spg_implications.pdf
7095
eng
reportzib
0
--
2018-11-21
--
Reduction-based exact solution of prize-collecting Steiner tree problems
1438-0064
urn:nbn:de:0297-zib-70958
Daniel Rehfeldt
Daniel Rehfeldt
Thorsten Koch
ZIB-Report
18-55
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Koch, Thorsten
Rehfeldt, Daniel
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/7095/pcstpZIB.pdf
7280
eng
reportzib
0
--
2019-03-20
--
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
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.
1438-0064
urn:nbn:de:0297-zib-72804
Yuji Shinano
Daniel Rehfeldt
Daniel Rehfeldt
Tristan Galley
ZIB-Report
19-14
Mathematical Optimization
Rehfeldt, Daniel
Shinano, Yuji
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/7280/pco2019.pdf
7726
2020
eng
article
0
2020-02-24
--
--
A Physarum-Inspired Algorithm for Minimum-Cost Relay Node Placement in Wireless Sensor Networks
IEEE/ACM Transactions on Networking
10.1109/TNET.2020.2971770
yes
Yahui Sun
Daniel Rehfeldt
Daniel Rehfeldt
Marcus Brazil
Doreen Thomas
Saman Halgamuge
Mathematical Optimization
Rehfeldt, Daniel
MODAL-SynLab
MODAL-Gesamt
6752
2018
eng
641
647
6
conferenceobject
Springer International Publishing
0
2018-03-26
--
--
Optimizing Large-Scale Linear Energy System Problems with Block Diagonal Structure by Using Parallel Interior-Point Methods
Current linear energy system models (ESM) acquiring to provide sufficient detail and reliability frequently bring along problems of both high intricacy and increasing scale. Unfortunately, the size and complexity of these problems often prove to be intractable even for commercial state-of-the-art linear programming solvers. This article describes an interdisciplinary approach to exploit the intrinsic structure of these large-scale linear problems to be able to solve them on massively parallel high-performance computers. A key aspect are extensions
to the parallel interior-point solver PIPS-IPM originally developed for stochastic optimization problems. Furthermore, a newly developed GAMS interface to the solver as well as some GAMS language extensions to model block-structured problems will be described.
Operations Research Proceedings 2017
10.1007/978-3-319-89920-6_85
yes
urn:nbn:de:0297-zib-66183
2017-12-08
Thomas Breuer
Ambros Gleixner
Michael Bussieck
Karl-Kien Cao
Felix Cebulla
Frederik Fiand
Hans Christian Gils
Ambros Gleixner
Dmitry Khabi
Thorsten Koch
Daniel Rehfeldt
Manuel Wetzel
Mathematical Optimization
Mathematical Optimization Methods
Gleixner, Ambros
Koch, Thorsten
Rehfeldt, Daniel
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
7086
2019
eng
369
398
30
1
29
article
Society for Industrial and Applied Mathematics
0
--
--
--
Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem
Borne out of a surprising variety of practical applications, the maximum-weight connected subgraph problem has attracted considerable interest during the past years. This interest has not only led to notable research on theoretical properties, but has also brought about several (exact) solvers-with steadily increasing performance. Continuing along this path, the following article introduces several new algorithms such as reduction techniques and heuristics and describes their integration into an exact solver. The new methods are evaluated with respect to both their theoretical and practical properties. Notably, the new exact framework allows to solve common problem instances from the literature faster than all previous approaches. Moreover, one large-scale benchmark instance from the 11th DIMACS Challenge can be solved for the first time to optimality and the primal-dual gap for two other ones can be significantly reduced.
SIAM Journal on Optimization
10.1137/17M1145963
yes
2018-10-30
urn:nbn:de:0297-zib-64699
Daniel Rehfeldt
Daniel Rehfeldt
Thorsten Koch
Mathematical Optimization
Mathematical Optimization Methods
Koch, Thorsten
Rehfeldt, Daniel
MIP-ZIBOPT
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
6759
2018
eng
191
196
6
conferenceobject
0
--
2018-03-26
--
SCIP-Jack—a solver for STP and variants with parallelization extensions: An update
The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. Although the different Steiner tree problem variants are usually strongly related, solution approaches employed so far have been prevalently problem-specific. Against this backdrop, the solver SCIP-Jack was created as a general-purpose framework that can be used to solve the classical Steiner tree problem and 11 of its variants. 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. Furthermore, SCIP-Jack includes various newly developed algorithmic components such as preprocessing routines and heuristics. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances. After the introduction of SCIP-Jack at the 2014 DIMACS Challenge on Steiner problems, the overall performance of the solver has considerably improved. This article provides an overview on the current state.
Operations Research Proceedings 2017
yes
urn:nbn:de:0297-zib-66416
2017-11-01
Daniel Rehfeldt
Daniel Rehfeldt
Thorsten Koch
Mathematical Optimization
Mathematical Optimization Methods
Koch, Thorsten
Rehfeldt, Daniel
MIP-ZIBOPT
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
8571
eng
reportzib
0
--
2022-02-01
--
Faster exact solution of sparse MaxCut and QUBO problems
1438-0064
urn:nbn:de:0297-zib-85715
publish
Daniel Rehfeldt
Rehfeldt
Thorsten Koch
Yuji Shinano
ZIB-Report
22-02
Koch, Thorsten
Rehfeldt, Daniel
Shinano, Yuji
MODAL-SynLab
MODAL-Gesamt
Applied Algorithmic Intelligence Methods
https://opus4.kobv.de/opus4-zib/files/8571/qubo.pdf
8513
2022
eng
314
332
3
80
article
Wiley
0
2022-05-23
2022-10-01
--
Optimal Connected Subgraphs: Integer Programming Formulations and Polyhedra
Networks
10.1002/net.22101
yes
publish
Daniel Rehfeldt
Daniel Rehfeldt
Henriette Franz
Thorsten Koch
Koch, Thorsten
Rehfeldt, Daniel
MODAL-SynLab
MODAL-Gesamt
Applied Algorithmic Intelligence Methods
MODAL-EnergyLab
5781
2015
2015
eng
185
masterthesis
0
--
--
2015-09-11
A Generic Approach to Solving the Steiner Tree Problem and Variants
Spawned by practical applications, numerous variations of the classical Steiner tree problem in graphs have been studied during the last decades. Despite the strong relationship between the different variants, solution approaches employed so far have been prevalently problem-specific.
In contrast, we pursue a general-purpose strategy resulting in a solver able to solve both the classical Steiner tree problem and ten of its variants without modification. These variants include well-known problems such as the prize-collecting Steiner tree problem, the maximum-weight connected subgraph problem or the rectilinear minimum Steiner tree problem. Bolstered by a variety of new methods, most notably reduction techniques, our solver is not only of unprecedented versatility, but furthermore competitive or even superior to specialized state-of-the-art programs for several Steiner problem variants.
urn:nbn:de:0297-zib-57817
Thorsten Koch
Daniel Rehfeldt
Daniel Rehfeldt
eng
uncontrolled
Steiner Tree Problem
eng
uncontrolled
Steiner Tree Problem Variants
Software
COMBINATORICS (For finite fields, see 11Txx)
Mathematical Optimization
Rehfeldt, Daniel
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
Technische Universität Berlin
https://opus4.kobv.de/opus4-zib/files/5781/MasterThesis.pdf
5229
eng
reportzib
0
--
2014-09-24
--
SCIP-Jack - A massively parallel STP solver
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.
1438-0064
urn:nbn:de:0297-zib-52293
no
Gerald Gamrath
Gerald Gamrath
Thorsten Koch
Daniel Rehfeldt
Yuji Shinano
ZIB-Report
14-35
eng
uncontrolled
Steiner Tree Problem
eng
uncontrolled
Mixed-Integer Programming
eng
uncontrolled
Branch-and-Cut
eng
uncontrolled
DIMACS Challenge
Trees
Algorithm design and analysis (REVISED)
Combinatorial optimization
Polyhedral combinatorics, branch-and-bound, branch-and-cut
Mathematical Optimization
Mathematical Optimization Methods
Gamrath, Gerald
Koch, Thorsten
Rehfeldt, Daniel
Shinano, Yuji
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/5229/ZR14-35.pdf
7111
eng
reportzib
0
--
2018-12-07
--
Building Optimal Steiner Trees on Supercomputers by using up to 43,000 Cores
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.
1438-0064
urn:nbn:de:0297-zib-71118
Yuji Shinano
Yuji Shinano
Daniel Rehfeldt
Thorsten Koch
ZIB-Report
18-58
Computing Methodologies
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Koch, Thorsten
Rehfeldt, Daniel
Shinano, Yuji
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/7111/ZIB-Report-18-58.pdf
https://opus4.kobv.de/opus4-zib/files/7111/ZIB-Report-18-58-rev.pdf
6618
eng
reportzib
0
--
2017-12-18
--
Optimizing Large-Scale Linear Energy System Problems with Block Diagonal Structure by Using Parallel Interior-Point Methods
Current linear energy system models (ESM) acquiring to provide sufficient detail and reliability frequently bring along problems of both high intricacy and increasing scale. Unfortunately, the size and complexity of these problems often prove to be intractable even for commercial state-of-the-art linear programming solvers. This article describes an interdisciplinary approach to exploit the intrinsic structure of these large-scale linear problems to be able to solve them on massively parallel high-performance computers. A key aspect are extensions to the parallel interior-point solver PIPS-IPM originally developed for stochastic optimization problems. Furthermore, a newly developed GAMS interface to the solver as well as some GAMS language extensions to model block-structured problems will be described.
1438-0064
urn:nbn:de:0297-zib-66183
10.1007/978-3-319-89920-6_85
Operations Research Proceedings 2017
Thomas Breuer
Daniel Rehfeldt
Michael Bussieck
Karl-Kien Cao
Felix Cebulla
Frederik Fiand
Hans Christian Gils
Ambros Gleixner
Dmitry Khabi
Thorsten Koch
Daniel Rehfeldt
Manuel Wetzel
ZIB-Report
17-75
eng
uncontrolled
energy system models
eng
uncontrolled
interior-point methods
eng
uncontrolled
high-performance computing
Software
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Gleixner, Ambros
Koch, Thorsten
Rehfeldt, Daniel
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6618/zibreport.pdf
5464
eng
reportzib
0
--
2015-04-24
--
SCIP-Jack - A solver for STP and variants with parallelization extensions
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.
1438-0064
urn:nbn:de:0297-zib-54648
A revised version is provided here: http://nbn-resolving.de/urn:nbn:de:0297-zib-60170.
urn:nbn:de:0297-zib-54648
Gerald Gamrath
Stephen J. Maher
Thorsten Koch
Stephen J. Maher
Daniel Rehfeldt
Yuji Shinano
ZIB-Report
15-27
Mixed integer programming
Mathematical Optimization
Mathematical Optimization Methods
Gamrath, Gerald
Koch, Thorsten
Rehfeldt, Daniel
Shinano, Yuji
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/5464/ZR-15-27.pdf
8514
2021
eng
doctoralthesis
0
--
--
--
Faster algorithms for Steiner tree and related problems: From theory to practice
urn:nbn:de:0297-zib-85148
publish
Thorsten Koch
Daniel Rehfeldt
Rehfeldt
Eduardo Uchoa
Renato Werneck
eng
uncontrolled
Steiner tree problem
Rehfeldt, Daniel
Applied Algorithmic Intelligence Methods
MODAL-EnergyLab
Technische Universität Berlin
https://opus4.kobv.de/opus4-zib/files/8514/dissertation_rehfeldt.pdf
8512
2023
eng
903
966
64
197
article
Springer
0
--
2023-02-01
--
Implications, Conflicts, and Reductions for Steiner Trees
Mathematical Programming
10.1007/s10107-021-01757-5
yes
2021-12-02
publish
Daniel Rehfeldt
Rehfeldt
Thorsten Koch
Koch, Thorsten
Rehfeldt, Daniel
MODAL-SynLab
MODAL-Gesamt
Applied Algorithmic Intelligence Methods
MODAL-EnergyLab
8922
2022
eng
conferenceobject
0
--
--
--
Faster Algorithms for Steiner Tree and related Problems: From Theory to Practice
Operations Research Proceedings 2022
yes
publish
Daniel Rehfeldt
Daniel Rehfeldt
Rehfeldt, Daniel
MODAL-SynLab
MODAL-Gesamt
Applied Algorithmic Intelligence Methods
MODAL-EnergyLab
8818
eng
reportzib
0
--
2022-11-16
--
Computing single-source shortest paths on graphs with over 8 trillion edges
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.
1438-0064
urn:nbn:de:0297-zib-88180
publish
Daniel Rehfeldt
Rehfeldt
Katsuki Fujisawa
Thorsten Koch
Masahiro Nakao
Yuji Shinano
ZIB-Report
22-22
Koch, Thorsten
Rehfeldt, Daniel
Shinano, Yuji
MODAL-Gesamt
Applied Algorithmic Intelligence Methods
MODAL-EnergyLab
https://opus4.kobv.de/opus4-zib/files/8818/main.pdf
8921
2022
eng
article
0
--
--
--
Faster Algorithms for Steiner Tree and related Problems: From Theory to Practice
OR News: Das Magazin der GOR
publish
No
Daniel Rehfeldt
Daniel Rehfeldt
Rehfeldt, Daniel
Applied Algorithmic Intelligence Methods
MODAL-EnergyLab
6017
eng
reportzib
0
--
2016-08-16
--
SCIP-Jack – A solver for STP and variants with parallelization extensions
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.
1438-0064
urn:nbn:de:0297-zib-60170
10.1007/s12532-016-0114-x
Mathematical Programming Computation, Vol. 9 (2)
Gerald Gamrath
Daniel Rehfeldt
Thorsten Koch
Stephen J. Maher
Daniel Rehfeldt
Yuji Shinano
ZIB-Report
16-41
eng
uncontrolled
Steiner tree problem
eng
uncontrolled
SCIP-Jack
eng
uncontrolled
Steiner tree variants
deu
uncontrolled
maximum-weight connected subgraph
deu
uncontrolled
prize-collecting Steiner tree
Software
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Gamrath, Gerald
Koch, Thorsten
Rehfeldt, Daniel
Shinano, Yuji
MIP-ZIBOPT
MODAL-GasLab
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6017/scipjack_ZIBreport.pdf
6042
eng
reportzib
0
--
2016-09-23
--
Reduction Techniques for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem
The concept of reduction has frequently distinguished itself as a pivotal ingredient of exact solving approaches for the Steiner tree problem in graphs. In this paper we broaden the focus and consider reduction techniques for three Steiner problem variants that have been extensively discussed in the literature and entail various practical applications: The prize-collecting Steiner tree problem, the rooted prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem.
By introducing and subsequently deploying numerous new reduction methods, we are able to drastically decrease the size of a large number of benchmark instances, already solving more than 90 percent of them to optimality. Furthermore, we demonstrate the impact of these techniques on exact solving, using the example of the state-of-the-art Steiner problem solver SCIP-Jack.
1438-0064
urn:nbn:de:0297-zib-60420
10.1002/net.21857
Daniel Rehfeldt
Daniel Rehfeldt
Thorsten Koch
Stephen J. Maher
ZIB-Report
16-47
eng
uncontrolled
Steiner tree problems
eng
uncontrolled
reduction techniques
eng
uncontrolled
prize-collecting Steiner tree problem
eng
uncontrolled
maximum-weight connected subgraph problem
Software
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Koch, Thorsten
Rehfeldt, Daniel
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6042/PcMwReductions.pdf
6134
eng
reportzib
0
--
2016-01-12
--
PySCIPOpt: Mathematical Programming in Python with the SCIP Optimization Suite
SCIP is a solver for a wide variety of mathematical optimization problems. It is written in C and extendable due to its plug-in based design. However, dealing with all C specifics when extending SCIP can be detrimental to development and testing of new ideas. This paper attempts to provide a remedy by introducing PySCIPOpt, a Python interface to SCIP that enables users to write new SCIP code entirely in Python. We demonstrate how to intuitively model mixed-integer linear and quadratic optimization problems and moreover provide examples on how new Python plug-ins can be added to SCIP.
1438-0064
urn:nbn:de:0297-zib-61348
10.1007/978-3-319-42432-3_37
Appeared in: Mathematical Software – ICMS 2016, Volume 9725, Pages 301-307
Stephen J. Maher
Matthias Miltenberger
Matthias Miltenberger
João Pedro Pedroso
Daniel Rehfeldt
Robert Schwarz
Felipe Serrano
ZIB-Report
16-64
eng
uncontrolled
SCIP, Mathematical optimization, Python, Modeling
Computer Applications
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Miltenberger, Matthias
Rehfeldt, Daniel
Serrano, Felipe
ASTfSCM
MIP-ZIBOPT
MODAL-GasLab
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6134/PySCIPOpt.pdf
6063
2017
eng
231
296
2
9
article
0
2017-06-19
--
--
SCIP-Jack – A solver for STP and variants with parallelization extensions
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.
Mathematical Programming Computation
10.1007/s12532-016-0114-x
yes
urn:nbn:de:0297-zib-60170
Gerald Gamrath
Daniel Rehfeldt
Thorsten Koch
Stephen J. Maher
Daniel Rehfeldt
Yuji Shinano
Mathematical Optimization
Mathematical Optimization Methods
Gamrath, Gerald
Koch, Thorsten
Rehfeldt, Daniel
Shinano, Yuji
MIP-ZIBOPT
MODAL-GasLab
MODAL-SynLab
MODAL-Gesamt
6333
2019
eng
206
233
2
73
article
Wiley
0
--
--
--
Reduction Techniques for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem
The concept of reduction has frequently distinguished itself as a pivotal ingredient of exact solving approaches for the Steiner tree problem in graphs. In this paper we broaden the focus and consider reduction techniques for three Steiner problem variants that have been extensively discussed in the literature and entail various practical applications: The prize-collecting Steiner tree problem, the rooted prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem.
By introducing and subsequently deploying numerous new reduction methods, we are able to drastically decrease the size of a large number of benchmark instances, already solving more than 90 percent of them to optimality. Furthermore, we demonstrate the impact of these techniques on exact solving, using the example of the state-of-the-art Steiner problem solver SCIP-Jack.
Networks
10.1002/net.21857
urn:nbn:de:0297-zib-60420
Yes
Daniel Rehfeldt
Daniel Rehfeldt
Thorsten Koch
Stephen J. Maher
Mathematical Optimization
Mathematical Optimization Methods
Koch, Thorsten
Rehfeldt, Daniel
MIP-ZIBOPT
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
6045
2016
eng
301
307
9725
conferenceobject
Springer
0
--
--
--
PySCIPOpt: Mathematical Programming in Python with the SCIP Optimization Suite
SCIP is a solver for a wide variety of mathematical optimization problems. It is written in C and extendable due to its plug-in based design. However, dealing with all C specifics when extending SCIP can be detrimental to development and testing of new ideas. This paper attempts to provide a remedy by introducing PySCIPOpt, a Python interface to SCIP that enables users to write new SCIP code entirely in Python. We demonstrate how to intuitively model mixed-integer linear and quadratic optimization problems and moreover provide examples on how new Python plug-ins can be added to SCIP.
Mathematical Software – ICMS 2016
10.1007/978-3-319-42432-3_37
yes
Lecture Notes in Computer Science
urn:nbn:de:0297-zib-61348
Stephen J. Maher
Daniel Rehfeldt
Matthias Miltenberger
João Pedro Pedroso
Daniel Rehfeldt
Robert Schwarz
Felipe Serrano
Mathematical Optimization
Miltenberger, Matthias
Rehfeldt, Daniel
Serrano, Felipe
MODAL-GasLab
MODAL-SynLab
MODAL-Gesamt
9059
eng
reportzib
0
--
2023-04-19
--
An efficient solver for multi-objective onshore wind farm siting and network integration
Existing planning approaches for onshore wind farm siting and network integration often do not meet minimum cost solutions or social and environmental considerations. In this paper, we develop an approach for the multi-objective optimization of turbine locations and their network connection using a Quota Steiner tree problem. Applying a novel transformation on a known directed cut formulation, reduction techniques, and heuristics, we design an exact solver that makes large problem instances solvable and outperforms generic MIP solvers. Although our case studies in selected regions of Germany show large trade-offs between the objective criteria of cost and landscape impact, small burdens on one criterion can significantly improve the other criteria. In addition, we demonstrate that contrary to many approaches for exclusive turbine siting, network integration must be simultaneously optimized in order to avoid excessive costs or landscape impacts in the course of a wind farm project. Our novel problem formulation and the developed solver can assist planners in decision making and help optimize wind farms in large regions in the future.
1438-0064
urn:nbn:de:0297-zib-90590
publish
Jaap Pedersen
Jaap Pedersen
Jann Michael Weinand
Chloi Syranidou
Daniel Rehfeldt
ZIB-Report
23-10
Rehfeldt, Daniel
MODAL-Gesamt
Pedersen, Jaap
Mathematical Algorithmic Intelligence
Applied Algorithmic Intelligence Methods
MODAL-EnergyLab
https://opus4.kobv.de/opus4-zib/files/9059/ZR_23-10.pdf
7360
2021
eng
conferenceobject
Springer
0
--
--
--
SCIP-Jack: An exact high performance solver for Steiner tree problems in graphs and related problems
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.
Modeling, Simulation and Optimization of Complex Processes HPSC 2018
Proceedings of the 7th International Conference on High Performance Scientific Computing
10.1007/978-3-030-55240-4_10
LNCS
yes
2019-05-28
Daniel Rehfeldt
Daniel Rehfeldt
Yuji Shinano
Thorsten Koch
Mathematical Optimization
Mathematical Optimization Methods
Koch, Thorsten
Rehfeldt, Daniel
Shinano, Yuji
MIP-ZIBOPT
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
8191
2022
eng
60
71
1
296
article
0
--
--
--
A massively parallel interior-point solver for LPs with generalized arrowhead structure, and applications to energy system models
Linear energy system models are a crucial component of energy system design and operations, as well as energy policy consulting. If detailed enough, such models lead to large-scale linear programs, which can be intractable even for the best state-of-the-art solvers. This article introduces an interior-point solver that exploits common structures of energy system models to efficiently run in parallel on distributed-memory systems. The solver is designed for linear programs with doubly-bordered block-diagonal constraint matrix and makes use of a Schur complement based decomposition. In order to handle the large number of linking constraints and variables commonly observed in energy system models, a distributed Schur complement preconditioner is used. In addition, the solver features a number of more generic techniques such as parallel matrix scaling and structure-preserving presolving. The implementation is based on the solver PIPS-IPM. We evaluate the computational performance on energy system models with up to four billion nonzero entries in the constraint matrix—and up to one billion columns and one billion rows. This article mainly concentrates on the energy system model ELMOD, which is a linear optimization model representing the European electricity markets by the use of a nodal pricing market-clearing. It has been widely applied in the literature on energy system analyses in recent years. However, it will be demonstrated that the new solver is also applicable to other energy system models.
European Journal of Operational Research
10.1016/j.ejor.2021.06.063
yes
publish
urn:nbn:de:0297-zib-74321
Daniel Rehfeldt
Rehfeldt
Hannes Hobbie
David Schönheit
Thorsten Koch
Dominik Möst
Ambros Gleixner
Gleixner, Ambros
Koch, Thorsten
Rehfeldt, Daniel
MODAL-SynLab
BEAM-ME
MODAL-Gesamt
Applied Algorithmic Intelligence Methods
MODAL-EnergyLab
8622
2020
eng
345
352
50
conferenceobject
0
--
--
--
BEAM-ME: Accelerating Linear Energy Systems Models by a Massively Parallel Interior Point Method
NIC Symposium 2020
NIC Series
no
publish
Thomas Breuer
Ambros Gleixner
Michael Bussieck
Karl-Kien Cao
Fred Fiand
Hans-Christian Gils
Ambros Gleixner
Dmitry Khabi
Nils Kempke
Thorsten Koch
Daniel Rehfeldt
Manuel Wetzel
Gleixner, Ambros
Koch, Thorsten
Rehfeldt, Daniel
BEAM-ME
AI in Society, Science, and Technology
8990
2023
eng
445
470
15
article
0
2023-04-15
--
--
Faster exact solution of sparse MaxCut and QUBO problems
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.
Mathematical Programming Computation
10.1007/s12532-023-00236-6
yes
urn:nbn:de:0297-zib-85715
Daniel Rehfeldt
Daniel Rehfeldt
Thorsten Koch
Yuji Shinano
Koch, Thorsten
Rehfeldt, Daniel
Shinano, Yuji
MODAL-SynLab
MODAL-Gesamt
Applied Algorithmic Intelligence Methods
MODAL-EnergyLab
6217
eng
reportzib
0
--
2017-08-03
--
The SCIP Optimization Suite 4.0
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.
1438-0064
urn:nbn:de:0297-zib-62170
Stephen J. Maher
Ambros Gleixner
Tobias Fischer
Tristan Gally
Gerald Gamrath
Ambros Gleixner
Robert Lion Gottwald
Gregor Hendel
Thorsten Koch
Marco Lübbecke
Matthias Miltenberger
Benjamin Müller
Marc Pfetsch
Christian Puchert
Daniel Rehfeldt
Sebastian Schenker
Robert Schwarz
Felipe Serrano
Yuji Shinano
Dieter Weninger
Jonas T. Witt
Jakob Witzig
ZIB-Report
17-12
Computer aspects of numerical algorithms
Linear programming
Mixed integer programming
Nonconvex programming, global optimization
Mathematical Optimization
Mathematical Optimization Methods
Gamrath, Gerald
Gleixner, Ambros
Gottwald, Robert
Hendel, Gregor
Koch, Thorsten
Miltenberger, Matthias
Rehfeldt, Daniel
Serrano, Felipe
Shinano, Yuji
Müller, Benjamin
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
Siemens
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6217/scipoptsuite-40.pdf
https://opus4.kobv.de/opus4-zib/files/6217/scipoptsuite-401.pdf
5767
eng
reportzib
0
--
2016-02-26
--
The SCIP Optimization Suite 3.2
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.
1438-0064
urn:nbn:de:0297-zib-57675
no
Gerald Gamrath
Gerald Gamrath
Tobias Fischer
Tristan Gally
Ambros Gleixner
Gregor Hendel
Thorsten Koch
Stephen J. Maher
Matthias Miltenberger
Benjamin Müller
Marc Pfetsch
Christian Puchert
Daniel Rehfeldt
Sebastian Schenker
Robert Schwarz
Felipe Serrano
Yuji Shinano
Stefan Vigerske
Dieter Weninger
Michael Winkler
Jonas T. Witt
Jakob Witzig
ZIB-Report
15-60
eng
uncontrolled
mixed-integer linear and nonlinear programming
eng
uncontrolled
MIP solver
eng
uncontrolled
MINLP solver
eng
uncontrolled
linear programming
eng
uncontrolled
LP solver
eng
uncontrolled
simplex method
eng
uncontrolled
modeling
eng
uncontrolled
parallel branch-and-bound
eng
uncontrolled
branch-cut-and-price framework
eng
uncontrolled
generic column generation
eng
uncontrolled
Steiner tree solver
eng
uncontrolled
multi-criteria optimization
eng
uncontrolled
mixed-integer semidefinite programming
Parallel computation
Linear programming
Integer programming
Mixed integer programming
Nonlinear programming
Applications of mathematical programming
Mathematical Optimization
Mathematical Optimization Methods
Gamrath, Gerald
Gleixner, Ambros
Hendel, Gregor
Koch, Thorsten
Miltenberger, Matthias
Rehfeldt, Daniel
Serrano, Felipe
Shinano, Yuji
Vigerske, Stefan
Winkler, Michael
Müller, Benjamin
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
CRC1026
Siemens
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/5767/scipopt-32.pdf
8530
eng
reportzib
0
--
2021-12-17
--
The SCIP Optimization Suite 8.0
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.
1438-0064
urn:nbn:de:0297-zib-85309
publish
Ksenia Bestuzheva
Ksenia Bestuzheva
Mathieu Besançon
Wei-Kun Chen
Antonia Chmiela
Tim Donkiewicz
Jasper van Doornmalen
Leon Eifler
Oliver Gaul
Gerald Gamrath
Ambros Gleixner
Leona Gottwald
Christoph Graczyk
Katrin Halbig
Alexander Hoen
Christopher Hojny
Rolf van der Hulst
Thorsten Koch
Marco Lübbecke
Stephen J. Maher
Frederic Matter
Erik Mühmer
Benjamin Müller
Marc E. Pfetsch
Daniel Rehfeldt
Steffan Schlein
Franziska Schlösser
Felipe Serrano
Yuji Shinano
Boro Sofranac
Mark Turner
Stefan Vigerske
Fabian Wegscheider
Philipp Wellner
Dieter Weninger
Jakob Witzig
ZIB-Report
21-41
eng
uncontrolled
Constraint integer programming
eng
uncontrolled
Linear programming
eng
uncontrolled
Mixed-integer linear programming
eng
uncontrolled
Mixed-integer nonlinear programming
eng
uncontrolled
Optimization solver
eng
uncontrolled
Branch-and-cut
eng
uncontrolled
Branch-and-price
eng
uncontrolled
Column generation
eng
uncontrolled
Parallelization
eng
uncontrolled
Mixed-integer semidefinite programming
Parallel computation
Linear programming
Integer programming
Mixed integer programming
Nonlinear programming
Applications of mathematical programming
Gamrath, Gerald
Gleixner, Ambros
Koch, Thorsten
Rehfeldt, Daniel
Serrano, Felipe
Shinano, Yuji
Vigerske, Stefan
Müller, Benjamin
MODAL-SynLab
Eifler, Leon
MODAL-Gesamt
Schlösser, Franziska
Turner, Mark Ruben
Chmiela, Antonia
Bestuzheva, Ksenia
HPO-NAVI
AI in Society, Science, and Technology
Applied Algorithmic Intelligence Methods
Graczyk, Christoph
Hoen, Alexander
https://opus4.kobv.de/opus4-zib/files/8530/scipopt-80.pdf
6629
eng
reportzib
0
--
2017-12-21
--
The SCIP Optimization Suite 5.0
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.
1438-0064
urn:nbn:de:0297-zib-66297
Ambros Gleixner
Gregor Hendel
Leon Eifler
Tristan Gally
Gerald Gamrath
Patrick Gemander
Robert Lion Gottwald
Gregor Hendel
Christopher Hojny
Thorsten Koch
Matthias Miltenberger
Benjamin Müller
Marc Pfetsch
Christian Puchert
Daniel Rehfeldt
Franziska Schlösser
Felipe Serrano
Yuji Shinano
Jan Merlin Viernickel
Stefan Vigerske
Dieter Weninger
Jonas T. Witt
Jakob Witzig
ZIB-Report
17-61
eng
uncontrolled
constraint integer programming
eng
uncontrolled
linear programming
eng
uncontrolled
mixed-integer linear programming
eng
uncontrolled
mixed-integer nonlinear programming
eng
uncontrolled
optimization solver
eng
uncontrolled
branch-and-cut
eng
uncontrolled
branch-and-price
eng
uncontrolled
column generation framework
eng
uncontrolled
parallelization
eng
uncontrolled
mixed-integer semidefinite programming
eng
uncontrolled
Steiner tree optimization
NUMERICAL ANALYSIS
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Gamrath, Gerald
Gleixner, Ambros
Gottwald, Robert
Hendel, Gregor
Koch, Thorsten
Miltenberger, Matthias
Rehfeldt, Daniel
Serrano, Felipe
Shinano, Yuji
Vigerske, Stefan
Müller, Benjamin
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
Siemens
Eifler, Leon
MODAL-Gesamt
Schlösser, Franziska
https://opus4.kobv.de/opus4-zib/files/6629/scipopt-50.pdf
6936
eng
reportzib
0
--
2018-07-02
--
The SCIP Optimization Suite 6.0
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.
1438-0064
urn:nbn:de:0297-zib-69361
Matthias Miltenberger
Ambros Gleixner
Michael Bastubbe
Leon Eifler
Tristan Gally
Gerald Gamrath
Robert Lion Gottwald
Gregor Hendel
Christopher Hojny
Thorsten Koch
Marco Lübbecke
Stephen J. Maher
Matthias Miltenberger
Benjamin Müller
Marc Pfetsch
Christian Puchert
Daniel Rehfeldt
Franziska Schlösser
Christoph Schubert
Felipe Serrano
Yuji Shinano
Jan Merlin Viernickel
Matthias Walter
Fabian Wegscheider
Jonas T. Witt
Jakob Witzig
ZIB-Report
18-26
eng
uncontrolled
constraint integer programming
eng
uncontrolled
linear programming
eng
uncontrolled
mixed-integer linear programming
eng
uncontrolled
mixed-integer nonlinear programming
eng
uncontrolled
optimization solver
eng
uncontrolled
branch-and-cut
eng
uncontrolled
branch-and-price
eng
uncontrolled
column generation framework
eng
uncontrolled
parallelization
eng
uncontrolled
mixed-integer semidefinite programming
eng
uncontrolled
Steiner tree optimization
NUMERICAL ANALYSIS
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Gamrath, Gerald
Gleixner, Ambros
Gottwald, Robert
Hendel, Gregor
Koch, Thorsten
Miltenberger, Matthias
Rehfeldt, Daniel
Serrano, Felipe
Shinano, Yuji
Vigerske, Stefan
Müller, Benjamin
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
Siemens
Eifler, Leon
MODAL-Gesamt
Schlösser, Franziska
Plan4res
https://opus4.kobv.de/opus4-zib/files/6936/scipopt-60.pdf
9338
2023
eng
conferenceobject
0
--
--
--
On the state of QUBO solving
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.
Operations Research Proceedings 2023
yes
accepted for publication
2023-12-11
publish
Thorsten Koch
Janina Zittel
Daniel Rehfeldt
Yuji Shinano
Koch, Thorsten
Rehfeldt, Daniel
Shinano, Yuji
MODAL-SynLab
MODAL-Gesamt
Applied Algorithmic Intelligence Methods
9405
2023
eng
1
21
2
49
article
0
--
--
--
Enabling research through the SCIP optimization suite 8.0
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.
ACM Transactions on Mathematical Software
10.1145/3585516
yes
publish
Ksenia Bestuzheva
Christoph Spiegel
Mathieu Besançon
Wei-Kun Chen
Antonia Chmiela
Tim Donkiewicz
Jasper Doornmalen
Leon Eifler
Oliver Gaul
Gerald Gamrath
Ambros Gleixner
Leona Gottwald
Christoph Graczyk
Katrin Halbig
Alexander Hoen
Christopher Hojny
Rolf Hulst
Thorsten Koch
Marco Lübbecke
Stephen J. Maher
Frederic Matter
Erik Mühmer
Benjamin Müller
Marc Pfetsch
Daniel Rehfeldt
Steffan Schlein
Franziska Schlösser
Felipe Serrano
Yuji Shinano
Boro Sofranac
Mark Turner
Stefan Vigerske
Fabian Wegscheider
Philipp Wellner
Dieter Weninger
Jakob Witzig
Gamrath, Gerald
Gleixner, Ambros
Koch, Thorsten
Rehfeldt, Daniel
Serrano, Felipe
Shinano, Yuji
Vigerske, Stefan
Müller, Benjamin
MODAL-SynLab
Eifler, Leon
MODAL-Gesamt
Schlösser, Franziska
Turner, Mark Ruben
Chmiela, Antonia
Bestuzheva, Ksenia
Šofranac, Boro
AI in Society, Science, and Technology
Graczyk, Christoph
Hoen, Alexander