Cologne Excellence Cluster on Cellular Stress Responses in Aging Associated Diseases
computer science publication serverNot a member yet
819 research outputs found
Sort by
Improved Mixed-Integer Programming Models for Multiprocessor Scheduling with Communication Delays
No full textWe revise existing and introduce new mixed-integer programming models for the Multiprocessor Scheduling Problem with Communication Delays. At first, we show how to provably reduce the number of product variables necessary to explicitly linearize the so-called packing formulation that contains bilinear terms. Then, we reveal that the feasible region of almost all existing formulations contains redundant solutions and formulate new constraints in order to exclude these. At the same time, by exploiting further structural properties, the models are improved concerning their size, strength, and modeling complexity. The discussion of these improvements leads to new much more compact formulations which are then experimentally compared with each other and with other formulations from the literature. We set up a realistic scenario with a preprocessing of the task graphs, delivering the gained information equally to all the tested models and evaluate not only running times but also the obtained lower and upper bounds on the makespan objective for unsolved instances of a large scale benchmark set
Compact Layered Drawings of General Directed Graphs
No full textWe consider the problem of layering general directed graphs
under height and possibly also width constraints. Given a directed graphG = (V,A) and a maximal height, we propose a layering approach that minimizes a weighted sum of the number of reversed arcs, the arc lengths, and the width of the drawing. We call this the Compact Generalized Layering Problem (CGLP). Here, the width of a drawing is defined as the maximum sum of the number of vertices placed on a layer and the number of dummy vertices caused by arcs traversing the layer. The CGLP is NP-hard. We present two MIP models for this problem. The first one (EXT) is our extension of a natural formulation for directed acyclic graphs as suggested by Healy and Nikolov. The second one (CGL) is a new formulation based on partial orderings. Our computational experiments on two benchmark sets show that the CGL formulation can be solved much faster than EXT using standard commercial MIP solvers. Moreover, we suggest a variant of CGL, called MML, that can be seen as a heuristic approach. In our experiments, MML clearly improves on CGL in terms of running time while it does not considerably increase the average arc lengths and widths of the layouts although it solves a slightly different problem where the dummy vertices are not taken into account
Bitonic st-orderings for Upward Planar Graphs
Full text linkCanonical orderings serve as the basis for many incremental planar drawing algorithms. All these techniques, however, have in common that they are limited to undirected graphs. While st-orderings do extend to directed graphs, especially planar st-graphs, they do not offer the same properties as canonical orderings. In this work we extend the so called bitonic st-orderings to directed graphs. We fully characterize planar st-graphs that admit such an ordering and provide a linear-time algorithm for recognition and ordering. If for a graph no bitonic st-ordering exists, we show how to find in linear time a minimum set of edges to split such that the resulting graph admits one. With this new technique we are able to draw every upward planar graph on n vertices by using at most one bend per edge, at most n - 3 bends in total and within quadratic area
Compact Linearization for Binary Quadratic Problems subject to Assignment Constraints
No full textWe prove new necessary and sufficient conditions to carry out a compact linearization approach for a general class of binary quadratic problems subject to assignment constraints
as it has been proposed by Liberti in 2007. The new conditions resolve inconsistencies that can occur when the original method is used. We also present a mixed-integer linear program to compute a minimally-sized linearization. When all the assignment constraints have non-overlapping variable support, this program is shown to have a totally unimodular constraint matrix. Finally, we give a polynomial-time combinatorial algorithm that is exact in this case and can still be used as a heuristic otherwise
An Integer Programming Approach to Optimal Basic Block Instruction Scheduling for Single-Issue Processors
No full textWe present a novel integer programming formulation for basic block instruction scheduling on single-issue processors. The problem can be considered as a very general sequential task scheduling problem with delayed precedence constraints. Our model is based on the linear ordering problem and has, in contrast to the last IP model proposed, numbers of variables and constraints that are strongly polynomial in the instance size. Combined with improved preprocessing techniques and given a time limit of ten minutes of CPU and system time, our branch-and-cut implementation is capable to solve all but eleven of the 369,861 basic blocks of the SPEC 2000 integer and floating point benchmarks to proven optimality. This is competitive to the current state-of-the art constraint programming approach that has also been evaluated on this test suite
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
Solving k-means on High-Dimensional Big Data
No full textIn recent years, there have been major efforts to develop data stream algorithms that process inputs in one pass over the data with little memory requirement. For the k-means problem, this has led to the development of several (1+ε)
-approximations (under the assumption that k is a constant), but also to the design of algorithms that are extremely fast in practice and compute solutions of high accuracy. However, when not only the length of the stream is high but also the dimensionality of the input points, then current methods reach their limits.
We propose two algorithms, piecy and piecy-mr that are based on the recently developed data stream algorithm BICO that can process high dimensional data in one pass and output a solution of high quality. While piecy is suited for high dimensional data with a medium number of points, piecy-mr is meant for high dimensional data that comes in a very long stream. We provide an extensive experimental study to evaluate piecy and piecy-mr that shows the strength of the new algorithms
On the non-unit count of interval graphs
No full textWe introduce the non-unit count of an interval graph as the minimum number of intervals in an interval representation whose lengths deviate from one. We characterize a variant of the non-unit count (where all interval lengths are required to be at least one) and graphs with non-unit count 1
2-Layer Fan-Planarity: From Caterpillar to Stegosaurus
Full text linkIn a fan-planar drawing of a graph there is no edge that crosses two other independent edges. We study 2-layer fan-planar drawings, i.e., fan-planar drawings such that the vertices are assigned to two distinct horizontal layers and edges are straight-line segments that connect vertices of different layers. We characterize 2-layer fan-planar drawable graphs and describe a linear-time testing and embedding algorithm for biconnected graphs. We also study the relationship between 2-layer fan-planar graphs and 2-layer right-angle crossing graphs