Speeding up continuous GRASP

Continuous GRASP (C-GRASP) is a stochastic local search metaheuristic for finding cost-efficient solutions to continuous global optimization problems subject to box constraints (Hirsch et al., 2007). Like a greedy randomized adaptive search procedure (GRASP), a C-GRASP is a multi-start procedure where a starting solution for local improvement is constructed in a greedy randomized fashion. In this paper, we describe several improvements that speed up the original C-GRASP and make it more robust. We compare the new C-GRASP with the original version as well as with other algorithms from the recent literature on a set of benchmark multimodal test functions whose global minima are known. Hart’s sequential stopping rule (1998) is implemented and C-GRASP is shown to converge on all test problems.     

Global optimization by continuous grasp

We introduce a novel global optimization method called Continuous GRASP (C-GRASP) which extends Feo and Resende’s greedy randomized adaptive search procedure (GRASP) from the domain of discrete optimization to that of continuous global optimization. This stochastic local search method is simple to implement, is widely applicable, and does not make use of derivative information, thus making it a well-suited approach for solving global optimization problems. We illustrate the effectiveness of the procedure on a set of standard test problems as well as two hard global optimization problems.     

A Python/C library for bound-constrained global optimization with continuous GRASP

This paper describes ${\texttt{libcgrpp}}$ , a GNU-style dynamic shared Python/C library of the continuous greedy randomized adaptive search procedure (C-GRASP) for bound constrained global optimization. C-GRASP is an extension of the GRASP metaheuristic (Feo and Resende, 1989) and has been used to solve unstable and nondifferentiable problems, as well as hard global optimization problems, such as chemical equilibrium systems and robot kinematics applications (Hirsch et al. in Optim lett 1:201–212, 2007). After a brief introduction to C-GRASP, we show how to download, install, configure, and use the library through an illustrative example.     

Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls

Metaheuristics are a class of approximate methods designed to solve hard combinatorial optimization problems arising within various different areas. The importance of metaheuristics results from their ability to continue the search beyond a local optimum so that near-optimal or optimal solutions are efficiently found. In order to solve the backhauling problem associated with mixed and simultaneous delivery and pick-ups, this paper presents a hybrid algorithm which is comprised of the two metaheuristics of tabu search and variable neighbourhood descent. The primary challenge associated with backhauling consists of creating routes in which vehicles are not only required to deliver goods, but also to perform pick-ups at customer locations. The problems associated with these two categories of problems, however, have received little attention in the literature to date. A set of examples taken from the literature with Euclidean cost matrices are presented. Finally, some numerical results are illustrated to show the effectiveness of the proposed approach.     

Adaptive and multi-mining versions of the DM-GRASP hybrid metaheuristic

Metaheuristics represent an important class of techniques to solve, approximately, hard combinatorial optimization problems for which the use of exact methods is impractical. Some researches have been combining machine learning techniques with metaheuristics to adaptively guide and improve the search for near optimal solutions. An example of such development is the DM-GRASP, a hybrid version of the Greedy Randomized Adaptative Search Procedures (GRASP) metaheuristic which incorporates a data mining process. In this hybrid proposal, after executing half of the total number of iterations, the data mining process extracts patterns from an elite set of sub-optimal solutions for the optimization problem. These patterns present characteristics of near optimal solutions and can be used to guide the following half GRASP iterations in the search through the solution space. In this work, we explore new versions of the DM-GRASP metaheuristic to experiment, not a single activation, but multiple and adaptive executions of the data mining process during the metaheuristic execution. We also applied the data mining technique into a reactive GRASP to show that a more sophisticated and not memoryless GRASP approach can also benefit from the use of this technique. In order to evaluate these new proposals, we adopted the server replication for reliable multicast problem since the best known results for this problem were obtained by GRASP and DM-GRASP implementations. The computational experiments, comparing traditional GRASP, DM-GRASP, and the new proposals, showed that multiple and adaptive executions of the data mining process can improve the results obtained by the DM-GRASP hybrid metaheuristic—the new proposals were able to find better results in less computational time for the reliable multicast problem.     

The GLOBAL optimization method revisited

The multistart clustering global optimization method called GLOBAL has been introduced in the 1980s for bound constrained global optimization problems with black-box type objective function. Since then the technological environment has been changed much. The present paper describes shortly the revisions and updates made on the involved algorithms to utilize the novel technologies, and to improve its reliability. We discuss in detail the results of the numerical comparison with the old version and with C-GRASP, a continuous version of the GRASP method. According to these findings, the new version of GLOBAL is both more reliable and more efficient than the old one, and it compares favorably with C-GRASP too.     

Solving systems of nonlinear equations with continuous GRASP

A method for finding all roots of a system of nonlinear equations is described. Our method makes use of C-GRASP, a recently proposed continuous global optimization heuristic. Given a nonlinear system, we solve a corresponding adaptively modified global optimization problem multiple times, each time using C-GRASP, with areas of repulsion around roots that have already been found. The heuristic makes no use of derivative information. We illustrate the approach using systems found in the literature.     

