KLUEDO RSS FeedKLUEDO Dokumente/documents
https://kluedo.ub.uni-kl.de/index/index/
Wed, 02 Mar 2016 11:29:07 +0100Wed, 02 Mar 2016 11:29:07 +0100Zone-based, Robust Flood Evacuation Planning
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4297
We consider the problem to evacuate several regions due to river flooding, where sufficient time is given to plan ahead. To ensure a smooth evacuation procedure, our model includes the decision which regions to assign to which shelter, and when evacuation orders should be issued, such that roads do not become congested.
Due to uncertainty in weather forecast, several possible scenarios are simultaneously considered in a robust optimization framework. To solve the resulting integer program, we apply a Tabu search algorithm based on decomposing the problem into better tractable subproblems. Computational experiments on random instances and an instance based on Kulmbach, Germany, data show considerable improvement compared to an MIP solver provided with a strong starting solution.Sabine Büttner; Marc Goerigkpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4297Wed, 03 Feb 2016 11:29:07 +0100Ranking Robustness and its Application to Evacuation Planning
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4296
We present a new approach to handle uncertain combinatorial optimization problems that uses solution ranking procedures to determine the degree of robustness of a solution. Unlike classic concepts for robust optimization, our approach is not purely based on absolute quantitative performance, but also includes qualitative aspects that are of major importance for the decision maker.
We discuss the two variants, solution ranking and objective ranking robustness, in more detail, presenting problem complexities and solution approaches. Using an uncertain shortest path problem as a computational example, the potential of our approach is demonstrated in the context of evacuation planning due to river flooding.Marc Goerigk; Horst Hamacher; Anika Kinscherffpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4296Wed, 03 Feb 2016 11:26:20 +0100Minimizing the Number of Apertures in Multileaf Collimator Sequencing with Field Splitting
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4206
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.Horst W. Hamacher; Ines M. Raschendorfer; Davaatseren Baatar; Matthias Ehrgottpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4206Wed, 28 Oct 2015 14:33:01 +0100Robust storage loading problems with stacking and payload constraints
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4158
We consider storage loading problems where items with uncertain weights have
to be loaded into a storage area, taking into account stacking and
payload constraints. Following the robust optimization paradigm, we propose
strict and adjustable optimization models for finite and interval-based
uncertainties. To solve these problems, exact decomposition and heuristic
solution algorithms are developed.
For strict robustness, we also present a compact formulation based
on a characterization of worst-case scenarios.
Computational results show that computation times and algorithm
gaps are reasonable for practical applications.
Furthermore, we find that the robustness concepts show different
potential depending on the type of data being used.
Marc Goerigk; Sigrid Knust; Xuan Thanh Lepreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4158Tue, 18 Aug 2015 08:23:49 +0200Discrete Parallel Machine Makespan ScheLoc Problem
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4129
Scheduling-Location (ScheLoc) Problems integrate the separate fields of
scheduling and location problems. In ScheLoc Problems the objective is to
find locations for the machines and a schedule for each machine subject to
some production and location constraints such that some scheduling object-
ive is minimized. In this paper we consider the Discrete Parallel Machine
Makespan (DPMM) ScheLoc Problem where the set of possible machine loc-
ations is discrete and a set of n jobs has to be taken to the machines and
processed such that the makespan is minimized. Since the separate location
and scheduling problem are both NP-hard, so is the corresponding ScheLoc
Problem. Therefore, we propose an integer programming formulation and
different versions of clustering heuristics, where jobs are split into clusters
and each cluster is assigned to one of the possible machine locations. Since
the IP formulation can only be solved for small scale instances we propose
several lower bounds to measure the quality of the clustering heuristics. Ex-
tensive computational tests show the efficiency of the heuristics.Corinna Heßler; Kaouthar Deghdakpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4129Tue, 28 Jul 2015 09:40:15 +0200A new solution approach for solving the 2-facility location problem in the plane with block norms
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4128
Motivated by the time-dependent location problem over T time-periods introduced in
Maier and Hamacher (2015) we consider the special case of two time-steps, which was shown
to be equivalent to the static 2-facility location problem in the plane. Geometric optimality
conditions are stated for the median objective. When using block norms, these conditions
are used to derive a polygon grid inducing a subdivision of the plane based on normal cones,
yielding a new approach to solve the 2-facility location problem in polynomial time. Combinatorial algorithms for the 2-facility location problem based on geometric properties are
deduced and their complexities are analyzed. These methods differ from others as they are
completely working on geometric objects to derive the optimal solution set.Andrea Maierpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4128Fri, 24 Jul 2015 11:31:09 +0200A Finite Dominating Set Algorithm for a Dynamic Location Problem in the Plane
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4017
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.Andrea Maier; Horst W. Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4017Thu, 05 Mar 2015 14:56:26 +0100Bicriteria approach to the optimal location of surveillance cameras
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3997
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.Horst W. Hamacher; Gross Aleksandrapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3997Fri, 20 Feb 2015 13:54:12 +0100A coverage-based Box-Algorithm to compute a representation for optimization problems with three objective functions
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3911
A new algorithm for optimization problems with three objective functions is presented which computes a representation for the set of nondominated points. This representation is guaranteed to have a desired coverage error and a bound on the number of iterations needed by the algorithm to meet this coverage error is derived. Since the representation does not necessarily contain nondominated points only, ideas to calculate bounds for the representation error are given. Moreover, the incorporation of domination during the algorithm and other quality measures are discussed.Tobias Kuhn; Stefan Ruzikapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3911Fri, 07 Nov 2014 10:55:37 +0100Optimization Models to Enhance Resilience in Evacuation Planning
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3897
We argue that the concepts of resilience in engineering science and robustness in mathematical optimization are strongly related. Using evacuation planning as an example application, we demonstrate optimization techniques to improve solution resilience. These include a direct modelling of the uncertainty for stochastic or robust optimization, as well as taking multiple objective functions into account.Marc Goerigk; Horst Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3897Thu, 16 Oct 2014 10:22:16 +0200Hierarchical Edge Colorings and Rehabilitation Therapy Planning in Germany
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3832
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. Ines M. Raschendorfer; Horst W. Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3832Tue, 22 Jul 2014 11:16:14 +0200Edgeworth expansions for lattice triangular arrays
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3765
Edgeworth expansions have been introduced as a generalization of the central limit theorem and allow to investigate the convergence properties of sums of i.i.d. random variables. We consider triangular arrays of lattice random vectors and obtain a valid Edgeworth expansion for this case. The presented results can be used, for example, to study the convergence behavior of lattice models.Alona Bockpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3765Wed, 26 Mar 2014 12:14:40 +0100Monitoring time series based on estimating functions
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3693
A large class of estimators including maximum likelihood, least squares and M-estimators are based on estimating functions. In sequential change point detection related monitoring functions can be used to monitor new incoming observations based on an initial estimator, which is computationally efficient because possible numeric optimization is restricted to the initial estimation. In this work, we give general regularity conditions under which we derive the asymptotic null behavior of the corresponding tests in addition to their behavior under alternatives, where conditions become particularly simple for sufficiently smooth estimating and monitoring functions. These regularity conditions unify and even extend a large amount of existing procedures in the literature, while they also allow us to derive monitoring schemes in time series that have not yet been considered in the literature including non-linear autoregressive time series and certain count time series such as binary or Poisson autoregressive models. We do not assume that the estimating and monitoring function are equal or even of the same dimension, allowing for example to combine a non-robust but more precise initial estimator with a robust monitoring scheme. Some simulations and data examples illustrate the usefulness of the described procedures.Claudia Kirch; Joseph Tadjuidje Kamgaingpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3693Wed, 29 Jan 2014 10:20:27 +0100On the Generality of the Greedy Algorithm for Solving Matroid Base Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3535
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. Lara Turner; Matthias Ehrgott; Horst W. Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3535Wed, 19 Jun 2013 08:27:31 +0200Maximum Likelihood Estimators for Multivariate Hidden Markov Mixture Models
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3480
In this paper we consider a multivariate switching model, with constant states means
and covariances. In this model, the switching mechanism between the basic states of
the observed time series is controlled by a hidden Markov chain. As illustration, under
Gaussian assumption on the innovations and some rather simple conditions, we prove
the consistency and asymptotic normality of the maximum likelihood estimates of the model parameters.Joseph Tadjuidje Kamgaingpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3480Mon, 15 Apr 2013 17:29:52 +0200A limitation of the estimation of intrinsic volumes via pixel configuration counts
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3273
It is often helpful to compute the intrinsic volumes of a set of which only a pixel image is observed. A computational efficient approach, which is suggested by several authors and used in practice, is to approximate the intrinsic volumes by a linear functional of the pixel configuration histogram. Here we want to examine, whether there is an optimal way of choosing this linear functional, where we will use a quite natural optimality criterion that has already been applied successfully for the estimation of the surface area. We will see that for intrinsic volumes other than volume or surface area this optimality criterion cannot be used, since estimators which ignore the data and return constant values are optimal w.r.t. this criterion. This shows that one has to be very careful, when intrinsic volumes are approximated by a linear functional of the pixel configuration histogram.Jürgen Kampfpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3273Mon, 01 Oct 2012 15:52:05 +0200Asymptotic Order of the Parallel Volume Difference
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2912
In this paper we investigate the asymptotic behaviour of the parallel volume
of fixed non-convex bodies in Minkowski spaces as the distance \(r\) tends to infinity.
We will show that the difference of the parallel volume of the convex hull of a
body and the parallel volume of the body itself can at most have order \(r^{d-2}\) in a \(d\)-dimensional space. Then we will show that in Euclidean spaces this difference can at most have order \(r^{d-3}\). These results have several applications, e.g. we will use
them to compute the derivative of \(f_\mu(rK)\) in \(r = 0\), where \(f_\mu\) is the Wills functional
or a similar functional, \(K\) is a body and \(rK\) is the Minkowski-product of \(r\) and \(K\). Finally we present applications concerning Brownian paths and Boolean models and derive new proofs for formulae for intrinsic volumes.Jürgen Kampfpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2912Mon, 27 Feb 2012 10:09:25 +0100Changepoint tests for INARCH time series
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2725
In this paper, we discuss the problem of testing for a changepoint in the structure
of an integer-valued time series. In particular, we consider a test statistic
of cumulative sum (CUSUM) type for general Poisson autoregressions of order
1. We investigate the asymptotic behaviour of conditional least-squares estimates
of the parameters in the presence of a changepoint. Then, we derive the
asymptotic distribution of the test statistic under the hypothesis of no change,
allowing for the calculation of critical values. We prove consistency of the test,
i.e. asymptotic power 1, and consistency of the corresponding changepoint estimate.
As an application, we have a look at changepoint detection in daily
epileptic seizure counts from a clinical study.Jürgen Franke; Claudia Kirch; Joseph Tadjuidje Kamgaingpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2725Mon, 12 Sep 2011 09:49:44 +0200Variants of the Shortest Path Problem
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2713
The shortest path problem in which the \((s,t)\)-paths \(P\) of a given digraph \(G =(V,E)\) are compared with respect to the sum of their edge costs is one of the best known problems in combinatorial optimization. The paper is concerned with a number of variations of this problem having different objective functions like bottleneck, balanced, minimum deviation, algebraic sum, \(k\)-sum and \(k\)-max objectives, \((k_1, k_2)-max, (k_1, k_2)\)-balanced and several types of trimmed-mean objectives. We give a survey on existing algorithms and propose a general model for those problems not yet treated in literature. The latter is based on the solution of resource constrained shortest path problems with equality constraints which can be solved in pseudo-polynomial time if the given graph is acyclic and the number of resources is fixed. In our setting, however, these problems can be solved in strongly polynomial time. Combining this with known results on \(k\)-sum and \(k\)-max optimization for general combinatorial problems, we obtain strongly polynomial algorithms for a variety of path problems on acyclic and general digraphs. Lara Turnerpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2713Thu, 25 Aug 2011 09:14:11 +0200Asymptotic order of the parallel volume difference
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2327
In this paper we continue the investigation of the asymptotic behavior of the parallel volume in Minkowski spaces as the distance tends to infinity that was started in [13]. We will show that the difference of the parallel volume of the convex hull of a body and the parallel volume of the body itself can at most have order \(r^{d-2}\) in dimension \(d\). Then we will show that in the Euclidean case this difference can at most have order \(r^{d-3}\). We will also examine the asymptotic behavior of the derivative of this difference as the distance tends to infinity. After this we will compute the derivative of \(f_\mu (rK)\) in \(r\), where \(f_\mu\) is the Wills functional or a similar functional, \(K\) is a fixed body and \(rK\) is the Minkowski-product of \(r\) and \(K\). Finally we will use these results to examine Brownian paths and Boolean models and derive new proofs for formulae for intrinsic volumes.Jürgen Kampfpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2327Thu, 26 May 2011 11:11:40 +0200A uniform central limit theorem for neural network based autoregressive processes with applications to change-point analysis
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2302
We consider an autoregressive process with a nonlinear regression function that is modeled by a feedforward neural network. We derive a uniform central limit theorem which is useful in the context of change-point analysis. We propose a test for a change in the autoregression function which - by the uniform central limit theorem - has asymptotic power one for a large class of alternatives including local alternatives.Claudia Kirch; Joseph Tadjuidje Kamgaingpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2302Fri, 25 Mar 2011 14:44:40 +0100Testing for parameter stability in nonlinear autoregressive models
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2301
In this paper we develop testing procedures for the detection of structural changes in nonlinear autoregressive processes. For the detection procedure we model the regression function by a single layer feedforward neural network. We show that CUSUM-type tests based on cumulative sums of estimated residuals, that have been intensively studied for linear regression, can be extended to this case. The limit distribution under the null hypothesis is obtained, which is needed to construct asymptotic tests. For a large class of alternatives it is shown that the tests have asymptotic power one. In this case, we obtain a consistent change-point estimator which is related to the test statistics. Power and size are further investigated in a small simulation study with a particular emphasis on situations where the model is misspecified, i.e. the data is not generated by a neural network but some other regression function. As illustration, an application on the Nile data set as well as S&P log-returns is given.Claudia Kirch; Joseph Tadjuidje Kamgaingpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2301Fri, 25 Mar 2011 14:44:06 +0100On a Cardinality Constrained Multicriteria Knapsack Problem
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2281
We consider a variant of a knapsack problem with a fixed cardinality constraint. There are three objective functions to be optimized: one real-valued and two integer-valued objectives. We show that this problem can be solved efficiently by a local search. The algorithm utilizes connectedness of a subset of feasible solutions and has optimal run-time.Florian Seipp; Stefan Ruzika; Luis Paquetepreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2281Tue, 08 Feb 2011 12:18:44 +0100Generalized Multiple Objective Bottleneck Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2252
We consider multiple objective combinatiorial optimization problems in which the first objective is of arbitrary type and the remaining objectives are either bottleneck or k-max objective functions. While the objective value of a bottleneck objective is determined by the largest cost value of any element in a feasible solution, the kth-largest element defines the objective value of the k-max objective. An efficient solution approach for the generation of the complete nondominated set is developed which is independent of the specific combinatiorial problem at hand. This implies a polynomial time algorithm for several important problem classes like shortest paths, spanning tree, and assignment problems with bottleneck objectives which are known to be NP-hard in the general multiple objective case.Jochen Gorski; Kathrin Klamroth; Stefan Ruzikapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2252Thu, 09 Dec 2010 10:21:17 +0100Universal Shortest Paths
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2230
We introduce the universal shortest path problem (Univ-SPP) which generalizes both - classical and new - shortest path problems. Starting with the definition of the even more general universal combinatorial optimization problem (Univ-COP), we show that a variety of objective functions for general combinatorial problems can be modeled if all feasible solutions have the same cardinality. Since this assumption is, in general, not satisfied when considering shortest paths, we give two alternative definitions for Univ-SPP, one based on a sequence of cardinality contrained subproblems, the other using an auxiliary construction to establish uniform length for all paths between source and sink. Both alternatives are shown to be (strongly) NP-hard and they can be formulated as quadratic integer or mixed integer linear programs. On graphs with specific assumptions on edge costs and path lengths, the second version of Univ-SPP can be solved as classical sum shortest path problem.Lara Turner; Horst W. Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2230Mon, 16 Aug 2010 11:00:30 +0200