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.     

A nonmonotone filter method for nonlinear optimization

We propose a new nonmonotone filter method to promote global and fast local convergence for sequential quadratic programming algorithms. Our method uses two filters: a standard, global g-filter for global convergence, and a local nonmonotone l-filter that allows us to establish fast local convergence. We show how to switch between the two filters efficiently, and we prove global and superlinear local convergence. A special feature of the proposed method is that it does not require second-order correction steps. We present preliminary numerical results comparing our implementation with a classical filter SQP method.     

A GRASP for the biquadratic assignment problem

The biquadratic assignment problem (BiQAP) is a generalization of the quadratic assignment problem (QAP). It is a nonlinear integer programming problem where the objective function is a fourth degree multivariable polynomial and the feasible domain is the assignment polytope. BiQAP problems appear in VLSI synthesis. Due to the difficulty of this problem, only heuristic solution approaches have been proposed. In this paper, we propose a new heuristic for the BiQAP, a greedy randomized adaptive search procedure (GRASP). Computational results on instances described in the literature indicate that this procedure consistently finds better solutions than previously described algorithms.     

A nonmonotone supermemory gradient algorithm for unconstrained optimization

This paper presents a nonmonotone supermemory gradient algorithm for unconstrained optimization problems. At each iteration, this proposed method sufficiently uses the previous multi-step iterative information and avoids the storage and computation of matrices associated with the Hessian of objective functions, thus it is suitable to solve large-scale optimization problems and can converge stably. Under some assumptions, the convergence properties of the proposed algorithm are analyzed. Numerical results are also reported to show the efficiency of this proposed method.     

A nonmonotone PSB algorithm for solving unconstrained optimization

PSB (Powell-Symmetric-Broyden) algorithm is a very important algorithm and has been extensively used in trust region methods. However, there are few studies on the line search type PSB algorithm. The primary reason is that the direction generated by this class of algorithms is not necessarily a descent direction of the objective function. In this paper, by combining a nonmonotone line search technique with the PSB method, we propose a nonmonotone PSB algorithm for solving unconstrained optimization. Under proper conditions, we establish global convergence and superlinear convergence of the proposed algorithm. At the same time we verify the efficiency of the proposed algorithm by some numerical experiments.     

A derivative-free nonmonotone line-search technique for unconstrained optimization

A tolerant derivative–free nonmonotone line-search technique is proposed and analyzed. Several consecutive increases in the objective function and also nondescent directions are admitted for unconstrained minimization. To exemplify the power of this new line search we describe a direct search algorithm in which the directions are chosen randomly. The convergence properties of this random method rely exclusively on the line-search technique. We present numerical experiments, to illustrate the advantages of using a derivative-free nonmonotone globalization strategy, with approximated-gradient type methods and also with the inverse SR1 update that could produce nondescent directions. In all cases we use a local variation finite differences approximation to the gradient.     

A GRASP metaheuristic for humanitarian aid distribution

Large scale disasters, natural or human-made, have huge consequences on people and infrastructures. After a disaster strikes, the distribution of humanitarian aid to the population affected is one of the main operations to be carried out, and several crucial decisions must be made in a short time. This paper addresses a last-mile distribution problem in disaster relief operations, under insecure and uncertain conditions. A model is presented that takes into account the cost and time of operation, the security and reliability of the routes, and the equity of aid handed out. The output of the model consists of a detailed set of itineraries that can be used to build an implementable distribution plan. Given its high complexity, the resulting problem is solved using a multi-criteria metaheuristic approach. In particular, a constructive algorithm and a GRASP based metaheuristic are developed, which are tested in a case study based on the 2010 Haiti earthquake.     

A nonmonotone approximate sequence algorithm for unconstrained nonlinear optimization

