KLUEDO RSS FeedKLUEDO Dokumente/documents
https://kluedo.ub.uni-kl.de/index/index/
Mon, 06 Nov 2017 11:45:28 +0100Mon, 06 Nov 2017 11:45:28 +0100A Note on Approximation Algorithms for the Multicriteria \(\Delta\)-TSP
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5031
The Tree and Christofides heuristic are weil known 1- and \(\frac{1} {2}\)- approximate algorithms for the \(\Delta\)-TSP. In this note their performance for the multicriteria case is described, depending on the norm in \(\mathbb{R}^Q\) in case of \(Q\) criteria.Matthias Ehrgott; Alexander Feldmannreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5031Mon, 06 Nov 2017 11:45:28 +0100On Matroids with Multiple Objectives
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4850
In this paper we investigate two optimization problems for matroids with multiple objective functions, namely finding the pareto set and the max-ordering problem which conists in finding a basis such that the largest objective value is minimal. We prove that the decision versions of both problems are NP-complete. A solution procedure for the max-ordering problem is presented and a result on the relation of the solution sets of the two problems is given. The main results are a characterization of pareto bases by a basis exchange property and finally a connectivity result for proper pareto solutions.Matthias Ehrgottreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4850Mon, 16 Oct 2017 09:14:56 +0200Lexicographic Max-Ordering - A Solution Concept for Multicriteria Combinatorial Optimization
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4849
In this paper we will introduce the concept of lexicographic max-ordering solutions for multicriteria combinatorial optimization problems. Section 1 provides the basic notions of
multicriteria combinatorial optimization and the definition of lexicographic max-ordering solutions. In Section 2 we will show that lexicographic max-ordering solutions are pareto optimal as well as max-ordering optimal solutions. Furthermore lexicographic max-ordering solutions can be used to characterize the set of pareto solutions. Further properties of lexicographic max-ordering solutions are given. Section 3 will be devoted to algorithms. We give a polynomial time algorithm for the two criteria case where one criterion is a sum and one is a bottleneck objective function, provided that the one criterion sum problem is solvable in polynomial time. For bottleneck functions an algorithm for the general case of Q criteria is presented.Matthias Ehrgottreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4849Mon, 16 Oct 2017 08:57:51 +0200Connectedness of Efficient Solutions in Multiple Criteria Combinatorial Optimization
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4844
In multiple criteria optimization an important research topic is the topological structure of the set \( X_e \) of efficient solutions. Of major interest is the connectedness of \( X_e \), since it would allow the determination of \( X_e \) without considering non-efficient solutions in the
process. We review general results on the subject,including the connectedness result for efficient solutions in multiple criteria linear programming. This result can be used to derive a definition of connectedness for discrete optimization problems. We present a counterexample to a previously stated result in this area, namely that the set of efficient solutions of the shortest path problem is connected. We will also show that connectedness does not hold for another important problem in discrete multiple criteria optimization: the spanning tree problem.Matthias Ehrgott; Kathrin Klamrothreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4844Mon, 16 Oct 2017 08:41:05 +0200Minimizing 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 +0100Minimizing the Number of Apertures in Multileaf Collimator Sequencing with Field Splitting
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4197
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.Davaatseren Baatar; Matthias Ehrgott; Horst W. Hamacher; Ines M. Raschendorferarticlehttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4197Fri, 16 Oct 2015 11:00:21 +0200On 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 +0200Decomposition of Matrices and Static Multileaf Collimators: A Survey
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1810
Multileaf Collimators (MLC) consist of (currently 20-100) pairs of movable metal leaves which are used to block radiation in Intensity Modulated Radiation Therapy (IMRT). The leaves modulate a uniform source of radiation to achieve given intensity profiles. The modulation process is modeled by the decomposition of a given non-negative integer matrix into a non-negative linear combination of matrices with the (strict) consecutive ones property.Matthias Ehrgott; Horst W. Hamacher; Marc Nußbaumpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1810Tue, 21 Nov 2006 13:41:32 +0100An Improved Epsilon-Constraint Method for Multiobjective Programming
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1679
In this paper we revisit one of the most important scalarization techniques used in multiobjective programming, the \(\varepsilon\)-constraint method.Matthias Ehrgott; Stefan Ruzikapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1679Wed, 09 Nov 2005 18:04:47 +0100Decomposition of Integer Matrices and Multileaf Collimator Sequencing
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1582
In this paper we consider the problem of decomposing an integer matrix into a weighted sum of binary matrices that have to strict consecutive ones property.Davaatseren Baatar; Horst W. Hamacher; Matthias Ehrgott; Gerhard J. Woegingerpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1582Mon, 08 Nov 2004 11:12:15 +0100Teoría de localización en las clases de matemáticas
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1427
La Teoría de localización abarca las posibilidades, para que con la ayuda de modelos matemáticos se busquen localizaciones teniendo en cuenta que los intereses económicos y administrativos sean óptimos. Así por ejemplo se encuentra la mejor localización para el almacén central de una empresa, cuando la suma de los gastos de transporte y de almacenaje sean mínimos y cuando se utilice el almacén óptimo. Si por otro lado, la administración busca la localización de una nueva estación de bomberos o de un hospital, hay que tener en cuenta un importante criterio para la localización óptima y es que la distancia mayor no sobrepase un valor dado.Matthias Ehrgott; Angela Euteneuer; Horst W. Hamacherreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1427Sat, 13 Sep 2003 10:30:11 +0200Locational planning in the Mathematics Curriculum of High Schools
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1426
Dealing with problems from locational planning in schools can enrich the mathematical education. In this report we describe planar locational problems which can be used in mathematical lessons. The problems production of a semiconductor plate, design of a fire brigade building and the warehouse problem are from real-world. The problems are worked out detailed so that the usage for school lessons is possible.Matthias Ehrgott; Angela Euteneuer; Horst W. Hamacher; Klaus-Peter Nieschulzreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1426Sat, 13 Sep 2003 10:24:42 +0200A Level Set Method for Multiobjective Combinatorial Optimization: Application to the Quadratic Assignment Problem
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1352
Multiobjective combinatorial optimization problems have received increasing attention in recent years. Nevertheless, many algorithms are still restricted to the bicriteria case. In this paper we propose a new algorithm for computing all Pareto optimal solutions. Our algorithm is based on the notion of level sets and level curves and contains as a subproblem the determination of K best solutions for a single objective combinatorial optimization problem. We apply the method to the Multiobjective Quadratic Assignment Problem (MOQAP). We present two algorithms for ranking QAP solutions and nally give computational results comparing the methods.Matthias Ehrgott; Thomas Stephan; Dagmar Tenfelde-Podehlpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1352Tue, 15 Oct 2002 22:29:00 +0200Standortplanung im Mathematikunterricht
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1266
Fragestellungen der Standortplanung sollen den Mathematikunterricht der Schule bereichern, dort behandelt und gelöst werden. In dieser Arbeit werden planare Standortprobleme vorgestellt, die im Mathematikunterricht behandelt werden können. Die Probleme Produktion von Halbleiterplatinen, Planung eines Feuerwehrhauses und das Zentrallagerproblem, die ausnahmlos real und nicht konstruiert sind, werden ausführlich durchgearbeitet, so dass es schnell möglich ist, daraus Unterrichtseinheiten zu entwickeln.Matthias Ehrgott; Angela Euteneuer; Horst W. Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1266Fri, 30 Nov 2001 00:00:00 +0100Some Complexity Results for k-Cardinality Minimum Cut Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1140
Many polynomially solvable combinatorial optimization problems (COP) become NP when we require solutions to satisfy an additional cardinality constraint. This family of problems has been considered only recently. We study a newproblem of this family: the k-cardinality minimum cut problem. Given an undirected edge-weighted graph the k-cardinality minimum cut problem is to find a partition of the vertex set V in two sets V 1 , V 2 such that the number of the edges between V 1 and V 2 is exactly k and the sum of the weights of these edges is minimal. A variant of this problem is the k-cardinality minimum s-t cut problem where s and t are fixed vertices and we have the additional request that s belongs to V 1 and t belongs to V 2 . We also consider other variants where the number of edges of the cut is constrained to be either less or greater than k. For all these problems we show complexity results in the most significant graph classes.Maurizio Bruglieri; Matthias Ehrgott; Horst W. Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1140Thu, 07 Sep 2000 00:00:00 +0200A Fuzzy Programming Approach to Multicriteria Facility Location Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1124
Facility Location Problems are concerned with the optimal location of one or several new facilities, with respect to a set of existing ones. The objectives involve the distance between new and existing facilities, usually a weighted sum or weighted maximum. Since the various stakeholders (decision makers) will have different opinions of the importance of the existing facilities, a multicriteria problem with several sets of weights, and thus several objectives, arises. In our approach, we assume the decision makers to make only fuzzy comparisons of the different existing facilities. A geometric mean method is used to obtain the fuzzy weights for each facility and each decision maker. The resulting multicriteria facility location problem is solved using fuzzy techniques again. We prove that the final compromise solution is weakly Pareto optimal and Pareto optimal, if it is unique, or under certain assumptions on the estimates of the Nadir point. A numerical example is considered to illustrate the methodology.Matthias Ehrgott; Rakesh Vermapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1124Tue, 29 Aug 2000 00:00:00 +0200The Balance Space Approach to Multicriteria Decision Making - Involving the Decision Maker
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1127
The balance space approach (introduced by Galperin in 1990) provides a new view on multicriteria optimization. Looking at deviations from global optimality of the different objectives, balance points and balance numbers are defined when either different or equal deviations for each objective are allowed. Apportioned balance numbers allow the specification of proportions among the deviations. Through this concept the decision maker can be involved in the decision process. In this paper we prove that the apportioned balance number can be formulated by a min-max operator. Furthermore we prove some relations between apportioned balance numbers and the balance set, and see the representation of balance numbers in the balance set. The main results are necessary and sufficient conditions for the balance set to be exhaustive, which means that by multiplying a vector of weights (proportions of deviation) with its corresponding apportioned balance number a balance point is attained. The results are used to formulate an interactive procedure for multicriteria optimization. All results are illustrated by examples.Matthias Ehrgottpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1127Tue, 29 Aug 2000 00:00:00 +0200Nadir Values: Computation and Use in Compromise Programming
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1128
In this paper we investigate the problem offending the Nadir point for multicriteria optimization problems (MOP). The Nadir point is characterized by the component wise maximal values of efficient points for (MOP). It can be easily computed in the bicriteria case. However, in general this problem is very difficult. We review some existing methods and heuristics and propose some new ones. We propose a general method to compute Nadir values for the case of three objectives, based on theoretical results valid for any number of criteria. We also investigate the use of the Nadir point for compromise programming, when the goal is to be as far away as possible from the worst outcomes. We prove some results about (weak) Pareto optimality of the resulting solutions. The results are illustrated by examples.Matthias Ehrgott; Dagmar Tenfelde-Podehlpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1128Tue, 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 +0200An Annotated Bibliography of Multiobjective Combinatorial Optimization
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1130
This paper provides an annotated bibliography of multiple objective combinatorial optimization, MOCO. We present a general formulation of MOCO problems, describe the main characteristics of MOCO problems, and review the main properties and theoretical results for these problems. One section is devoted to a brief description of the available solution methodology, both exact and heuristic. The main part of the paper is devoted to an annotation of the existing literature in the field organized problem by problem. We conclude the paper by stating open questions and areas of future research. The list of references comprises more than 350 entries.Matthias Ehrgott; Xavier Gandibleuxpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1130Tue, 29 Aug 2000 00:00:00 +0200A Characterization of Lexicographic Max-Ordering Solutions
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/484
In this paper we give the definition of a solution concept in multicriteria combinatorial optimization. We show how Pareto, max-ordering and lexicographically optimal solutions can be incorporated in this framework. Furthermore we state some properties of lexicographic max-ordering solutions, which combine features of these three kinds of optimal solutions. Two of these properties, which are desirable from a decision maker" s point of view, are satisfied if and only of the solution concept is that of lexicographic max-ordering.Matthias Ehrgottpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/484Mon, 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 +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 +0200Saddle Points and Pareto Points in Multiple Objective Programming
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/504
In this paper relationships between Pareto points and saddle points in multiple objective programming are investigated. Convex and nonconvex problems are considered and the equivalence between Pareto points and saddle points is proved in both cases. The results are based on scalarizations of multiple objective programs and related linear and augmented Lagrangian functions. Partitions of the index sets of objectives and constranints are introduced to reduce the size of the problems. The relevance of the results in the context of decision making is also discussed.Matthias Ehrgott; Margaret M. Wiecekpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/504Mon, 03 Apr 2000 00:00:00 +0200Discrete Decision Problems, Multiple Criteria Optimization Classes and Lexicographic Max-Ordering
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/505
The topic of this paper are discrete decision problems with multiple criteria. We first define discrete multiple criteria decision problems and introduce a classification scheme for multiple criteria optimization problems. To do so we use multiople criteria optimization classes. The main result is a characterization of the class of lexicographic max-ordering problems by two very useful properties, reduction and regularity. Subsequently we discuss the assumptions under which the application of this specific MCO class is justified. Finally we provide (simple) solution methods to find optimal decisions in the case of discrete multiple criteria optimization problems.Matthias Ehrgottpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/505Mon, 03 Apr 2000 00:00:00 +0200