@article{LeKoch2022, author = {Le, Thi Thai and Koch, Thorsten}, title = {Viscosity and porosity effects on tangential-discontinuity surface stability in 3D Compressible Media}, volume = {34}, journal = {Physics of Fluids}, number = {7}, publisher = {AIP Publishing}, doi = {10.1063/5.0095970}, year = {2022}, abstract = {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}, language = {en} } @article{LenzSerrano2022, author = {Lenz, Ralf and Serrano, Felipe}, title = {Tight Convex Relaxations for the Expansion Planning Problem}, volume = {194}, journal = {Journal of Optimization Theory and Applications}, doi = {10.1007/s10957-022-02029-8}, pages = {325 -- 352}, year = {2022}, abstract = {Secure energy transport is considered as highly relevant for the basic infrastructure of nowadays society and economy. To satisfy increasing demands and to handle more diverse transport situations, operators of energy networks regularly expand the capacity of their network by building new network elements, known as the expansion planning problem. A key constraint function in expansion planning problems is a nonlinear and nonconvex potential loss function. In order to improve the algorithmic performance of state-of-the-art MINLP solvers, this paper presents an algebraic description for the convex envelope of this function. Through a thorough computational study, we show that this tighter relaxation tremendously improves the performance of the MINLP solver SCIP on a large test set of practically relevant instances for the expansion planning problem. In particular, the results show that our achievements lead to an improvement of the solver performance for a development version by up to 58\%.}, language = {en} } @article{HosadaMaherShinanoetal.2022, author = {Hosada, Junko and Maher, Stephen and Shinano, Yuji and Villumsen, Jonas Christoffer}, title = {Location, transshipment and routing: An adaptive transportation network integrating long-haul and local vehicle routing}, volume = {11}, journal = {EURO Journal on Transportation and Logistics}, publisher = {Elsevier}, doi = {10.1016/j.ejtl.2022.100091}, year = {2022}, language = {en} } @misc{HosodaMaherShinano2024, author = {Hosoda, Junko and Maher, Stephen J. and Shinano, Yuji}, title = {Combining Benders' decomposition and parallelisation to solve large-scale adaptive network supply chain management problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-98744}, year = {2024}, abstract = {Integrated supply chain network design—combining warehouse clustering with inter- and intra-cluster vehicle routing—is a fundamental feature of supply chain management problems. In this paper, a Benders' decomposition-based parallel heuristic approach for the integrated long-haul and local vehicle routing problem is proposed. The proposed algorithm comprises lower- and upper-bound search algorithms running in parallel to find high-quality solutions for challenging supply chain management problems. A novel Benders' decomposition approach is proposed to aid the improvement in the lower bound for large-scale problems. The results demonstrate that the Benders' decomposition approach is effective in finding strong lower bounds and is beneficial for obtaining high-quality solutions.}, language = {en} } @misc{FujiiKimKojimaetal.2022, author = {Fujii, Koichi and Kim, Sunyoung and Kojima, Masakazu and Mittelmann, Hans D. and Shinano, Yuji}, title = {The Largest Unsolved QAP Instance Tai256c Can Be Converted into A 256-dimensional Simple BQOP with A Single Cardinality Constraint}, issn = {1438-0064}, doi = {10.12752/8808}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-88086}, year = {2022}, abstract = {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.}, language = {en} } @article{ChenKochZakiyevaetal.2022, author = {Chen, Ying and Koch, Thorsten and Zakiyeva, Nazgul and Liu, Kailiang and Xu, Zhitong and Chen, Chun-houh and Nakano, Junji and Honda, Keisuke}, title = {Article's Scientific Prestige: Measuring the Impact of Individual Articles in the Web of Science}, volume = {17}, number = {1}, doi = {https://doi.org/10.1016/j.joi.2023.101379}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-86380}, pages = {101379}, year = {2022}, abstract = {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.}, language = {en} } @misc{TurnerKochSerranoetal.2022, author = {Turner, Mark and Koch, Thorsten and Serrano, Felipe and Winkler, Michael}, title = {Adaptive Cut Selection in Mixed-Integer Linear Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-86055}, year = {2022}, abstract = {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.}, language = {en} } @misc{RehfeldtKochShinano2022, author = {Rehfeldt, Daniel and Koch, Thorsten and Shinano, Yuji}, title = {Faster exact solution of sparse MaxCut and QUBO problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-85715}, year = {2022}, language = {en} } @article{HoppmannBaumBurdakovMexietal.2022, author = {Hoppmann-Baum, Kai and Burdakov, Oleg and Mexi, Gioni and Casselgren, Carl Johan and Koch, Thorsten}, title = {Length-Constrained Cycle Partition with an Application to UAV Routing}, journal = {Optimization Methods and Software}, doi = {10.1080/10556788.2022.2053972}, year = {2022}, abstract = {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.}, language = {en} } @article{TurnerKochSerranoetal.2023, author = {Turner, Mark and Koch, Thorsten and Serrano, Felipe and Winkler, Michael}, title = {Adaptive Cut Selection in Mixed-Integer Linear Programming}, volume = {4}, journal = {Open Journal of Mathematical Optimization}, doi = {10.5802/ojmo.25}, pages = {5}, year = {2023}, abstract = {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.}, language = {en} }