Refine
Faculty / Organisational entity
- Fachbereich Mathematik (35)
- Fraunhofer (ITWM) (3)
Year of publication
Document Type
- Preprint (38) (remove)
Keywords
- Mathematikunterricht (2)
- Modellierung (2)
- hub location (2)
- integer programming (2)
- integer programming (2)
- network flows (2)
- optimization (2)
- praxisorientiert (2)
- valid inequalities (2)
- Algorithmics (1)
-
Hierarchical Edge Colorings and Rehabilitation Therapy Planning in Germany
(2014)
- In this paper we give an overview on the system of rehabilitation clinics in Germany in general and the literature on patient scheduling applied to rehabilitation facilities in particular. We apply a class-teacher model developed to this environment and then generalize it to meet some of the specific constraints of inpatient rehabilitation clinics. To this end we introduce a restricted edge coloring on undirected bipartite graphs which is called group-wise balanced. The problem considered is called patient-therapist-timetable problem with group-wise balanced constraints (PTTPgb). In order to specify weekly schedules further such that they produce a reasonable allocation to morning/afternoon (second level decision) and to the single periods (third level decision) we introduce (hierarchical PTTPgb). For the corresponding model, the hierarchical edge coloring problem, we present some first feasibility results.
-
Sink Location to Find Optimal Shelters in Evacuation Planning
(2014)
- The sink location problem is a combination of network flow and location problems: From a given set of nodes in a flow network a minimum cost subset \(W\) has to be selected such that given supplies can be transported to the nodes in \(W\). In contrast to its counterpart, the source location problem which has already been studied in the literature, sinks have, in general, a limited capacity. Sink location has a decisive application in evacuation planning, where the supplies correspond to the number of evacuees and the sinks to emergency shelters. We classify sink location problems according to capacities on shelter nodes, simultaneous or non-simultaneous flows, and single or multiple assignments of evacuee groups to shelters. Resulting combinations are interpreted in the evacuation context and analyzed with respect to their worst-case complexity status. There are several approaches to tackle these problems: Generic solution methods for uncapacitated problems are based on source location and modifications of the network. In the capacitated case, for which source location cannot be applied, we suggest alternative approaches which work in the original network. It turns out that latter class algorithms are superior to the former ones. This is established in numerical tests including random data as well as real world data from the city of Kaiserslautern, Germany.
-
On the Generality of the Greedy Algorithm for Solving Matroid Base Problems
(2013)
- It is well known that the greedy algorithm solves matroid base problems for all linear cost functions and is, in fact, correct if and only if the underlying combinatorial structure of the problem is a matroid. Moreover, the algorithm can be applied to problems with sum, bottleneck, algebraic sum or \(k\)-sum objective functions.
-
Scheduling and Location (ScheLoc): Makespan Problem with Variable Release Dates
(2007)
- While in classical scheduling theory the locations of machines are assumed to be fixed we will show how to tackle location and scheduling problems simultaneously. Obviously, this integrated approach enhances the modeling power of scheduling for various real-life problems. In this paper, we present in an exemplary way theory and a solution algorithm for a specific type of a scheduling and a rather general, planar location problem, respectively. More general results and a report on numerical tests will be presented in a subsequent paper.
-
Multicriteria network location problems with sumb objectives
(1999)
- In this paper network location problems with several objectives are discussed, where every single objective is a classical median objective function. We will lock at the problem of finding Pareto optimal locations and lexicographically optimal locations. It is shown that for Pareto optimal locations in undirected networks no node dominance result can be shown. Structural results as well as efficient algorithms for these multi-criteria problems are developed. In the special case of a tree network a generalization of Goldman's dominance algorithm for finding Pareto locations is presented.
-
Classification of Location Problems
(1999)
- There are several good reasons to introduce classification schemes for optimization problems including, for instance, the ability for concise problem statement opposed to verbal, often ambiguous, descriptions or simple data encoding and information retrieval in bibliographical information systems or software libraries. In some branches like scheduling and queuing theory classification is therefore a widely accepted and appreciated tool. The aim of this paper is to propose a 5-position classification which can be used to cover all location problems. We will provide a list of currentliy available symbols and indicate its usefulness in a - necessarily non-comprehensive - list of classical location problems. The classification scheme is in use since 1992 and has since proved to be useful in research, software development, classroom, and for overview articles.
-
Planar Location Problems with Barriers under Polyhedral Gauges
(1999)
- The Weber problem for a given finite set of existing facilities {cal E}x = {Ex_1,Ex_2, ... ,Ex_M} subset R^2 with positive weights w_m (m = 1, ... ,M) is to find a new facility X* in R^2 such that sum_{m=1}^{M} w_{m}d(X,Ex_m) is minimized for some distance function d. In this paper we consider distances defined by polyhedral gauges. A variation of this problem is obtained if barriers are introduced which are convex polygonal subsets of the plane where neither location of new facilities nor traveling is allowed. Such barriers like lakes, military regions, national parks or mountains are frequently encountered in practice.From a mathematical point of view barrier problems are difficult, since the prensence of barriers destroys the convexity of the objective function. Nevertheless, this paper establishes a descretization result: One of the grid points in the grid defined by the existing facilities and the fuundamental directions of the gauge distances can be proved to be an optimal location. Thus the barrier problem can be solved with a polynomial algorithm.
-
Geometric Methods to Solve Max-Ordering Location Problems
(1999)
- Location problems with Q (in general conflicting) criteria are considered. After reviewing previous results of the authors dealing with lexicographic and Pareto location the main focus of the paper is on max-ordering locations. In these location problems the worst of the single objectives is minimized. After discussing some general results (including reductions to single criterion problems and the relation to lexicographic and Pareto locations) three solution techniques are introduced and exemplified using one location problem class, each: The direct approach, the decision space approach and the objective space approach. In the resulting solution algorithms emphasis is on the representation of the underlying geometric idea without fully exploring the computational complexity issue. A further specialization of max-ordering locations is obtained by introducing lexicographic max-ordering locations, which can be found efficiently. The paper is concluded by some ideas about future research topics related to max-ordering location problems.
-
A Note on Center Problems with forbidden Polyhedra
(1999)
- The problem of finding an optimal location X* minimizing the maximum Euclidean distance to existing facilities is well solved by e.g. the Elzinga-Hearn algorithm. In practical situations X* will however often not be feasible. We therefore suggest in this note a polynomial algorithm which will find an optimal location X^F in a feasible subset F of the plane R^2
-
Heuristics for the K-Cardinality Tree and Subgraph Problems
(1996)
- In this paper we consider the problem of finding in a given graph a minimal weight subtree of connected subgraph, which has a given number of edges. These NP-hard combinatorial optimization problems have various applications in the oil industry, in facility layout and graph partitioning. We will present different heuristic approaches based on spanning tree and shortest path methods and on an exact algorithm solving the problem in polynomial time if the underlying graph is a tree. Both the edge- and node weighted case are investigated and extensive numerical results on the behaviour of the heuristics compared to optimal solutions are presented. The best heuristic yielded results within an error margin of less than one percent from optimality for most cases. In a large percentage of tests even optimal solutions have been found.
