KLUEDO RSS FeedNeueste Dokumente / Latest documents
https://kluedo.ub.uni-kl.de/index/index/
Tue, 29 Aug 2000 00:00:00 +0200Tue, 29 Aug 2000 00:00:00 +0200Geometrical properties of generalized single facility location problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1125
In this paper we deal with single facility location problems in a general normed space where the existing facilities are represented by sets. The criterion to be satis ed by the service facility is the minimization of an increasing function of the distances from the service to the closest point ofeach demand set. We obtain a geometrical characterization of the set of optimal solutions for this problem. Two remarkable cases - the classical Weber problem and the minmax problem with demand sets - are studied as particular instances of our problem. Finally, for the planar polyhedral case we give an algorithmic description of the solution set of the considered problems.Stefan Nickel; Justo Puerto; Antonio M. Rodriguez-Chiapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1125Tue, 29 Aug 2000 00:00:00 +0200Multicriteria Ordered Weber Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1126
In this paper we deal with the determination of the whole set of Pareto-solutions of location problems with respect to Q general criteria.These criteria include median, center or cent-dian objective functions as particular instances.The paper characterizes the set of Pareto-solutions of a these multicriteria problems. An efficient algorithm for the planar case is developed and its complexity is established. Extensions to higher dimensions as well as to the non-convexcase are also considered.The proposed approach is more general than the previously published approaches to multi-criteria location problems and includes almost all of them as particular instances.Stefan Nickel; Justo Puerto; Antonio M. Rodriguez-Chiapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1126Tue, 29 Aug 2000 00:00:00 +0200On the Number of Criteria Needed to Decide Pareto Optimality
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1129
In this paper we address the question of how many objective functions are needed to decide whether a given point is a Pareto optimal solution for a multicriteria optimization problem. We extend earlier results showing that the set of weakly Pareto optimal points is the union of Pareto optimal sets of subproblems and show their limitations. We prove that for strictly quasi-convex problems in two variables Pareto optimality can be decided by consideration of at most three objectives at a time. Our results are based on a geometric characterization of Pareto, strict Pareto and weak Pareto solutions and Helly's Theorem. We also show that a generalization to quasi-convex objectives is not possible, and state a weaker result for this case. Furthermore, we show that a generalization to strictly Pareto optimal solutions is impossible, even in the convex case.Matthias Ehrgott; Stefan Nickelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1129Tue, 29 Aug 2000 00:00:00 +0200Polyhedral Properties of the Uncapacitated Multiple Allocation Hub Location Problem
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1132
We examine the feasibility polyhedron of the uncapacitated hub location problem (UHL) with multiple allocation, which has applications in the fields of air passenger and cargo transportation, telecommunication and postal delivery services. In particular we determine the dimension and derive some classes of facets of this polyhedron. We develop some general rules about lifting facets from the uncapacitated facility location (UFL) for UHL and projecting facets from UHL to UFL. By applying these rules we get a new class of facets for UHL which dominates the inequalities in the original formulation. Thus we get a new formulation of UHL whose constraints are all facet defining. We show its superior computational performance by benchmarking it on a well known data set.Horst W. Hamacher; Martine Labbé; Stefan Nickel; Tim Sonnebornpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1132Tue, 29 Aug 2000 00:00:00 +0200A unified approach to network location problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/486
In this paper we introduce a new type of single facility location problems on networks which includes as special cases most of the classical criteria in the literature. Structural results as well as a finite dominationg set for the optimal locations are developed. Also the extension to the multi-facility case is discussed.Stefan Nickel; Justo Puertopreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/486Mon, 03 Apr 2000 00:00:00 +0200Multicriteria network location problems with sumb objectives
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/487
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.Horst W. Hamacher; Stefan Nickel; Martine Labbepreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/487Mon, 03 Apr 2000 00:00:00 +0200Multiple objective programming with piecewise linear functions
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/488
An approach to generating all efficient solutions of multiple objective programs with piecewise linear objective functions and linear constraints is presented. The approach is based on the decomposition of the feasible set into subsets, referred to as cells, so that the original problem reduces to a series of lenear multiple objective programs over the cells. The concepts of cell-efficiency and complex-efficiency are introduced and their relationship with efficiency is examined. A generic algorithm for finding efficent solutions is proposed. Applications in location theory as well as in worst case analysis are highlighted.Stefan Nickel; M. Wiecekpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/488Mon, 03 Apr 2000 00:00:00 +0200Error bounds for the approximative solution of restricted planar location problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/489
Facility location problems in the plane play an important role in mathematical programming. When looking for new locations in modeling real-word problems, we are often confronted with forbidden regions, that are not feasible for the placement of new locations. Furthermore these forbidden regions may habe complicated shapes. It may be more useful or even necessary to use approcimations of such forbidden regions when trying to solve location problems. In this paper we develop error bounds for the approximative solution of restricted planar location problems using the so called sandwich algorithm. The number of approximation steps required to achieve a specified error bound is analyzed. As examples of these approximation schemes, we discuss round norms and polyhedral norms. Also computational tests are included.Stefan Nickel; Barbara Käferpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/489Mon, 03 Apr 2000 00:00:00 +0200Classification of Location Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/491
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.Horst W. Hamacher; Stefan Nickel; Anja Schneiderpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/491Mon, 03 Apr 2000 00:00:00 +0200On the number of Criteria Needed to Decide Pareto Optimality
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/492
In this paper we prove a reduction result for the number of criteria in convex multiobjective optimization. This result states that to decide wheter a point x in the decision space is pareto optimal it suffices to consider at most n? criteria at a time, where n is the dimension of the decision space. The main theorem is based on a geometric characterization of pareto, strict pareto and weak pareto solutionsMatthias Ehrgott; Stefan Nickelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/492Mon, 03 Apr 2000 00:00:00 +0200An Interior Point Method for Multifacility Location Problems with Forbidden Regions
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/496
In this paper we consider generalizations of multifacility location problems in which as an additional constraint the new facilities are not allowed to be located in a presprcified region. We propose several different solution schemes for this non-convex optimization problem. These include a linear programming type approach, penalty approaches and barrier approaches. Moreover, structural results as well as illustratrive examples showing the difficulties of this problem are presentedStefan Nickel; Jörg Fliegepreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/496Mon, 03 Apr 2000 00:00:00 +0200A flexible approach to location problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/499
In continous location problems we are given a set of existing facilities and we are looking for the location of one or several new facilities. In the classical approaches weights are assigned to existing facilities expressing the importance of the new facilities for the existing ones. In this paper, we consider a pointwise defined objective function where the weights are assigned to the existing facilities depending on the location of the new facility. This approach is shown to be a generalization of the median, center and centdian objective functions. In addition, this approach allows to formulate completely new location models. Efficient algorithms as well as structure results for this algebraic approach for location problems are presented. Extensions to the multifacility and restricted case are also considered.Stefan Nickel; Justo Puertoi; Antonio M. Rodriguez-Chiapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/499Mon, 03 Apr 2000 00:00:00 +0200A geometric approach to global optimization
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/500
In this paper we consider the problem of optimizing a piecewise-linear objective function over a non-convex domain. In particular we do not allow the solution to lie in the interior of a prespecified region R. We discuss the geometrical properties of this problems and present algorithms based on combinatorial arguments. In addition we show how we can construct quite complicated shaped sets R while maintaining the combinatorial properties.Stefan Nickel; Anita Schöbelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/500Mon, 03 Apr 2000 00:00:00 +0200General Continuous Multicriteria Location Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/501
In this paper we deal with the determination of the whole set of Pareto-solutions of location problems with respect to Q general criteria. These criteria include as particular instances median, center or cent-dian objective functions. The paper characterizes the set of Pareto-solutions of all these multicriteria problems. An efficient algorithm for the planar case is developed and its complexity is established. the proposed approach is more general than the previously published approaches to multicriteria location problems and includes almost all of them as particular instances.Stefan Nickel; Justo Puerto; Antonio M. Rodriguez-Chia; Ansgar Weißlerpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/501Mon, 03 Apr 2000 00:00:00 +0200Geometric Methods to Solve Max-Ordering Location Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/502
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.Matthias Ehrgott; Horst W. Hamacher; Stefan Nickelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/502Mon, 03 Apr 2000 00:00:00 +0200Robust facility location
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/509
Let A be a nonempty finite subset of R^2 representing the geographical coordinates of a set of demand points (towns, ...), to be served by a facility, whose location within a given region S is sought. Assuming that the unit cost for a in A if the facility is located at x in S is proportional to dist(x,a) - the distance from x to a - and that demand of point a is given by w_a, minimizing the total trnsportation cost TC(w,x) amounts to solving the Weber problem. In practice, it may be the case, however, that the demand vector w is not known, and only an estimator {hat w} can be provided. Moreover the errors in sich estimation process may be non-negligible. We propose a new model for this situation: select a threshold valus B 0 representing the highest admissible transportation cost. Define the robustness p of a location x as the minimum increase in demand needed to become inadmissible, i.e. p(x) = min{||w^*-{hat w}|| : TC(w^*,x) B, w^* = 0} and solve then the optimization problem max_{x in S} p(x) to get the most robust location.Stefan Nickel; Emilio Carrizosapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/509Mon, 03 Apr 2000 00:00:00 +0200On Bisectors for Different Distance Functions
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/517
Let rC and rD be two convexdistance funtions in the plane with convex unit balls C and D. Given two points, p and q, we investigate the bisector, B(p,q), of p and q, where distance from p is measured by rC and distance from q by rD. We provide the following results. B(p,q) may consist of many connected components whose precise number can be derived from the intersection of the unit balls, C nd D. The bisector can contain bounded or unbounded 2-dimensional areas. Even more surprising, pieces of the bisector may appear inside the region of all points closer to p than to q. If C and D are convex polygons over m and m vertices, respectively, the bisector B(p,q) can consist of at most min(m,n) connected components which contain at most 2(m+n) vertices altogether. The former bound is tight, the latter is tight up to an additive constant. We also present an optimal O(m+n) time algorithm for computing the bisector.Christian Icking; Rolf Klein; Lihong Ma; Stefan Nickel; Ansgar Weisslerpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/517Mon, 03 Apr 2000 00:00:00 +0200Weber s Problem with attraction and repulsion under Polyhedral Gauges
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/520
Given a finite set of points in the plane and a forbidden region R, we want to find a point X not an element of int(R), such that the weighted sum to all given points is minimized. This location problem is a variant of the well-known Weber Problem, where we measure the distance by polyhedral gauges and allow each of the weights to be positive or negative. The unit ball of a polyhedral gauge may be any convex polyhedron containing the origin. This large class of distance functions allows very general (practical) settings - such as asymmetry - to be modeled. Each given point is allowed to have its own gauge and the forbidden region R enables us to include negative information in the model. Additionally the use of negative and positive weights allows to include the level of attraction or dislikeness of a new facility. Polynomial algorithms and structural properties for this global optimization problem (d.c. objective function and a non-convex feasible set) based on combinatorial and geometrical methods are presented.Stefan Nickel; Eva Maria Dudenhöfferpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/520Mon, 03 Apr 2000 00:00:00 +0200Solving nonconvex planar location problems by finite dominating sets
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/973
It is well-known that some of the classical location problems with polyhedral gauges can be solved in polynomial time by finding a finite dominating set, i.e. a finite set of candidates guaranteed to contain at least one optimal location. In this paper it is first established that this result holds for a much larger class of problems than currently considered in the literature. The model for which this result can be proven includes, for instance, location problems with attraction and repulsion, and location-allocation problems. Next, it is shown that the approximation of general gauges by polyhedral ones in the objective function of our general model can be analyzed with regard to the subsequent error in the optimal objective value. For the approximation problem two different approaches are described, the sandwich procedure and the greedy algorithm. Both of these approaches lead - for fixed epsilon - to polynomial approximation algorithms with accuracy epsilon for solving the general model considered in this paper.Emilio Carrizosa; Horst W. Hamacher; Rolf Klein; Stefan Nickelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/973Fri, 18 Feb 2000 00:00:00 +0100Convex Analysis
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/837
Preface Convex analysis is one of the mathematical tools which is used both explicitly and indirectly in many mathematical disciplines. However, there are not so many courses which have convex analysis as the main topic. More often, parts of convex analysis are taught in courses like linear or nonlinear optimization, probability theory, geometry, location theory, etc.. This manuscript gives a systematic introduction to the concepts of convex analysis. A focus is set to the geometrical interpretation of convex analysis. This focus was one of the reasons why I have decided to restrict myself to the finite dimensional case. Another reason for this restriction is that in the infinite dimensional case many proofs become more difficult and more technical. Therefore, it would not have been possible (for me) to cover all the topics I wanted to discuss in this introductory text in the infinite dimensional case, too. Anyway, I am convinced that even for someone who is interested in the infinite dimensional case this manuscript will be a good starting point. When I offered a course in convex analysis in the Wintersemester 1997/1998 (upon which this manuscript is based) a lot of students asked me how this course fits in their own studies. Because this manuscript will (hopefully) be used by some students in the future, I will give here some of the possible statements to answer this very question. - Convex analysis can be seen as an extension of classical analysis, in which still we get many of the results, like a mean-value theorem, with less assumptions on the smoothness of the function. - Convex analysis can be seen as a foundation of linear and nonlinear optimization which provides many tools to handle concepts in optimization much easier (for example the Lemma of Farkas). - Finally, convex analysis can be seen as a link between abstract geometry and very algorithmic oriented computational geometry. As already explained before, this manuscript is based on a one semester course and therefore cannot cover all topics and discuss all aspects of convex analysis in detail. To guide the interested reader I have included a list of nice books about this subject at the end of the manuscript. It should be noted that the philosophy of this course follows [3], [4] and THE BOOK of modern convex analysis [6]. The geometrical emphasis however, is also related to intentions of [1].^LStefan Nickellecturehttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/837Wed, 25 Aug 1999 00:00:00 +0200