KLUEDO RSS FeedNeueste Dokumente / Latest documents
https://kluedo.ub.uni-kl.de/index/index/
Mon, 31 Mar 2014 07:47:17 +0200Mon, 31 Mar 2014 07:47:17 +0200Hypervolume Subset Selection in Two Dimensions: Formulations and Algorithms
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3770
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.Tobias Kuhn; Carlos M. Fonseca; Luís Paquete; Stefan Ruzika; José Rui Figueirapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3770Mon, 31 Mar 2014 07:47:17 +0200Reliable and Restricted Quickest Path Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2288
In a dynamic network, the quickest path problem asks for a path minimizing the time needed to send a given amount of flow from source to sink along this path. In practical settings, for example in evacuation or transportation planning, the reliability of network arcs depends on the specific scenario of interest. In this circumstance, the question of finding a quickest path among all those having at least a desired path reliability arises. In this article, this reliable quickest path problem is solved by transforming it to the restricted quickest path problem. In the latter, each arc is associated a nonnegative cost value and the goal is to find a quickest path among those not exceeding a predefined budget with respect to the overall (additive) cost value. For both, the restricted and reliable quickest path problem, pseudopolynomial exact algorithms and fully polynomial-time approximation schemes are proposed.Stefan Ruzika; Markus Thiemannreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2288Wed, 02 Mar 2011 16:45:38 +0100On a Cardinality Constrained Multicriteria Knapsack Problem
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2281
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.Florian Seipp; Stefan Ruzika; Luis Paquetepreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2281Tue, 08 Feb 2011 12:18:44 +0100Generalized Multiple Objective Bottleneck Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2252
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.Jochen Gorski; Kathrin Klamroth; Stefan Ruzikapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2252Thu, 09 Dec 2010 10:21:17 +0100Min-Max Quickest Path Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2249
In a dynamic network, the quickest path problem asks for a path such that a given amount of flow can be sent from source to sink via this path in minimal time. In practical settings, for example in evacuation or transportation planning, the problem parameters might not be known exactly a-priori. It is therefore of interest to consider robust versions of these problems in which travel times and/or capacities of arcs depend on a certain scenario. In this article, min-max versions of robust quickest path problems are investigated and, depending on their complexity status, exact algorithms or fully polynomial-time approximation schemes are proposed.Stefan Ruzika; Markus Thiemannreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2249Fri, 19 Nov 2010 09:57:06 +0100Earliest Arrival Flows in Series-Parallel Graphs
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2137
We present an exact algorithm for computing an earliest arrival flow in a discrete time setting on series-parallel graphs. In contrast to previous results for the earliest arrival flow problem this algorithm runs in polynomial time.Stefan Ruzika; Heike Sperber; Mechthild Steinerreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2137Tue, 06 Oct 2009 15:31:20 +0200Connectedness of Efficient Solutions in Multiple Objective Combinatorial Optimization
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1815
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.Jochen Gorski; Kathrin Klamroth; Stefan Ruzikapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1815Tue, 28 Nov 2006 11:52:25 +0100Acquisition Prioritization: A Multicriteria Approach Based on a Case Study
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1798
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.Horst W. Hamacher; Stefan Ruzika; Akin Tanatmispreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1798Wed, 08 Nov 2006 23:24:46 +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 +0100Multiple Objective Minimum Cost Flow Problems: A Review
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1677
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.Horst W. Hamacher; Christian Pedersen; Stefan Ruzikapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1677Thu, 27 Oct 2005 16:08:17 +0200Finding Representative Systems for Discrete Bicriteria Optimization Problems by Box Algorithms
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1655
Given a discrete bicriteria optimization problem (DBOP), we propose two versions of an approximation procedure, the box algorithm, which results in a representation of the complete set of nondominated solutions by a finite representative system Rep satisfying the following quality features.Horst W. Hamacher; Christian Roed Pedersen; Stefan Ruzikapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1655Wed, 17 Aug 2005 16:14:06 +0200Algorithms for Time-Dependent Bicriteria Shortest Path Problems (revised version)
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1581
In this paper we generalize the classical shortest path problem in two ways. We consider two objective functions and time-dependent data. The resulting problem, called the time-dependent bicriteria shortest path problem (TdBiSP), has several interesting practical applications, but has not gained much attention in the literature.Horst W. Hamacher; Stefan Ruzika; Stevanus A. Tjandrapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1581Thu, 28 Oct 2004 13:21:33 +0200A Survey of Approximation Methods in Multiobjective Programming
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1451
Approaches to approximate the efficient and Pareto sets of multiobjective programs are reviewed. Special attention is given to approximating structures, methods generating Pareto points, and approximation quality. The survey covers 48 articles published since 1975.Stefan Ruzika; Margaret M. Wiecekpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1451Thu, 13 Nov 2003 11:18:57 +0100