Refine
Year of publication
Document Type
- Preprint (25) (remove)
Has Fulltext
- yes (25)
Keywords
Faculty / Organisational entity
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.
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.
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.
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.
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.
Convex Operators in Vector Optimization: Directional Derivatives and the Cone of Decrease Directions
(1999)
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.
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.
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 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.
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.