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 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.
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.
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.
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.
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.
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.
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.