Tabu Search directed by direct search methods for nonlinear global optimization

In recent years, there has been a great deal of interest in metaheuristics in the optimization community. Tabu Search (TS) represents a popular class of metaheuristics. However, compared with other metaheuristics like genetic algorithm and simulated annealing, contributions of TS that deals with continuous problems are still very limited. In this paper, we introduce a continuous TS called Directed Tabu Search (DTS) method. In the DTS method, direct-search-based strategies are used to direct a tabu search. These strategies are based on the well-known Nelder–Mead method and a new pattern search procedure called adaptive pattern search. Moreover, we introduce a new tabu list conception with anti-cycling rules called Tabu Regions and Semi-Tabu Regions. In addition, Diversification and Intensification Search schemes are employed. Numerical results show that the proposed method is promising and produces high quality solutions.     

A GRASP for Coloring Sparse Graphs

We first present a literature review of heuristics and metaheuristics developed for the problem of coloring graphs. We then present a Greedy Randomized Adaptive Search Procedure (GRASP) for coloring sparse graphs. The procedure is tested on graphs of known chromatic number, as well as random graphs with edge probability 0.1 having from 50 to 500 vertices. Empirical results indicate that the proposed GRASP implementation compares favorably to classical heuristics and implementations of simulated annealing and tabu search. GRASP is also found to be competitive with a genetic algorithm that is considered one of the best currently available for graph coloring.     

Scatter search for the cutwidth minimization problem

The cutwidth minimization problem consists of finding a linear layout of a graph so that the maximum linear cut of edges is minimized. This NP-hard problem has applications in network scheduling, automatic graph drawing and information retrieval. We propose a heuristic method based on the Scatter Search (SS) methodology for finding approximate solutions to this optimization problem. This metaheuristic explores solution space by evolving a set of reference points. Our SS method is based on a GRASP constructive algorithm, a local search strategy based on insertion moves and voting-based combination methods. We also introduce a new measure to control the diversity in the search process. Empirical results with 252 previously reported instances indicate that the proposed procedure compares favorably to previous metaheuristics for this problem, such as Simulated Annealing and Evolutionary Path Relinking.     

The efficiency of indicator-based local search for multi-objective combinatorial optimisation problems

In the last few years, a significant number of multi-objective metaheuristics have been proposed in the literature in order to address real-world problems. Local search methods play a major role in many of these metaheuristic procedures. In this paper, we adapt a recent and popular indicator-based selection method proposed by Zitzler and Künzli in 2004, in order to define a population-based multi-objective local search. The proposed algorithm is designed in order to be easily adaptable, parameter independent and to have a high convergence rate. In order to evaluate the capacity of our algorithm to reach these goals, a large part of the paper is dedicated to experiments. Three combinatorial optimisation problems are tested: a flow shop problem, a ring star problem and a nurse scheduling problem. The experiments show that our algorithm can be applied with success to different types of multi-objective optimisation problems and that it outperforms some classical metaheuristics. Furthermore, the parameter sensitivity analysis enables us to provide some useful guidelines about how to set the parameters.     

Algorithms for single machine total tardiness scheduling with sequence dependent setups

We consider the problem of scheduling a single machine to minimize total tardiness with sequence dependent setup times. We present two algorithms, a problem space-based local search heuristic and a Greedy Randomized Adaptive Search Procedure (GRASP) for this problem. With respect to GRASP, our main contributions are—a new cost function in the construction phase, a new variation of Variable Neighborhood Search in the improvement phase, and Path Relinking using three different search neighborhoods. The problem space-based local search heuristic incorporates local search with respect to both the problem space and the solution space. We compare our algorithms with Simulated Annealing, Genetic Search, Pairwise Interchange, Branch and Bound and Ant Colony Search on a set of test problems from literature, showing that the algorithms perform very competitively.     

A novel metaheuristics approach for continuous global optimization

This paper proposes a novel metaheuristics approach to find the global optimum of continuous global optimization problems with box constraints. This approach combines the characteristics of modern metaheuristics such as scatter search (SS), genetic algorithms (GAs), and tabu search (TS) and named as hybrid scatter genetic tabu (HSGT) search. The development of the HSGT search, parameter settings, experimentation, and efficiency of the HSGT search are discussed. The HSGT has been tested against a simulated annealing algorithm, a GA under the name GENOCOP, and a modified version of a hybrid scatter genetic (HSG) search by using 19 well known test functions. Applications to Neural Network training are also examined. From the computational results, the HSGT search proved to be quite effective in identifying the global optimum solution which makes the HSGT search a promising approach to solve the general nonlinear optimization problem.     

GRASP heuristic with path-relinking for the multi-plant capacitated lot sizing problem

This paper addresses the independent multi-plant, multi-period, and multi-item capacitated lot sizing problem where transfers between the plants are allowed. This is an NP-hard combinatorial optimization problem and few solution methods have been proposed to solve it. We develop a GRASP (Greedy Randomized Adaptive Search Procedure) heuristic as well as a path-relinking intensification procedure to find cost-effective solutions for this problem. In addition, the proposed heuristics is used to solve some instances of the capacitated lot sizing problem with parallel machines. The results of the computational tests show that the proposed heuristics outperform other heuristics previously described in the literature. The results are confirmed by statistical tests.     

