Philipp Hungerländer The main contributions of this thesis are the comparison of existing and the design of new exact approaches based on linear, quadratic and semidefinite relaxations for row layout problems and several applications in logistic. In particular we demonstrate that our suggested semidefinite approach is the strongest exact method to date for most row layout problems. … Read more
We suggest a new variant of a row layout problem: Find an ordering of n departments with given lengths such that the total weighted sum of their distances to a given checkpoint is minimized. The Checkpoint Ordering Problem (COP) is both of theoretical and practical interest. It has several applications and is conceptually related to … Read more
The $k$-Parallel Row Ordering Problem (kPROP) is an extension of the Single-Row Facility Layout Problem (SRFLP) that considers arrangements of the departments along more than one row. We propose an exact algorithm for the kPROP that extends the semidefinite programming approach for the SRFLP by modelling inter-row distances as products of ordering variables. For k=2 … Read more
A primal-dual active set method for quadratic problems with bound constraints is presented which extends the infeasible active set approach of [K. Kunisch and F. Rendl. An infeasible active set method for convex problems with simple bounds. SIAM Journal on Optimization, 14(1):35-52, 2003]. Based on a guess of the active set, a primal-dual pair (x,α) … Read more
In this paper we discuss two particular layout problems, namely the Single-Row Equidistant Facility Layout Problem (SREFLP) and the Single-Row Facility Layout Problem (SRFLP). Our aim is to consolidate the two respective branches in the layout literature. We show that the SREFLP is not only a special case of the Quadratic Assignment Problem but also … Read more
We present a semide nite programming (SDP) approach for the problem of ordering vertices of a layered graph such that the edges of the graph are drawn as vertical as possible. This Multi-Level Vertical Ordering (MLVO) problem is a quadratic ordering problem and conceptually related to the well-studied problem of Multi-Level Crossing Minimization (MLCM). In contrast … Read more
In traditional multi-level graph drawing – known as Sugiyama’s framework – the number of crossings is considered one of the most important goals. Herein, we propose the alternative concept of optimizing the verticality of the drawn edges. We formally specify the problem, discuss its relative merits, and show that drawings that are good w.r.t. verticality … Read more
The single row facility layout problem (SRFLP) is an NP-hard combinatorial optimization problem that is concerned with the arrangement of n departments of given lengths on a line so as to minimize the weighted sum of the distances between department pairs. (SRFLP) is the one-dimensional version of the facility layout problem that seeks to arrange … Read more
Ordering problems assign weights to each ordering and ask to find an ordering of maximum weight. We consider problems where the cost function is either linear or quadratic. In the first case, there is a given profit if the element u is before v in the ordering. In the second case, the profit depends on … Read more