Efficient multicriterial optimization based on intensive reuse of search information

This paper proposes an efficient method for solving complex multicriterial optimization problems, for which the optimality criteria may be multiextremal and the calculations of the criteria values may be time-consuming. The approach involves reducing multicriterial problems to global optimization ones through minimax convolution of partial criteria, reducing dimensionality by using Peano curves and implementing efficient information-statistical methods for global optimization. To efficiently find the set of Pareto-optimal solutions, it is proposed to reuse all the search information obtained in the course of optimization. The results of computational experiments indicate that the proposed approach greatly reduces the computational complexity of solving multicriterial optimization problems.     

A Hybrid Meta-Heuristic for Multi-Objective Optimization: MOSATS

Real optimization problems often involve not one, but multiple objectives, usually in conflict. In single-objective optimization there exists a global optimum, while in the multi-objective case no optimal solution is clearly defined but rather a set of solutions, called the Pareto-optimal front. Thus, the goal of multi-objective strategies is to generate a set of non-dominated solutions as an approximation to this front. However, the majority of problems of this kind cannot be solved exactly because they have very large and highly complex search spaces. In recent years, meta-heuristics have become important tools for solving multi-objective problems encountered in industry as well as in the theoretical field. This paper presents a novel approach based on hybridizing Simulated Annealing and Tabu Search. Experiments on the Graph Partitioning Problem show that this new method is a better tool for approximating the efficient set than other strategies also based on these meta-heuristics.     

A hybrid method for solving multi-objective global optimization problems

Real optimization problems often involve not one, but multiple objectives, usually in conflict. In single-objective optimization there exists a global optimum, while in the multi-objective case no optimal solution is clearly defined but rather a set of optimums, which constitute the so called Pareto-optimal front. Thus, the goal of multi-objective strategies is to generate a set of non-dominated solutions as an approximation to this front. However, most problems of this kind cannot be solved exactly because they have very large and highly complex search spaces. The objective of this work is to compare the performance of a new hybrid method here proposed, with several well-known multi-objective evolutionary algorithms (MOEA). The main attraction of these methods is the integration of selection and diversity maintenance. Since it is very difficult to describe exactly what a good approximation is in terms of a number of criteria, the performance is quantified with adequate metrics that evaluate the proximity to the global Pareto-front. In addition, this work is also one of the few empirical studies that solves three-objective optimization problems using the concept of global Pareto-optimality.     

Identifying Pareto-optimal settlements for two-party resource allocation negotiations

We explore models to identify Pareto-optimal outcomes in two-party multiple program resource allocation post-settlement settlement negotiations. The approximation of the contract curve, that is the set of Pareto-optimal outcomes, is also discussed. We consider the case where the parties split a shared hard resource. An application of the models to a resource allocation problem in a Finnish university is also discussed.     

Convergence of stochastic search algorithms to finite size pareto set approximations

In this work we investigate the convergence of stochastic search algorithms toward the Pareto set of continuous multi-objective optimization problems. The focus is on obtaining a finite approximation that should capture the entire solution set in a suitable sense, which will be defined using the concept of ε-dominance. Under mild assumptions about the process to generate new candidate solutions, the limit approximation set will be determined entirely by the archiving strategy. We propose and analyse two different archiving strategies which lead to a different limit behavior of the algorithms, yielding bounds on the obtained approximation quality as well as on the cardinality of the resulting Pareto set approximation.      

Some Issues in the Theory of Optimal Algorithms and Informational Complexity

The article presents the basic concepts and reviews the main results of the theory of optimal algorithms and informational complexity. Informational complexity bounds are provided for Lipschitzian multi-criterion problems that construct the approximate Pareto-optimal strategy set under different interpretations of approximation—approximation by the functional and approximation by the argument. The informational complexity is compared for the scalar global optimization problem and the problem of finding the roots of nonlinear equations by global search methods.     

The primal-dual method for approximation algorithms

In this survey, we give an overview of a technique used to design and analyze algorithms that provide approximate solutions to NP-hard problems in combinatorial optimization. Because of parallels with the primal-dual method commonly used in combinatorial optimization, we call it the primal-dual method for approximation algorithms. We show how this technique can be used to derive approximation algorithms for a number of different problems, including network design problems, feedback vertex set problems, and facility location problems. Received: June 19, 2000 / Accepted: February 7, 2001?Published online October 2, 2001     

