Refine
Language
- English (21)
Has Fulltext
- yes (21)
Is part of the Bibliography
- no (21)
Keywords
- Location Theory (6)
- Algebraic Optimization (2)
- Approximation (2)
- Geometrical Algorithms (2)
- Multicriteria Optimization (2)
- Algebraic optimization (1)
- Analysis (1)
- Applications (1)
- Bisector (1)
- Continuous Location (1)
Faculty / Organisational entity
- Fachbereich Mathematik (20)
- Fraunhofer (ITWM) (1)
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.
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
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
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.
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.
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.
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.
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.
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.
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.
