Library

Description: 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.

Description: In the transition towards a pure hydrogen infrastructure, repurposing the existing natural gas infrastructure is considered. In this study, the maximal technically feasible injection of hydrogen into the existing German natural gas transmission network is analysed with respect to regulatory limits regarding the gas quality. We propose a transient tracking model based on the general pooling problem including linepack. The analysis is conducted using real-world hourly gas flow data on a network of about 10,000 km length.

Description: The fight against climate change makes extreme but inevitable changes in the energy sector necessary. These in turn lead to novel and complex challenges for the transmission system operators (TSOs) of gas transport networks. In this thesis, we consider four different planning problems emerging from real-world operations and present mathematical programming models and solution approaches for all of them. Due to regulatory requirements and side effects of renewable energy production, controlling today's gas networks with their involved topologies is becoming increasingly difficult. Based on the network station modeling concept for approximating the technical capabilities of complex subnetworks, e.g., compressor stations, we introduce a tri-level MIP model to determine important global control decisions. Its goal is to avoid changes in the network elements' settings while deviations from future inflow pressures as well as supplies and demands are minimized. A sequential linear programming inspired post-processing routine is run to derive physically accurate solutions w.r.t. the transient gas flow in pipelines. Computational experiments based on real-world data show that meaningful solutions are quickly and reliably determined. Therefore, the algorithmic approach is used within KOMPASS, a decision support system for the transient network control that we developed together with the Open Grid Europe GmbH (OGE), one of Europe's largest natural gas TSOs. Anticipating future use cases, we adapt the aforementioned algorithmic approach for hydrogen transport. We investigate whether the natural gas infrastructure can be repurposed and how the network control changes when energy-equivalent amounts of hydrogen are transported. Besides proving the need for purpose-built compressors, we observe that, due to the reduced linepack, the network control becomes more dynamic, compression energy increases by 440% on average, and stricter regulatory rules regarding the balancing of supply and demand become necessary. Extreme load flows expose the technical limits of gas networks and are therefore of great importance to the TSOs. In this context, we introduce the Maximum Transportation Problem and the Maximum Potential Transport Moment Problem to determine severe transport scenarios. Both can be modeled as linear bilevel programs where the leader selects supplies and demands, maximizing the follower's transport effort. To solve them, we identify solution-equivalent instances with acyclic networks, provide variable bounds regarding their KKT reformulations, apply the big-M technique, and solve the resulting MIPs. A case study shows that the obtained scenarios exceed the maximum severity values of a provided test set by at least 23%. OGE's transmission system is 11,540km long. Monitoring it is crucial for safe operations. To this end, we discuss the idea of using uncrewed aerial vehicles and introduce the Length-Constrained Cycle Partition Problem to optimize their routing. Its goal is to find a smallest cycle partition satisfying vertex-induced length requirements. Besides a greedy-style heuristic, we propose two MIP models. Combining them with symmetry-breaking constraints as well as valid inequalities and lower bounds from conflict hypergraphs yields a highly performant solution algorithm for this class of problems.

Description: The Hemiptera is the largest non-endopterygote insect order comprising approximately 98,000 recent species. All species of the suborders Cicadomorpha (leafhoppers, spittlebugs, treehoppers and cicadas) and Fulgoromorpha (planthoppers) feed by sucking sap from plant tissues and are thus often vectors for economically important phytopathogens. Except for the cicadas (Cicadomorpha: Cicadoidea: Cicadidae) which produce air-borne sounds, all species of the suborders Cicadomorpha and Fulgoromorpha communicate by vibrational (substrate-borne) signals. While the generation of these signals has been extensively investigated, the mechanisms of perception are poorly understood. This study provides a full description and 3D reconstruction of a large and complex array of six paired chordotonal organs in the first abdominal segments of the Rhododendron leafhopper Graphocephala fennahi (Cicadomorpha: Membracoidea: Cicadellidae). Further we were able to identify homologous organs in the closely related spittlebug Philaenus spumarius (Cicadomorpha: Cercopoidea: Aphrophoridae) and the planthopper Issus coleoptratus (Fulgoromorpha: Fulgoroidea: Issidae). The configuration is congruent with the abdominal chordotonal organs in cicadas, where one of them is an elaborate tympanal organ. This indicates that these organs, together with the tymbal organ constitute a synapomorphy of the Tymbalia (Hemiptera excl. Sternorrhyncha). Our results contribute to the understanding of the evolution from substrate-borne to airborne communication in insects.

Description: The present dataset contains the 3D models analyzed in Berio, F., Bayle, Y., Baum, D., Goudemand, N., and Debiais-Thibaud, M. 2022. Hide and seek shark teeth in Random Forests: Machine learning applied to Scyliorhinus canicula. It contains the head surfaces of 56 North Atlantic and Mediterranean small-spotted catsharks Scyliorhinus canicula, from which tooth surfaces were further extracted to perform geometric morphometrics and machine learning.

