Cologne Excellence Cluster on Cellular Stress Responses in Aging Associated Diseases
computer science publication serverNot a member yet
819 research outputs found
Sort by
Solving the Simple Offset Assignment Problem as a Traveling Salesman
No full textIn this paper, we present an exact approach to the Simple Offset Assignment problem arising in the domain of address code generation for digital signal processors. It is based on transformations to weighted Hamiltonian cycle problems and integer linear programming. To the best of our knowledge, it is the first approach capable to solve all instances of the established OffsetStone benchmark set to optimality within reasonable time. Therefore, it enables to evaluate the quality of several heuristics relative to the optimum solutions for the first time. Further, using the same transformations, we present a simple and effective improvement heuristic. In addition, we include an existing heuristic into our experiments that has so far not been evaluated with OffsetStone
Algorithm Engineering im Graphenzeichnen
No full textAnhand zweier Beispiele illustrieren wir die Anwendung von Algorithm Engineering im Bereich des automatischen Zeichnens von Graphen. Zunächst berichten wir über die Planarisierungsmethode und zeichnen ihre Entwicklung in den letzten ca. 10 Jahren nach. Dann widmen wir uns der Darstellung von Clustergraphen als topographische Karten, einem Thema, mit dem wir uns erst seit kurzem beschäftigen. Schließlich geben wir einen Ausblick auf eine mögliche Zusammenführung dieser scheinbar zusammenhanglosen Gebiete des automatischen Zeichnens von Graphen. Ein Großteil der hier beschriebenen Entwicklungen wurde von der DFG im Rahmen des SPP 1307 bzw. vorangegangenen Schwerpunktprogrammen gefördert
Applicability of rescheduling strategies in tram networks
No full textHighly utilized tram networks, where multiple lines share tracks and stations, are inevitably affected by dis-turbances during daily operation. While consequences of small, local perturbations may be counteracted by schedule characteristics, e.g. robustness, long lasting disturbances have to be addressed by dispatchers via schedule adjustments.
Several methods for the identification and assessment of different rescheduling actions have been proposed. However, most of these methods have only been applied in railway networks. Therefore, in this paper we compare different rescheduling strategies and assess their applicability in tram networks.
This paper begins with a description of possible rescheduling actions and the requirements and limitations to rescheduling strategies in tram networks. Different strategies for railway networks are then described and compared in regard to their applicability in tram networks
A robust schedule for Montpellier's Tramway network
No full textThe city of Montpellier in the Languedoc-Roussillon region of France features a fast growing tram network as a central part of its public service infrastructure. Here, as in many other tram networks, resources like tracks and stations are shared between different lines. Because of the resulting dependencies, small inevitable delays can spread through the network and affect its global performance.
Abstract This article examines whether a robust tram schedule may help to raise punctuality in Montpellier's tram network. To accomplish this, we apply a tool set designed to generate schedules optimized for robustness, which also satisfy given sets of planning requirements. These tools allow to compare time tables with respect to their punctuality and other key indicators.
Abstract After an introduction to the goals of this paper, we continue with a description of the tool set focusing on optimization and simulation modules. These software utilities are then employed to generate and simulate robust and non-robust schedules for Montpellier's tram network, which are subsequently compared for the resulting delays
Engineering Branch-and-Cut Algorithms for the Equicut Problem
No full textA minimum equicut of an edge-weighted graph is a partition of the nodes of the graph into two sets of equal size such hat the sum of the weights of edges joining nodes in different partitions is minimum. We compare basic linear and semidefnite relaxations for the equicut problem, and and that linear bounds are competitive with the corresponding
semidefnite ones but can be computed much faster. Motivated by an application of equicut in theoretical physics, we revisit an approach by Brunetta et al. and present an enhanced branch-and-cut algorithm. Our computational results suggest that the proposed branch-andcut
algorithm has a better performance than the algorithm of Brunetta et al.. Further, it is able to solve to optimality in reasonable time several instances with more than 200 nodes from the physics application
Effectiveness of pre- and inprocessing for CDCL-based SAT solving
No full textApplying pre- and inprocessing techniques to simplify CNF formulas both before and during search can considerably improve the performance of modern SAT solvers. These algorithms mostly aim at reducing the number of clauses, literals, and variables in the formula. However, to be worthwhile, it is necessary that their additional runtime does not exceed the runtime saved during the subsequent SAT solver execution. In this paper we investigate the efficiency and the practicability of selected simplification algorithms for CDCL-based SAT solving. We first analyze them by means of their expected impact on the CNF formula and SAT solving at all. While testing them on real-world and combinatorial SAT instances, we show which techniques and combinations of them yield a desirable speedup and which ones should be avoided
The Early Years in Bonn and Augsburg
No full textMartin Grötschel is one of the most influential mathematicians of our time. He has received numerous honors and serves in a number of key positions in the international mathematical community. A summary is sketched in the preceding short curriculum vitae taken from his professional homepage. Numerous scientific and popular articles recount his achievements and prominent role. These include articles in respected papers such as DIE ZEIT, Financial Times, Die Welt, and Der Tagesspiegel. His “scientific facets” will be covered in detail in the rest of this book.
When we first conceived of this chapter, we had a different perspective in mind. As his first doctoral descendants, we can tell a different story, because we were actively involved in his early career. This was the time when he developed from a scientific assistant in Bonn to a full professor in Augsburg. In the following, we recount some of our memories of this time, with no guarantee for either accuracy or completeness. Instead, these are the stories that came to mind when we sat together in Heidelberg and Cologne, preparing this chapter
Simulation and optimization of Cologne's tram schedule
No full textIn many tram networks multiple lines share tracks and stations, thus requiring robust schedules which prevent inevitable delays from spreading through the network. Feasible schedules also have to fulfill various planning requirements originating from political and economical reasons.
In this article we present a tool set designed to generate schedules optimized for robustness, which also satisfy given sets of planning requirements. These tools allow us to compare time tables with respect to their applicability and evaluate them prior to their implementation in the field.
This paper begins with a description of the tool set focusing on optimization and simulation modules. These software utilities are then employed to generate schedules for our hometown Cologne's tram network, and to subsequently compare them for their applicability
A simulation based approach on robust airline job pairing
No full textJob paring, i.e. the composition of duty rosters from single activities, is an important part of the airline operations planning process. With labor costs being a major factor in an airline's cost structure, such personnel schedules have to ensure efficiency to be of practical relevance. At the same time they have to improve customer acceptance by offering best possible robustness, keeping inevitable local delays from spreading through the airline's flight network.
In this paper we present a project currently in development which aims for generating robust personnel schedules for airline operations. The resulting tool set will allow us to effectively allocate flight personnel, using optimization and simulation techniques to generate and compare schedules with respect to their applicability and their demand for standby personnel, and to evaluate them prior to their implementation in the field.
This paper begins with a short introduction of the airline planning process, focusing on the job pairing problem. We then describe our project, presenting our optimization and simulation approaches