J. Computer Applications
Refine
Year of publication
Document Type
- ZIB-Report (45)
- Master's Thesis (10)
- Bachelor's Thesis (3)
- Doctoral Thesis (3)
Keywords
- Periodic Timetabling (8)
- Periodic Event Scheduling Problem (6)
- Mixed-Integer Programming (4)
- Mixed Integer Programming (3)
- Railway Timetabling (3)
- model-based inversion (3)
- Computational Diagnosis (2)
- Knee Osteoarthritis (2)
- Machine Learning (2)
- Monte Carlo (2)
- Periodic timetabling (2)
- Public Transport (2)
- Railway Track Allocation (2)
- Timetabling (2)
- blood oxygen saturation (2)
- branch-and-bound (2)
- inverse problem (2)
- quantitative photoacoustic imaging (2)
- spectral unmixing (2)
- 2-photon microscopy (1)
- 3D neural network (1)
- Adaptive Importance Sampling (1)
- Ancient sundials (1)
- Balanced Cuts (1)
- Benchmark Solutions (1)
- Benders Decomposition (1)
- Bi-invariant statistics (1)
- Bipartite matching (1)
- Boolean Satisfiability Problem (1)
- Brain connectomes (1)
- Buchungsvalidierung (1)
- Bézier splines (1)
- Change-cycle inequality (1)
- Connected Component Labeling (1)
- Cycle Bases (1)
- Cycle inequality (1)
- Dense connectome (1)
- Discrete optimization (1)
- GPGPU (1)
- Gasnetzplanung (1)
- Girsanov (1)
- Graph Algorithms (1)
- Graph Partitioning (1)
- Graph Separators (1)
- Integrated Passenger Routing (1)
- Interval Data (1)
- Ising Model (1)
- Lattice problem (1)
- Lattice-based cryptography (1)
- Line Planning (1)
- MINLP model (1)
- Metadynamics (1)
- Metastability (1)
- Mixed-Integer Linear Programming (1)
- Molecular Dynamics (1)
- Monte Carlo methods for light transport (1)
- Moving Block (1)
- NBLAST (1)
- Network Design (1)
- Nominierungsvalidierung (1)
- Non Equilibrium Sampling (1)
- Nonlinear Programming (1)
- PESPlib (1)
- Parallel algorithms (1)
- Piecewise Linear Approximation (1)
- Preprocessing Shortest Path Problems (1)
- Reconstruction (1)
- Regression in Riemannian manifolds (1)
- Rescheduling (1)
- SCIP (1)
- SCIP, Mathematical optimization, Python, Modeling (1)
- Shape analysis (1)
- Shortest Routes in Public Transport (1)
- Shortest vector problem (1)
- Split Closure (1)
- Swendsen-Wang Multi-Cluster Algorithm (1)
- Technische Kapazitäten (1)
- Topologieplanung (1)
- Topology Optimization (1)
- Train Routing (1)
- Ubiquity Generator Framework (1)
- Variance Reduction (1)
- Vehicle scheduling (1)
- Xeon Phi (1)
- acyclic orientations (1)
- approximate convex decomposition (1)
- benchmarking (1)
- bipolar orientations (1)
- bone anchored hearing implant (1)
- bound tightening (1)
- boundary conditions (1)
- brain wiring (1)
- cell type (1)
- chromophore concentration (1)
- clustering (1)
- column generation (1)
- compressor station (1)
- computational lithography (1)
- computational metrology (1)
- convex hull reformulation (1)
- coordinate search (1)
- cow, potassium, model, ode (1)
- cultural heritage (1)
- data management (1)
- data sets (1)
- data workflows (1)
- digital preservation (1)
- disjunctive set (1)
- dislocation, diffraction contrast, scanning transmission electron microscopy, stereoscopy, visualization (1)
- electromagnetic field solver (1)
- elevator control (1)
- entry-exit model (1)
- enumeration algorithm (1)
- filopodia (1)
- finite- element methods (1)
- flow patterns (1)
- freely allocable capacity (1)
- gas compressor modeling (1)
- gas compressor modeling, polyhedral model, accuracy, z factor (1)
- gas network optimization (1)
- growth cone dynamics (1)
- large-scale mixed-integer nonlinear programming (1)
- linear programming (1)
- mixed-integer programming (1)
- model (1)
- model reduction (1)
- model reformulation (1)
- multi-modal, intergrated data analysis, topology (1)
- multi-way compressor station (1)
- multiple sources and sinks (1)
- nanolithography (1)
- nanooptics (1)
- neuroinformatics (1)
- neuron similarity (1)
- nonlinear model (1)
- operations research in energy (1)
- optical critical dimension metrology (1)
- optical metrology (1)
- optimization (1)
- optimization in public transport (1)
- oxygen saturation (1)
- periodic timetabling (1)
- photoacoustic imaging (1)
- polyhedral model (1)
- quantitative photoacoustic tomography (1)
- reduced basis method (1)
- reoptimization (1)
- segmentation (1)
- simplex (1)
- surgery planning (1)
- unfolding, papyri, computed tomography (1)
- visualization (1)
Institute
- Mathematical Optimization (19)
- Network Optimization (19)
- Visual and Data-centric Computing (13)
- Visual Data Analysis (10)
- Numerical Mathematics (5)
- Distributed Algorithms and Supercomputing (3)
- Mathematical Optimization Methods (2)
- Applied Algorithmic Intelligence Methods (1)
- Computational Nano Optics (1)
- Digital Data and Information for Society, Science, and Culture (1)
Periodic timetabling is a challenging planning task in public transport.
As safety requirements are crucial, track allocation is indispensable for validating the practical feasibility of a railway timetable. For busy stations with limited capacities, this requires a detailed planning of turnarounds. It is therefore desirable to integrate timetabling not only with track allocation, but also with vehicle scheduling and line planning. This is captured by the Integrated Line Planning and Turn-Sensitive Periodic Timetabling Problem with Track Choice, whose MIP formulation has been demonstrated to be effective for construction site railway rescheduling, as long as a good quality initial solution is available. In this paper, we discuss how to generate such a solution by extending the SAT formulation of the Periodic Event Scheduling Problem with track choice, track occupation, and minimum service frequency components. The SAT approach is superior to pure MIP on real-world instances of the S-Bahn Berlin network.
Polymorphism is the property exhibited by many inorganic and organic molecules to crystallize in more than one crystal structure. There is a strong need for understanding the influencing factors on polymorphism, as it is responsible for differences in many physicochemical properties such as stability and solubility. Nearly 80 % of marketed drugs exhibit polymorphism. In this work, we took the model system of paracetamol to investigate the influence of solvent choice on its polymorphism. Different methods were developed and employed to understand the influence of small organic solvents on the crystallization of paracetamol. Non-equilibrium molecular dynamics simulations with periodic simulated annealing were used as a tool to probe the nature of precursors of the metastable intermediates occurring in the crystallization process. Using this method, it was found that the structures of the building blocks of crystals of paracetamol is governed by solvent-solute interactions. In situ Raman spectroscopy was used with a custom-made acoustic levitator to follow crystallization. This set-up is a reliable method for investigating solvent influence, attenuating heterogeneous nucleation and stabilizing other environmental factors. It was established that as a solvent, ethanol is much stronger than methanol in its effect of driving paracetamol solutions to their crystal form. The time-resolved Raman spectroscopy crystallization data was processed using a newly developed objective function based non-negative matrix factorization method (NMF). An orthogonal time-lapse photography was used in conjunction with NMF to get unique and accurate factors that pertain to the spectra and concentrations of different moieties of paracetamol crystallization existing as latent components in the untreated data.
The Periodic Event Scheduling Problem (PESP) is a notoriously hard combinatorial optimization problem, essential for the design of periodic timetables in public transportation. The coefficients of the integer variables in the standard mixed integer linear programming formulations of PESP are the period time, e.g., 60 for a horizon of one hour with a resolution of one minute. In many application scenarios, lines with different frequencies have to be scheduled, leading to period times with many divisors. It then seems natural to consider derived instances, where the period time is a divisor of the original one, thereby smaller, and bounds are scaled and rounded accordingly. To this end, we identify two rounding schemes: wide and tight. We then discuss the approximation performance of both strategies, in theory and practice.
We present incremental heuristics for the Periodic Event Scheduling Problem (PESP), the standard mathematical tool to optimize periodic timetables in public transport. The core of our method is to solve successively larger subinstances making use of previously found solutions. Introducing the technical notion of free stratifications, we formulate a general scheme for incremental heuristics for PESP. More practically, we use line and station information to create heuristics that add lines or stations one by one, and we evaluate these heuristics on instances of the benchmarking library PESPlib. This approach is indeed viable, and leads to new incumbent solutions for six PESPlib instances.
Mixed-integer linear programming (MILP) plays a crucial role in the field of mathematical optimization and is especially relevant for practical applications due to the broad range of problems that can be modeled in that fashion. The vast majority of MILP solvers employ the LP-based branch-and-cut approach. As the name suggests, the linear programming (LP) subproblems that need to be solved therein influence their behavior and performance significantly.
This thesis explores the impact of various LP solvers as well as LP solving techniques on the constraint integer programming framework SCIP Optimization Suite. SCIP allows for comparisons between academic and open-source LP solvers like Clp and SoPlex, as well as commercially developed, high-end codes like CPLEX, Gurobi, and Xpress.
We investigate how the overall performance and stability of an MILP solver can be improved by new algorithmic enhancements like LP solution polishing and persistent scaling that we have implemented in the LP solver SoPlex. The former decreases the fractionality of LP solutions by selecting another vertex on the optimal hyperplane of the LP relaxation, exploiting degeneracy. The latter provides better numerical properties for the LP solver throughout the MILP solving process by preserving and extending the initial scaling factors, effectively also improving the overall performance of SCIP. Both enhancement techniques are activated by default in the SCIP Optimization Suite.
Additionally, we provide an analysis of numerical conditions in SCIP through the lens of the LP solver by comparing different measures and how these evolve during the different stages of the solving process. A side effect of our work on this topic was the development of TreeD: a new and convenient way of presenting the search tree interactively and animated in the three-dimensional space. This visualization technique facilitates a better understanding of the MILP solving process of SCIP.
Furthermore, this thesis presents the various algorithmic techniques like the row representation and iterative refinement that are implemented in SoPlex and that distinguish the solver from other simplex-based codes. Although it is often not as performant as its competitors, SoPlex demonstrates the ongoing research efforts in the field of linear programming with the simplex method.
Aside from that, we demonstrate the rapid prototyping of algorithmic ideas and modeling approaches via PySCIPOpt, the Python interface to the SCIP Optimization Suite. This tool allows for convenient access to SCIP's internal data structures from the user-friendly Python programming language to implement custom algorithms and extensions without any prior knowledge of SCIP's programming language C. TreeD is one such example, demonstrating the use of several Python libraries on top of SCIP. PySCIPOpt also provides an intuitive modeling layer to formulate problems directly in the code without having to utilize another modeling language or framework.
All contributions presented in this thesis are readily accessible in source code in SCIP Optimization Suite or as separate projects on the public code-sharing platform GitHub.
Data analysis has become fundamental to our society and comes in multiple facets and approaches. Nevertheless, in research and applications, the focus was primarily on data from Euclidean vector spaces. Consequently, the majority of methods that are applied today are not suited for more general data types. Driven by needs from fields like image processing, (medical) shape analysis, and network analysis, more and more attention has recently been given to data from non-Euclidean spaces---particularly (curved) manifolds. It has led to the field of geometric data analysis whose methods explicitly take the structure (for example, the topology and geometry) of the underlying space into account.
This thesis contributes to the methodology of geometric data analysis by generalizing several fundamental notions from multivariate statistics to manifolds. We thereby focus on two different viewpoints.
First, we use Riemannian structures to derive a novel regression scheme for general manifolds that relies on splines of generalized Bézier curves. It can accurately model non-geodesic relationships, for example, time-dependent trends with saturation effects or cyclic trends. Since Bézier curves can be evaluated with the constructive de Casteljau algorithm, working with data from manifolds of high dimensions (for example, a hundred thousand or more) is feasible. Relying on the regression, we further develop
a hierarchical statistical model for an adequate analysis of longitudinal data in manifolds, and a method to control for confounding variables.
We secondly focus on data that is not only manifold- but even Lie group-valued, which is frequently the case in applications. We can only achieve this by endowing the group with an affine connection structure that is generally not Riemannian. Utilizing it, we derive generalizations of several well-known dissimilarity measures between data distributions that can be used for various tasks, including hypothesis testing. Invariance under data translations is proven, and a connection to continuous distributions is given for one measure.
A further central contribution of this thesis is that it shows use cases for all notions in real-world applications, particularly in problems from shape analysis in medical imaging and archaeology. We can replicate or further quantify several known findings for shape changes of the femur and the right hippocampus under osteoarthritis and Alzheimer's, respectively. Furthermore, in an archaeological application, we obtain new insights into the construction principles of ancient sundials. Last but not least, we use the geometric structure underlying human brain connectomes to predict cognitive scores. Utilizing a sample selection procedure, we obtain state-of-the-art results.
The Periodic Event Scheduling Problem (PESP) is the central mathematical tool for periodic timetable optimization in public transport. PESP can be formulated in several ways as a mixed-integer linear program with typically general integer variables.
We investigate the split closure of these formulations and show that split inequalities are identical with the recently introduced flip inequalities. While split inequalities are a general mixed-integer programming technique, flip inequalities are defined in purely combinatorial terms, namely cycles and arc sets of the digraph underlying the PESP instance. It is known that flip inequalities can be separated in pseudo-polynomial time. We prove that this is best possible unless P $=$ NP, but also observe that the complexity becomes linear-time if the cycle defining the flip inequality is fixed.
Moreover, introducing mixed-integer-compatible maps, we compare the split closures of different formulations, and show that reformulation or binarization by subdivision do not lead to stronger split closures. Finally, we estimate computationally how much of the optimality gap of the instances of the benchmark library PESPlib can be closed exclusively by split cuts, and provide better dual bounds for five instances.
The optimization of periodic timetables is an indispensable planning task in public transport. Although the periodic event scheduling problem (PESP) provides an elegant mathematical formulation of the periodic timetabling problem that led to many insights for primal heuristics, it is notoriously hard to solve to optimality. One reason is that for the standard mixed-integer linear programming formulations, linear programming relaxations are weak and the integer variables are of pure technical nature and in general do not correlate with the objective value. While the first problem has been addressed by developing several families of cutting planes, we focus on the second aspect. We discuss integral forward cycle bases as a concept to compute improved dual bounds for PESP instances. To this end, we develop the theory of forward cycle bases on general digraphs. Specifically for the application of timetabling, we devise a generic procedure to construct line-based event-activity networks, and give a simple recipe for an integral forward cycle basis on such networks. Finally, we analyze the 16 railway instances of the benchmark library PESPlib, match them to the line-based structure and use forward cycle bases to compute better dual bounds for 14 out of the 16 instances.
Classic models to derive a timetable for public transport often face a chicken-and-egg situation: A good timetable should offer passengers routes with small travel times, but the route choice of passengers depends on the timetable. While models that fix passenger routes were frequently considered in the literature, integrated models that simultaneously optimize timetables and passenger routes have seen increasing attention lately. This creates a growing need for a set of instances that allows to test and compare new algorithmic developments for the integrated problem. Our paper addresses this requirement by presenting TimPassLib, a new benchmark library of instances for integrated periodic timetabling and passenger routing.
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.
In graphical representations of public transportation networks, there is often some degree of uncertainty in the arc values, due to delays or transfer times. This uncertainty can be expressed as a parameterized weight on the transfer arcs. Classical shortest path algorithms often have difficulty handling parameterized arc weights and a tropical geometry approach has been shown as a possible solution. The connection between the classical shortest path problem and tropical geometry is well establish: Tropically multiplying the n × n adjacency matrix of a graph with itself n − 1 times results in the so-called Kleene star, and is a matrix-form solution to the all-pairs shortest path problem. Michael Joswig and Benjamin Schröter showed in their paper The Tropical Geometry of Shortest Paths that the same method can be used to find the solution to the all-pairs shortest path problem even in the case of variable arc weights and they proposed an algorithm to solve the single-target shortest path problem in such a case. The solution takes the form of a polyhedral subdivision of the parameter space. As the number of variable arc weights grows, the time needed to execute an implementation of this algorithm grows exponentially. As the size of a public transportation network grows, the number of variable arc weights grows exponentially as well. However, it has been observed that in public transportation networks, there are usually only a few possible shortest routes. Geometrically, this means that there should be few polyhedra in the polyhedral subdivision. This algorithm is used on an example of a real-world public transportation network and an analysis of the polyhedral subdivision is made. Then a geometrical approach is used to analyze the impact of limiting the number of transfers, and thereby limiting the number of parameterized arcs used, as an estimation of the solution to the all-pairs shortest path problem
Die Planung vom Zugumläufen ist eine der wichtigsten Aufgaben für Eisenbahnun- ternehmen. Dabei spielt auch die Einhaltung von vorgegebenen Wartungsintervallen eine zentrale Rolle für die Sicherheit und Zuverlässigkeit der Schienenfahrzeuge. Wir zeigen, wie man dieses Umlaufplanungsproblem unter Beachtung von Wartungsbe- dingungen mathematisch formuliert, modelliert und löst — sowohl in der Theorie als auch im Anwendungsfall mit Szenarien der DB Fernverkehr AG, einer Konzern- tochter der Deutschen Bahn für den Schienenpersonenfernverkehr.
Markus Reuther hat sich in seiner Dissertation [11] mit diesem Problem beschäftigt und es mit Hilfe eines passenden Hypergraphen als gemischt-ganzzahliges Programm modelliert. Neben der Modellierung präsentiert Reuther in seiner Arbeit neuartige algorithmische Ideen, darunter den sogenannten Coarse-to-Fine -Ansatz, bei dem zunächst Teile des Problems auf einer weniger detaillierten ( coarse ) Ebene gelöst werden und diese Lösung dann verwendet wird, um auf effiziente Art und Weise eine Lösung für das ursprüngliche Problem zu finden. Zur Wartungsplanung nutzt Reuther einen Fluss im Hypergraphen, der den Ressourcenverbrauch der Fahrzeuge modelliert. In der linearen Relaxierung des Modells führt dies dazu, dass die Zahl der notwendigen Wartungen systematisch unterschätzt wird. Dadurch bleibt in vielen Fällen eine große Lücke zwischen dem Zielfunktionswert einer optimalen Lösung des ganzzahligen Problems und der untere Schranke, die uns die lineare Relaxierung liefert.
Wir nehmen uns in dieser Arbeit dieses Problems an. Wir entwickeln ein auf Pfaden basierendes ganzzahliges Modell für das Umlaufplanungsproblem und zeigen, dass die untere Schranke mindestens so scharf oder schärfer ist als die untere Schranke, die das Modell von Reuther liefert. Um das Modell zu lösen, entwickeln wir einen Algorithmus, der Spaltengenerierung mit dem Coarse-to-Fine-Ansatz von Reuther verbindet. Weiterhin entwickeln wir eine Spaltenauswahlregel zur Beschleunigung des Algorithmus. Das Modell und alle in der Arbeit vorgestellten Algorithmen wur- den im Rahmen der Arbeit implementiert und mit Anwendungsszenarien der DB Fernverkehr AG getestet. Unsere Tests zeigen, dass unser Modell für fast alle Szena- rien deutlich schärfere untere Schranken liefert als das Modell von Reuther. In den getesteten Instanzen konnten wir durch die Verbesserung der unteren Schranke bis zu 99% der Optimalitätslücke schließen. In einem Drittel der Fälle konnten wir durch unseren Ansatz auch für das ganzzahlige Programm verbesserte Zielfunktionswerte erreichen
Algorithms that solve the shortest path problem can largely be split into the two categories of label setting and label correcting. The Multiobjective Shortest Path (MOSP) problem is a generalization of the classical shortest path problem in terms of the dimension of the cost function. We explore the differences of two similar MOSP label setting algorithms. Furthermore, we present and prove a general method of how to derive Fully Polynomial Time Approximation Schemes (FPTAS) for MOSP label setting algorithms. Finally, we explore two pruning techniques for the one to one variants of exact label setting MOSP algorithms and adapt them to their FPTAS variants.
For this thesis we study the Constrained Horizontal Flightplanning Problem (CHFPP) for which one has to find the path of minimum cost between airports s and t in a directed graph that respects a set of boolean constraints. To this end we give a survey of three different multilabel algorithms that all use a domination subroutine. We summarize an approach by Knudsen, Chiarandini and Larsen to define this domination and afterwards present our own method which builds on that approach. We suggest different implementation techniques to speed up the computation time, most notably a Reoptimization for an iterative method to solve the problem. Furthermore we implemented the different versions of the algorithm and present statistics on their computation as well as an overview of statistics on the set of real-world constraints that we were given. Finally we present two alternative approaches that tackle the problem, a heuristic with similarities to a Lagrangian relaxation and an approach that makes use of an algorithm which finds the k shortest path of a graph such as the ones of Epstein or Yen.
Scheduling ist ein wichtiger Forschungsgegenstand im Bereich der diskreten Optimierung. Es geht darum, einen Schedule, d.h. einen Ablaufplan, für gegebene Ereignisse zu finden. Dieser soll optimal hinsichtlich einer Zielfunktion wie zum Beispiel minimaler Dauer oder Kosten sein. Dabei gibt es in der Regel Nebenbedingungen wie Vorrangbeziehungen zwischen den Ereignissen oder zeitliche Einschränkungen, die zu erfüllen sind. Falls die Ereignisse periodisch wiederkehren, spricht man von periodischem Scheduling. Beispiele sind das Erstellen von Zugfahrplänen, die Schaltungvon Ampelsignalen oder die Planung von Produktionsabläufen.
Mathematisch können diese Probleme mit dem Periodic Event Scheduling Problem (PESP) modelliert werden, das als gemischt-ganzzahliges Programm formuliert werden kann. In dieser Bachelorarbeit wird ein Ansatz zur Lösung des PESP mittels Zerlegung und Dualisierung entwickelt. In den Kapiteln 2 und 3 werden zunächst die notwendigen graphentheoretischen Grundlagen und das PESP eingeführt. In Kapitel 4 wird das PESP durch Fixierung der ganzzahligen Variablen in lineare Programme zerlegt. Dieses Unterproblem wird dualisiert und wieder in das PESP eingesetzt. Dafür ist eine weitere Nebenbedingung nötig.
Im fünften Kapitel behandeln wir die Lösung des teildualisierten PESP. Eine Möglichkeit ist es, sich auf eine Teilmenge der Nebenbedingungen zu beschränken. Eine weitere Möglichkeit ist ein Algorithmus, derähnlich wie BendersZerlegung die Nebenbedingungen dynamisch erzeugt. Dieser Algorithmus wird in Kapitel 6 implementiert und an vier Beispielen getestet.
We propose a tropical interpretation of the solution space of the Periodic Event Scheduling Problem as a collection of polytropes, making use of the characterization of tropical cones as weighted digraph polyhedra. General and geometric properties of the polytropal collection are inspected and understood in connection with the combinatorial properties of the underlying periodic event scheduling instance. Novel algorithmic
ideas are presented and tested, making use of the aforementioned theoretical results to solve and optimize the problem.
One of the fundamental steps in the optimization of public transport is line planning. It involves determining lines and assigning frequencies of service such that costs are minimized while also maximizing passenger comfort and satisfying travel demands. We formulate the problem as a mixed integer linear program that considers all circuit-like lines in a graph and allows free passenger routing. Traveler and operator costs are included in a linear scalarization in the objective. We apply said programming problem to the Parametric City, which is a graph model introduced by Fielbaum, Jara-Díaz and Gschwender that exibly represents different cities. In his dissertation, Fielbaum solved the line planning problem for various parameter choices in the Parametric City. In a first step, we therefore review his results and make comparative computations. Unlike Fielbaum we arrive at the conclusion that the optimal line plan for this model indeed depends on the demand. Consequently, we analyze the line planning problem in-depth: We find equivalent, but easier to compute formulations and provide a lower bound by LP-relaxation, which we show to be equivalent to a multi-commodity flow problem. Further, we examine what impact symmetry has on the solutions. Supported both by computational results as well as by theoretical analysis, we reach the conclusion that symmetric line plans are optimal or near-optimal in the Parametric City. Restricting the model to symmetric line plans allows for a \kappa-factor approximation algorithm for the line planning problem in the Parametric City.
This work presents a fully automated pipeline, centered around a deep neural network, as well as a method to train that network in an efficient manner, that enables accurate detection of lesions in meniscal anatomical subregions. The network architecture is based on a transformer encoder/decoder. It is trained on DESS and tuned on IW TSE 3D MRI scans sourced from the Osteoarthritis Initiative. Furthermore, it is trained in a multilabel, and multitask fashion, using an auxiliary detection head. The former enables implicit localisation
of meniscal defects, that to the best of my knowledge, has not yet been reported elsewhere. The latter enables efficient learning on the entire 3D MRI volume. Thus, the proposed method does not require any expert knowledge at inference. Aggregated inference results from two datasets resulted in an overall AUCROC result of 0.90, 0.91 and 0.93 for meniscal lesion detection anywhere in the knee, in medial and in lateral menisci respectively. These results compare very well to the related work, even though only a fraction of the data has been utilized. Clinical applicability and benefit is yet to be determined.