Description: Shark populations that are distributed alongside a latitudinal gradient often display body size differences at sexual maturity and vicariance patterns related to their number of tooth files. Previous works have demonstrated that Scyliorhinus canicula exhibits distinct genetic structures, life history traits, and body size differences between populations inhabiting the North Atlantic Ocean and the Mediterranean Sea. In this work, we sample more than 3,000 S. canicula teeth from 56 specimens and provide and use a dataset containing their shape coordinates. We investigate tooth shape and form differences between a Mediterranean and an Atlantic S. canicula population using two approaches. Classification results show that the classical geometric morphometric framework is outperformed by an original Random Forests-based framework. Visually, both S. canicula populations share similar ontogenetic trends and timing of gynandric heterodonty emergence but the Atlantic population has bigger, blunter teeth, and less numerous accessory cusps than the Mediterranean population. According to the models, the populations are best differentiated based on their lateral tooth edges, which bear accessory cusps, and the tooth centroid sizes significantly improve classification performances. The differences observed are discussed in light of dietary and behavioural habits of the populations considered. The method proposed in this study could be further adapted to complement DNA analyses to identify shark species or populations based on tooth morphologies. This process would be of particular interest for fisheries management and identification of shark fossils.

Description: Grasping, in both biological and engineered mechanisms, can be highly sensitive to the gripper and object morphology, as well as perception and motion planning. Here we circumvent the need for feedback or precise planning by using an array of fluidically-actuated slender hollow elastomeric filaments to actively entangle with objects that vary in geometric and topological complexity. The resulting stochastic interactions enable a unique soft and conformable grasping strategy across a range of target objects that vary in size, weight, and shape. We experimentally evaluate the grasping performance of our strategy, and use a computational framework for the collective mechanics of flexible filaments in contact with complex objects to explain our findings. Overall, our study highlights how active collective entanglement of a filament array via an uncontrolled, spatially distributed scheme provides new options for soft, adaptable grasping.

Description: Faithful chromosome segregation requires the assembly of a bipolar spindle, consisting of two antiparallel microtubule (MT) arrays having most of their minus ends focused at the spindle poles and their plus ends overlapping in the spindle midzone. Spindle assembly, chromosome alignment and segregation require highly dynamic MTs. The plus ends of MTs have been extensively investigated; instead, their minus end structure remains poorly characterized. Here, we used large-scale electron tomography to study the morphology of the MT minus ends in 3D-reconstructed metaphase spindles in HeLa cells. In contrast to the homogeneous open morphology of the MT plus ends at the kinetochores, we found that MT minus ends are heterogeneous showing either open or closed morphologies. Silencing the minus-end specific stabilizer, MCRS1 increased the proportion of open MT minus ends. Altogether, these data suggest a correlation between the morphology and the dynamic state of the MT ends. Taking this heterogeneity of the MT minus end morphologies into account, our work indicates an unsynchronized behavior of MTs at the spindle poles, thus laying the ground for further studies on the complexity of MT dynamics regulation.

Description: The remarkably complex skeletal systems of the sea stars (Echinodermata, Asteroidea), consisting of hundreds to thousands of individual elements (ossicles), have intrigued investigators for more than 150 years. While the general features and structural diversity of isolated asteroid ossicles have been well documented in the literature, the task of mapping the spatial organization of these constituent skeletal elements in a whole-animal context represents an incredibly laborious process, and as such, has remained largely unexplored. To address this unmet need, particularly in the context of understanding structure-function relationships in these complex skeletal systems, we present an integrated approach that combines micro-computed tomography, semi-automated ossicle segmentation, data visualization tools, and the production of additively manufactured tangible models to reveal biologically relevant structural data that can be rapidly analyzed in an intuitive manner. In the present study, we demonstrate this high-throughput workflow by segmenting and analyzing entire skeletal systems of the giant knobby star, Pisaster giganteus, at four different stages of growth. The in-depth analysis, presented herein, provides a fundamental understanding of the three-dimensional skeletal architecture of the sea star body wall, the process of skeletal maturation during growth, and the relationship between skeletal organization and morphological characteristics of individual ossicles. The widespread implementation of this approach for investigating other species, subspecies, and growth series has the potential to fundamentally improve our understanding of asteroid skeletal architecture and biodiversity in relation to mobility, feeding habits, and environmental specialization in this fascinating group of echinoderms.

Description: Shape analysis provides principled means for understanding anatomical structures from medical images. The underlying notions of shape spaces, however, come with strict assumptions prohibiting the analysis of incomplete and/or topologically varying shapes. This work aims to alleviate these limitations by adapting the concept of soft correspondences. In particular, we present a graph-based learning approach for morphometric classification of disease states that is based on a generalized notion of shape correspondences in terms of functional maps. We demonstrate the performance of the derived classifier on the open-access ADNI database for differentiating normal controls and subjects with Alzheimer’s disease. Notably, our experiment shows that our approach can improve over state-of-the-art from geometric deep learning.