A multiobjective metaheuristic for a mean-risk static stochastic knapsack problem

In this paper we address two major challenges presented by stochastic discrete optimisation problems: the multiobjective nature of the problems, once risk aversion is incorporated, and the frequent difficulties in computing exactly, or even approximately, the objective function. The latter has often been handled with methods involving sample average approximation, where a random sample is generated so that population parameters may be estimated from sample statistics—usually the expected value is estimated from the sample average. We propose the use of multiobjective metaheuristics to deal with these difficulties, and apply a multiobjective local search metaheuristic to both exact and sample approximation versions of a mean-risk static stochastic knapsack problem. Variance and conditional value-at-risk are considered as risk measures. Results of a computational study are presented, that indicate the approach is capable of producing high-quality approximations to the efficient sets, with a modest computational effort.     

CHESS—Changing Horizon Efficient Set Search: A Simple Principle for Multiobjective Optimization

This paper presents a new concept for generating approximations to the non-dominated set in multiobjective optimization problems. The approximation set A is constructed by solving several single-objective minimization problems in which a particular function D(A, z) is minimized. A new algorithm to calculate D(A, z) is proposed.No general approach is available to solve the one-dimensional optimization problems, but metaheuristics based on local search procedures are used instead. Tests with multiobjective combinatorial problems whose non-dominated sets are known confirm that CHESS can be used to approximate the non-dominated set. Straightforward parallelization of the CHESS approach is illustrated with examples.The algorithm to calculate D(A, z) can be used in any other applications that need to determine Tchebycheff distances between a point and a dominant-free set.     

Coordination of production planning and distribution

This is a summary of the main results presented in the author’s Ph.D thesis, supervised by C. Prins and defended at the Université de Technologie de Troyes in October 2006. The thesis, written in French, is available from the author upon request. It deals with the integrated optimization of production planning and distribution in supply chains. A single product case and a multiproduct case are investigated. Integer linear programming models are proposed and different approaches based on heuristics, metaheuristics and cooperative methods are developed. Significant savings are obtained, compared to classical decoupled methods. These results confirm both the interest of integrating production and distribution decisions and of using metaheuristics for the largest instances.      

Approximative solution methods for multiobjective combinatorial optimization

In this paper we present a review of approximative solution methods, that is, heuristics and metaheuristics designed for the solution of multiobjective combinatorial optimization problems (MOCO). First, we discuss questions related to approximation in this context, such as performance ratios, bounds, and quality measures. We give some examples of heuristics proposed for the solution of MOCO problems. The main part of the paper covers metaheuristics and more precisely non-evolutionary methods. The pioneering methods and their derivatives are described in a unified way. We provide an algorithmic presentation of each of the methods together with examples of applications, extensions, and a bibliographic note. Finally, we outline trends in this area. The research of M. Ehrgott has been partially supported by University of Auckland grant 3602178/9275 and grant Ka 477/27-1 of the Deutsche Forschungsgemeinschaft (DFG).     

Evaluating Parallel Simulated Evolution Strategies for VLSI Cell Placement

Simulated Evolution (SimE) is an evolutionary metaheuristic that has produced results comparable to well established stochastic heuristics such as SA, TS and GA, with shorter runtimes. However, for optimization problems with a very large set of elements, such as in VLSI cell placement and routing, runtimes can still be very large and parallelization is an attractive option for reducing runtimes. Compared to other metaheuristics, parallelization of SimE has not been extensively explored. This paper presents a comprehensive set of parallelization approaches for SimE when applied to multiobjective VLSI cell placement problem. Each of these approaches are evaluated with respect to SimE characteristics and the constraints imposed by the problem instance. Conclusions drawn can be extended to parallelization of SimE when applied to other optimization problems.      

Multicriteria scheduling optimization using an elitist multiobjective population heuristic: the h-NSDE algorithm

