## Fachbereich Mathematik

### Filtern

#### Schlagworte

- Location Theory (6)
- Algebraic Optimization (2)
- Geometrical Algorithms (2)
- Multicriteria Optimization (2)
- Algebraic optimization (1)
- Analysis (1)
- Applications (1)
- Approximation (1)
- Bisector (1)
- Convex Analysis (1)

- Bicriterial and restricted planar 2-Median Problems (1993)
- Efficient algorithms and structural results are presented for median problems with 2 new facilities including the classical 2-Median problem, the 2-Median problem with forbidden regions and bicriterial 2-Median problems. This is the first paper dealing with multi-facility multiobjective location problems. The time complexity of all presented algorithms is O(MlogM), where M is the number of existing facilities.

- Robust facility location (1998)
- 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.

- Convex Analysis (1998)
- 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].^L

- A unified approach to network location problems (1999)
- 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.

- 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.

- Multiple objective programming with piecewise linear functions (1999)
- 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.

- Error bounds for the approximative solution of restricted planar location problems (1999)
- 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.

- 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.

- On the number of Criteria Needed to Decide Pareto Optimality (1999)
- 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 solutions

- An Interior Point Method for Multifacility Location Problems with Forbidden Regions (1999)
- 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 presented