Control-space properties of cooperative games

If two or more players agree to cooperate while playing a game, they help one another to minimize their respective costs as long as it is not to their individual disadvantages. This leads at once to the concept of undominated solutions to a game. Anundominated orPareto-optimal solution has the property that, compared to any other solution, at least one playerdoes worse or alldo the same if they use a solution other than the Pareto-optimal one.Closely related to the concept of a Pareto-optimal solution is theabsolutely cooperative solution. Such a solution has the property that, compared to any other permissible solution,every playerdoes no better if a solution other than the absolutely cooperative one is employed.This paper deals with control-space properties of Pareto-optimal and absolutely cooperative solutions for both static, continuous games and differential games. Conditions are given for cases in which solutions to the Pareto-optimal and absolutely cooperative games lie in the interior or on the boundary of the control set.The solution of a Pareto-optimal or absolutely cooperative game is related to the solution of a minimization problem with avector cost criterion. The question of whether or not a problem with a vector cost criterion can be reduced to a family of minimization problems with ascalar cost criterion is also discussed.An example is given to illustrate the theory.This research was supported in part by NASA Grant No. NGR-03-002-011 and ONR Contract No. N00014-69-A-0200-1020.     

Annealing-tabu PAES: a multi-objective hybrid meta-heuristic

Most real-life optimization problems require taking into account not one, but multiple objectives simultaneously. In most cases these objectives are in conflict, i.e. the improvement of some objectives implies the deterioration of others. In single-objective optimization there exists a global optimum, while in the multi-objective case no optimal solution is clearly defined, but rather a set of solutions. In the last decade most papers dealing with multi-objective optimization use the concept of Pareto-optimality. The goal of Pareto-based multi-objective strategies is to generate a front (set) of non-dominated solutions as an approximation to the true Pareto-optimal front. However, this front is unknown for problems with large and highly complex search spaces, which is why meta-heuristic methods have become important tools for solving this kind of problem. Hybridization in the multi-objective context is nowadays an open research area. This article presents a novel extension of the well-known Pareto archived evolution strategy (PAES) which combines simulated annealing and tabu search. Experiments on several mathematical problems show that this hybridization allows an improvement in the quality of the non-dominated solutions in comparison with PAES, and also with its extension M-PAES.     

Quasiconcave vector maximization: Connectedness of the sets of Pareto-optimal and weak Pareto-optimal alternatives

We study the sets of Pareto-optimal and weakly Pareto-optimal solutions to a vector maximization problem defined by a continuous vector-valued quasiconcave criterion functionf and a closed convex set of alternativesS. IfS is compact, it is shown that the set of weakly Pareto-optimal alternatives is connected, but that the set of Pareto-optimal alternatives is not necessarily connected. However, the set of Pareto optima is shown to be connected for some important subclasses of quasiconcave functions. We also provide some reasonable conditions under which the compactness assumption onS may be relaxed and connectedness maintained.     

On well posedness of best simultaneous approximation problems in Banach spaces

The well posedness of best simultaneous approximation problems is considered. We establish the generic results on the well posedness of the best simultaneous approximation problems for any closed weakly compact nonempty subset in a strictly convex Kadec Banach space. Further, we prove that the set of all points inE(G) such that the best simultaneous approximation problems are not well posed is a u- porous set inE(G) whenX is a uniformly convex Banach space. In addition, we also investigate the generic property of the ambiguous loci of the best simultaneous approximation.     

Approximation in multiobjective optimization

Some results of approximation type for multiobjective optimization problems with a finite number of objective functions are presented. Namely, for a sequence of multiobjective optimization problems P _n which converges in a suitable sense to a limit problem P, properties of the sequence of approximate Pareto efficient sets of the P _n 's, are studied with respect to the Pareto efficient set of P. The exterior penalty method as well as the variational approximation method appear to be particular cases of this framework.     

Finite-dimensional approximation of tikhonov regularized solutions of non-linear ill-posed problems

In this paper we consider non-linear ill-posed problems F(x)=y0 in a Hilbert space setting. We solve these problems with Tikhonov regularization combined with finite-dimensional approximation where the data y0 and the non-linear operator F are assumed to be known only approximately. Conditions are given that guarantee optimal convergence rates with respect to both, the data noise and the finite-dimensional approximation. Finally, we present some numerical results for parameter estimation problems that verify the theoretical results.     