In today’s manufacturing industry more than one performance criteria are considered for optimization to various degrees simultaneously. To deal with such hard competitive environments it is essential to develop appropriate multicriteria scheduling approaches. In this paper consideration is given to the problem of scheduling n independent jobs on a single machine with due dates and objective to simultaneously minimize three performance criteria namely, total weighted tardiness (TWT), maximum tardiness and maximum earliness. In the single machine scheduling literature no previous studies have been performed on test problems examining these criteria simultaneously. After positioning the problem within the relevant research field, we present a new heuristic algorithm for its solution. The developed algorithm termed the hybrid non-dominated sorting differential evolution (h-NSDE) is an extension of the author’s previous algorithm for the single-machine mono-criterion TWT problem. h-NSDE is devoted to the search for Pareto-optimal solutions. To enable the decision maker for evaluating a greater number of alternative non-dominated solutions, three multiobjective optimization approaches have been implemented and tested within the context of h-NSDE: including a weighted-sum based approach, a fuzzy-measures based approach which takes into account the interaction among the criteria as well as a Pareto-based approach. Experiments conducted on existing data set benchmarks problems show the effect of these approaches on the performance of the h-NSDE algorithm. Moreover, comparative results between h-NSDE and some of the most popular multiobjective metaheuristics including SPEA2 and NSGA-II show clear superiority for h-NSDE in terms of both solution quality and solution diversity.     

Solving the musical orchestration problem using multiobjective constrained optimization with a genetic local search approach

In this paper a computational approach of musical orchestration is presented. We consider orchestration as the search of relevant sound combinations within large instruments sample databases and propose two cooperating metaheuristics to solve this problem. Orchestration is seen here as a particular case of finding optimal constrained multisets on a large ensemble with respect to several objectives. We suggest a generic and easily extendible formalization of orchestration as a constrained multiobjective search towards a target timbre, in which several perceptual dimensions are jointly optimized. We introduce Orchidée, a time-efficient evolutionary orchestration algorithm that allows the discovery of optimal solutions and favors the exploration of non-intuitive sound mixtures. We also define a formal framework for global constraints specification and introduce the innovative CDCSolver repair metaheuristic, thanks to which the search is led towards regions fulfilling a set of musical-related requirements. Evaluation of our approach on a wide set of real orchestration problems is also provided.     

Simulated annealing metaheuristics for the vehicle routing problem with time windows

This paper develops simulated annealing metaheuristics for the vehicle routing and scheduling problem with time window constraints. Two different neighborhood structures, the λ-interchange mechanism of Osman and thek-node interchange process of Christofides and Beasley, are implemented. The enhancement of the annealing process with a short-term memory function via a tabu list is examined as a basis for improving the metaheuristic approach. Computational results on test problems from the literature as well as large-scale real-world problem are reported. The metaheuristics achieve solutions that compare favorably with previously reported results.     

A novel elitist multiobjective optimization algorithm: Multiobjective extremal optimization

Recently, a general-purpose local-search heuristic method called extremal optimization (EO) has been successfully applied to some NP-hard combinatorial optimization problems. This paper presents an investigation on EO with its application in numerical multiobjective optimization and proposes a new novel elitist (1 + λ) multiobjective algorithm, called multiobjective extremal optimization (MOEO). In order to extend EO to solve the multiobjective optimization problems, the Pareto dominance strategy is introduced to the fitness assignment of the proposed approach. We also present a new hybrid mutation operator that enhances the exploratory capabilities of our algorithm. The proposed approach is validated using five popular benchmark functions. The simulation results indicate that the proposed approach is highly competitive with the state-of-the-art multiobjective evolutionary algorithms. Thus MOEO can be considered a good alternative to solve numerical multiobjective optimization problems.     

Combining metaheuristics with mathematical programming, constraint programming and machine learning

During the last years, interest on hybrid metaheuristics has risen considerably in the field of optimization and machine learning. The best results found for many optimization problems in science and industry are obtained by hybrid optimization algorithms. Combinations of optimization tools such as metaheuristics, mathematical programming, constraint programming and machine learning, have provided very efficient optimization algorithms. Four different types of combinations are considered in this paper: (i) Combining metaheuristics with complementary metaheuristics. (ii) Combining metaheuristics with exact methods from mathematical programming approaches which are mostly used in the operations research community. (iii) Combining metaheuristics with constraint programming approaches developed in the artificial intelligence community. (iv) Combining metaheuristics with machine learning and data mining techniques.     

