@misc{RiedmuellerBuchholzZittel2025, author = {Riedm{\"u}ller, Stephanie and Buchholz, Annika and Zittel, Janina}, title = {Enhancing Multi-Energy Modeling: The Role of Mixed-Integer Optimization Decisions}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-100329}, year = {2025}, abstract = {The goal to decarbonize the energy sector has led to increased research in modeling and optimizing multi-energy systems. One of the most promising and popular techniques for modeling and solving (multi-)energy optimization problems is (multi-objective) mixed-integer programming, valued for its ability to represent the complexities of integrated energy systems. While the literature often focuses on deriving mathematical formulations and parameter settings, less attention is given to critical post-formulation decisions. Modeling multi-energy systems as mixed-integer linear optimization programs demands decisions across multiple degrees of freedom. Key steps include reducing a real-world multi energy network into an abstract topology, defining variables, formulating the relevant (in-)equalities to represent technical requirements, setting (multiple) objectives, and integrating these elements into a mixed-integer program (MIP). However, with these elements fixed, the specific transformation of the abstract topology into a graph structure and the construction of the MIP remain non-uniquely. These choices can significantly impact user-friendliness, problem size, and computational efficiency, thus affecting the feasibility and efficiency of modeling efforts. In this work, we identify and analyze the additional degrees of freedom and describe two distinct approaches to address them. The approaches are compared regarding mathematical equivalence, suitability for solution algorithms, and clarity of the underlying topology. A case study on a realistic subarea of Berlin's district heating network involving tri-objective optimization for a unit commitment problem demonstrates the practical significance of these decisions. By highlighting these critical yet often overlooked aspects, our work equips energy system modelers with insights to improve computational efficiency, scalability, and interpretability in their optimization efforts, ultimately enhancing the practicality and effectiveness of multi-energy system models.}, language = {en} } @misc{PedersenLindnerRehfeldtetal.2025, author = {Pedersen, Jaap and Lindner, Niels and Rehfeldt, Daniel and Koch, Thorsten}, title = {Comparing Branching Rules for the Quota Steiner Tree Problem with Interference}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-101250}, year = {2025}, abstract = {Branching decisions play a crucial role in branch-and-bound algorithms for solving combinatorial optimization problems. In this paper, we investigate several branching rules applied to the Quota Steiner Tree Problem with Interference (QSTPI). The Quota Steiner Tree Problem (QSTP) generalizes the classical Steiner Tree Problem (STP) in graphs by seeking a minimum-cost tree that connects a subset of profit-associated vertices to meet a given quota. The extended version, QSTPI, introduces interference among vertices: Selecting certain vertices simultaneously reduces their individual contributions to the overall profit. This problem arises, for example, in positioning and connecting wind turbines, where turbines possibly shadow other turbines, reducing their energy yield. While exact solvers for standard STP-related problems often rely heavily on reduction techniques and cutting-plane methods - rarely generating large branch-and-bound trees - experiments reveal that large instances of QSTPI require significantly more branching to compute provably optimal solutions. In contrast to branching on variables, we utilize the combinatorial structure of the QSTPI by branching on the graph's vertices. We adapt classical and problem-specific branching rules and present a comprehensive computational study comparing the effectiveness of these branching strategies.}, language = {en} } @misc{KempkeKoch2025, author = {Kempke, Nils-Christian and Koch, Thorsten}, title = {A GPU accelerated variant of Schroeppel-Shamir's algorithm for solving the market split problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-100554}, year = {2025}, abstract = {The market split problem (MSP), introduced by Cornu{\´e}jols and Dawande (1998), is a challenging binary optimization problem that performs poorly on state-of-the-art linear programming-based branch-and-cut solvers. We present a novel algorithm for solving the feasibility version of this problem, derived from Schroeppel-Shamir's algorithm for the one-dimensional subset sum problem. Our approach is based on exhaustively enumerating one-dimensional solutions of MSP and utilizing GPUs to evaluate candidate solutions across the entire problem. The resulting hybrid CPU-GPU implementation efficiently solves instances with up to 10 constraints and 90 variables. We demonstrate the algorithm's performance on benchmark problems, solving instances of size (9, 80) in less than fifteen minutes and (10, 90) in up to one day.}, language = {en} } @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} } @inproceedings{RiedmuellerBuchholzZittel2025, author = {Riedm{\"u}ller, Stephanie and Buchholz, Annika and Zittel, Janina}, title = {Enhancing Multi-Energy Modeling: The Role of Mixed-Integer Optimization Decisions}, booktitle = {The 38th International Conference on Efficiency, Cost, Optimization, Simulation and Environmental Impact of Energy Systems - ECOS 2025}, arxiv = {http://arxiv.org/abs/2505.14492}, year = {2025}, abstract = {The goal to decarbonize the energy sector has led to increased research in modeling and optimizing multi-energy systems. One of the most promising and popular techniques for modeling and solving (multi-)energy optimization problems is (multi-objective) mixed-integer programming, valued for its ability to represent the complexities of integrated energy systems. While the literature often focuses on deriving mathematical formulations and parameter settings, less attention is given to critical post-formulation decisions. Modeling multi-energy systems as mixed-integer linear optimization programs demands decisions across multiple degrees of freedom. Key steps include reducing a real-world multi energy network into an abstract topology, defining variables, formulating the relevant (in-)equalities to represent technical requirements, setting (multiple) objectives, and integrating these elements into a mixed-integer program (MIP). However, with these elements fixed, the specific transformation of the abstract topology into a graph structure and the construction of the MIP remain non-uniquely. These choices can significantly impact user-friendliness, problem size, and computational efficiency, thus affecting the feasibility and efficiency of modeling efforts. In this work, we identify and analyze the additional degrees of freedom and describe two distinct approaches to address them. The approaches are compared regarding mathematical equivalence, suitability for solution algorithms, and clarity of the underlying topology. A case study on a realistic subarea of Berlin's district heating network involving tri-objective optimization for a unit commitment problem demonstrates the practical significance of these decisions. By highlighting these critical yet often overlooked aspects, our work equips energy system modelers with insights to improve computational efficiency, scalability, and interpretability in their optimization efforts, ultimately enhancing the practicality and effectiveness of multi-energy system models.}, language = {en} } @misc{MehlLindnerBartoszuketal.2025, author = {Mehl, Lukas and Lindner, Niels and Bartoszuk, Karolina and Zittel, Janina}, title = {Prototypical warm-starts for demand-robust LP-based energy system optimization}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-101242}, year = {2025}, abstract = {The expressiveness of energy system optimization models (ESOMs) depends on a multitude of exogenous parameters. For example, sound estimates of the future energy demand are essential to enable qualified decisions on long-term investments. However, the enormous demand fluctuations even on a fine-grained scale diminish the computational performance of large-scale ESOMs. We therefore propose a clustering-and-decomposition method for linear programming based ESOMs that first identifies and solves prototypical demand scenarios with the dual simplex algorithm, and then composes dual optimal prototype bases to a warm-start basis for the full model. We evaluate the feasibility and computational efficiency our approach on a real-world case study, using a sector-coupled ESOM with hourly resolution for the Berlin-Brandenburg area in Germany, based on the oemof framework.}, language = {en} } @misc{RiedmuellerZittelKoch2025, author = {Riedm{\"u}ller, Stephanie and Zittel, Janina and Koch, Thorsten}, title = {Warm-starting Strategies in Scalarization Methods for Multi-Objective Optimization}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-101073}, year = {2025}, abstract = {We explore how warm-starting strategies can be integrated into scalarization-based approaches for multi-objective optimization in (mixed) integer linear programming. Scalarization methods remain widely used classical techniques to compute Pareto-optimal solutions in applied settings. They are favored due to their algorithmic simplicity and broad applicability across continuous and integer programs with an arbitrary number of objectives. While warm-starting has been applied in this context before, a systematic methodology and analysis remain lacking. We address this gap by providing a theoretical characterization of warm-starting within scalarization methods, focusing on the sequencing of subproblems. However, optimizing the order of subproblems to maximize warm-start efficiency may conflict with alternative criteria, such as early identification of infeasible regions. We quantify these trade-offs through an extensive computational study.}, language = {en} } @incollection{GotzesBuchholzKallrathetal.2025, author = {Gotzes, Uwe and Buchholz, Annika and Kallrath, Josef and Lindner, Niels and Koch, Thorsten}, title = {Flexible Pooling Pattern Design with Integer Programming}, volume = {226}, booktitle = {Theory, Algorithms and Experiments in Applied Optimization. In Honor of the 70th Birthday of Panos Pardalos}, publisher = {Springer}, year = {2025}, abstract = {Sample pooling has the potential to significantly enhance large-scale screening procedures, especially in scenarios like the COVID-19 pandemic, where rapid and widespread PCR testing has been crucial. Efficient strategies are essential to increase the testing capacity, i.e., the number of tests that can be processed within a given timeframe. Non-adaptive pooling strategies can further streamline the testing process by reducing the required testing rounds. In contrast to adaptive strategies, where subsequent tests depend on prior results, non-adaptive pooling processes all samples in a single round, eliminating the need for sequential retesting and reducing delays. This paper presents a highly flexible method based on integer programming to design optimized pooling patterns suitable for various applications, including medical diagnostics and quality control in industrial production. Using coronavirus testing as a case study, we formulate and solve optimization and satisfiability models that compute efficient pool designs. Our optimized pooling does not only increase testing capacity, but also accelerates the testing process and reduces overall costs. The proposed method is adaptable and can be seamlessly integrated into automated testing systems.}, language = {en} } @article{ZhouChenPengetal.2025, author = {Zhou, Lei and Chen, Ying and Peng, Hanqiu and Koch, Thorsten}, title = {Is innovation slowing down? Insights from the AIMS framework of patent values}, volume = {280}, journal = {Expert Systems with Applications}, doi = {10.1016/j.eswa.2025.127355}, pages = {127355}, year = {2025}, abstract = {Amidst the unprecedented expansion of scientific and technological knowledge over the past century, concerns persist regarding a slowdown in innovation. To address this, we introduce the AIMS framework, which categorizes patents into four types—Aurora, Invisible, Mirage, and Success—based on their respective inherent scientific values and market-recognized economic values. Utilizing USPTO patent and citation data from 1976 to 2022, our analysis reveals an increasing volume of patent issuances but a concerning dilution in scientific quality starting in the 2000s. This trend is primarily attributed to the rise of low scientific value patents—categorized as Mirage and Invisible—and a modest decline in high-impact scientific patents—categorized as Success and Aurora. Meanwhile, the economic value of patents has risen, especially noted with the growth in Mirage patents since the 2010s, indicating a shift towards strategies that prioritize market-driven patenting. This study highlights the evolving nature of patents from mere indicators of scientific innovation to strategic tools for market dominance, providing an alternative understanding of patent value and its implications for firms' strategic decisions over patent issuance across different sectors.}, language = {en} } @article{RiedmuellerKoch2025, author = {Riedm{\"u}ller, Stephanie and Koch, Thorsten}, title = {Exact Objective Space Contraction for the Preprocessing of Multi-objective Integer Programs}, arxiv = {http://arxiv.org/abs/2512.01535}, year = {2025}, abstract = {Solving integer optimization problems with large or widely ranged objective coefficients can lead to numerical instability and increased runtimes. When the problem also involves multiple objectives, the impact of the objective coefficients on runtimes and numerical issues multiplies. We address this issue by transforming the coefficients of linear objective functions into smaller integer coefficients. To the best of our knowledge, this problem has not been defined before. Next to a straightforward scaling heuristic, we introduce a novel exact transformation approach for the preprocessing of multi-objective binary problems. In this exact approach, the large or widely ranged integer objective coefficients are transformed into the minimal integer objective coefficients that preserve the dominance relation of the points in the objective space. The transformation problem is solved with an integer programming formulation with an exponential number of constraints. We present a cutting-plane algorithm that can efficiently handle the problem size. In a first computational study, we analyze how often and in which settings the transformation actually leads to smaller coefficients. In a second study, we evaluate how the exact transformation and a typical scaling heuristic, when used as preprocessing, affect the runtime and numerical stability of the Defining Point Algorithm.}, language = {en} } @article{ChenKochPengetal.2025, author = {Chen, Ying and Koch, Thorsten and Peng, Hanqui and Zhang, Hongrui}, title = {Benchmarking of Quantum and Classical Computing in Large-Scale Dynamic Portfolio Optimization Under Market Frictions}, arxiv = {http://arxiv.org/abs/2502.05226}, year = {2025}, abstract = {Quantum computing is poised to transform the financial industry, yet its advantages over traditional methods have not been evidenced. As this technology rapidly evolves, benchmarking is essential to fairly evaluate and compare different computational strategies. This study presents a challenging yet solvable problem of large-scale dynamic portfolio optimization under realistic market conditions with frictions. We frame this issue as a Quadratic Unconstrained Binary Optimization (QUBO) problem, compatible with digital computing and ready for quantum computing, to establish a reliable benchmark. By applying the latest solvers to real data, we release benchmarks that help verify true advancements in dynamic trading strategies, either quantum or digital computing, ensuring that reported improvements in portfolio optimization are based on robust, transparent, and comparable metrics.}, language = {en} } @article{PetkovicZittel2025, author = {Petkovic, Milena and Zittel, Janina}, title = {Leveraging Transfer Learning to Overcome Data Limitations in Czochralski Crystal Growth}, volume = {8}, journal = {Advanced Theory and Simulations}, number = {11}, doi = {10.1002/adts.202500677}, year = {2025}, language = {en} } @misc{TateiwaShinanoYasudaetal.2021, 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}, year = {2021}, 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} } @misc{HosodaMaherShinanoetal.2023, 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}, year = {2023}, 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} } @misc{FujiiItoKimetal.2021, 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}, year = {2021}, 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{FujiiKimKojimaetal.2023, 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}, year = {2023}, 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{FujiiItoKimetal.2022, author = {Fujii, Koichi and Ito, Naoki and Kim, Sunyoung and Kojima, Masakazu and Shinano, Yuji and Toh, Kim-Chuan}, title = {大規模二次割当問題への挑戦}, journal = {統計数理研究所共同研究リポート 453 最適化:モデリングとアルゴリズム33 2022年3月 「大規模二次割当問題への挑戦」 p.84-p.92}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-86779}, year = {2022}, abstract = {二次割当問題は線形緩和が弱いことが知られ,強化のため多様な緩和手法が考案されているが,その一つである二重非負値計画緩和( DNN 緩和)及びその解法として近年研究が進んでいるニュートン・ブラケット法を紹介し,それらに基づく分枝限定法の実装及び数値実験結果について報告する.}, language = {ja} } @misc{Shinano2021, author = {Shinano, Yuji}, title = {UG - Ubiquity Generator Framework v1.0.0beta}, doi = {10.12752/8521}, year = {2021}, 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{RehfeldtKoch2020, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {On the exact solution of prize-collecting Steiner tree problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-78174}, year = {2020}, language = {en} } @article{XuChenZhangetal.2022, author = {Xu, Xiaofei and Chen, Ying and Zhang, Ge and Koch, Thorsten}, title = {Modeling Functional Time Series and Mixed-Type Predictors With Partially Functional Autoregressions}, volume = {42}, journal = {Journal of Business \& Economic Statistics}, number = {2}, publisher = {Informa UK Limited}, issn = {0735-0015}, doi = {https://doi.org/10.1080/07350015.2021.2011299}, pages = {349 -- 366}, year = {2022}, language = {en} } @inproceedings{HadjidimitriouLippiNastroetal.2024, author = {Hadjidimitriou, Natalia Selini and Lippi, Marco and Nastro, Raffaele and Koch, Thorsten and Mamei, Marco}, title = {Short-Term Forecasting of Energy Consumption and Production in Local Energy Communities}, booktitle = {2024 32nd International Conference on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE)}, publisher = {IEEE}, doi = {10.1109/WETICE64632.2024.00022}, pages = {74 -- 79}, year = {2024}, language = {en} } @misc{Mexi2021, type = {Master Thesis}, author = {Mexi, Gioni}, title = {New Ideas for the Feasibility Pump: Using Multiple Reference Vectors}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-83724}, year = {2021}, language = {en} } @article{YokoyamaKamadaShinanoetal.2021, 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}, volume = {229}, journal = {Energy}, doi = {https://doi.org/10.1016/j.energy.2021.120343}, year = {2021}, 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} } @article{LenzBecker2022, author = {Lenz, Ralf and Becker, Kai-Helge}, title = {Optimization of Capacity Expansion in Potential-driven Networks including Multiple Looping - A comparison of modelling approaches}, volume = {44}, journal = {OR Spectrum}, doi = {https://doi.org/10.1007/s00291-021-00648-7}, pages = {179 -- 224}, year = {2022}, abstract = {In commodity transport networks such as natural gas, hydrogen and water networks, flows arise from nonlinear potential differences between the nodes, which can be represented by so-called "potential-driven" network models. When operators of these networks face increasing demand or the need to handle more diverse transport situations, they regularly seek to expand the capacity of their network by building new pipelines parallel to existing ones ("looping"). The paper introduces a new mixed-integer non-linear programming (MINLP) model and a new non-linear programming (NLP) model and compares these with existing models for the looping problem and related problems in the literature, both theoretically and experimentally. On this basis, we give recommendations about the circumstances under which a certain model should be used. In particular, it turns out that one of our novel models outperforms the existing models. Moreover, the paper is the first to include the practically relevant option that a particular pipeline may be looped several times.}, language = {en} } @article{CardereraPokutta2020, author = {Carderera, Alejandro and Pokutta, Sebastian}, title = {Second-order Conditional Gradient Sliding}, year = {2020}, abstract = {Constrained second-order convex optimization algorithms are the method of choice when a high accuracy solution to a problem is needed, due to their local quadratic convergence. These algorithms require the solution of a constrained quadratic subproblem at every iteration. We present the \emph{Second-Order Conditional Gradient Sliding} (SOCGS) algorithm, which uses a projection-free algorithm to solve the constrained quadratic subproblems inexactly. When the feasible region is a polytope the algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations. Once in the quadratic regime the SOCGS algorithm requires O(log(log1/ε)) first-order and Hessian oracle calls and O(log(1/ε)log(log1/ε)) linear minimization oracle calls to achieve an ε-optimal solution. This algorithm is useful when the feasible region can only be accessed efficiently through a linear optimization oracle, and computing first-order information of the function, although possible, is costly.}, language = {en} } @article{MathieuCardereraPokutta2022, author = {Mathieu, Besan{\c{c}}on and Carderera, Alejandro and Pokutta, Sebastian}, title = {FrankWolfe.jl: a high-performance and flexible toolbox for Frank-Wolfe algorithms and Conditional Gradients}, volume = {34}, journal = {INFORMS Journal on Computing}, number = {5}, doi = {10.1287/ijoc.2022.1191}, pages = {2383 -- 2865}, year = {2022}, abstract = {We present FrankWolfe.jl, an open-source implementation of several popular Frank-Wolfe and conditional gradients variants for first-order constrained optimization. The package is designed with flexibility and high performance in mind, allowing for easy extension and relying on few assumptions regarding the user-provided functions. It supports Julia's unique multiple dispatch feature, and it interfaces smoothly with generic linear optimization formulations using MathOptInterface.jl.}, language = {en} } @article{RehfeldtKoch2023, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {Implications, Conflicts, and Reductions for Steiner Trees}, volume = {197}, journal = {Mathematical Programming}, publisher = {Springer}, doi = {10.1007/s10107-021-01757-5}, pages = {903 -- 966}, year = {2023}, language = {en} } @misc{KempkeRehfeldtKoch2024, author = {Kempke, Nils-Christian and Rehfeldt, Daniel and Koch, Thorsten}, title = {A Massively Parallel Interior-Point-Method for Arrowhead Linear Programs}, issn = {1438-0064}, arxiv = {http://arxiv.org/abs/2412.07731}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-98829}, year = {2024}, abstract = {In practice, non-specialized interior point algorithms often cannot utilize the massively parallel compute resources offered by modern many- and multi-core compute platforms. However, efficient distributed solution techniques are required, especially for large-scale linear programs. This article describes a new decomposition technique for systems of linear equations implemented in the parallel interior-point solver PIPS-IPM++. The algorithm exploits a matrix structure commonly found in optimization problems: a doubly-bordered block-diagonal or arrowhead structure. This structure is preserved in the linear KKT systems solved during each iteration of the interior-point method. We present a hierarchical Schur complement decomposition that distributes and solves the linear optimization problem; it is designed for high-performance architectures and scales well with the availability of additional computing resources. The decomposition approach uses the border constraints' locality to decouple the factorization process. Our approach is motivated by large-scale unit-commitment problems. We demonstrate the performance of our method on a set of mid-to large-scale instances, some of which have more than 10^9 nonzeros in their constraint matrix.}, language = {en} } @article{FujiiKimKojimaetal.2024, 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}, journal = {Optimization Letters}, publisher = {Springer Science and Business Media LLC}, issn = {1862-4472}, doi = {10.1007/s11590-024-02157-2}, year = {2024}, 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. Despite this difficulty, it is imperative to decrease the gap in order to ultimately solve the BQOP exactly. To effectively improve the LB, we propose an efficient BB method that incorporates a doubly nonnegative relaxation, the orbit branching and the isomorphism pruning. With this BB method, a new LB with 1.25\% gap is successfully obtained, and computing an LB with gap is shown to be still quite difficult.}, language = {en} } @article{HosodaMaherShinanoetal.2024, 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}, volume = {165}, journal = {Computers \& Operations Research}, publisher = {Elsevier BV}, issn = {0305-0548}, doi = {10.1016/j.cor.2024.106570}, year = {2024}, 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} } @misc{YuekselErguenLitzelPeng2024, author = {Yueksel-Erguen, Inci and Litzel, Ida and Peng, Hanqiu}, title = {Integrating Large Citation Datasets}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-98033}, year = {2024}, abstract = {This paper explores methods for building a comprehensive citation graph using big data techniques to evaluate scientific impact more accurately. Traditional citation metrics have limitations, and this work investigates merging large citation datasets to create a more accurate picture. Challenges of big data, like inconsistent data formats and lack of unique identifiers, are addressed through deduplication efforts, resulting in a streamlined and reliable merged dataset with over 119 million records and 1.4 billion citations. We demonstrate that merging large citation datasets builds a more accurate citation graph facilitating a more robust evaluation of scientific impact.}, 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{VuKochXu2024, author = {Vu, Thi Huong and Koch, Thorsten and Xu, Hong-Kun}, title = {The gradient projection method: Is the Polyak adaptive stepsize rule optimal?}, year = {2024}, abstract = {Not always! This is our answer to the question of whether the Polyak adaptive stepsize rule in the gradient projection method is optimal. The answer is based on revisiting the subgradient projection method by Polyak [USSR Computational Mathematics and Mathematical Physics 9 (1969)] for smooth and convex minimization problems where the objective function possesses a geometric property called flatness. Our results show that the method can be more flexible (the effective range for the parameter controlling the stepsize can be wider) and have sharper convergence rates. Applications to split feasibility/equality problems are presented, deriving for the first time the O(1/k) rate of convergence for the adaptive CQ method. A theoretical guarantee of the linear convergence of the gradient descent method with adaptive stepsizes for Google PageRank is provided. At the same time, numerical experiments are designed to spot the ``optimal" stepsize and to compare with other basic gradient methods.}, language = {en} } @inproceedings{HadjidimitriouKochLippietal.2024, author = {Hadjidimitriou, Natalia Selini and Koch, Thorsten and Lippi, Marco and Petkovic, Milena and Mamei, Marco}, title = {Analysis of the Impact of COVID-19 and Russo-Ukraine War on Natural Gas Flow Using Time Series Forecasting}, booktitle = {Preceedings of the 16th International Conference on Management of Digital Ecosystems}, year = {2024}, language = {en} } @misc{Kunt2023, type = {Master Thesis}, author = {Kunt, Tim}, title = {The n-Queens Problem in Higher Dimensions}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-96468}, pages = {84}, year = {2023}, abstract = {How many mutually non-attacking queens can be placed on a d-dimensional chessboard of size n? The n-queens problem in higher dimensions is a generalization of the well-known n-queens problem. We provide a comprehensive overview of theoretical results, bounds, solution methods, and the interconnectivity of the problem within topics of discrete optimization and combinatorics. We present an integer programming formulation of the n-queens problem in higher dimensions and several strengthenings through additional valid inequalities. Compared to recent benchmarks, we achieve a speedup in computational time between 15-70x over all instances of the integer programs. Our computational results prove optimality of certificates for several large instances. Breaking additional, previously unsolved instances with the proposed methods is likely possible. On the primal side, we further discuss heuristic approaches to constructing solutions that turn out to be optimal when compared to the IP. We conclude with preliminary results on the number and density of the solutions.}, language = {en} } @misc{RiedmuellerRivettaZittel2024, author = {Riedm{\"u}ller, Stephanie and Rivetta, Fabian and Zittel, Janina}, title = {Long-Term Multi-Objective Optimization for Integrated Unit Commitment and Investment Planning for District Heating Networks}, issn = {1438-0064}, doi = {10.1007/978-3-031-92575-7_33}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-97804}, year = {2024}, abstract = {The need to decarbonize the energy system has intensified the focus on district heating networks in urban and suburban areas. Therefore, exploring transformation pathways with reasonable trade-offs between economic viability and environmental goals became necessary. We introduce a network-flow-based model class integrating unit commitment and long-term investment planning for multi-energy systems. While the integration of unit commitment and investment planning has been applied to multi-energy systems, a formal introduction and suitability for the application of long-term portfolio planning of an energy provider on an urban scale has yet to be met. Based on mixed integer linear programming, the model bridges the gap between overly detailed industrial modeling tools not designed for computational efficiency at scale and rather abstract academic models. The formulation is tested on Berlin's district heating network. Hence, the challenge lies in a large number of variables and constraints and the coupling of time steps, for example, through investment decisions. A case study explores different solutions on the Pareto front defined by optimal trade-offs between minimizing costs and emissions through a lexicographic optimization approach. The resulting solution catalog can provide decision-makers valuable insights into feasible transformation pathways, highlighting distinctions between robust and target-dependent investments.}, language = {en} } @misc{LindnerBartoszukDebguptaetal.2024, author = {Lindner, Niels and Bartoszuk, Karolina and Debgupta, Srinwanti and Gering, Marie-Claire and Muschner, Christoph and Zittel, Janina}, title = {Warm-starting modeling to generate alternatives for energy transition paths in the Berlin-Brandenburg area}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-97835}, year = {2024}, abstract = {Energy system optimization models are key to investigate energy transition paths towards a decarbonized future. Since this approach comes with intrinsic uncertainties, it is insufficient to compute a single optimal solution assuming perfect foresight to provide a profound basis for decision makers. The paradigm of modeling to generate alternatives enables to explore the near-optimal solution space to a certain extent. However, large-scale energy models require a non-negligible computation time to be solved. We propose to use warm start methods to accelerate the process of finding close-to-optimal alternatives. In an extensive case study for the energy transition of the Berlin-Brandenburg area, we make use of the sector-coupled linear programming oemof-B3 model to analyze a scenario for the year 2050 with a resolution of one hour and 100\% reduction of greenhouse gas emissions. We demonstrate that we can actually achieve a significant computational speedup.}, language = {en} } @misc{Le2024, author = {Le, Thi Thai}, title = {Effect of viscous forces on the interface stability of a tangential-velocity discontinuity in compressible fluids}, journal = {Journal}, year = {2024}, abstract = {Compressible flows are prevalent in natural and technological processes, particularly in the energy transition to renewable energy systems. Consequently, extensive research has focused on understanding the stability of tangential--velocity discontinuity in compressible media. Despite recent advancements that address industrial challenges more realistically, many studies have ignored viscous stress tensors' impact, leading to inaccuracies in predicting interface stability. This omission becomes critical, especially in high Reynolds or low Mach number flows, where viscous forces dissipate kinetic energy across interfaces, affect total energy dissipation, and dampen flow instabilities. Our work is thus motivated to analyze the viscosity force effect by including the viscous stress tensor terms in the motion equations. Our results show that by considering the effect of viscous forces, the tangential-velocity discontinuity interface is constantly destabilized for the entire range of the Mach number.}, language = {en} } @inproceedings{MuschnerYuekselErguenGeringetal.2024, author = {Muschner, Christoph and Y{\"u}ksel-Erg{\"u}n, Inci and Gering, Marie-Claire and Bartoszuk, Karolina and Haas, Sabine and Zittel, Janina}, title = {Sensitivity analysis of the energy transition path in the Berlin-Brandenburg area to uncertainties in operational and investment costs of diverse energy production technologies}, booktitle = {37th International Conference on Efficiency, Cost, Optimization, Simulation and Environmental Impact of Energy Systems (ECOS 2024)}, doi = {10.52202/077185-0115}, pages = {1339 -- 1350}, year = {2024}, abstract = {The investigation of energy transition paths toward a sustainable and decarbonized future under uncertainty is a critical aspect of contemporary energy planning and policy development. There are numerous methods for analysing uncertainties and sensitivities and many studies on sustainable transformation paths, but there is a lack of combined application to relevant use-cases. In this study, we investigate the sensitivity of energy transition paths to uncertainties in operational and investment costs of power plants in the metropolitan area of Berlin and its rural surroundings. By employing the linear programming energy system model oemof-B3, we extensively focus on the system's energy technologies, such as wind turbines, photovoltaics, hydro and combustion plants, and energy storages. Greenhouse gas reduction and electrification rates per commodity are realized by selected constraints. Our research aims to discern how investments in energy production capacities are influenced by uncertainties of other energy technologies' investment and operational costs in the system. We apply a quantitative approach to investigate such interdependencies of cost variations and their impact on long-term energy planning. Thus, the analysis sheds light on the robustness of energy transition paths in the face of these uncertainties. The region Berlin-Brandenburg serves as a case study and thus reflects on the present space conflicts to meet energy demands in urban and suburban areas and their rural surroundings. An electricity-intensive scenario is selected that assumes a 100 \% reduction in greenhouse gas emissions by 2050. With the results of the case study, we show how our approach enables rural and metropolitan decision-makers to collaborate in achieving sustainable energy. Decision-making in long-term energy planning can be made more robust and flexible by acknowledging the identified sensitivities and enable such regions better to navigate challenges and uncertainties associated with sustainable energy planning.}, language = {en} } @article{PedersenLeKochetal.2024, author = {Pedersen, Jaap and Le, Thi Thai and Koch, Thorsten and Zittel, Janina}, title = {Optimal discrete pipe sizing for tree-shaped CO2 networks}, volume = {46}, journal = {OR Spectrum}, doi = {10.1007/s00291-024-00773-z}, pages = {1163 -- 1187}, year = {2024}, abstract = {For industries like the cement industry, switching to a carbon-neutral production process is impossible. They must rely on carbon capture, utilization and storage (CCUS) technologies to reduce their production processes' inevitable carbon dioxide (CO2) emissions. For transporting continuously large amounts of CO2, utilizing a pipeline network is the most effective solution; however, building such a network is expensive. Therefore minimizing the cost of the pipelines to be built is extremely important to make the operation financially feasible. In this context, we investigate the problem of finding optimal pipeline diameters from a discrete set of diameters for a tree-shaped network transporting captured CO2 from multiple sources to a single sink. The general problem of optimizing arc capacities in potential-based fluid networks is already a challenging mixed-integer nonlinear optimization problem. The problem becomes even more complex when adding the highly sensitive nonlinear behavior of CO2 regarding temperature and pressure changes. We propose an iterative algorithm splitting the problem into two parts: a) the pipe-sizing problem under a fixed supply scenario and temperature distribution and b) the thermophysical modeling, including mixing effects, the Joule-Thomson effect, and heat exchange with the surrounding environment. We demonstrate the effectiveness of our approach by applying our algorithm to a real-world network planning problem for a CO2 network in Western Germany. Further, we show the robustness of the algorithm by solving a large artificially created set of network instances.}, language = {en} } @article{VanBulckGoossensClarneretal.2024, author = {Van Bulck, David and Goossens, Dries and Clarner, Jan-Patrick and Dimitsas, Angelos and Fonseca, Georg H. G. and Lamas-Fernandez, Carlos and Lester, Martin Mariusz and Pedersen, Jaap and Phillips, Antony E. and Rosati, Roberto Maria}, title = {Which algorithm to select in sports timetabling?}, volume = {318}, journal = {European Journal of Operational Research}, number = {2}, arxiv = {http://arxiv.org/abs/2309.03229}, doi = {10.1016/j.ejor.2024.06.005}, pages = {575 -- 591}, year = {2024}, abstract = {Any sports competition needs a timetable, specifying when and where teams meet each other. The recent International Timetabling Competition (ITC2021) on sports timetabling showed that, although it is possible to develop general algorithms, the performance of each algorithm varies considerably over the problem instances. This paper provides a problem type analysis for sports timetabling, resulting in powerful insights into the strengths and weaknesses of eight state-of-the-art algorithms. Based on machine learning techniques, we propose an algorithm selection system that predicts which algorithm is likely to perform best based on the type of competition and constraints being used (i.e., the problem type) in a given sports timetabling problem instance. Furthermore, we visualize how the problem type relates to algorithm performance, providing insights and possibilities to further enhance several algorithms. Finally, we assess the empirical hardness of the instances. Our results are based on large computational experiments involving about 50 years of CPU time on more than 500 newly generated problem instances.}, language = {en} } @misc{YuekselErguenKochZittel2024, author = {Yueksel-Erguen, Inci and Koch, Thorsten and Zittel, Janina}, title = {Mathematical optimization based flow scenario generation for operational analysis of European gas transport networks based on open data}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-95789}, year = {2024}, abstract = {The decarbonization of the European energy system demands a rapid and comprehensive transformation while securing energy supplies at all times. Still, natural gas plays a crucial role in this process. Recent unexpected events forced drastic changes in gas routes throughout Europe. Therefore, operational-level analysis of the gas transport networks and technical capacities to cope with these transitions using unconventional scenarios has become essential. Unfortunately, data limitations often hinder such analyses. To overcome this challenge, we propose a mathematical model-based scenario generator that enables operational analysis of the European gas network using open data. Our approach focuses on the consistent analysis of specific partitions of the gas transport network, whose network topology data is readily available. We generate reproducible and consistent node-based gas in/out-flow scenarios for these defined network partitions to enable feasibility analysis and data quality assessment. Our proposed method is demonstrated through several applications that address the feasibility analysis and data quality assessment of the German gas transport network. By using open data and a mathematical modeling approach, our method allows for a more comprehensive understanding of the gas transport network's behavior and assists in decision-making during the transition to decarbonization.}, language = {en} } @inproceedings{ZittelClarnerTawfiketal.2024, author = {Zittel, Janina and Clarner, Jan-Patrick and Tawfik, Christine and Dykes, Maxwell and Rivetta, Fabian and Riedm{\"u}ller, Stephanie}, title = {A multi-objective optimization strategy for district heating production portfolio planning}, booktitle = {37th International Conference on Efficiency, Cost, Optimization, Simulation and Environmental Impact of Energy Systems (ECOS 2024)}, doi = {10.52202/077185-0066}, pages = {764 -- 775}, year = {2024}, abstract = {The imperative to decarbonize energy systems has intensified the need for efficient transformations within the heating sector, with a particular focus on district heating networks. This study addresses this challenge by proposing a comprehensive optimization approach evaluated on the district heating network of the M{\"a}rkisches Viertel of Berlin. Our objective is to simultaneously optimize heat production with three targets: minimizing costs, minimizing CO2-emissions, and maximizing heat generation from Combined Heat and Power (CHP) plants for enhanced efficiency. To tackle this optimization problem, we employed a Mixed-Integer Linear Program (MILP) that encompasses the conversion of various fuels into heat and power, integration with relevant markets, and considerations for technical constraints on power plant operation. These constraints include startup and minimum downtime, activation costs, and storage limits. The ultimate goal is to delineate the Pareto front, representing the optimal trade-offs between the three targets. We evaluate variants of the 𝜖-constraint algorithm for their effectiveness in coordinating these objectives, with a simultaneous focus on the quality of the estimated Pareto front and computational efficiency. One algorithm explores solutions on an evenly spaced grid in the objective space, while another dynamically adjusts the grid based on identified solutions. Initial findings highlight the strengths and limitations of each algorithm, providing guidance on algorithm selection depending on desired outcomes and computational constraints. Our study emphasizes that the optimal choice of algorithm hinges on the density and distribution of solutions in the feasible space. Whether solutions are clustered or evenly distributed significantly influences algorithm performance. These insights contribute to a nuanced understanding of algorithm selection for multi-objective multi-energy system optimization, offering valuable guidance for future research and practical applications for planning sustainable district heating networks.}, language = {en} } @misc{CaoAndersonBoehmeetal.2023, author = {Cao, Karl-Kien and Anderson, Lovis and B{\"o}hme, Aileen and Breuer, Thomas and Buschmann, Jan and Fiand, Frederick and Frey, Ulrich and Fuchs, Benjamin and Kempe, Nils-Christian and von Krbek, Kai and Medjroubi, Wided and Riehm, Judith and Sasanpour, Shima and Simon, Sonja and Vanaret, Charlie and Wetzel, Manuel and Xiao, Mengzhu and Zittel, Janina}, title = {Evaluation of Uncertainties in Linear-Optimizing Energy System Models - Compendium}, journal = {DLR-Forschungsbericht}, number = {DLR-FB-2023-15}, doi = {10.57676/w2rq-bj85}, pages = {95}, year = {2023}, abstract = {F{\"u}r die Energiesystemforschung sind Software-Modelle ein Kernelement zur Analyse von Szenarien. Das Forschungsprojekt UNSEEN hatte das Ziel eine bisher unerreichte Anzahl an modellbasierten Energieszenarien zu berechnen, um Unsicherheiten - vor allem unter Nutzung linear optimierender Energiesystem-Modelle - besser bewerten zu k{\"o}nnen. Hierf{\"u}r wurden umfangreiche Parametervariationen auf Energieszenarien angewendet und das wesentliche methodische Hindernis in diesem Zusammenhang adressiert: die rechnerische Beherrschbarkeit der zu l{\"o}senden mathematischen Optimierungsprobleme. Im Vorl{\"a}uferprojekt BEAM-ME wurde mit der Entwicklung und Anwendung des Open-Source-L{\"o}sers PIPS-IPM++ die Grundlage f{\"u}r den Einsatz von High-Performance-Computing (HPC) zur L{\"o}sung dieser Modelle gelegt. In UNSEEN war dieser L{\"o}ser die zentrale Komponente eines Workflows, welcher zur Generierung, L{\"o}sung und multi-kriteriellen Bewertung von Energieszenarien auf dem Hochleistungscomputer JUWELS am Forschungszentrum J{\"u}lich implementiert wurde. Zur effizienten Generierung und Kommunikation von Modellinstanzen f{\"u}r Methoden der mathematischen Optimierung auf HPC wurde eine weitere Workflow-Komponente von der GAMS Software GmbH entwickelt: der Szenariogenerator. Bei der Weiterentwicklung von L{\"o}sungsalgorithmen f{\"u}r linear optimierende Energie-Systemmodelle standen gemischt-ganzzahlige Optimierungsprobleme im Fokus, welche f{\"u}r die Modellierung konkreter Infrastrukturen und Maßnahmen zur Umsetzung der Energiewende gel{\"o}st werden m{\"u}ssen. Die in diesem Zusammenhang stehenden Arbeiten zur Entwicklung von Algorithmen wurden von der Technischen Universit{\"a}t Berlin verantwortet. Bei Design und Implementierung dieser Methoden wurde sie vom Zuse Instituts Berlin unterst{\"u}tzt.}, language = {en} } @article{PedersenWeinandSyranidouetal.2024, author = {Pedersen, Jaap and Weinand, Jann Michael and Syranidou, Chloi and Rehfeldt, Daniel}, title = {An efficient solver for large-scale onshore wind farm siting including cable routing}, volume = {317}, journal = {European Journal of Operational Research}, number = {2}, arxiv = {http://arxiv.org/abs/2304.09658}, doi = {10.1016/j.ejor.2024.04.026}, pages = {616 -- 630}, year = {2024}, abstract = {Existing planning approaches for onshore wind farm siting and grid integration often do not meet minimum cost solutions or social and environmental considerations. In this paper, we develop an exact approach for the integrated layout and cable routing problem of onshore wind farm planning using the 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. In selected regions of Germany, the trade-offs between minimizing costs and landscape impact of onshore wind farm siting are investigated. Although our case studies 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, grid integration must be simultaneously optimized 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.}, language = {en} } @inproceedings{KiesslingVanaretAstudilloetal.2024, author = {Kiessling, David and Vanaret, Charlie and Astudillo, Alejandro and Decr{\´e}, Wilm and Swevers, Jan}, title = {An Almost Feasible Sequential Linear Programming Algorithm}, booktitle = {2024 European Control Conference (ECC), Stockholm, Sweden}, arxiv = {http://arxiv.org/abs/2401.13840}, doi = {10.23919/ECC64448.2024.10590864}, pages = {2328 -- 2335}, year = {2024}, abstract = {This paper proposes an almost feasible Sequential Linear Programming (afSLP) algorithm. In the first part, the practical limitations of previously proposed Feasible Sequential Linear Programming (FSLP) methods are discussed along with illustrative examples. Then, we present a generalization of FSLP based on a tolerance-tube method that addresses the shortcomings of FSLP. The proposed algorithm afSLP consists of two phases. Phase I starts from random infeasible points and iterates towards a relaxation of the feasible set. Once the tolerance-tube around the feasible set is reached, phase II is started and all future iterates are kept within the tolerance-tube. The novel method includes enhancements to the originally proposed tolerance-tube method that are necessary for global convergence. afSLP is shown to outperform FSLP and the state-of-the-art solver IPOPT on a SCARA robot optimization problem.}, language = {en} } @misc{PetkovicZakiyevaZittel2021, author = {Petkovic, Milena and Zakiyeva, Nazgul and Zittel, Janina}, title = {Statistical analysis and modeling for detecting regime changes in gas nomination time series}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82988}, year = {2021}, abstract = {As a result of the legislation for gas markets introduced by the European Union in 2005, separate independent companies have to conduct the transport and trading of natural gas. The current gas market of Germany, which has a market value of more than 54 billion USD, consists of Transmission System Operators (TSO), network users, and traders. Traders can nominate a certain amount of gas anytime and anywhere in the network. Such unrestricted access for the traders, on the other hand, increase the uncertainty in the gas supply management. Some customers' behaviors may cause abrupt structural changes in gas flow time series. In particular, it is a challenging task for the TSO operators to predict gas nominations 6 to 10 hours ahead. In our study, we aim to investigate the regime changes in the time series of nominations to predict the 6 to 10 hours ahead of gas nominations.}, language = {en} } @article{PetkovicChenGamrathetal.2022, author = {Petkovic, Milena and Chen, Ying and Gamrath, Inken and Gotzes, Uwe and Hadjidimitrou, Natalia Selini and Zittel, Janina and Xu, Xiaofei and Koch, Thorsten}, title = {A hybrid approach for high precision prediction of gas flows}, volume = {13}, journal = {Energy Systems}, doi = {10.1007/s12667-021-00466-4}, pages = {383 -- 408}, year = {2022}, abstract = {About 23\% of the German energy demand is supplied by natural gas. Additionally, for about the same amount Germany serves as a transit country. Thereby, the German network represents a central hub in the European natural gas transport network. The transport infrastructure is operated by transmissions system operators (TSOs). The number one priority of the TSOs is to ensure the security of supply. However, the TSOs have only very limited knowledge about the intentions and planned actions of the shippers (traders). Open Grid Europe (OGE), one of Germany's largest TSO, operates a high-pressure transport network of about 12,000 km length. With the introduction of peak-load gas power stations, it is of great importance to predict in- and out-flow of the network to ensure the necessary flexibility and security of supply for the German Energy Transition ("Energiewende"). In this paper, we introduce a novel hybrid forecast method applied to gas flows at the boundary nodes of a transport network. This method employs an optimized feature selection and minimization. We use a combination of a FAR, LSTM and mathematical programming to achieve robust high-quality forecasts on real-world data for different types of network nodes.}, language = {en} } @article{HillerSaitenmacherWalther2021, author = {Hiller, Benjamin and Saitenmacher, Ren{\´e} and Walther, Tom}, title = {Improved models for operation modes of complex compressor stations}, volume = {94}, journal = {Mathematical Methods of Operations Research}, doi = {https://doi.org/10.1007/s00186-021-00745-x}, pages = {171 -- 195}, year = {2021}, abstract = {We study combinatorial structures in large-scale mixed-integer (nonlinear) programming problems arising in gas network optimization. We propose a preprocessing strategy exploiting the observation that a large part of the combinatorial complexity arises in certain subnetworks. Our approach analyzes these subnetworks and the combinatorial structure of the flows within these subnetworks in order to provide alternative models with a stronger combinatorial structure that can be exploited by off-the-shelve solvers. In particular, we consider the modeling of operation modes for complex compressor stations (i.e., ones with several in- or outlets) in gas networks. We propose a refined model that allows to precompute tighter bounds for each operation mode and a number of model variants based on the refined model exploiting these tighter bounds. We provide a procedure to obtain the refined model from the input data for the original model. This procedure is based on a nontrivial reduction of the graph representing the gas flow through the compressor station in an operation mode. We evaluate our model variants on reference benchmark data, showing that they reduce the average running time between 10\% for easy instances and 46\% for hard instances. Moreover, for three of four considered networks, the average number of search tree nodes is at least halved, showing the effectivity of our model variants to guide the solver's search.}, language = {en} } @article{YokoyamaTakeuchiShinanoetal.2021, 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}, volume = {228}, journal = {Energy}, doi = {https://doi.org/10.1016/j.energy.2021.120505}, year = {2021}, 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{LeFukumoto2022, author = {Le, Thi Thai and Fukumoto, Yasuhide}, title = {Effect of depth discontinuity on interfacial stability of tangential-velocity discontinuity in shallow-water flow}, volume = {436}, journal = {Physics Letters A}, publisher = {ELSEVIER}, doi = {10.1016/j.physleta.2022.128073}, pages = {128073}, year = {2022}, abstract = {It is well known as the Kelvin-Helmholtz instability (KHI) that an interface of tangential velocity discontinuity is necessarily unstable, regardless of the velocity difference's strength. However, the KHI is suppressed for shallow water flows if the Froude number, defined by the ratio of the velocity difference to the gravity wave's speed, is sufficiently large. In this investigation, we examine the effect of the depth difference of two fluid layers on the KHI. The depth difference enhances instability. Given the Froude number in the instability range, the growth rate sensitively depends on the depth ratio and increases monotonically with the depth ratio difference from unity. The critical value of the Froude number for stabilization varies with the depth ratio and attains the minimum value √8 for equal depth. This behavior is verified by asymptotic analysis.}, language = {en} } @inproceedings{PedersenHoppmannBaumZitteletal.2022, author = {Pedersen, Jaap and Hoppmann-Baum, Kai and Zittel, Janina and Koch, Thorsten}, title = {Blending hydrogen into natural gas: An assessment of the capacity of the German gas grid}, booktitle = {Operations Research Proceedings 2021}, doi = {https://doi.org/10.1007/978-3-031-08623-6_28}, pages = {182 -- 187}, year = {2022}, abstract = {In the transition towards a pure hydrogen infrastructure, repurposing the existing natural gas infrastructure is considered. In this study, the maximal technically feasible injection of hydrogen into the existing German natural gas transmission network is analysed with respect to regulatory limits regarding the gas quality. We propose a transient tracking model based on the general pooling problem including linepack. The analysis is conducted using real-world hourly gas flow data on a network of about 10,000 km length.}, language = {en} } @article{BertholdKochShinano2021, author = {Berthold, Timo and Koch, Thorsten and Shinano, Yuji}, title = {MILP. Try. Repeat.}, volume = {2}, journal = {Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling - PATAT 2021}, year = {2021}, language = {en} } @misc{HosodaMaherShinanoetal.2021, 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}, year = {2021}, 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} }