KLUEDO RSS FeedKLUEDO Dokumente/documents
https://kluedo.ub.uni-kl.de/index/index/
Wed, 19 Jun 2013 08:27:31 +0200Wed, 19 Jun 2013 08:27:31 +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 +0200Min-Max Formulation of the Balance Number in Multiobjetive Global Optimization
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/515
The notion of the balance number introduced in [3,page 139] through a certain set contraction procedure for nonscalarized multiobjective global optimization is represented via a min-max operation on the data of the problem. This representation yields a different computational procedure for the calculation of the balance number and allows us to generalize the approach for problems with countably many performance criteria.Matthias Ehrgott; Efim A. Galperinpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/515Mon, 03 Apr 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 +0200Bicriteria cost versus service analysis of the distribution network of a chemical company
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/508
In order to improve the distribution system for the Nordic countries the BASF AG considered 13 alternative scenarios to the existing system. These involved the construction of warehouses at various locations. For every scenario the transportation, storage, and handling cost incurred was to be as low as possible, where restrictions on the delivery time were given. The scenarios were evaluated according to (minimal) total cost and weighted average delivery time. The results led to a restriction to only three cases, involving only one new warehouse each. For these a more accurate model for the cost was developped and evaluated, yielding results similar to a simple linear model. Since there were no clear preferences between cost and delivery time, the final decision was chosen to represent a compromise between the two criteria.Matthias Ehrgott; Andrea Raupreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/508Mon, 03 Apr 2000 00:00:00 +0200Approximation Algorithms for Combinatorial Multicriteria Optimization Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/512
The computational complexity of combinatorial multiple objective programming problems is investigated. NP-completeness and #P-completeness results are presented. Using two definitions of approximability, general results are presented, which outline limits for approximation algorithms. The performance of the well known tree and Christofides' heuristics for the TSP is investigated in the multicriteria case with respect to the two definitions of approximability.Matthias Ehrgottpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/512Mon, 03 Apr 2000 00:00:00 +0200Convex Operators in Vector Optimization: Directional Derivatives and the Cone of Decrease Directions
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/514
The paper is devoted to the investigation of directional derivatives and the cone of decrease directions for convex operators on Banach spaces. We prove a condition for the existence of directional derivatives which does not assume regularity of the ordering cone K. This result is then used to prove that for continuous convex operators the cone of decrease directions can be represented in terms of the directional derivatices . Decrease directions are those for which the directional derivative lies in the negative interior of the ordering cone K. Finally, we show that the continuity of the convex operator can be replaced by its K-boundedness.Alexander L. Topchishvili; Vilhelm G. Maisuradze; Matthias Ehrgottpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/514Mon, 03 Apr 2000 00:00:00 +0200Local Search Algorithms for the k-Cardinality Tree Problem
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/519
In this paper we deal with an NP-hard combinatorial optimization problem, the k-cardinality tree problem in node weighted graphs. This problem has several applications , which justify the need for efficient methods to obtain good solutions. We review existing literature on the problem. Then we prove that under the condition that the graph contains exactly one trough, the problem can be solved in ploynomial time. For the general NP-hard problem we implemented several local search methods to obtain heuristics solutions, which are qualitatively better than solutions found by constructive heuristics and which require significantly less time than needed to obtain optimal solutions. We used the well known concepts of genetic algorithms and tabu search with useful extensions. We show that all the methods find optimal solutions for the class of graphs containing exactly one trough. The general performance of our methods as compared to other heuristics is illustrated by numerical results.Christian Blum; Ehrgott Matthiaspreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/519Mon, 03 Apr 2000 00:00:00 +0200Heuristics for the K-Cardinality Tree and Subgraph Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/524
In this paper we consider the problem of finding in a given graph a minimal weight subtree of connected subgraph, which has a given number of edges. These NP-hard combinatorial optimization problems have various applications in the oil industry, in facility layout and graph partitioning. We will present different heuristic approaches based on spanning tree and shortest path methods and on an exact algorithm solving the problem in polynomial time if the underlying graph is a tree. Both the edge- and node weighted case are investigated and extensive numerical results on the behaviour of the heuristics compared to optimal solutions are presented. The best heuristic yielded results within an error margin of less than one percent from optimality for most cases. In a large percentage of tests even optimal solutions have been found.Matthias Ehrgott; Horst. W. Hamacher; J. Freitag; F. Maffiolipreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/524Mon, 03 Apr 2000 00:00:00 +0200