How good are SPT schedules for fair optimality criteria

We consider the following scheduling setting: a set of n tasks have to be executed on a set of m identical machines. It is well known that shortest processing time (SPT) schedules are optimal for the problem of minimizing the total sum of completion times of the tasks. In this paper, we measure the quality of SPT schedules, from an approximation point of view, with respect to the following optimality criteria: sum of completion times per machine, global fairness, and individual fairness.     

Interactive Polyhedral Outer Approximation (IPOA) strategy for general multiobjective optimization problems

We propose an interactive polyhedral outer approximation (IPOA) method to solve a broad class of multiobjective optimization problems (MOP) with, possibly, nonlinear and nondifferentiable objective and constraint functions, and with continuous or discrete decision variables. During the interactive optimization phase, the method progressively constructs a polyhedral approximation of the decision-maker’s (DM’s) unknown preference structure and a polyhedral outer-approximation of the feasible set of MOP. The piecewise linear approximation of the DM’s preferences also provides a mechanism for testing the consistency of the DM’s assessments and removing inconsistencies; it also allows post-optimality analysis. All the feasible trial solutions are non-dominated (efficient, or Pareto-optimal) so preference assessments are made in the context of non-dominated alternatives only. Upper and lower bounds on the yet unknown optimal value are produced at every iteration, allowing terminating the search prematurely at a good-enough solution and providing information about the closeness of this solution to the optimal solution. The IPOA method includes a preliminary phase in which a limited probe of the efficient set is conducted in order to find a good initial trial solution for the interactive phase. The computational requirements of the algorithm are relatively simple. The results of an extensive computational study are reported.     

Multistage stochastic programming: Error analysis for the convex case

We consider convex stochastic multistage problems and present an approximation technique which allows to analyse the error with respect to time. The technique is based on barycentric approximation of conditional and marginal probability spaces and requiresstrict nonanticipativity for the constraint multifunction and thesaddle property for the value functions.Part of this work was carried out at the Institute of Operations Research of the University of Zurich.     

An algorithm for large scale 0–1 integer programming with application to airline crew scheduling

We present an approximation algorithm for solving large 0–1 integer programming problems whereA is 0–1 and whereb is integer. The method can be viewed as a dual coordinate search for solving the LP-relaxation, reformulated as an unconstrained nonlinear problem, and an approximation scheme working together with this method. The approximation scheme works by adjusting the costs as little as possible so that the new problem has an integer solution. The degree of approximation is determined by a parameter, and for different levels of approximation the resulting algorithm can be interpreted in terms of linear programming, dynamic programming, and as a greedy algorithm. The algorithm is used in the CARMEN system for airline crew scheduling used by several major airlines, and we show that the algorithm performs well for large set covering problems, in comparison to the CPLEX system, in terms of both time and quality. We also present results on some well known difficult set covering problems that have appeared in the literature.     

How to Allocate Network Centers

This paper deals with the issue of allocating and utilizing centers in a distributed network, in its various forms. The paper discusses the significant parameters of center allocation, defines the resulting optimization problems, and proposes several approximation algorithms for selecting centers and for distributing the users among them. We concentrate mainly on balanced versions of the problem, i.e., in which it is required that the assignment of clients to centers be as balanced as possible. The main results are constant ratio approximation algorithms for the balanced κ-centers and balanced κ-weighted centers problems, and logarithmic ratio approximation algorithms for the ρ-dominating set and the k-tolerant set problems.     

Dual approach to minimization on the set of pareto-optimal solutions

LetX ^* be the set of Pareto-optimal solutions of a multicriteria programming problem. We are interested in finding a vectorxX ^* which minimizes another criterion. SinceX ^* is a nonconvex set, our problem is that of minimization over a nonconvex set. By exploiting the fact that the number of criteria is often very small compared with the number of variables, we use a dual approach to obtain a practical algorithm. We report preliminary numerical results on problems with up to 100 variables and 5 criteria.The authors express their special thanks to Professor H. P. Benson and the referees for many valuable comments and suggestions and for pointing out valuable references. They also thank Dr. Y. Ishizuka for the references of Theorem 2.2.