Desarrollo de un algoritmo de optimización global en colonias de hormigas con selección de región factible para espacios continuos

This study introduces a new algorithm for the ant colony optimization (ACO) method, which has been proposed to solve global optimization problems with continuous decision variables. This algorithm, namely ACO-FRS, involves a strategy for the selection of feasible regions during optimization search and it performs the exploration of the search space using a similar approach to that used by the ants during the search of food. Four variants of this algorithm have been tested in several benchmark problems and the results of this study have been compared with those reported in literature for other ACO-type methods for continuous spaces. Overall, the results show that the incorporation of the selection of feasible regions allows the performing of a global search to explore those regions with low level of pheromone, thus increasing the feasibility of ACO for finding the global optimal solution.     

无记忆非拟 Newton 算法的导出和全局收敛性

In this paper, a new class of memoryless non-quasi-Newton method for solving unconstrained optimization problems is proposed, and the global convergence of this method with inexact line search is proved. Furthermore, we propose a hybrid method that mixes both the memoryless non-quasi-Newton method and the memoryless Perry-Shanno quasi-Newton method. The global convergence of this hybrid memoryless method is proved under mild assumptions. The initial results show that these new methods are efficient for the given test problems. Especially the memoryless non-quasi-Newton method requires little storage and computation, so it is able to efficiently solve large scale optimization problems.     

Multiobjective GRASP with Path Relinking

In this paper we review and propose different adaptations of the GRASP metaheuristic to solve multiobjective combinatorial optimization problems. In particular, we describe several alternatives to specialize the construction and improvement components of GRASP when two or more objectives are considered. GRASP has been successfully coupled with Path Relinking for single-objective optimization. Moreover, we propose different hybridizations of GRASP and Path Relinking for multiobjective optimization. We apply the proposed GRASP with Path Relinking variants to two combinatorial optimization problems, the biobjective orienteering problem and the biobjective path dissimilarity problem. We report on empirical tests with 70 instances and 30 algorithms, that show that the proposed heuristics are competitive with the state-of-the-art methods for these problems.     

GRASP with path-relinking for the non-identical parallel machine scheduling problem with minimising total weighted completion times

In this work, we tackle the problem of scheduling a set of jobs on a set of non-identical parallel machines with the goal of minimising the total weighted completion times. GRASP is a multi-start method that consists of two phases: a solution construction phase, which randomly constructs a greedy solution, and an improvement phase, which uses that solution as an initial starting point. In the last few years, the GRASP methodology has arisen as a prospective metaheuristic approach to find high-quality solutions for several difficult problems in reasonable computational times. With the aim of providing additional results and insights along this line of research, this paper proposes a new GRASP model that combines the basic scheme with two significant elements that have been shown to be very successful in order to improve GRASP performance. These elements are path-relinking and evolutionary path-relinking. The benefits of our proposal in comparison to existing metaheuristics proposed in the literature are experimentally shown.     

Greedy Randomized Adaptive Search Procedures

Today, a variety of heuristic approaches are available to the operations research practitioner. One methodology that has a strong intuitive appeal, a prominent empirical track record, and is trivial to efficiently implement on parallel processors is GRASP (Greedy Randomized Adaptive Search Procedures). GRASP is an iterative randomized sampling technique in which each iteration provides a solution to the problem at hand. The incumbent solution over all GRASP iterations is kept as the final result. There are two phases within each GRASP iteration: the first intelligently constructs an initial solution via an adaptive randomized greedy function; the second applies a local search procedure to the constructed solution in hope of finding an improvement. In this paper, we define the various components comprising a GRASP and demonstrate, step by step, how to develop such heuristics for combinatorial optimization problems. Intuitive justifications for the observed empirical behavior of the methodology are discussed. The paper concludes with a brief literature review of GRASP implementations and mentions two industrial applications.     

The Global Convergence of Self-Scaling BFGS Algorithm with Nonmonotone Line Search for Unconstrained Nonconvex Optimization Problems

The self-scaling quasi-Newton method solves an unconstrained optimization problem by scaling the Hessian approximation matrix before it is updated at each iteration to avoid the possible large eigenvalues in the Hessian approximation matrices of the objective function. It has been proved in the literature that this method has the global and superlinear convergence when the objective function is convex （or even uniformly convex）. We propose to solve unconstrained nonconvex optimization problems by a self-scaling BFGS algorithm with nonmonotone linear search. Nonmonotone line search has been recognized in numerical practices as a competitive approach for solving large-scale nonlinear problems. We consider two different nonmonotone line search forms and study the global convergence of these nonmonotone self-scale BFGS algorithms. We prove that, under some weaker condition than that in the literature, both forms of the self-scaling BFGS algorithm are globally convergent for unconstrained nonconvex optimization problems.