ZIB-Report
Refine
Year of publication
- 2022 (25) (remove)
Document Type
- ZIB-Report (24)
- Article (1)
Has Fulltext
- yes (25)
Keywords
- Periodic Timetabling (2)
- cut selection (2)
- CO2 Transport (1)
- DeepGreen (1)
- Investment planning (1)
- Mixed-Integer Programming (1)
- Multi-energy systems (1)
- Neighbourhood Search (1)
- Network Design (1)
- Open Access (1)
Institute
- Applied Algorithmic Intelligence Methods (13)
- Network Optimization (4)
- Mathematical Optimization (3)
- Modeling and Simulation of Complex Processes (3)
- Digital Data and Information for Society, Science, and Culture (2)
- Mathematical Algorithmic Intelligence (2)
- Numerical Mathematics (2)
- Visual and Data-centric Computing (2)
- AI in Society, Science, and Technology (1)
- Distributed Algorithms and Supercomputing (1)
22-17
The European energy system has been through a fundamental transformation since the Paris Agreement to reduce greenhouse gas emissions. The transition involves several energy-generating and consuming sectors emphasizing sector coupling. The increase in the share of renewable energy sources has revealed the need for flexibility in the electri
city grid. Thus, holistic planning of pathways towards decarbonized energy systems also involves assessing the gas infrastructure to provide such a flexibility and support for the security of supply. In this paper, we propose a workflow to investigate such optimal energy transition pathways considering sector coupling. This workflow involves an integrated operational analysis of the electricity market, its transmission grid, and the gas grid in high spatio-temporal resolution. In a case study on a pan-European scale between 2020-2050, we show that carbon neutrality can be reached within feasible additional costs and in time. However, the manifestation of the potential pathways strongly depends on political and technological constraints. Sector coupling acts as an enabler of cross-border cooperation to achieve both, decarbonization and security of supply.
22-04
Cut selection is a subroutine used in all modern mixed-integer linear programming solvers with the goal of selecting a subset of generated cuts that induce optimal solver performance. These solvers have millions of parameter combinations, and so are excellent candidates for parameter tuning. Cut selection scoring rules are usually weighted sums of different measurements, where the weights are parameters. We present a parametric family of mixed-integer linear programs together with infinitely many family-wide valid cuts. Some of these cuts can induce integer optimal solutions directly after being applied, while others fail to do so even if an infinite amount are applied. We show for a specific cut selection rule, that any finite grid search of the parameter space will always miss all parameter values, which select integer optimal inducing cuts in an infinite amount of our problems. We propose a variation on the design of existing graph convolutional neural networks, adapting them to learn cut selection rule parameters. We present a reinforcement learning framework for selecting cuts, and train our design using said framework over MIPLIB 2017. Our framework and design show that adaptive cut selection does substantially improve performance over a diverse set of instances, but that finding a single function describing such a rule is difficult. Code for reproducing all experiments is available at https://github.com/Opt-Mucca/Adaptive-Cutsel-MILP.
22-28
Cutting planes are a crucial component of state-of-the-art mixed-integer programming solvers, with the choice of which subset of cuts to add being vital for solver performance. We propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. For this purpose, we use the analytic centers of the relaxation polytope or of its optimal face, as well as alternative optimal solutions of the linear programming relaxation. We assess the impact of the choice of distance measure on root node performance and throughout the whole branch-and-bound tree, comparing our measures against those prevalent in the literature. Finally, by a multi-output regression, we predict the relative performance of each measure, using static features readily available before the separation process. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space and that our multiregression approach can further improve on any individual method.
22-21
Our theoretical study concerns an urea-urease-based pH oscillator confined to giant lipid vesicles. Under suitable conditions, differential transport of urea and hydrogen ion across the unilamellar vesicle membrane periodically resets the pH clock that switches the system from acid to basic, resulting in self-sustained oscillations. We analyse the structure of the limit cycle, which controls the dynamics for giant vesicles and dominates the strongly stochastic oscillations in small vesicles of submicrometer size. To this end, we derive reduced models, amenable to analytic treatments, and show that the accuracy of predictions, including the period of oscillations, is highly sensitive to the choice of the reduction scheme. In particular, we suggest an accurate two-variable model and show its equivalence to a three-variable model that admits an interpretation in terms of a chemical reaction network. The accurate description of a single pH oscillator appears crucial for rationalizing experiments and understanding communication of vesicles and synchronization of rhythms.
22-25
One of the main challenges in molecular dynamics is overcoming the “timescale barrier”, a phrase used to describe that in many realistic molecular systems, biologically important rare transitions occur on timescales that are not accessible to direct numerical simulation, not even on the largest or specifically dedicated supercomputers. This article discusses how to circumvent the timescale barrier by a collection of transfer operator-based techniques that have emerged from dynamical systems theory, numerical mathematics, and machine learning over the last two decades. We will focus on how transfer operators can be used to approximate the dynamical behavior on long timescales, review the introduction of this approach into molecular dynamics, and outline the respective theory as well as the algorithmic development from the early numerics-based methods, via variational reformulations, to modern data-based techniques utilizing and
improving concepts from machine learning. Furthermore, its relation to rare event simulation techniques will be explained, revealing a broad equivalence of variational principles for long-time quantities in MD. The article will mainly take a mathematical perspective and will leave the application to real-world molecular systems to the more than 1000 research articles already written on this subject.
22-22
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.
22-19
This work presents an innovative short to mid-term forecasting model that analyzes nonlinear complex spatial and temporal dynamics in energy networks under demand and supply balance constraints using Network Nonlinear Time Series (TS) and Mathematical Programming (MP) approach. We address three challenges simultaneously, namely, the adjacency matrix is unknown; the total amount in the network has to be balanced; dependence is unnecessarily linear. We use a nonparametric approach to handle the nonlinearity and estimate the adjacency matrix under the sparsity assumption. The estimation is conducted with the Mathematical Optimisation method.
We illustrate the accuracy and effectiveness of the model on the example of the natural gas transmission network of one of the largest transmission system operators (TSOs) in Germany, Open Grid Europe. The obtained results show that, especially for shorter forecasting horizons, the proposed method outperforms all considered benchmark models, improving the average nMAPE for 5.1% and average RMSE for 79.6% compared to the second-best model. The model is capable of capturing the nonlinear dependencies in the complex spatial-temporal network dynamics and benefits from both sparsity assumption and the demand and supply balance constraint.
22-15
While energy-intensive industries like the steel industry plan to switch to renewable energy sources, other industries, such as the cement industry, have to rely on carbon capture storage and utilization technologies to reduce the inevitable carbon dioxide (CO2) emissions of their production processes. 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 a challenging mixed-integer nonlinear program. Additionally, the behaviour of CO2 is highly sensitive and nonlinear 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 modelling including mixing effects, the Joule-Thomson effect, and heat exchange with the surrounding environment. We show the effectiveness of our approach by applying our algorithm to a real-world network planning problem for a CO2 network in Western Germany.
22-12
The Sasaki metric is the canonical metric on the tangent bundle TM of a Riemannian manifold M. It is highly useful for data analysis in TM (e.g., when one is interested in the statistics of a set of geodesics in M). To this end, computing the Riemannian logarithm is often necessary, and an iterative algorithm was proposed by Muralidharan and Fletcher. In this note, we derive approximation formulas of the energy gradients in their algorithm that we use with success.
22-26
We propose a mixed-integer linear programming model to generate and optimize periodic timetables with integrated track choice in the context of railway construction sites. When a section of a railway network becomes unavailable, the nearby areas are typically operated close to their capacity limits, and hence carefully modeling headways and allowing flexible routings becomes vital. We therefore discuss first how to integrate headway constraints into the Periodic Event Scheduling Problem (PESP) that do not only prevent overtaking, but also guarantee conflict-free timetables in general and particularly inside stations. Secondly, we introduce a turn-sensitive event-activity network, which is able to integrate routing alternatives for turnarounds at stations, e.g., turning at a platform vs. at a pocket track for metro-like systems. We propose several model formulations to include track choice, and finally evaluate them on six real construction site scenarios on the S-Bahn Berlin network.
22-01
We consider the line planning problem in public transport in the Parametric City, an idealized model that captures typical scenarios by a (small) number of parameters. The Parametric City is rotation symmetric, but optimal line plans are not always symmetric. This raises the question to quantify the symmetry gap between the best symmetric and the overall best solution. For our analysis, we formulate the line planning problem as a mixed integer linear program, that can be solved in polynomial time if the solutions are forced to be symmetric. The symmetry gap is provably small when a specific Parametric City parameter is fixed, and we give an approximation algorithm for line planning in the Parametric City in this case. While the symmetry gap can be arbitrarily large in general, we show that symmetric line plans are a good choice in most practical situations.
22-10
Understanding the Romanization Spreading on Historical Interregional Networks in Northern Tunisia
(2022)
Spreading processes are important drivers of change in social systems. To understand the mechanisms of spreading it is fundamental to have information about the underlying contact network and the dynamical parameters of the process.
However, in many real-wold examples, this information is not known and needs to be inferred from data. State-of-the-art spreading inference methods have mostly been applied to modern social systems, as they rely on availability of very detailed data. In this paper we study the inference challenges for historical spreading processes, for which only very fragmented information is available. To cope with this problem, we extend existing network models by formulating a model on a mesoscale with temporal spreading rate. Furthermore, we formulate the respective parameter inference problem for the extended model. We apply our approach to the romanization process of Northern Tunisia, a scarce dataset, and study properties of the inferred time-evolving interregional networks. As a result, we show that (1) optimal solutions consist of very different network structures and spreading rate functions; and that (2) these diverse solutions produce very similar spreading patterns. Finally, we discuss how inferred dominant interregional connections are related to available archaeological traces. Historical networks resulting from our approach can help understanding complex processes of cultural change in ancient times.
21-20
This study investigates the progress made in LP and MILP solver performance during the last two decades by comparing the solver software from the beginning of the millennium with the codes available today.
On average, we found out that for solving LP/MILP, computer hardware got about 20 times faster, and the algorithms improved by a factor of about nine for LP and around 50 for MILP, which gives a total speed-up of about 180 and 1,000 times, respectively.
However, these numbers have a very high variance and they considerably underestimate the progress made on the algorithmic side: many problem instances can nowadays be solved within seconds, which the old codes are not able to solve within any reasonable time.
22-08
Optimizing the transient control of gas networks is a highly challenging task.
The corresponding model incorporates the combinatorial complexity of determining the settings for the many active elements as well as the non-linear and non-convex nature of the physical and technical principles of gas transport.
In this paper, we present the latest improvements of our ongoing work to solve this problem for real-world, large-scale problem instances:
By adjusting our mixed-integer non-linear programming model regarding the gas compression capabilities in the network, we reflect the technical limits of the underlying units more accurately while maintaining a similar overall model size.
In addition, we introduce a new algorithmic approach that is based on splitting the complexity of the problem by first finding assignments for discrete variables and then determining the continuous variables as locally optimal solution of the corresponding non-linear program.
For the first task, we design multiple different heuristics based on concepts for general time-expanded optimization problems that find solutions by solving a sequence of sub-problems defined on reduced time horizons.
To demonstrate the competitiveness of our approach, we test our algorithm on particularly challenging historic demand scenarios.
The results show that high-quality solutions are obtained reliably within short solving times, making the algorithm well-suited to be applied at the core of time-critical industrial applications.
22-18
Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB; a 1.48% gap remains between the best known feasible objective value and lower bound of the unknown optimal value. This paper shows that the instance can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which requires the sum of the binary variables to be 92.The converted BQOP is much simpler than the original QAP tai256c and it also inherits some of the symmetry properties. However, it is still very difficult to solve. We present an efficient branch and bound method for improving the lower bound effectively. A new lower bound with 1.36% gap is also provided.
22-11
大規模二次割当問題への挑戦
(2022)
22-03
Im Rahmen ihrer Strategie zur Langzeitarchivierung forscht die Deutsche Kinemathek in einer Kooperation mit dem Zuse-Institut Berlin (ZIB) an der digitalen Langzeitarchivierung von AV-Materialien. Ausgangspunkt des Projektes sind die enormen Dateigrößen und die heterogenen Dateiformate, die einem Werk und einer Fassung zugeordnet werden müssen. Die Verwendung von persistenten Identifikatoren stellt den Lösungsansatz dar.
22-16
In light of the energy transition production planning of future decarbonized energy systems lead to very large and complex optimization problems. A widely used modeling paradigm for modeling and solving such problems is mathematical programming. While there are various scientific energy system models and modeling tools, most of them do not provide the necessary level of detail or the modeling flexibility to be applicable for industrial usage. Industrial modeling tools, on the other hand, provide a high level of detail and modeling flexibility. However, those models often exhibit a size and complexity that restricts their scope to a time horizon of several months, severely complicating long-term planning. As a remedy, we propose a model class that is detailed enough for real-world usage but still compact enough for long-term planning. The model class is based on a generalized unit commitment problem on a network with investment decisions. The focus lies on the topological dependency of different energy production and transportation units.
22-07
Article's Scientific Prestige: Measuring the Impact of Individual Articles in the Web of Science
(2022)
We performed a citation analysis on the Web of Science publications consisting of more than 63 million articles and 1.45 billion citations on 254 subjects from 1981 to 2020. We proposed the Article’s Scientific Prestige (ASP) metric and compared this metric to number of citations (#Cit) and journal grade in measuring the scientific impact of individual articles in the large-scale
hierarchical and multi-disciplined citation network. In contrast to #Cit, ASP, that is computed based on the eigenvector centrality, considers both direct and indirect citations, and provides
steady-state evaluation cross different disciplines. We found that ASP and #Cit are not aligned for most articles, with a growing mismatch amongst the less cited articles. While both metrics are reliable for evaluating the prestige of articles such as Nobel Prize winning articles, ASP tends to provide more persuasive rankings than #Cit when the articles are not highly cited. The journal grade, that is eventually determined by a few highly cited articles, is unable to properly
reflect the scientific impact of individual articles. The number of references and coauthors are
less relevant to scientific impact, but subjects do make a difference.