Refine
Year of publication
Document Type
- Preprint (37)
- Report (8)
- Article (1)
- Working Paper (1)
Language
- English (47) (remove)
Has Fulltext
- yes (47)
Keywords
- integer programming (4)
- Intensity modulated radiation therapy (3)
- Mathematikunterricht (3)
- Modellierung (3)
- modelling (3)
- praxisorientiert (3)
- Beam-on time (2)
- Combinatorial optimization (2)
- Decomposition cardinality (2)
- Field splitting (2)
- Lineare Algebra (2)
- Multileaf collimator sequencing (2)
- facets (2)
- hub location (2)
- linear algebra (2)
- mathematical education (2)
- network flows (2)
- praxis orientated (2)
- valid inequalities (2)
- (dynamic) network flows (1)
- Algorithmics (1)
- Approximation (1)
- Box Algorithms (1)
- Continuous Location (1)
- Decision support (1)
- Decomposition of integer matrices (1)
- Discrete Bicriteria Optimization (1)
- Dynamic cut (1)
- Earliest arrival augmenting path (1)
- Education (1)
- Finite Dominating Sets (1)
- FlowLoc (1)
- Gauge Distances (1)
- Graph coloring (1)
- Greedy Algorithm (1)
- Greedy algorithm (1)
- Grid Graphs (1)
- Hierarchies (1)
- Label correcting algorithm (1)
- Label setting algorithm (1)
- Lineare Optimierung (1)
- Location Theory (1)
- Location problems (1)
- Locational Planning (1)
- Machine Scheduling (1)
- Matroids (1)
- Multicriteria optimization (1)
- Multiple criteria analysis (1)
- Multiple criteria optimization (1)
- Multiple objective optimization (1)
- Network flows (1)
- Polyhedral Gauges (1)
- Project prioritization (1)
- Project selection (1)
- Rehabilitation clinics (1)
- Representation (1)
- Sandwich Algorithm (1)
- Scheduling (1)
- Simplex (1)
- Standortplanung (1)
- Stücklisten (1)
- Timetabling (1)
- Uniform matroids (1)
- Universal objective function (1)
- bicriteria shortest path problem (1)
- bills of materials (1)
- branch and cut (1)
- cancer (1)
- cancer radiation therapy (1)
- cardinality constraint combinatorial optimization (1)
- center and median problems (1)
- computational complexity (1)
- consecutive ones matrix (1)
- consecutive ones property (1)
- cut basis problem (1)
- efficient solution (1)
- facility location (1)
- graph and network algorithm (1)
- heuristic (1)
- hub covering (1)
- intensity map segmentation (1)
- inverse mathematical models (1)
- inverse optimization (1)
- k-cardinality minimum cut (1)
- label setting algorithm (1)
- linear optimization (1)
- linear programming (1)
- location theory (1)
- locational analysis (1)
- matrix decomposition (1)
- maximum capacity path (1)
- maximum flows (1)
- minimum cut (1)
- multileaf collimator (1)
- multileaf collimator sequencing (1)
- multiliead collimator sequencing (1)
- multiple objective linear programming problem (1)
- network flow (1)
- network location (1)
- optimization (1)
- radiation therapy (1)
- radiotherapy (1)
- representative systems (1)
- scheduling theory (1)
- shortest path problem (1)
- simplex (1)
- sink location (1)
- time-dependent shortest path problem (1)
- treatment planning (1)
- universal objective function (1)
- variable cardinality case (1)
Faculty / Organisational entity
Covering edges in networks
(2019)
In this paper we consider the covering problem on a networkG=(V,E)withedgedemands. The task is to cover a subsetJ⊆Eof the edges with a minimum numberof facilities within a predefined coverage radius. We focus on both the nodal andthe absolute version of this problem. In the latter, facilities may be placed every-where in the network. While there already exist polynomial time algorithms to solvethe problem on trees, we establish a finite dominating set (i.e., a finite subset ofpoints provably containing an optimal solution) for the absolute version in generalgraphs. Complexity and approximability results are given and a greedy strategy isproved to be a (1+ln(|J|))-approximate algorithm. Finally, the different approachesare compared in a computational study.
Multifacility location problems arise in many real world applications. Often, the facilities can only be placed in feasible regions such as development or industrial areas. In this paper we show the existence of a finite dominating set (FDS) for the planar multifacility location problem with polyhedral gauges as distance functions, and polyhedral feasible regions, if the interacting facilities form a tree. As application we show how to solve the planar 2-hub location problem in polynomial time. This approach will yield an ε-approximation for the euclidean norm case polynomial in the input data and 1/ε.
In this paper a modified version of dynamic network
ows is discussed. Whereas dynamic network flows are widely analyzed already, we consider a dynamic flow problem with aggregate arc capacities called Bridge
Problem which was introduced by Melkonian [Mel07]. We extend his research to integer flows and show that this problem is strongly NP-hard. For practical relevance we also introduce and analyze the hybrid bridge problem, i.e. with underlying networks whose arc capacity can limit aggregate flow (bridge problem) or the flow entering an arc at each time (general dynamic flow). For this kind of problem we present efficient procedures for
special cases that run in polynomial time. Moreover, we present a heuristic for general hybrid graphs with restriction on the number of bridge arcs.
Computational experiments show that the heuristic works well, both on random graphs and on graphs modeling also on realistic scenarios.
In this paper we consider the problem of decomposing a given integer matrix A into
a positive integer linear combination of consecutive-ones matrices with a bound on the
number of columns per matrix. This problem is of relevance in the realization stage
of intensity modulated radiation therapy (IMRT) using linear accelerators and multileaf
collimators with limited width. Constrained and unconstrained versions of the problem
with the objectives of minimizing beam-on time and decomposition cardinality are considered.
We introduce a new approach which can be used to find the minimum beam-on
time for both constrained and unconstrained versions of the problem. The decomposition
cardinality problem is shown to be NP-hard and an approach is proposed to solve the
lexicographic decomposition problem of minimizing the decomposition cardinality subject
to optimal beam-on time.
In this paper we consider the problem of decomposing a given integer matrix A into
a positive integer linear combination of consecutive-ones matrices with a bound on the
number of columns per matrix. This problem is of relevance in the realization stage
of intensity modulated radiation therapy (IMRT) using linear accelerators and multileaf
collimators with limited width. Constrained and unconstrained versions of the problem
with the objectives of minimizing beam-on time and decomposition cardinality are considered.
We introduce a new approach which can be used to find the minimum beam-on
time for both constrained and unconstrained versions of the problem. The decomposition
cardinality problem is shown to be NP-hard and an approach is proposed to solve the
lexicographic decomposition problem of minimizing the decomposition cardinality subject
to optimal beam-on time.
We consider the problem of finding efficient locations of surveillance cameras, where we distinguish
between two different problems. In the first, the whole area must be monitored and the number of cameras
should be as small as possible. In the second, the goal is to maximize the monitored area for a fixed number of
cameras. In both of these problems, restrictions on the ability of the cameras, like limited depth of view or range
of vision are taken into account. We present solution approaches for these problems and report on results of
their implementations applied to an authentic problem. We also consider a bicriteria problem with two objectives:
maximizing the monitored area and minimizing the number of cameras, and solve it for our study case.
A single facility problem in the plane is considered, where an optimal location has to be
identified for each of finitely many time-steps with respect to time-dependent weights and
demand points. It is shown that the median objective can be reduced to a special case of the
static multifacility median problem such that results from the latter can be used to tackle the
dynamic location problem. When using block norms as distance measure between facilities,
a Finite Dominating Set (FDS) is derived. For the special case with only two time-steps, the
resulting algorithm is analyzed with respect to its worst-case complexity. Due to the relation
between dynamic location problems for T time periods and T-facility problems, this algorithm
can also be applied to the static 2-facility location problem.
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.
Due to the increasing number of natural or man-made disasters, the application of operations research methods in evacuation planning has seen a rising interest in the research community. From the beginning, evacuation planning has been highly focused on car-based evacuation. Recently, also the evacuation of transit depended evacuees with the help of buses has been considered.
In this case study, we apply two such models and solution algorithms to evacuate a core part of the metropolitan capital city Kathmandu of Nepal as a hypothetical endangered region, where a large part of population is transit dependent. We discuss the computational results for evacuation time under a broad range of possible scenarios, and derive planning suggestions for practitioners.
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.