Solving the maximum clique problem using a tabu search approach

We describe two variants of a tabu search heuristic, a deterministic one and a probabilistic one, for the maximum clique problem. This heuristic may be viewed as a natural alternative implementation of tabu search for this problem when compared to existing ones. We also present a new random graph generator, the -generator, which produces graphs with larger clique sizes than comparable ones obtained by classical random graph generating techniques. Computational results on a large set of test problems randomly generated with this new generator are reported and compared with those of other approximate methods.The authors are grateful to the Quebec Government (Fonds F.C.A.R.) and to the Canadian Natural Sciences and Engineering Research Council (grant 0GP0038816) for financial support.     

MultiGLODS: global and local multiobjective optimization using direct search

The optimization of multimodal functions is a challenging task, in particular when derivatives are not available for use. Recently, in a directional direct search framework, a clever multistart strategy was proposed for global derivative-free optimization of single objective functions. The goal of the current work is to generalize this approach to the computation of global Pareto fronts for multiobjective multimodal derivative-free optimization problems. The proposed algorithm alternates between initializing new searches, using a multistart strategy, and exploring promising subregions, resorting to directional direct search. Components of the objective function are not aggregated and new points are accepted using the concept of Pareto dominance. The initialized searches are not all conducted until the end, merging when they start to be close to each other. The convergence of the method is analyzed under the common assumptions of directional direct search. Numerical experiments show its ability to generate approximations to the different Pareto fronts of a given problem.     

Solving a chemical batch scheduling problem by local search

In this paper the following chemical batch scheduling problem is considered: a set of orders has to be processed on a set of facilities. For each order a given amount of a product must be produced by means of chemical reactions before a given deadline. The production consists of a sequence of processes whereby each process has to be performed by one facility out of a given subset of facilities allowed for this process. The processing times depend on the choice of the facility and the processing is done in batch mode with given minimum and maximum sizes. The problem is to assign the processes to the facilities, splitting them into batches, and scheduling these batches in order to produce the demands within the given deadlines. For the scheduling part of the problem we present an approach based on the following steps. First, a procedure to calculate the minimum number of batches needed to satisfy the demands is presented. Based on this, the given problem is modeled in two different ways: as a general shop scheduling problem with set-up times or as scheduling problem with positive time-lags. Finally, a two-phase tabu search method is presented which is based on the two different formulations of the problem. The method is tested on some real world data. This revised version was published online in June 2006 with corrections to the Cover Date.     

Solving the unconstrained optimization problem by a variable neighborhood search

This paper presents variable neighborhood search (VNS) for the problem of finding the global minimum of a nonconvex function. The variable neighborhood search, which changes systematically neighborhood structures in the search for finding a better solution, is used to guide a set of standard improvement heuristics. This algorithm was tested on some standard test functions, and successful results were obtained. Its performance was compared with the other algorithms, and observed to be better.     

A hybrid genetic algorithm for multiobjective problems with activity analysis-based local search

The objective of this research was the development of a method that integrated an activity analysis model of profits from production with a biophysical model, and included the capacity for optimization over multiple objectives. We specified a hybrid genetic algorithm using activity analysis as a local search method, and NSGA-II for calculation of the multiple objective Pareto optimal set. We describe a parallel computing approach to computation of the genetic algorithm, and apply the algorithm to evaluation of an input tax to regulate pollution from agricultural production.     

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.     

Solving the frequency assignment problem with polarization by local search and tabu

In the Frequency Assignment Problem with Polarization (FAPP), a given set of links must each be assigned a frequency and a polarization, while respecting given radio-electric compatibility constraints defined on pairs of links. In this paper, we propose a tabu search algorithm for the FAPP. A specialized neighborhood is proposed for the problem. Other key features of the algorithm are an adaptive technique to adjust the tabu tenure, an original diversification technique, and a pre-processing procedure based on arc-consistency techniques. The algorithm is tested on the 40 instances of the ROADEF Challenge 2001. It reaches the best known feasibility level for all instances and finds or improves on the best known solutions of the Challenge for a majority of the instances.Received: July 2003 / Revised version: September 2004MSC classification: 90B18, 68T20All correspondence to: Philippe Galinier     

Evacuation planning using multiobjective evolutionary optimization approach

In an emergency situation, evacuation is conducted in order to displace people from a dangerous place to a safer place, and it usually needs to be done in a hurry. It is necessary to prepare evacuation plans in order to have a good response in an emergency situation. A central challenge in developing an evacuation plan is in determining the distribution of evacuees into the safe areas, that is, deciding where and from which road each evacuee should go. To achieve this aim, several objective functions should be brought into consideration and need to be satisfied simultaneously, though these objective functions may often conflict with each other.     

Solving the index tracking problem: a continuous optimization approach

Central European Journal of Operations Research - Investing vast amounts of money with the goal of fostering medium to long-term growth in returns is a challenging task in financial optimization. A...     

Investigating a hybrid simulated annealing and local search algorithm for constrained optimization

Constrained Optimization Problems (COP) often take place in many practical applications such as kinematics, chemical process optimization, power systems and so on. These problems are challenging in terms of identifying feasible solutions when constraints are non-linear and non-convex. Therefore, finding the location of the global optimum in the non-convex COP is more difficult as compared to non-convex bound-constrained global optimization problems. This paper proposes a Hybrid Simulated Annealing method (HSA), for solving the general COP. HSA has features that address both feasibility and optimality issues and here, it is supported by a local search procedure, Feasible Sequential Quadratic Programming (FSQP). We develop two versions of HSA. The first version (HSAP) incorporates penalty methods for constraint handling and the second one (HSAD) eliminates the need for imposing penalties in the objective function by tracing feasible and infeasible solution sequences independently. Numerical experiments show that the second version is more reliable in the worst case performance.     

A united search particle swarm optimization algorithm for multiobjective scheduling problem

The performance of a scheduling system, in practice, is not evaluated to satisfy a single objective, but to obtain a trade-off schedule regarding multiple objectives. Therefore, in this research, I make use of multiple objective decision-making method, a global criterion approach, to develop a multi-objective scheduling problem model with different due-dates on parallel machines processes, in which consider three performance measures, namely minimum run time of every machine, earlierness time (no tardiness) and process time of every job, simultaneously. According to this special multi-objective scheduling problem, the method of reverse order drawing GATT will be proposed, at the same time, bring forward a united search particle swarm optimization algorithm (USPSOA) solves this multi-objective scheduling problem. The validity and adaptability of the USPSOA is investigated through experimental results.     

Bilevel optimization with a multiobjective problem in the lower level

Numerical Algorithms - Bilevel problems model instances with a hierarchical structure. Aiming at an efficient solution of a constrained multiobjective problem according with some pre-defined...     

Solving the Dial-a-Ride problem using genetic algorithms

In the Dial-a-Ride problem (DARP), customers request transportation from an operator. A request consists of a specified pickup location and destination location along with a desired departure or arrival time and capacity demand. The aim of DARP is to minimize transportation cost while satisfying customer service level constraints (Quality of Service). In this paper, we present a genetic algorithm (GA) for solving the DARP. The algorithm is based on the classical cluster-first, route-second approach, where it alternates between assigning customers to vehicles using a GA and solving independent routing problems for the vehicles using a routing heuristic. The algorithm is implemented in Java and tested on publicly available data sets. The new solution method has achieved solutions comparable with the current state-of-the-art methods.     

Solving a multiobjective possibilistic problem through compromise programming

Real decision problems usually consider several objectives that have parameters which are often given by the decision maker in an imprecise way. It is possible to handle these kinds of problems through multiple criteria models in terms of possibility theory.Here we propose a method for solving these kinds of models through a fuzzy compromise programming approach.To formulate a fuzzy compromise programming problem from a possibilistic multiobjective linear programming problem the fuzzy ideal solution concept is introduced. This concept is based on soft preference and indifference relationships and on canonical representation of fuzzy numbers by means of their α-cuts. The accuracy between the ideal solution and the objective values is evaluated handling the fuzzy parameters through their expected intervals and a definition of discrepancy between intervals is introduced in our analysis.     

Solving the multiobjective possibilistic linear programming problem

In conventional multiobjective decision making problems, the estimation of the parameters of the model is often a problematic task. Normally they are either given by the decision maker (DM), who has imprecise information and/or expresses his considerations subjectively, or by statistical inference from past data and their stability is doubtful. Therefore, it is reasonable to construct a model reflecting imprecise data or ambiguity in terms of fuzzy sets for which a lot of fuzzy approaches to multiobjective programming have been developed. In this paper we propose a method to solve a multiobjective linear programming problem involving fuzzy parameters (FP-MOLP), whose possibility distributions are given by fuzzy numbers, estimated from the information provided by the DM. As the parameters, intervening in the model, are fuzzy the solutions will be also fuzzy. We propose a new Pareto Optimal Solution concept for fuzzy multiobjective programming problems. It is based on the extension principle and the joint possibility distribution of the fuzzy parameters of the problem. The method relies on α-cuts of the fuzzy solution to generate its possibility distributions. These ideas are illustrated with a numerical example.     

Bayesian approach to global optimization and application to multiobjective and constrained problems

In this paper, the Bayesian methods of global optimization are considered. They provide the minimal expected deviation from the global minimum. It is shown that, using the Bayesian methods, the asymptotic density of calculations of the objective function is much greater around the point of global minimum. The relation of this density to the parameters of the method and to the function is defined.Algorithms are described which apply the Bayesian methods to problems with linear and nonlinear constraints. The Bayesian approach to global multiobjective optimization is defined. Interactive procedures and reduction of multidimensional data in the case of global optimization are discussed.     

Convex optimization approach to a single quadratically constrained quadratic minimization problem

In this paper, first we show that for rank deficient matrices, the optimal solution of a single equality constrained quadratic minimization problem can be found by relaxing the equality constraint to the inequality one, which makes the problem a convex problem. Then we show that for full rank matrices, an optimal solution can be obtained using semidefinite optimization framework.     

A local relaxation method for the cardinality constrained portfolio optimization problem

The NP-hard nature of cardinality constrained mean-variance portfolio optimization problems has led to a number of different algorithms with varying degrees of success in reaching optimality given limited computational resources and under the presence of strict time constraints present in practice. The proposed local relaxation algorithm explores the inherent structure of the objective function. It solves a sequence of small, local, quadratic-programs by first projecting asset returns onto a reduced metric space, followed by clustering in this space to identify sub-groups of assets that best accentuate a suitable measure of similarity amongst different assets. The algorithm can either be cold started using a suitable heuristic method such as the centroids of initial clusters or be warm started based on the last output. Results, using a basket of up to 3,000 stocks and with different cardinality constraints, indicates that the proposed algorithm can lead to significant performance gain over popular branch-and-cut methods. One key application of this algorithm is in dealing with large scale cardinality constrained portfolio optimization under tight time constraint, such as for the purpose of index tracking or index arbitrage at high frequency.     

Solving nonlinearly constrained global optimization problem via an auxiliary function method

This paper considers the nonlinearly constrained continuous global minimization problem. Based on the idea of the penalty function method, an auxiliary function, which has approximately the same global minimizers as the original problem, is constructed. An algorithm is developed to minimize the auxiliary function to find an approximate constrained global minimizer of the constrained global minimization problem. The algorithm can escape from the previously converged local minimizers, and can converge to an approximate global minimizer of the problem asymptotically with probability one. Numerical experiments show that it is better than some other well known recent methods for constrained global minimization problems.     

Solving a multiobjective traveling salesman problem by dynamic programming

In this paper Klötzler's method of multiobjective dynamic programming is applied to the solution of a two-dimensional traveling salesman problem. In this way Bellman's and Held/Karp's dynamic programming approach to one-dimensional traveling salesman problems is extended to the multiobjective case.