A new nonmonotone algorithm is proposed and analyzed for unconstrained nonlinear optimization. The nonmonotone techniques applied in this algorithm are based on the estimate sequence proposed by Nesterov (Introductory Lectures on Convex Optimization: A Basic Course, 2004) for convex optimization. Under proper assumptions, global convergence of this algorithm is established for minimizing general nonlinear objective function with Lipschitz continuous derivatives. For convex objective function, this algorithm maintains the optimal convergence rate of convex optimization. In numerical experiments, this algorithm is specified by employing safe-guarded nonlinear conjugate gradient search directions. Numerical results show the nonmonotone algorithm performs significantly better than the corresponding monotone algorithm for solving the unconstrained optimization problems in the CUTEr (Bongartz et al. in ACM Trans. Math. Softw. 21:123–160, 1995) library.     

A nonmonotone Jacobian smoothing inexact Newton method for NCP

In this paper we propose Jacobian smoothing inexact Newton method for nonlinear complementarity problems (NCP) with derivative-free nonmonotone line search. This nonmonotone line search technique ensures globalization and is a combination of Grippo-Lampariello-Lucidi (GLL) and Li-Fukushima (LF) strategies, with the aim to take into account their advantages. The method is based on very well known Fischer-Burmeister reformulation of NCP and its smoothing Kanzow’s approximation. The mixed Newton equation, which combines the semismooth function with the Jacobian of its smooth operator, is solved approximately in every iteration, so the method belongs to the class of Jacobian smoothing inexact Newton methods. The inexact search direction is not in general a descent direction and this is the reason why nonmonotone scheme is used for globalization. Global convergence and local superlinear convergence of method are proved. Numerical performances are also analyzed and point out that high level of nonmonotonicity of this line search rule enables robust and efficient method.     

A nonmonotone smoothing Newton method for circular cone programming

The circular cone programming (CCP) problem is to minimize or maximize a linear function over the intersection of an affine space with the Cartesian product of circular cones. In this paper, we study nondegeneracy and strict complementarity for the CCP, and present a nonmonotone smoothing Newton method for solving the CCP. We reformulate the CCP as a second-order cone programming (SOCP) problem using the algebraic relation between the circular cone and the second-order cone. Then based on a one parametric class of smoothing functions for the SOCP, a smoothing Newton method is developed for the CCP by adopting a new nonmonotone line search scheme. Without restrictions regarding its starting point, our algorithm solves one linear system of equations approximately and performs one line search at each iteration. Under mild assumptions, our algorithm is shown to possess global and local quadratic convergence properties. Some preliminary numerical results illustrate that our nonmonotone smoothing Newton method is promising for solving the CCP.     

A quasi-discrete Newton algorithm with a nonmonotone stabilization technique

In this paper, we define an unconstrained optimization algorithm employing only first-order derivatives, in which a nonmonotone stabilization technique is used in conjunction with a quasidiscrete Newton method for the computation of the search direction. Global and superlinear convergence is proved, and numerical results are reported.     

A GRASP heuristic for the manufacturing cell formation problem

In this work, we address the Manufacturing Cell Formation Problem (MCFP). Cellular Manufacturing is a production strategy that has emerged to reduce materials handling and set up times in order to reduce lead times in production systems and to improve customer??s service levels while reducing costs. We propose a GRASP heuristic to obtain lower bounds for the optimal solution of the problem. To evaluate the performance of the proposed method, we test the heuristic with different instances from the literature and compare the results obtained with those provided by other heuristic methods from the literature. According to the obtained results, the proposed GRASP procedure provides good quality lower bounds with reasonable computational effort.     

A new nonmonotone line search technique for unconstrained optimization

In this paper, we propose a new nonmonotone line search technique for unconstrained optimization problems. By using this new technique, we establish the global convergence under conditions weaker than those of the existed nonmonotone line search techniques.     

A class of nonmonotone stabilization methods in unconstrained optimization

