Refine
Document Type
- Preprint (12) (remove)
Language
- English (12)
Has Fulltext
- yes (12)
Keywords
- Multiobjective optimization (3)
- Approximation (2)
- Hypervolume (2)
- Subset selection (2)
- combinatorial optimization (2)
- connectedness (2)
- k-link shortest path (2)
- Box Algorithms (1)
- Box-Algorithm (1)
- Decision support (1)
Faculty / Organisational entity
In this paper, theory and algorithms for solving the multiple objective minimum cost flow problem are reviewed. For both the continuous and integer case exact and approximation algorithms are presented. In addition, a section on compromise solutions summarizes corresponding results. The reference list consists of all papers known to the autheors which deal with the multiple objective minimum cost flow problem.
Selection of new projects is one of the major decision making activities in any company. Given a set of potential projects to invest, a subset which matches the company's strategy and internal resources best has to be selected. In this paper, we propose a multicriteria model for portfolio selection of projects, where we take into consideration that each of the potential projects has several - usually conflicting - values.
Connectedness of efficient solutions is a powerful property in multiple objective combinatorial optimization since it allows the construction of the complete efficient set using neighborhood search techniques. In this paper we show that, however, most of the classical multiple objective combinatorial optimization problems do not possess the connectedness property in general, including, among others, knapsack problems (and even several special cases of knapsack problems) and linear assignment problems. We also extend already known non-connectedness results for several optimization problems on graphs like shortest path, spanning tree and minimum cost flow problems. Different concepts of connectedness are discussed in a formal setting, and numerical tests are performed for different variants of the knapsack problem to analyze the likelihood with which non-connected adjacency graphs occur in randomly generated problem instances.
We consider a variant of a knapsack problem with a fixed cardinality constraint. There are three objective functions to be optimized: one real-valued and two integer-valued objectives. We show that this problem can be solved efficiently by a local search. The algorithm utilizes connectedness of a subset of feasible solutions and has optimal run-time.
We consider multiple objective combinatiorial optimization problems in which the first objective is of arbitrary type and the remaining objectives are either bottleneck or k-max objective functions. While the objective value of a bottleneck objective is determined by the largest cost value of any element in a feasible solution, the kth-largest element defines the objective value of the k-max objective. An efficient solution approach for the generation of the complete nondominated set is developed which is independent of the specific combinatiorial problem at hand. This implies a polynomial time algorithm for several important problem classes like shortest paths, spanning tree, and assignment problems with bottleneck objectives which are known to be NP-hard in the general multiple objective case.
The hypervolume subset selection problem consists of finding a subset, with a given cardinality \(k\), of a set of nondominated points that maximizes the hypervolume indicator. This problem arises in selection procedures of evolutionary algorithms for multiobjective optimization, for which practically efficient algorithms are required. In this article, two new formulations are provided for the two-dimensional variant of this problem.
The first is a (linear) integer programming formulation that can be solved by solving its linear programming relaxation. The second formulation is a \(k\)-link shortest path formulation on a special digraph with the Monge property that can be solved by dynamic programming in \(\mathcal{O}(n(k + \log n))\) time. This improves upon the \(\mathcal{O}(n^2k)\) result of Bader (2009), and matches the recent result of Bringmann et al. (2014), which was developed independently from this work using different techniques. Moreover, it is shown that these bounds may be further improved under mild conditions on \(k\).
The hypervolume subset selection problem consists of finding a subset, with a given cardinality, of a nondominated set of points that maximizes the hypervolume indicator. This problem arises in selection procedures of population-based heuristics for multiobjective optimization, and for which practically efficient algorithms are strongly required. In this article, we provide two new formulations for the two-dimensional variant of this problem.
The first is an integer programming formulation that can be solved by solving its linear relaxation. The second formulation is a \(k\)-link shortest path formulation on a special digraph with Monge property that can be solved by dynamic programming in \(\mathcal{O}(n^2)\) time complexity. This improves upon the existing result of \(O(n^3)\) in Bader.
A new algorithm for optimization problems with three objective functions is presented which computes a representation for the set of nondominated points. This representation is guaranteed to have a desired coverage error and a bound on the number of iterations needed by the algorithm to meet this coverage error is derived. Since the representation does not necessarily contain nondominated points only, ideas to calculate bounds for the representation error are given. Moreover, the incorporation of domination during the algorithm and other quality measures are discussed.