We present an exact rational solver for mixed-integer linear programming that avoids the numerical inaccuracies inherent in the floating-point computations used by existing software. This allows the solver to be used for establishing theoretical results and in applications where correct solutions are critical due to legal and financial consequences. Our solver is a hybrid symbolic/numeric implementation of LP-based branch-and-bound, using numerically-safe methods for all binding computations in the search tree. Computing provably accurate solutions by dynamically choosing the fastest of several safe dual bounding methods depending on the structure of the instance, our exact solver is only moderately slower than an inexact floating-point branch-and-bound solver. The software is incorporated into the SCIP optimization framework, using the exact LP solver QSopt_ex and the GMP arithmetic library. Computational results are presented for a suite of test instances taken from the MIPLIB and Mittelmann libraries and for a new collection of numerically difficult instances.
Modern mixed-integer programming (MIP) solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound. Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three distinct phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behaviour of the non-commercial MIP solver Scip at the predicted phase transition points.
The ZIMPL modeling language
(2017)
In this article we investigate methods to solve a fundamental task in gas transportation, namely the validation of nomination problem: Given a gas transmission network consisting of passive pipelines and active, controllable elements and given an amount of gas at every entry and exit point of the network, find operational settings for all active elements such that there exists a network state meeting all physical, technical, and legal constraints.
We describe a two-stage approach to solve the resulting complex and numerically difficult feasibility problem. The first phase consists of four distinct algorithms applying linear, and methods for complementarity constraints to compute possible settings for the discrete decisions. The second phase employs a precise continuous programming model of the gas network. Using this setup, we are able to compute high quality solutions to real-world industrial instances that are significantly larger than networks that have appeared in the mathematical programming literature before.
The Steiner tree packing problem (STPP) in graphs is a long studied problem in combinatorial optimization. In contrast to many other problems, where there have been tremendous advances in practical problem solving, STPP remains very difficult. Most heuristics schemes are ineffective and even finding feasible solutions is already NP-hard. What makes this problem special is that in order to reach the overall optimal solution non-optimal solutions to the underlying NP-hard Steiner tree problems must be used. Any non-global approach to the STPP is likely to fail. Integer programming is currently the best approach for computing optimal solutions. In this paper we review some “classical” STPP instances which model the underlying real world application only in a reduced form. Through improved modelling, including some new cutting planes, and by emplyoing recent advances in solver technology we are for the first time able to solve those instances in the original 3D grid graphs to optimimality.
The recently imposed new gas market liberalization rules in Germany lead to a change of business of gas network operators. While previously network operator and gas vendor were united, they were forced to split up into independent companies. The network has to be open to any other gas trader at the same conditions, and free network capacities have to be identified and publicly offered in a non-discriminatory way. We discuss how these changing paradigms lead to new and challenging mathematical optimization problems. This includes the validation of nominations, that asks for the decision if the network’s capacity is sufficient to transport a specific amount of flow, the verification of booked capacities and the detection of available freely allocable capacities, and the topological extension of the network with new pipelines or compressors in order to increase its capacity. In order to solve each of these problems and to provide meaningful results for the practice, a mixture of different mathematical aspects have to be addressed, such as combinatorics, stochasticity, uncertainty, and nonlinearity. Currently, no numerical solver is available that can deal with such blended problems out-of-the-box. The main goal of our research is to develop such a solver, that moreover is able to solve instances of realistic size. In this article, we describe the main ingredients of our prototypical software implementations.
Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree
problem in graphs. In this paper transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, we demonstrate the considerable implications for practical solving approaches, including the computation of strong upper and lower bounds.
MIPLIB 2010
(2011)
Optimierung des G-WiN
(2000)
The final NETLIB-LP results
(2004)
Branching Rules Revisited
(2005)
MIPLIB 2003
(2006)
This paper describes three presolving techniques for solving mixed integer programming problems (MIPs) that were implemented in the academic MIP solver SCIP. The task of presolving is to reduce the problem size and strengthen the formulation, mainly by eliminating redundant information and exploiting problem structures. The first method fixes continuous singleton columns and extends results known from duality fixing. The second analyzes and exploits pairwise dominance relations between variables, whereas the third detects isolated subproblems and solves them independently. The performance of the presented techniques is demonstrated on two MIP test sets. One contains all benchmark instances from the last three MIPLIB versions, while the other consists of real-world supply chain management problems. The computational results show that the combination of all three presolving techniques almost halves the solving time for the considered supply chain management problems. For the MIPLIB instances we obtain a speedup of 20 % on affected instances while not degrading the performance on the remaining problems.
Im Oktober 2012 hatte die Deutsche Forschungsgemeinschaft (DFG) ein Förderprogramm zur Neuausrichtung überregionaler Informationsservices ausgeschrieben, um eine umfassende Reorganisation bestehender Infrastrukturen anzustoßen, die mit den Empfehlungen des Wissenschaftsrates zur Zukunft der bibliothekarischen Verbundsysteme in Deutschland gefordert wurde. Im Themenfeld „Bibliotheksdateninfrastruktur und Lokale Systeme“ der DFG-Ausschreibung wurde das vom Hessischen Bibliotheksinformationssystem (HeBIS), vom Bibliotheksverbund Bayern (BVB) und vom Kooperativen Bibliotheksverbund Berlin-Brandenburg (KOBV) beantragte Vorhaben „Cloudbasierte Infrastruktur für Bibliotheksdaten“ (CIB) bewilligt. Das Projekt zielt auf die Überführung bibliothekarischer Workflows und Dienste in cloudbasierte Arbeitsumgebungen und die sukzessive Ablösung traditioneller Verbund- und Lokalsysteme durch internationale Systemplattformen. Zu den Arbeitspaketen des Vorhabens gehört u. a. die Einbindung von Norm- und Fremddatenangeboten und von weiteren Services in diese Plattformen.
One quarter of Europe's energy demand is provided by natural gas distributed through a vast pipeline network covering the whole of Europe. At a cost of 1 million Euro per km extending the European pipeline network is already a multi-billion Euro business. Therefore, automatic planning tools that support the decision process are desired. Unfortunately, current mathematical methods are not capable of solving the arising network design problems due to their size and complexity. In this article, we will show how to apply optimization methods that can converge to a proven global optimal solution. By introducing a new class of valid inequalities that improve the relaxation of our mixed-integer nonlinear programming model, we are able to speed up the necessary computations substantially.
We report on the selection process leading to the sixth version of the Mixed Integer Programming Library. Selected from an initial pool of over 5,000 instances, the new MIPLIB 2017 collection consists of 1,065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, the compilation of these sets was done using a data-driven selection process supported by the solution of a sequence of mixed integer optimization problems, which encoded requirements on diversity and balancedness with respect to instance features and performance data.
The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of robust and future-proof decision support systems. The complexity of industrial-scale supply chain optimization, however, often poses limits to the application of general mixed-integer programming solvers. In this paper we describe algorithmic innovations that help to ensure that MIP solver performance matches the complexity of the large supply chain problems and tight time limits encountered in practice. Our computational evaluation is based on a diverse set, modeling real-world scenarios supplied by our industry partner SAP.
In this paper, we describe an algorithmic framework for the optimal operation of transient gas transport networks consisting of a hierarchical MILP formulation together with a sequential linear programming inspired post-processing routine. Its implementation is part of the KOMPASS decision support system, which is currently used in an industrial setting.
Real-world gas transport networks are controlled by operating complex pipeline intersection areas, which comprise multiple compressor units, regulators, and valves. In the following, we introduce the concept of network stations to model them. Thereby, we represent the technical capabilities of a station by hand-tailored artificial arcs and add them to network. Furthermore, we choose from a predefined set of flow directions for each network station and time step, which determines where the gas enters and leaves the station. Additionally, we have to select a supported simple state, which consists of two subsets of artificial arcs: Arcs that must and arcs that cannot be used. The goal is to determine a stable control of the network satisfying all supplies and demands.
The pipeline intersections, that are represented by the network stations, were initially built centuries ago. Subsequently, due to updates, changes, and extensions, they evolved into highly complex and involved topologies. To extract their basic properties and to model them using computer-readable and optimizable descriptions took several years of effort.
To support the dispatchers in controlling the network, we need to compute a continuously updated list of recommended measures. Our motivation for the model presented here is to make fast decisions on important transient global control parameters, i.e., how to route the flow and where to compress the gas. Detailed continuous and discrete technical control measures realizing them, which take all hardware details into account, are determined in a subsequent step.
In this paper, we present computational results from the KOMPASS project using detailed real-world data.
Borne out of a surprising variety of practical applications, the maximum-weight connected subgraph problem has attracted considerable interest during the past years. This interest has not only led to notable research on theoretical properties, but has also brought about several (exact) solvers-with steadily increasing performance. Continuing along this path, the following article introduces several new algorithms such as reduction techniques and heuristics and describes their integration into an exact solver. The new methods are evaluated with respect to both their theoretical and practical properties. Notably, the new exact framework allows to solve common problem instances from the literature faster than all previous approaches. Moreover, one large-scale benchmark instance from the 11th DIMACS Challenge can be solved for the first time to optimality and the primal-dual gap for two other ones can be significantly reduced.
In 2005 the European Union liberalized the gas market with a disruptive change
and decoupled trading of natural gas from its transport. The gas is now trans-
ported by independent so-called transmissions system operators or TSOs. The
market model established by the European Union views the gas transmission
network as a black box, providing shippers (gas traders and consumers) the
opportunity to transport gas from any entry to any exit. TSOs are required
to offer the maximum possible capacities at each entry and exit such that any
resulting gas flow can be realized by the network. The revenue from selling these
capacities more than one billion Euro in Germany alone, but overestimating the
capacity might compromise the security of supply. Therefore, evaluating the
available transport capacities is extremely important to the TSOs.
This is a report on a large project in mathematical optimization, set out
to develop a new toolset for evaluating gas network capacities. The goals and
the challenges as they occurred in the project are described, as well as the
developments and design decisions taken to meet the requirements.
MILP. Try. Repeat.
(2021)
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.
This article discusses the Length-Constrained Cycle Partition Problem (LCCP), which constitutes a new generalization of the Travelling Salesperson Problem (TSP). Apart from nonnegative edge weights, the undirected graph in LCCP features a nonnegative critical length parameter for each vertex. A cycle partition, i.e., a vertex-disjoint cycle cover, is a feasible solution for LCCP if the length of each cycle is not greater than the critical length of each vertex contained in it. The goal is to find a feasible partition having a minimum number of cycles. Besides analyzing theoretical properties and developing preprocessing techniques, we propose an elaborate heuristic algorithm that produces solutions of good quality even for large-size instances. Moreover, we present two exact mixed-integer programming formulations (MIPs) for LCCP, which are inspired by well-known modeling approaches for TSP. Further, we introduce the concept of conflict hypergraphs, whose cliques yield valid constraints for the MIP models. We conclude with a discussion on computational experiments that we conducted using (A)TSPLIB-based problem instances. As a motivating example application, we describe a routing problem where a fleet of uncrewed aerial vehicles (UAVs) must patrol a given set of areas.
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.
Article’s scientific prestige: Measuring the impact of individual articles in the web of science
(2023)
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.
The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problem-specific. In contrast, this paper introduces a general-purpose solver that can be used to solve both the classical Steiner tree problem and many of its variants without modification. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances.
The concept of reduction has frequently distinguished itself as a pivotal ingredient of exact solving approaches for the Steiner tree problem in graphs. In this paper we broaden the focus and consider reduction techniques for three Steiner problem variants that have been extensively discussed in the literature and entail various practical applications: The prize-collecting Steiner tree problem, the rooted prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem.
By introducing and subsequently deploying numerous new reduction methods, we are able to drastically decrease the size of a large number of benchmark instances, already solving more than 90 percent of them to optimality. Furthermore, we demonstrate the impact of these techniques on exact solving, using the example of the state-of-the-art Steiner problem solver SCIP-Jack.
Forecasting natural gas demand and supply is essential for an efficient operation of the German gas distribution system and a basis for the operational decisions of the transmission system operators. The German gas market is moving towards more short-term planning, in particular, day-ahead contracts. This increases the difficulty that the operators in the dispatching centre are facing, as well as the necessity of accurate forecasts. This paper presents a novel predictive model that provides day-ahead forecasts of the high resolution gas flow by developing a Functional AutoRegressive model with eXogenous variables (FARX). The predictive model allows the dynamic patterns of hourly gas flows to be described in a wide range of historical profiles, while also taking the relevant determinants data into account. By taking into account a richer set of information, FARX provides stronger performance in real data analysis, with both accuracy and high computational efficiency. Compared to several alternative models in out-of-sample forecasts, the proposed model can improve forecast accuracy by at least 12% and up to 5-fold for one node, 3% to 2-fold and 2-fold to 4-fold for the other two nodes. The results show that lagged 1-day gas flow and nominations are important predictors, and with their presence in the forecast model, temperature becomes insignificant for short-term predictions.
As the natural gas market is moving towards short-term planning, accurate and robust short-term forecasts of the demand and supply of natural gas is of fundamental importance for a stable energy supply, a natural gas control schedule, and transport operation on a daily basis. We propose a hybrid forecast model, Functional AutoRegressive and Convolutional Neural Network model, based on state-of-the-art statistical modeling and artificial neural networks. We conduct short-term forecasting of the hourly natural gas flows of 92 distribution nodes in the German high-pressure gas pipeline network, showing that the proposed model provides nice and stable accuracy for different types of nodes. It outperforms all the alternative models, with an improved relative accuracy up to twofold for plant nodes and up to fourfold for municipal nodes. For the border nodes with rather flat gas flows, it has an accuracy that is comparable to the best performing alternative model.
制約整数計画ソルバ SCIP の並列化
(2013)
制約整数計画(CIP: Constraint Integer Programs)は,制約プログラミング(CP: Constraint Programming),混合整数計画(MIP: Mixed Integer Programming),充足可能性問題(SAT: Satisfability Problem)の研究分野におけるモデリング技術と解法を統合している.その結果,制約整数計画は,広いクラスの最適化問題を扱うことができる.SCIP(Solving Constraint Integer Programs)は,CIP を解くソルバとして実装され,Zuse Institute Berlin(ZIB)の研究者を中心として継続的に拡張が続けられている.本論文では,著者らによって開発された SCIP に対する2 種類の並列化拡張を紹介する.一つは,複数計算ノード間で大規模に並列動作する ParaSCIPである.もう一つは,複数コアと共有メモリを持つ 1 台の計算機上で(スレッド)並列で動作する FiberSCIP である.ParaSCIP は,HLRN II スーパーコンピュータ上で,一つのインスタンスを解くために最大 7,168 コアを利用した動作実績がある.また,統計数理研究所の Fujitsu PRIMERGY RX200S5 上でも,最大 512 コアを利用した動作実績がある.統計数理研究所のFujitsu PRIMERGY RX200S5 上では,これまでに最適解が得られていなかった MIPLIB2010のインスタンスである dg012142 に最適解を与えた.
Cutting plane 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 and a neural network verification data set. 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.
Linear energy system models are a crucial component of energy system design and operations, as well as energy policy consulting. If detailed enough, such models lead to large-scale linear programs, which can be intractable even for the best state-of-the-art solvers. This article introduces an interior-point solver that exploits common structures of energy system models to efficiently run in parallel on distributed-memory systems. The solver is designed for linear programs with doubly-bordered block-diagonal constraint matrix and makes use of a Schur complement based decomposition. In order to handle the large number of linking constraints and variables commonly observed in energy system models, a distributed Schur complement preconditioner is used. In addition, the solver features a number of more generic techniques such as parallel matrix scaling and structure-preserving presolving. The implementation is based on the solver PIPS-IPM. We evaluate the computational performance on energy system models with up to four billion nonzero entries in the constraint matrix—and up to one billion columns and one billion rows. This article mainly concentrates on the energy system model ELMOD, which is a linear optimization model representing the European electricity markets by the use of a nodal pricing market-clearing. It has been widely applied in the literature on energy system analyses in recent years. However, it will be demonstrated that the new solver is also applicable to other energy system models.
A decision support system relies on frequent re-solving of similar problem instances. While the general structure remains the same in corresponding applications, the input parameters are updated on a regular basis. We propose a generative neural network design for learning integer decision variables of mixed-integer linear programming (MILP) formulations of these problems. We utilise a deep neural network discriminator and a MILP solver as our oracle to train our generative neural network. In this article, we present the results of our design applied to the transient gas optimisation problem. With the trained network we produce a feasible solution in 2.5s, use it as a warm-start solution, and thereby decrease global optimal solution solve time by 60.5%.
Die europaische Gasinfrastruktur wird disruptiv in ein zukunftiges dekarbonisiertes Energiesystem verändert; ein Prozess, der angesichts der jüngsten politischen Situation beschleunigt werden muss. Mit einem wachsenden Wasserstoffmarkt wird der pipelinebasierte Transport unter Nutzung der bestehenden Erdgasinfrastruktur wirtschaftlich sinnvoll, trägt zur Erhöhung der öffentlichen Akzeptanz bei und beschleunigt den Umstellungsprozess. In diesem Beitrag wird die maximal technisch machbare Einspeisung von Wasserstoff in das bestehende deutsche Erdgastransportnetz hinsichtlich regulatorischer Grenzwerte der Gasqualität analysiert. Die Analyse erfolgt auf Basis eines transienten Tracking-Modells, das auf dem allgemeinen Pooling-Problem einschließlich Linepack aufbaut. Es zeigt sich, dass das Gasnetz auch bei strengen Grenzwerten gen ̈ugend Kapazität bietet, um für einen großen Teil der bis 2030 geplanten Erzeugungskapazität für grünen Wasserstoff als garantierter Abnehmer zu dienen.
Die europäische Gasinfrastruktur wird disruptiv in ein zukünftiges dekarbonisiertes Energiesystem verändert; ein Prozess, der angesichts der jüngsten politischen Situation beschleunigt werden muss. Mit einem wachsenden Wasserstoffmarkt wird der pipelinebasierte Transport unter Nutzung der bestehenden Erdgasinfrastruktur wirtschaftlich sinnvoll, trägt zur Erhöhung der öffentlichen Akzeptanz bei und beschleunigt den Umstellungsprozess. In diesem Fachbeitrag wird die maximal technisch machbare Einspeisung von Wasserstoff in das bestehende deutsche Erdgastransportnetz hinsichtlich regulatorischer Grenzwerte der Gasqualität analysiert. Die Analyse erfolgt auf Basis eines transienten Tracking-Modells, das auf dem allgemeinen Pooling-Problem
einschließlich Linepack aufbaut. Es zeigt sich, dass das Gasnetz auch bei strengen Grenzwerten genügend Kapazität bietet, um für einen großen Teil der bis 2030 geplanten Erzeugungskapazität für grünen Wasserstoff als garantierter Abnehmer zu dienen.
The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems—by using mathematical programming techniques. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse maximum-cut and quadratic unconstrained binary optimization instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.
Natural gas is the cleanest fossil fuel since it emits the lowest amount of other remains after being burned. Over the years, natural gas usage has increased significantly. Accurate forecasting is crucial for maintaining gas supplies, transportation and network stability. This paper presents two methodologies to identify the optimal configuration o parameters of a Neural Network (NN) to forecast the next 24 h of gas flow for each node of a large gas network.
In particular the first one applies a Design Of Experiments (DOE) to obtain a quick initial solution. An orthogonal design, consisting of 18 experiments selected among a total of 4.374 combinations of seven parameters (training algorithm, transfer function, regularization, learning rate, lags, and epochs), is used. The best result is selected as initial solution of an extended experiment for which the Simulated Annealing is run to find the optimal design among 89.100 possible combinations of parameters.
The second technique is based on the application of Genetic Algorithm for the selection of the optimal parameters of a recurrent neural network for time series forecast. GA was applied with binary representation of potential solutions, where subsets of bits in the bit string represent different values for several parameters of the recurrent neural network.
We tested these methods on three municipal nodes, using one year and half of hourly gas flow to train the network and 60 days for testing. Our results clearly show that the presented methodologies bring promising results in terms of optimal configuration of parameters and forecast error.
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.
Cutting planes and branching are two of the most important algorithms for solving mixed-integer linear programs. For both algorithms, disjunctions play an important role, being used both as branching candidates and as the foundation for some cutting planes. We relate branching decisions and cutting planes to each other through the underlying disjunctions that they are based on, with a focus on Gomory mixed-integer cuts and their corresponding split disjunctions. We show that selecting branching decisions based on quality measures of Gomory mixed-integer cuts leads to relatively small branch-and-bound trees, and that the result improves when using cuts that more accurately represent the branching decisions. Finally, we show how the history of previously computed Gomory mixed-integer cuts can be used to improve the performance of the state-of-the-art hybrid branching rule of SCIP. Our results show a $4\%$ decrease in solve time, and an $8\%$ decrease in number of nodes over affected instances of MIPLIB 2017.
The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. The focus of this article is on the role of the SCIP Optimization Suite in supporting research. SCIP’s main design principles are discussed, followed by a presentation of the latest performance improvements and developments in version 8.0, which serve both as examples of SCIP’s application as a research tool and as a platform for further developments. Furthermore, this article gives an overview of interfaces to other programming and modeling languages, new features that expand the possibilities for user interaction with the framework, and the latest developments in several extensions built upon SCIP.
In this article, we introduce the Maximum Diversity Assortment Selection Problem (MDASP), which is a generalization of the two-dimensional Knapsack Problem (2D-KP). Given a set of rectangles and a rectangular container, the goal of 2D-KP is to determine a subset of rectangles that can be placed in the container without overlapping, i.e., a feasible assortment, such that a maximum area is covered. MDASP is to determine a set of feasible assortments, each of them covering a certain minimum threshold of the container, such that the diversity among them is maximized. Thereby, diversity is defined as the minimum or average normalized Hamming distance of all assortment pairs. MDASP was the topic of the 11th AIMMS-MOPTA Competition in 2019. The methods described in this article and the resulting computational results won the contest. In the following, we give a definition of the problem, introduce a mathematical model and solution approaches, determine upper bounds on the diversity, and conclude with computational experiments conducted on test instances derived from the 2D-KP literature.
It has been shown that any 9 by 9 Sudoku puzzle must contain at least 17 clues to have a unique solution. This paper investigates the more specific question: given a particular completed Sudoku grid, what is the minimum number of clues in any puzzle whose unique solution is the given grid? We call this problem the Minimum Sudoku Clue Problem (MSCP). We formulate MSCP as a binary bilevel linear program, present a class of globally valid inequalities, and provide a computational study on 50 MSCP instances of 9 by 9 Sudoku grids. Using a general bilevel solver, we solve 95% of instances to optimality, and show that the solution process benefits from the addition of a moderate amount of inequalities. Finally, we extend the proposed model to other combinatorial problems in which uniqueness of the solution is of interest.
Modeling functional time series and mixed-type predictors with partially functional autoregressions*
(2021)
In many business and economics studies, researchers have sought to measure the dynamic dependence of curves with high-dimensional mixed-type predictors. We propose a partially functional autoregressive model (pFAR) where the serial dependence of curves is controlled by coefficient operators that are defined on a two-dimensional surface, and the individual and group effects of mixed-type predictors are estimated with a two-layer regularization. We develop an efficient estimation with the proven asymptotic properties of consistency and sparsity. We show how to choose the sieve and tuning parameters in regularization based on a forward-looking criterion. In addition to the asymptotic properties, numerical validation suggests that the dependence structure is accurately detected. The implementation of the pFAR within a real-world analysis of dependence in German daily natural gas flow curves, with seven lagged curves and 85 scalar predictors, produces superior forecast accuracy and an insightful understanding of the dynamics of natural gas supply and demand for the municipal, industry, and border nodes, respectively.
Compressor stations are the heart of every high-pressure gas transport network.
Located at intersection areas of the network they are contained in huge complex plants, where they are in combination with valves and regulators responsible for routing and pushing the gas through the network.
Due to their complexity and lack of data compressor stations are usually dealt with in the scientific literature in a highly simplified and idealized manner.
As part of an ongoing project with one of Germany's largest Transmission System Operators to develop a decision support system for their dispatching center, we investigated how to automatize control of compressor stations. Each station has to be in a particular configuration, leading in combination with the other nearby elements to a discrete set of up to 2000 possible feasible operation modes in the intersection area.
Since the desired performance of the station changes over time, the configuration of the station has to adapt.
Our goal is to minimize the necessary changes in the overall operation modes and related elements over time, while fulfilling a preset performance envelope or demand scenario.
This article describes the chosen model and the implemented mixed integer programming based algorithms to tackle this challenge.
By presenting extensive computational results on real world data we demonstrate the performance of our approach.
Compressible flows appear in many natural and technological processes, for instance, the flow of natural gases in a pipe system. Thus, a detailed study of the stability of tangential velocity discontinuity in compressible media is relevant and necessary. The first early investigation in two-dimensional (2D) media was given more than 70 years ago. In this article, we continue investigating the stability in three-dimensional (3D) media. The idealized statement of this problem in an infinite spatial space was studied by Syrovatskii in 1954. However, the omission of the absolute sign of cos θ with θ being the angle between vectors of velocity and wave number in a certain inequality produced the inaccurate conclusion that the flow is always unstable for entire values of the Mach number M. First, we revisit this case to arrive at the correct conclusion, namely that the discontinuity surface is stabilized for a large Mach number with a given value of the angle θ. Next, we introduce a real finite spatial system such that it is bounded by solid walls along the flow direction. We show that the discontinuity surface is stable if and only if the dispersion relation equation has only real roots, with a large value of the Mach number; otherwise, the surface is always unstable. In particular, we show that a smaller critical value of the Mach number is required to make the flow in a narrow channel stable.
Linear stability of a simple shear layer between two parallel streams in a shallow water flow
(2024)
The stability of shear layers in fluid flows is a crucial factor in forming vortices and jets and plays a fundamental role in the development of turbulence. Such shear layer instabilities are ubiquitous in natural phenomena, such as atmospheric and oceanic flows, contributing to the formation of weather systems and predicting tsunamis. This study specifically focuses on the stability of a shear layer sandwiched between two semi-infinite layers within a two-dimensional flow. The velocity profile of the shear layer is assumed to be linearly dependent on the vertical coordinate, while the velocity of the other layers remains uniform with differing strengths. The effect of viscosity and surface tension is ignored to simplify the analysis. The shallow water equations are used to analyze the interface stability of the shear layer, and the resulting dispersion relation between wave frequency and other wave characteristics is obtained. This relation incorporates Whittaker functions and their first derivatives and is used to derive appropriate limits corresponding to various physical conditions. Our study thus contributes to a deeper understanding of the stability of shear layers and their implications for natural phenomena.
The stability of a flow in porous media relates to the velocity rate of injecting and withdrawing natural gases inside porous storage. We thus aim to analyze the stability of flows in porous media to accelerate the energy transition process. This research examines a flow model of a tangential--velocity discontinuity with porosity and viscosity changes in a three-dimensional (3D) compressible medium because of a co-existence of different gases in a storage. The fluids are assumed to move in a relative motion where the plane y=0 is a tangential-velocity discontinuity surface. We obtain that the critical value of the Mach number to stabilize a tangential discontinuity surface of flows via porous media is smaller than the one of flows in a plane. The critical value of the Mach number M to stabilize a discontinuity surface of the 3D flow is different by a factor |cosθ| compared to the two-dimensional (2D) flow. Here, θ is the angle between velocity and wavenumber vectors. Our results also show that the flow model with viscosity and porosity effects is stable faster than those without these terms. Our analysis is done for both infinite and finite flows. The effect of solid walls along the flow direction could suppress the instability, i.e., the tangential-discontinuity surface is stabilized faster
The present study investigates the stability of a tangential-velocity discontinuity in porous media during the withdrawing and injecting processes of natural gases from and into an underground gas storage. The focus is placed on analyzing the impact of inertia forces on the interface stability using the Forchheimer equations. Other publications have relied primarily on Darcy's law to describe flow stability in porous media. However, Darcy's law only adequately describes flows in which viscous forces dominate over inertia forces. As the flow rate increases, the significance of inertia forces becomes more pronounced, and Darcy's law becomes insufficient for considering such flows. Our findings indicate that even a slight consideration of the inertia effect leads to permanent destabilization of the discontinuity interface, regardless of the fluid viscosity or the Mach number. In contrast, when the inertia effect is neglected, the interface is stabilized across the entire Mach number range if the fluid viscosity is strong enough.
The stability of flows in porous media plays a vital role in transiting energy supply from natural gas to hydrogen, especially for estimating the usability of existing underground gas storage infrastructures. Thus, this research aims to analyze the interface stability of the tangential-velocity discontinuity between two compressible gases by using Darcy's model to include the porosity effect. The results shown in this research will be a basis for considering whether underground gas storages in porous material can be used to store hydrogen. We show the relation between the Mach number M, the viscosity \mu, and the porosity \epsilon on the stability of the interface. This interface stability affects gases' withdrawal and injection processes, thus will help us to determine the velocity which with gas can be extracted and injected into the storage effectively. By imposing solid walls along the flow direction, the critical values of these parameters regarding the stability of the interface are smaller than when considering no walls. The consideration of bounded flows approaches the problem more realistically. In particular, this analysis plays a vital role when considering two-dimensional gas flows in storages and pipes.
Deep learning for spatio-temporal supply anddemand forecasting in natural gas transmission networks
(2021)
Germany is the largest market for natural gas in the European Union, with an annual consumption of approx. 95 billion cubic meters. Germany's high-pressure gas pipeline network is roughly 40,000 km long, which enables highly fluctuating quantities of gas to be transported safely over long distances. Considering that similar amounts of gas are also transshipped through Germany to other EU states, it is clear that Germany's gas transport system is essential to the European energy supply. Since the average velocity of gas in a pipeline is only 25km/h, an adequate high-precision, high-frequency forecasting of supply and demand is crucial for efficient control and operation of such a transmission network. We propose a deep learning model based on spatio-temporal convolutional neural networks (DLST) to tackle the problem of gas flow forecasting in a complex high-pressure transmission network. Experiments show that our model effectively captures comprehensive spatio-temporal correlations through modeling gas networks and consistently outperforms state-of-the-art benchmarks on real-world data sets by at least 21%.
The results demonstrate that the proposed model can deal with complex nonlinear gas network flow forecasting with high accuracy and effectiveness.