A nonmonotone GRASP

Authors: M De Santis P Festa G Liuzzi S Lucidi F Rinaldi

Publish Date: 2016/05/07

Volume: 8, Issue: 3, Pages: 271-309

PDF Link

Abstract

A greedy randomized adaptive search procedure GRASP is an iterative multistart metaheuristic for difficult combinatorial optimization problems Each GRASP iteration consists of two phases a construction phase in which a feasible solution is produced and a local search phase in which a local optimum in the neighborhood of the constructed solution is sought Repeated applications of the construction procedure yields different starting solutions for the local search and the best overall solution is kept as the result The GRASP local search applies iterative improvement until a locally optimal solution is found During this phase starting from the current solution an improving neighbor solution is accepted and considered as the new current solution In this paper we propose a variant of the GRASP framework that uses a new “nonmonotone” strategy to explore the neighborhood of the current solution We formally state the convergence of the nonmonotone local search to a locally optimal solution and illustrate the effectiveness of the resulting Nonmonotone GRASP on three classical hard combinatorial optimization problems the maximum cut problem MAXCUT the weighted maximum satisfiability problem MAXSAT and the quadratic assignment problem QAPIn this appendix we report the detailed tables related to the comparison between NMGRASP and the original version of GRASP for MAXCUT MAXSAT and QAP The first column of the three tables reports the name of the instance The remaining columns report for each of the two approaches the average CPU time Time the average number of iterations Iter the average objective function value Obj with the standard deviation in brackets and the best objective function value obtained over the ten runs Best Obj with the number of times the best value is obtained in bracketsFigure 10 depicts the empirical distributions of the random variable timetotargetsolutionvalue using as target values 2532 2293 2382 and 2932 for the instances g1250n G40 sg3dl142000mc and toruspm31550 respectively These values are the best objective function values found by the classical GRASP over 10 runs As we can see from the plots also in this case the NMGRASP is able to reach the target value in less than 100 s for all the runs On the other hand the classical GRASP failed to reach the target solution within the time limit in several runs especially for instances g1250n and G40By using instances g1250n G40 sg3dl142000mc and toruspm31550 we plot in Fig 11 the empirical distributions of the random variable timetotargetsolutionvalue using as target values 2556 2362 2420 and 2980 respectively These target values are the best cuts found by the NMGRASP over 10 runs In this case the classical GRASP failed to reach the target solution within the time limit for all runs and all instances On the contrary the NMGRASP is able to reach the target solution for all runs for instances g1250n and sg3dl142000mc

Keywords: