An Experimental Evaluation of a Scatter Search for the Linear Ordering Problem

Scatter search is a population-based method that has recently been shown to yield promising outcomes for solving combinatorial and nonlinear global optimization problems. Based on formulations originally proposed in the 1960s for combining decision rules and problem constraints, such as in generating surrogate constraints, scatter search uses strategies for combining solution vectors that have proved effective in a variety of problem settings. In this paper, we present a scatter search implementation designed to find high quality solutions for the NP-hard linear ordering problem, which has a significant number of applications in practice. The LOP, for example, is equivalent to the so-called triangulation problem for input-output tables in economics. Our implementation incorporates innovative mechanisms to combine solutions and to create a balance between quality and diversification in the reference set. We also use a tracking process that generates solution statistics disclosing the nature of combinations and the ranks of antecedent solutions that produced the best final solutions. Extensive computational experiments with more than 300 instances establishes the effectiveness of our procedure in relation to approaches previously identified to be best.     

Scatter tabu search for multiobjective clustering problems

We propose a hybrid heuristic procedure based on scatter search and tabu search for the problem of clustering objects to optimize multiple criteria. Our goal is to search for good approximations of the efficient frontier for this class of problems and provide a means for improving decision making in multiple application areas. Our procedure can be viewed as an extension of SSPMO (a scatter search application to nonlinear multiobjective optimization) to which we add new elements and strategies specially suited for combinatorial optimization problems. Clustering problems have been the subject of numerous studies; however, most of the work has focused on single-objective problems. Clustering using multiple criteria and/or multiple data sources has received limited attention in the operational research literature. Our scatter tabu search implementation is general and tackles several problems classes within this area of combinatorial data analysis. We conduct extensive experimentation to show that our method is capable of delivering good approximations of the efficient frontier for improved analysis and decision making.     

Principles of scatter search

Scatter search is an evolutionary method that has been successfully applied to hard optimization problems. The fundamental concepts and principles of the method were first proposed in the 1970s, based on formulations dating back to the 1960s for combining decision rules and problem constraints. In contrast to other evolutionary methods like genetic algorithms, scatter search is founded on the premise that systematic designs and methods for creating new solutions afford significant benefits beyond those derived from recourse to randomization. It uses strategies for search diversification and intensification that have proved effective in a variety of optimization problems.This paper provides the main principles and ideas of scatter search and its generalized form path relinking. We first describe a basic design to give the reader the tools to create relatively simple implementations. More advanced designs derive from the fact that scatter search and path relinking are also intimately related to the tabu search (TS) metaheuristic, and gain additional advantage by making use of TS adaptive memory and associated memory-exploiting mechanisms capable of being tailored to particular contexts. These and other advanced processes described in the paper facilitate the creation of sophisticated implementations for hard problems that often arise in practical settings. Due to their flexibility and proven effectiveness, scatter search and path relinking can be successfully adapted to tackle optimization problems spanning a wide range of applications and a diverse collection of structures, as shown in the papers of this volume.     

A black-box scatter search for optimization problems with integer variables

The goal of this work is the development of a black-box solver based on the scatter search methodology. In particular, we seek a solver capable of obtaining high quality outcomes to optimization problems for which solutions are represented as a vector of integer values. We refer to these problems as integer optimization problems. We assume that the decision variables are bounded and that there may be constraints that require that the black-box evaluator is called in order to know whether they are satisfied. Problems of this type are common in operational research areas of applications such as telecommunications, project management, engineering design and the like.Our experimental testing includes 171 instances within four classes of problems taken from the literature. The experiments compare the performance of the proposed method with both the best context-specific procedures designed for each class of problem as well as context-independent commercial software. The experiments show that the proposed solution method competes well against commercial software and that can be competitive with specialized procedures in some problem classes.     

Interactive multiobjective complex search

An interactive procedure based on Box's complex search is used to solve the vector maximization problem. This method has the advantage that the decision maker's underlying value function need not be explicitly specified. Also, the problem may have nonlinear objective functions and nonlinear constraints. Several example problems are presented.     

Heuristic solutions to the problem of routing school buses with multiple objectives

In this paper we address the problem of routing school buses in a rural area. We approach this problem with a node routing model with multiple objectives that arise from conflicting viewpoints. From the point of view of cost, it is desirable to minimise the number of buses used to transport students from their homes to school and back. From the point of view of service, it is desirable to minimise the time that a given student spends en route. The current literature deals primarily with single-objective problems and the models with multiple objectives typically employ a weighted function to combine the objectives into a single one. We develop a solution procedure that considers each objective separately and search for a set of efficient solutions instead of a single optimum. Our solution procedure is based on constructing, improving and then combining solutions within the framework of the evolutionary approach known as scatter search. Experimental testing with real data is used to assess the merit of our proposed procedure.     

Characterizations of the nonemptiness and compactness for solution sets of convex set-valued optimization problems

In this paper, we first derive several characterizations of the nonemptiness and compactness for the solution set of a convex scalar set-valued optimization problem (with or without cone constraints) in which the decision space is finite-dimensional. The characterizations are expressed in terms of the coercivity of some scalar set-valued maps and the well-posedness of the set-valued optimization problem, respectively. Then we investigate characterizations of the nonemptiness and compactness for the weakly efficient solution set of a convex vector set-valued optimization problem (with or without cone constraints) in which the objective space is a normed space ordered by a nontrivial, closed and convex cone with nonempty interior and the decision space is finite-dimensional. We establish that the nonemptiness and compactness for the weakly efficient solution set of a convex vector set-valued optimization problem (with or without cone constraints) can be exactly characterized as those of a family of linearly scalarized convex set-valued optimization problems and the well-posedness of the original problem.     

Sample average approximation of stochastic dominance constrained programs

In this paper we study optimization problems with second-order stochastic dominance constraints. This class of problems allows for the modeling of optimization problems where a risk-averse decision maker wants to ensure that the solution produced by the model dominates certain benchmarks. Here we deal with the case of multi-variate stochastic dominance under general distributions and nonlinear functions. We introduce the concept of ${\mathcal{C}}$ -dominance, which generalizes some notions of multi-variate dominance found in the literature. We apply the Sample Average Approximation (SAA) method to this problem, which results in a semi-infinite program, and study asymptotic convergence of optimal values and optimal solutions, as well as the rate of convergence of the feasibility set of the resulting semi-infinite program as the sample size goes to infinity. We develop a finitely convergent method to find an ${\epsilon}$ -optimal solution of the SAA problem. An important aspect of our contribution is the construction of practical statistical lower and upper bounds for the true optimal objective value. We also show that the bounds are asymptotically tight as the sample size goes to infinity.     

Solving a class of semidefinite programs via nonlinear programming

In this paper, we introduce a transformation that converts a class of linear and nonlinear semidefinite programming (SDP) problems into nonlinear optimization problems. For those problems of interest, the transformation replaces matrix-valued constraints by vector-valued ones, hence reducing the number of constraints by an order of magnitude. The class of transformable problems includes instances of SDP relaxations of combinatorial optimization problems with binary variables as well as other important SDP problems. We also derive gradient formulas for the objective function of the resulting nonlinear optimization problem and show that both function and gradient evaluations have affordable complexities that effectively exploit the sparsity of the problem data. This transformation, together with the efficient gradient formulas, enables the solution of very large-scale SDP problems by gradient-based nonlinear optimization techniques. In particular, we propose a first-order log-barrier method designed for solving a class of large-scale linear SDP problems. This algorithm operates entirely within the space of the transformed problem while still maintaining close ties with both the primal and the dual of the original SDP problem. Global convergence of the algorithm is established under mild and reasonable assumptions. Received: January 5, 2000 / Accepted: October 2001?Published online February 14, 2002     

Finding an efficient solution to linear bilevel programming problem: An effective approach

Multilevel programming is developed to solve the decentralized problem in which decision makers (DMs) are often arranged within a hierarchical administrative structure. The linear bilevel programming (BLP) problem, i.e., a special case of multilevel programming problems with a two level structure, is a set of nested linear optimization problems over polyhedral set of constraints. Two DMs are located at the different hierarchical levels, both controlling one set of decision variables independently, with different and perhaps conflicting objective functions. One of the interesting features of the linear BLP problem is that its solution may not be Paretooptimal. There may exist a feasible solution where one or both levels may increase their objective values without decreasing the objective value of any level. The result from such a system may be economically inadmissible. If the decision makers of the two levels are willing to find an efficient compromise solution, we propose a solution procedure which can generate effcient solutions, without finding the optimal solution in advance. When the near-optimal solution of the BLP problem is used as the reference point for finding the efficient solution, the result can be easily found during the decision process.