On solving the forward kinematics of 3RPR planar parallel manipulator using hybrid metaheuristics

Hybrid metaheuristics have been applied with success in solving many real-world problems. This work introduces hybrid metaheuristics to the field of kinematics problem, in particular, for solving the forward kinematics of the 3RPR parallel manipulator. It implements a combination of genetic algorithms and simulated annealing into two popular hybrid metaheuristic techniques. They are combined as teamwork and relay collaborative hybrid metaheuristics and compared to the performance of genetic algorithms and simulated annealing alone. The results show that the meta-heuristic approaches give robust and high quality solutions. Genetic algorithms and teamwork collaborative metaheuristics showed better performance than simulated annealing and relay collaborative metaheuristics. The given metaheuristic methods obtain all the unique solutions and comparisons with algebraic methods show promising results.     

DC-GRASP: directing the search on continuous-GRASP

Several papers in the scientific literature use metaheuristics to solve continuous global optimization. To perform this task, some metaheuristics originally proposed for solving combinatorial optimization problems, such as Greedy Randomized Adaptive Search Procedure (GRASP), Tabu Search and Simulated Annealing, among others, have been adapted to solve continuous global optimization problems. Proposed by Hirsch et al., the Continuous-GRASP (C-GRASP) is one example of this group of metaheuristics. The C-GRASP is an adaptation of GRASP proposed to solve continuous global optimization problems under box constraints. It is simple to implement, derivative-free and widely applicable method. However, according to Hedar, due to its random construction, C-GRASP may fail to detect promising search directions especially in the vicinity of minima, which may result in a slow convergence. To minimize this problem, in this paper we propose a set of methods to direct the search on C-GRASP, called Directed Continuous-GRASP (DC-GRASP). The proposal is to combine the ability of C-GRASP to diversify the search over the space with some efficient local search strategies to accelerate its convergence. We compare the DC-GRASP with the C-GRASP and other metaheuristics from literature on a set of standard test problems whose global minima are known. Computational results show the effectiveness and efficiency of the proposed methods, as well as their ability to accelerate the convergence of the C-GRASP.     

Multicriteria optimization with a multiobjective golden section line search

This work presents an algorithm for multiobjective optimization that is structured as: (i) a descent direction is calculated, within the cone of descent and feasible directions, and (ii) a multiobjective line search is conducted over such direction, with a new multiobjective golden section segment partitioning scheme that directly finds line-constrained efficient points that dominate the current one. This multiobjective line search procedure exploits the structure of the line-constrained efficient set, presenting a faster compression rate of the search segment than single-objective golden section line search. The proposed multiobjective optimization algorithm converges to points that satisfy the Kuhn-Tucker first-order necessary conditions for efficiency (the Pareto-critical points). Numerical results on two antenna design problems support the conclusion that the proposed method can solve robustly difficult nonlinear multiobjective problems defined in terms of computationally expensive black-box objective functions.     

Metaheuristics for a Flexible Assembly System Design Problem

Flexibility has become an important priority in the formulation and implementation of manufacturing strategies. This in turn has opened up a new class of design problems for such systems. Flexible assembly systems (FAS), consisting of a variety of processors and operations, provide the opportunity for improving product manufacturing flexibility, hence gaining competitive advantages. This paper considers a particular design decision problem for FAS. A matrix-based, polynomial-time lower bound algorithm is presented. Simulated annealing and tabu search metaheuristics are formulated to address the problems. Computational experience with these metaheuristics is reported.     

ParadisEO-MO: from fitness landscape analysis to efficient local search algorithms

This paper presents a general-purpose software framework dedicated to the design, the analysis and the implementation of local search metaheuristics: ParadisEO-MO. A substantial number of single solution-based local search metaheuristics has been proposed so far, and an attempt of unifying existing approaches is here presented. Based on a fine-grained decomposition, a conceptual model is proposed and is validated by regarding a number of state-of-the-art methodologies as simple variants of the same structure. This model is then incorporated into the ParadisEO-MO software framework. This framework has proven its efficiency and high flexibility by enabling the resolution of many academic and real-world optimization problems from science and industry.     

