@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{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} } @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{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{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{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{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} } @misc{ZakiyevaPetkovic2021, author = {Zakiyeva, Nazgul and Petkovic, Milena}, title = {Modeling and forecasting gas network flows with multivariate time series and mathematical programming approach}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82966}, year = {2021}, abstract = {With annual consumption of approx. 95 billion cubic me-ters and similar amounts of gas just transshipped through Germany toother EU states, Germany's gas transport system plays a vital role inEuropean energy supply. The complex, more than 40,000 km long high-pressure transmission network is controlled by several transmission sys-tem operators (TSOs) whose main task is to provide security of supplyin a cost-efficient way. Given the slow speed of gas flows through the gastransmission network pipelines, it has been an essential task for the gasnetwork operators to enhance the forecast tools to build an accurate andeffective gas flow prediction model for the whole network. By incorpo-rating the recent progress in mathematical programming and time seriesmodeling, we aim to model natural gas network and predict gas in- andout-flows at multiple supply and demand nodes for different forecastinghorizons. Our model is able to describe the dynamics in the network bydetecting the key nodes, which may help to build an optimal manage-ment strategy for transmission system operators.}, language = {en} } @article{PetkovicKochZittel2021, author = {Petkovic, Milena and Koch, Thorsten and Zittel, Janina}, title = {Deep learning for spatio-temporal supply anddemand forecasting in natural gas transmission networks}, journal = {Energy Science and Engineering}, doi = {https://doi.org/10.1002/ese3.932}, year = {2021}, abstract = {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.}, language = {en} } @incollection{SchwarzLacalandraScheweetal.2020, author = {Schwarz, R. and Lacalandra, F. and Schewe, L. and Bettinelli, A. and Vigo, D. and Bischi, A. and Parriani, T. and Martelli, E. and Vuik, K. and Lenz, R. and Madsen, H. and Blanco, I. and Guericke, D. and Y{\"u}ksel-Erg{\"u}n, I. and Zittel, J.}, title = {Network and Storage}, volume = {4}, booktitle = {Mathematical Optimization for Efficient and Robust Energy Networks}, publisher = {Springer}, isbn = {978-3-030-57442-0}, doi = {https://doi.org/10.1007/978-3-030-57442-0_6}, year = {2020}, abstract = {Natural gas is considered by many to be the most important energy source for the future. The objectives of energy commodities strategic problems can be mainly related to natural gas and deal with the definition of the "optimal" gas pipelines design which includes a number of related sub problems such as: Gas stations (compression) location and Gas storage locations, as well as compression station design and optimal operation.}, language = {en} } @misc{TateiwaShinanoYamamuraetal.2021, author = {Tateiwa, Nariaki and Shinano, Yuji and Yamamura, Keiichiro and Yoshida, Akihiro and Kaji, Shizuo and Yasuda, Masaya and Fujisawa, Katsuki}, title = {CMAP-LAP: Configurable Massively Parallel Solver for Lattice Problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82802}, year = {2021}, abstract = {Lattice problems are a class of optimization problems that are notably hard. There are no classical or quantum algorithms known to solve these problems efficiently. Their hardness has made lattices a major cryptographic primitive for post-quantum cryptography. Several different approaches have been used for lattice problems with different computational profiles; some suffer from super-exponential time, and others require exponential space. This motivated us to develop a novel lattice problem solver, CMAP-LAP, based on the clever coordination of different algorithms that run massively in parallel. With our flexible framework, heterogeneous modules run asynchronously in parallel on a large-scale distributed system while exchanging information, which drastically boosts the overall performance. We also implement full checkpoint-and-restart functionality, which is vital to high-dimensional lattice problems. Through numerical experiments with up to 103,680 cores, we evaluated the performance and stability of our system and demonstrated its high capability for future massive-scale experiments.}, language = {en} } @misc{PedersenHoppmannBaumZitteletal.2021, 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; Technical Report}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82838}, year = {2021}, abstract = {In the transition towards a pure hydrogen infrastructure, utilizing the existing natural gas infrastructure is a necessity. 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{AlzaatrehAljarrahAlmagambetovaetal.2021, author = {Alzaatreh, Ayman and Aljarrah, Mohammad and Almagambetova, Ayanna and Zakiyeva, Nazgul}, title = {On the Regression Model for Generalized Normal Distributions}, volume = {23}, journal = {Entropy}, number = {2}, doi = {https://doi.org/10.3390/e23020173}, pages = {173}, year = {2021}, abstract = {The traditional linear regression model that assumes normal residuals is applied extensively in engineering and science. However, the normality assumption of the model residuals is often ineffective. This drawback can be overcome by using a generalized normal regression model that assumes a non-normal response. In this paper, we propose regression models based on generalizations of the normal distribution. The proposed regression models can be used effectively in modeling data with a highly skewed response. Furthermore, we study in some details the structural properties of the proposed generalizations of the normal distribution. The maximum likelihood method is used for estimating the parameters of the proposed method. The performance of the maximum likelihood estimators in estimating the distributional parameters is assessed through a small simulation study. Applications to two real datasets are given to illustrate the flexibility and the usefulness of the proposed distributions and their regression models.}, language = {en} } @article{JinLeFukumoto2019, author = {Jin, Liangbing and Le, Thi Thai and Fukumoto, Yasuhide}, title = {Frictional effect on stability of discontinuity interface in tangential velocity of a shallow-water flow}, volume = {383}, journal = {Physics Letters A}, number = {26}, doi = {10.1016/j.physleta.2019.125839}, pages = {125839}, year = {2019}, abstract = {We examine a frictional effect on the linear stability of an interface of discontinuity in tangential velocity. The fluid is moving with uniform velocity U in a region but is at rest in the other, and the bottom surface is assumed to exert drag force, quadratic in velocity, on the thin fluid layer. In the absence of the drag, the instability of the Kelvin-Helmholtz type is suppressed for U>√8 c, with c being the propagating speed of the gravity wave. We find by asymptotic analyses for both small and large values of the drag strength that the drag, regardless of its strength, makes the flow unstable for the whole range of the Froude number U/c.}, language = {en} } @article{Le2021, author = {Le, Thi Thai}, title = {Effect of water depth on Kelvin - Helmholtz instability in a shallow-water flow}, volume = {62}, journal = {Journal of Mathematical Physics}, number = {10}, publisher = {AIP Publishing}, doi = {10.1063/1.5145060}, pages = {103101}, year = {2021}, abstract = {It is well known that the interface between two regions of an incompressible ideal fluid flow moving in a relative motion is necessarily destabilized, regardless of the velocity difference's strength. This phenomenon is the so-called Kelvin-Helmholtz instability (KHI). However, a large number of works demonstrated a surprising result that the instability is suppressed for shallow water flows; the interface is stabilized if the Froude number, defined by the velocity difference's ratio to the gravity wave's speed, is sufficiently large. In a limited way, these authors have been used the shallow-water equations without the higher-order effect of the dispersive terms. Thus, this investigation aims to examine these higher-order dispersive effects to analyze the interface stability problem of tangential-velocity discontinuity in shallow-water flows. In particular, we use the Green-Naghdi equations to introduce the dispersive terms related to the depth and the depth-averaged horizontal velocities of the fluid. We show that the interface stability depends on the Froude number (i.e., the velocity difference's strength) and the water depth. A critical value of the Froude number to stabilize the interface is smaller than the case of no dispersive terms, and the flow in a deeper region is more stable than in a shallower one. We also consider the distribution of kinetic and potential energy to clarify a feature characteristic of a large class of instabilities in shallow water flow. The instability of flows is caused by the decrease in the kinetic energy during the perturbation of waves. This phenomenon is known as negative energy modes and plays a vital role in applying the model to industrial equipment. A conclusion is that the equipartition of energies occurs if and only if the velocity difference is zero and the water depth is shallow enough to ignore the dispersive terms.}, language = {en} } @inproceedings{PedersenSchachlerHeideretal.2021, author = {Pedersen, Jaap and Schachler, Birgit and Heider, Anya and Pleßmann, Guido}, title = {Distribution System Planning with Battery Storage using Multiperiod Optimal Power Flow}, volume = {6}, booktitle = {14th International Renewable Energy Storage Conference 2020 (IRES 2020)}, doi = {https://doi.org/10.2991/ahe.k.210202.007}, pages = {41 -- 48}, year = {2021}, abstract = {The ongoing energy transition introduces new challenges for distribution networks and brings about the need to expand existing power grid capacities. In order to contain network expansion and with it economic costs, utilization of various flexibility options to reduce expansion needs is discussed. This paper proposes a multiperiod optimal power flow (MPOPF) approach with a new continuous network expansion formulation to optimize the deployment of flexibility options under the objective of minimizing network expansion costs. In a comparison of the newly proposed continuous network expansion formulation with an existing mixed integer formulation and a continuous interpretation of the latter the here proposed formulation is shown to be useful in order to obtain a solvable problem and contain computational efforts. The presented MPOPF including the flexibility options storage units and curtailment is then assessed on synthetic medium voltage grids and applied to evaluate the benefit of a combined vs. a stepwise optimization of these flexibility options. It is demonstrated that using a local solver the proposed approach is applicable and yields a solution in reasonable time. Furthermore, it is shown that the combined optimization generally leads to a more efficient utilization of the considered flexibility options and therefore lower grid expansion costs than the stepwise consideration.}, language = {en} } @article{HenningsAndersonHoppmannBaumetal.2021, author = {Hennings, Felix and Anderson, Lovis and Hoppmann-Baum, Kai and Turner, Mark and Koch, Thorsten}, title = {Controlling transient gas flow in real-world pipeline intersection areas}, volume = {22}, journal = {Optimization and Engineering}, edition = {2}, publisher = {Springer Nature}, doi = {https://doi.org/10.1007/s11081-020-09559-y}, pages = {687 -- 734}, year = {2021}, abstract = {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.}, language = {en} } @article{ZakiyevaPetkovic2025, author = {Zakiyeva, Nazgul and Petkovic, Milena}, title = {High-dimensional high-frequency time series prediction with a mixed integer optimisation method}, journal = {Operations Research Proceedings 2023. OR 2023}, issn = {1438-0064}, doi = {10.1007/978-3-031-58405-3_54}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-93068}, pages = {423 -- 429}, year = {2025}, abstract = {We study a functional autoregressive model for high-frequency time series. We approach the estimation of the proposed model using a Mixed Integer Optimisation method. The proposed model captures serial dependence in the functional time series by including high-dimensional curves. We illustrate our methodology on large-scale natural gas network data. Our model provides more accurate day-ahead hourly out-of-sample forecast of the gas in and out-flows compared to alternative prediction models.}, language = {en} }