Summary This paper deals with the solution of smooth unconstrained minimization problems by Newton-type methods whose global convergence is enforced by means of a nonmonotone stabilization strategy. In particular, a stabilization scheme is analyzed, which includes different kinds of relaxation of the descent requirements. An extensive numerical experimentation is reported.     

A reactive GRASP with path relinking for capacitated clustering

This paper presents a greedy randomized adaptive search procedure (GRASP) coupled with path relinking (PR) to solve the problem of clustering n nodes in a graph into p clusters. The objective is to maximize the sum of the edge weights within each cluster such that the sum of the corresponding node weights does not exceed a fixed capacity. In phase I, both a heaviest weight edge (HWE) algorithm and a constrained minimum cut algorithm are used to select seeds for initializing the p clusters. Feasible solutions are obtained with the help of a self-adjusting restricted candidate list that sequentially guides the assignment of the remaining nodes. At each major GRASP iteration, the list length is randomly set based on a probability density function that is updated dynamically to reflect the solution quality realized in past iterations. In phase II, three neighborhoods, each defined by common edge and node swaps, are explored to attain local optimality. The following exploration strategies are investigated: cyclic neighborhood search, variable neighborhood descent, and randomized variable neighborhood descent (RVND). The best solutions found are stored in an elite pool.     

A GRASP algorithm for constrained two-dimensional non-guillotine cutting problems

This paper presents a greedy randomized adaptive search procedure (GRASP) for the constrained two-dimensional non-guillotine cutting problem, the problem of cutting the rectangular pieces from a large rectangle so as to maximize the value of the pieces cut. We investigate several strategies for the constructive and improvement phases and several choices for critical search parameters. We perform extensive computational experiments with well-known instances previously reported, first to select the best alternatives and then to compare the efficiency of our algorithm with other procedures.     

A nonmonotone trust-region method of conic model for unconstrained optimization

In this paper, we present a nonmonotone trust-region method of conic model for unconstrained optimization. The new method combines a new trust-region subproblem of conic model proposed in [Y. Ji, S.J. Qu, Y.J. Wang, H.M. Li, A conic trust-region method for optimization with nonlinear equality and inequality 4 constrains via active-set strategy, Appl. Math. Comput. 183 (2006) 217–231] with a nonmonotone technique for solving unconstrained optimization. The local and global convergence properties are proved under reasonable assumptions. Numerical experiments are conducted to compare this method with the method of [Y. Ji, S.J. Qu, Y.J. Wang, H.M. Li, A conic trust-region method for optimization with nonlinear equality and inequality 4 constrains via active-set strategy, Appl. Math. Comput. 183 (2006) 217–231].     

Variational inequalities with nonmonotone operators

In this paper, existence results on variational inequalities and generalized variational inequalities for some nonmonotone operators over closed convex subsets of a real reflexive Banach space are proved. In particular, some surjectivity results and applications to complementarity and generalized complementarity problems are given.This work was partially supported by the National Science Council of the Republic of China under Contracts NSC 81-0208-M-007-34 and NSC 82-0208-M-110-023.     

A modified nonmonotone BFGS algorithm for solving smooth nonlinear equations

In this paper, a modified nonmonotone BFGS algorithm is developed for solving a smooth system of nonlinear equations. Different from the existent techniques of nonmonotone line search, the value of an algorithmic parameter controlling the magnitude of nonmonotonicity is updated at each iteration by the known information of the system of nonlinear equations such that the numerical performance of the developed algorithm is improved. Under some suitable assumptions, the global convergence of the algorithm is established for solving a generic nonlinear system of equations. Implementing the algorithm to solve some benchmark test problems, the obtained numerical results demonstrate that it is more effective than some similar algorithms available in the literature.     

A modified Solodov-Svaiter method for solving nonmonotone variational inequality problems

Numerical Algorithms - In a very interesting paper (SIAM J. Control Optim. 37(3): 765–776, 1999), Solodov and Svaiter introduced an effective projection algorithm with linesearch for finding...