Evolutionary,constructive and hybrid procedures for the bi-objective set packing problem

The bi-objective set packing problem is a multi-objective combinatorial optimization problem similar to the well-known set covering/partitioning problems. To our knowledge and surprise, this problem has not yet been studied whereas several applications have been reported. Unfortunately, solving the problem exactly in a reasonable time using a generic solver is only possible for small instances. We designed three alternative procedures for approximating solutions to this problem. The first is derived from the original ‘Strength Pareto Evolutionary Algorithm’, which is a population-based metaheuristic. The second is an adaptation of the ‘Greedy Randomized Adaptative Search Procedure’, which is a constructive metaheuristic. As underlined in the overview of the literature summarized here, almost all the recent, effective procedures designed for approximating optimal solutions to multi-objective combinatorial optimization problems are based on a blend of techniques, called hybrid metaheuristics. Thus, the third alternative, which is the primary subject of this paper, is an original hybridization of the previous two metaheuristics. The algorithmic aspects, which differ from the original definition of these metaheuristics, are described, so that our results can be reproduced. The performance of our procedures is reported and the computational results for 120 numerical instances are discussed.     

A contribution to the stochastic flow shop scheduling problem

This paper deals with performance evaluation and scheduling problems in m machine stochastic flow shop with unlimited buffers. The processing time of each job on each machine is a random variable exponentially distributed with a known rate. We consider permutation flow shop. The objective is to find a job schedule which minimizes the expected makespan. A classification of works about stochastic flow shop with random processing times is first given. In order to solve the performance evaluation problem, we propose a recursive algorithm based on a Markov chain to compute the expected makespan and a discrete event simulation model to evaluate the expected makespan. The recursive algorithm is a generalization of a method proposed in the literature for the two machine flow shop problem to the m machine flow shop problem with unlimited buffers. In deterministic context, heuristics (like CDS [Management Science 16 (10) (1970) B630] and Rapid Access [Management Science 23 (11) (1977) 1174]) and metaheuristics (like simulated annealing) provide good results. We propose to adapt and to test this kind of methods for the stochastic scheduling problem. Combinations between heuristics or metaheuristics and the performance evaluation models are proposed. One of the objectives of this paper is to compare the methods together. Our methods are tested on problems from the OR-Library and give good results: for the two machine problems, we obtain the optimal solution and for the m machine problems, the methods are mutually validated.     

Robust multiobjective optimization & applications in portfolio optimization

Motivated by Markowitz portfolio optimization problems under uncertainty in the problem data, we consider general convex parametric multiobjective optimization problems under data uncertainty. For the first time, this uncertainty is treated by a robust multiobjective formulation in the gist of Ben-Tal and Nemirovski. For this novel formulation, we investigate its relationship to the original multiobjective formulation as well as to its scalarizations. Further, we provide a characterization of the location of the robust Pareto frontier with respect to the corresponding original Pareto frontier and show that standard techniques from multiobjective optimization can be employed to characterize this robust efficient frontier. We illustrate our results based on a standard mean–variance problem.     

On <Emphasis Type="Italic">G</Emphasis>-invex multiobjective programming. Part II. Duality

This paper represents the second part of a study concerning the so-called G-multiobjective programming. A new approach to duality in differentiable vector optimization problems is presented. The techniques used are based on the results established in the paper: On G-invex multiobjective programming. Part I. Optimality by T.Antczak. In this work, we use a generalization of convexity, namely G-invexity, to prove new duality results for nonlinear differentiable multiobjective programming problems. For such vector optimization problems, a number of new vector duality problems is introduced. The so-called G-Mond–Weir, G-Wolfe and G-mixed dual vector problems to the primal one are defined. Furthermore, various so-called G-duality theorems are proved between the considered differentiable multiobjective programming problem and its nonconvex vector G-dual problems. Some previous duality results for differentiable multiobjective programming problems turn out to be special cases of the results described in the paper.