A group-based search for solutions of the n-queens problem

The n-queens problem is a well-known problem in mathematics, yet a full search for n-queens solutions has been tackled until now using only simple algorithms (with the exception of the Rivin-Zabih algorithm). In this article, we discuss optimizations that mainly rely on group actions on the set of n-queens solutions. Most of our arguments deal with the case of toroidal queens; at the end, the application to the regular n-queens problem is discussed, and also the Rivin-Zabih algorithm.     

Simulated annealing for the unconstrained quadratic pseudo-Boolean function

In this paper, we develop a simulated annealing (SA) based heuristic for the unconstrained quadratic pseudo-Boolean function. An algorithm that solves the problem in O(n²) at each temperature of the cooling schedule is given. The performance of SA based heuristic is compared with existing bounding algorithms for this problem. Computational results and comparisons on several hundred test problems demonstrate the efficiency of our heuristic in terms of solution quality and computational time. A new set of hard test problems with their best solution is provided to facilitate future comparison.     

Comparing local search metaheuristics for the maximum diversity problem

The Maximum Diversity Problem (MDP) requires to extract a subset M of given cardinality from a set N, maximising the sum of the pair-wise diversities between the extracted elements. The MDP has recently been the subject of much research, and several sophisticated heuristics have been proposed to solve it. The present work compares four local search metaheuristics for the MDP, all based on the same Tabu Search procedure, with the aim to identify what additional elements provide the strongest improvement. The four metaheuristics are an Exploring Tabu Search, a Scatter Search, a Variable Neighbourhood Search and a simple Random Restart algorithm. All of them prove competitive with the best algorithms proposed in the literature. Quite surprisingly, the best ones are the simple Random Restart algorithm and a Variable Neighbourhood Search algorithm with an unusual parameter setting, which makes it quite close to random restart. Although this is probably related to the elementary structure of the MDP, it also suggests that, more often than expected, simpler algorithms might be better.     

Three new stochastic local search algorithms for continuous optimization problems

This paper introduces three new stochastic local search metaheuristics algorithms namely, the Best Performance Algorithm (BPA), the Iterative Best Performance Algorithm (IBPA) and the Largest Absolute Difference Algorithm (LADA). BPA and IBPA are based on the competitive nature of professional athletes, in them desiring to improve on their best recorded performances. LADA is modeled on calculating the absolute difference between two numbers. The performances of the algorithms have been tested on a large collection of benchmark unconstrained continuous optimization functions. They were benchmarked against two well-known local-search metaheuristics namely, Tabu Search (TS) and Simulated Annealing (SA). Results obtained show that each of the new algorithms delivers higher percentages of the best and mean function values found, compared to both TS and SA. The execution times of these new algorithms are also comparable. LADA gives the best performance in terms of execution time.     

A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem

Over the last decade, many metaheuristics have been applied to the flowshop scheduling problem, ranging from Simulated Annealing or Tabu Search to complex hybrid techniques. Some of these methods provide excellent effectiveness and efficiency at the expense of being utterly complicated. In fact, several published methods require substantial implementation efforts, exploit problem specific speed-up techniques that cannot be applied to slight variations of the original problem, and often re-implementations of these methods by other researchers produce results that are quite different from the original ones. In this work we present a new iterated greedy algorithm that applies two phases iteratively, named destruction, were some jobs are eliminated from the incumbent solution, and construction, where the eliminated jobs are reinserted into the sequence using the well known NEH construction heuristic. Optionally, a local search can be applied after the construction phase. Our iterated greedy algorithm is both very simple to implement and, as shown by experimental results, highly effective when compared to state-of-the-art methods.     

Finding maximin latin hypercube designs by Iterated Local Search heuristics

The maximin LHD problem calls for arranging N points in a k-dimensional grid so that no pair of points share a coordinate and the distance of the closest pair of points is as large as possible. In this paper we propose to tackle this problem by heuristic algorithms belonging to the Iterated Local Search (ILS) family and show through some computational experiments that the proposed algorithms compare very well with different heuristic approaches in the established literature.     

A Recovering Beam Search algorithm for the one-machine dynamic total completion time scheduling problem

This paper deals with the one-machine dynamic total completion time scheduling problem. This problem is known to be NP-hard in the strong sense. A polynomial time heuristic algorithm is proposed which applies the recently introduced Recovering Beam Search (RBS) approach. The algorithm is based on a beam search procedure with unitary beam width and includes a recovering subroutine that allows to overcome wrong decisions taken at higher levels of the beam search tree. It is shown that the total number of considered nodes is bounded by n where n is the jobsize. The proposed algorithm is able to solve in very short CPU time problems with up to 500 jobs outperforming the best state of the art heuristics.     

A morph-based simulated annealing heuristic for a modified bin-packing problem

This paper presents a local-search heuristic, based on the simulated annealing (SA) algorithm for a modified bin-packing problem (MBPP). The objective of the MBPP is to assign items of various sizes to a fixed number of bins, such that the sum-of-squared deviation (across all bins) from the target bin workload is minimized. This problem has a number of practical applications which include the assignment of computer jobs to processors, the assignment of projects to work teams, and infinite-loading machine scheduling problems. The SA-based heuristic we developed uses a morph-based search procedure when looking for better allocations. In a large computational study we evaluated 12 versions of this new heuristic, as well as two versions of a previously published SA-based heuristic that used a completely random search. The primary performance measure for this evaluation was the mean percent above the best known objective value (MPABKOV). Since the MPABKOV associated with the best version of the random-search SA heuristic was more than 290 times larger than that of the best version of the morph-based SA heuristic, we conclude that the morphing process is a significant enhancement to SA algorithms for these problems.     

An improved heuristic for the far from most strings problem

The Far From Most Strings Problem (FFMSP) asks for a string that is far from as many as possible of a given set of strings. All the input and the output strings are of the same length, and two strings are far if their Hamming distance is greater than or equal to a given threshold. FFMSP belongs to the class of sequence consensus problems which have applications in molecular biology, amongst others. FFMSP is NP-hard. It does not admit a constant-ratio approximation either, unless P=NP. In the last few years, heuristic and metaheuristic algorithms have been proposed for the problem, which use local search and require a heuristic, also called an evaluation function, to evaluate candidate solutions during local search. The heuristic function used, for this purpose, in these algorithms is the problem’s objective function. However, since many candidate solutions can be of the same objective value, the resulting search landscape includes many points which correspond to local maxima. In this paper, we devise a new heuristic function to evaluate candidate solutions. We then incorporate the proposed heuristic function within a Greedy Randomized Adaptive Search Procedure (GRASP), a metaheuristic originally proposed for the problem by Festa. The resulting algorithm outperforms state-of-the-art with respect to solution quality, in some cases by orders of magnitude, on both random and real data in our experiments. The results indicate that the number of local optima is considerably reduced using the proposed heuristic.     

Comparative analysis of three metaheuristics for short-term open pit block sequencing

This paper presents the application of simulated annealing (SA), Tabu search (TS) and hybrid TS–SA to solve a real-world mining optimisation problem called open pit block sequencing (OPBS). The OPBS seeks the optimum extraction sequences under a variety of geological and technical constraints over short-term horizons. As industry-scale OPBS instances are intractable for standard mixed integer programming (MIP) solvers, SA, TS and hybrid TS–SA are developed to solve the OPBS problem. MIP exact solution is also combined with the proposed metaheuristics to polish solutions in feasible neighbourhood moves. Extensive sensitivity analysis is conducted to analyse the characteristics and determine the optimum sets of values of the proposed metaheuristics algorithms’ parameters. Computational experiments show that the proposed algorithms are satisfactory for solving the OPBS problem. Additionally, this comparative study shows that the hybrid TS–SA is superior to SA or TS in solving the OPBS problem in several aspects.     

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.     

Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem

The unconstrained binary quadratic programming problem (BQP) is known to be NP-hard and has many practical applications. This paper presents a simulated annealing (SA)-based heuristic for the BQP. The new SA heuristic for the BQP is based on a simple (1-opt) local search heuristic and designed with a simple cooling schedule, but the multiple annealing processes are adopted. To show practical performances of the SA, we test on publicly available benchmark instances of large size ranging from 500 to 2500 variables and compare them with other heuristics such as multi-start local search, the previous SA, tabu search, and genetic algorithm incorporating the 1-opt local search. Computational results indicate that our SA leads to high-quality solutions with short times and is more effective than the competitors particularly for the largest benchmark set. Furthermore, the values of new best-known solutions found by the SA for several large instances are also reported.     

混合启发式算法求解多配送人员车辆路径问题

为解决带时间窗和多配送人员的车辆路径问题,本文采用混合启发式算法对其进行求解。该算法主要由整数规划重组、局部搜索算法和模拟退火算法三部分组成。在算法中,整数规划重组有效提高了解的质量,局部搜索算法和模拟退火算法保证了算法搜索的深入性和广泛性。通过与CPLEX和禁忌搜索算法进行对比,证实了混合启发式算法实用价值更高,求解效果更好。     

Single machine earliness and tardiness scheduling

We examine the problem of scheduling a given set of jobs on a single machine to minimize total early and tardy costs without considering machine idle time. We decompose the problem into two subproblems with a simpler structure. Then the lower bound of the problem is the sum of the lower bounds of two subproblems. A lower bound of each subproblem is obtained by Lagrangian relaxation. Rather than using the well-known subgradient optimization approach, we develop two efficient multiplier adjustment procedures with complexity O(nlog n) to solve two Lagrangian dual subproblems. A branch-and-bound algorithm based on the two efficient procedures is presented, and is used to solve problems with up to 50 jobs, hence doubling the size of problems that can be solved by existing branch-and-bound algorithms. We also propose a heuristic procedure based on the neighborhood search approach. The computational results for problems with up to 3 000 jobs show that the heuristic procedure performs much better than known heuristics for this problem in terms of both solution efficiency and quality. In addition, the results establish the effectiveness of the heuristic procedure in solving realistic problems to optimality or near optimality.     

Heuristics for a coupled-operation scheduling problem

In this paper, we study a strongly NP-hard single machine scheduling problem in which each job consists of two operations that are separated by a time delay which lies within a specified range. The objective is to minimize the makespan. Determining the feasibility and, if applicable, makespan of any proposed permutation of the operations is non-trivial, requiring a longest path algorithm with O(n²) complexity for each permutation. Several heuristic algorithms are proposed: a deterministic and randomized construction algorithm, three descent algorithms and two reactive tabu search algorithms. The local search algorithms use a first improvement neighbourhood and mainly visit only feasible solutions within the search space. Results of extensive computational tests are reported, showing that the heavy computational burden of testing potential solutions renders the local search algorithms uncompetitive in comparison to the construction algorithms. The iterated descent algorithm performs least well.     

Weighted heuristic search in networks

The evaluation function used in heuristic search algorithms commonly has the form , where n is any node in the network, is the cost of the best path currently known from the start node to n, and is the heuristic estimate associated with node n. A more general form of the evaluation function can be obtained by incorporating a weighting parameter α:

Full-size image

, where 0≤ α ≤1. Such an evaluation function has been used in some recent experimental investigations of the 8-puzzle problem. In this paper a theoretical framework is developed for the analysis of the worst-case behavior of weighted heuristic search algorithms. A new algorithm is proposed whose worst-case performance characteristics are greatly superior to those of earlier algorithms in terms of the following two measures: how good is the solution, and how many nodes are expanded. Bounds are also obtained on some useful network parameters for both general and special types of heuristic estimate functions.     

Combining the Scalability of Local Search with the Pruning Techniques of Systematic Search

Systematic backtracking is used in many constraint solvers and combinatorial optimisation algorithms. It is complete and can be combined with powerful search pruning techniques such as branch-and-bound, constraint propagation and dynamic variable ordering. However, it often scales poorly to large problems. Local search is incomplete, and has the additional drawback that it cannot exploit pruning techniques, making it uncompetitive on some problems. Nevertheless its scalability makes it superior for many large applications. This paper describes a hybrid approach called Incomplete Dynamic Backtracking, a very flexible form of backtracking that sacrifices completeness to achieve the scalability of local search. It is combined with forward checking and dynamic variable ordering, and evaluated on three combinatorial problems: on the n-queens problem it out-performs the best local search algorithms; it finds large optimal Golomb rulers much more quickly than a constraint-based backtracker, and better rulers than a genetic algorithm; and on benchmark graphs it finds larger cliques than almost all other tested algorithms. We argue that this form of backtracking is actually local search in a space of consistent partial assignments, offering a generic way of combining standard pruning techniques with local search.     

An empirical investigation on parallelization strategies for Scatter Search

As other metaheuristics, Scatter Search can gain from a parallel implementation. However, it is not clear beforehand which of the possible alternative parallelization strategies is more effective. To address this question, it has been selected as a test bed for empirical testing a classical combinatorial optimization problem, namely 0–1 knapsack problem, for which the sequential application of Scatter Search is well known. Two phases or groups of steps in the Scatter Search template have been identified as natural candidates for parallelization and several ways of carrying out that parallelization are proposed. An extensive experimental analysis involving 18 different parallel algorithms has been carried out testing the combinations of these alternative parallelization strategies on a battery of large random instances generated using a public code from the literature. The interpretation of the ANOVA results gives cues about the significance of the alternatives used in each phase and about the effect of the dynamic (vs. static) updating of the RefSet. A low average efficiency has been observed, although it has to be taken into account that, due to the termination condition used, not all algorithms tested carry out the same number of iterations.     

Win–win match using a genetic algorithm

As the service industries grow, tasks are not directly assigned to the skills but the knowledge of the worker which is to be valued more in finding the best match. The problem becomes difficult mainly because the match has to be seen with the objectives of both sides. Assignment methods fail to respond to a multi-objective, multi-constraint problem with complicated match; whereas, metaheuristics is preferable based on computational simplicity. A conditional genetic algorithm is developed in this study to propose both global and composite match using different fitness functions. This algorithm kills the infeasibilities to achieve the maximum number of matches. The proposed algorithm is applied on an academic problem of multi-alternative candidates and multi-alternative tasks (m × n problem) in two stages. In the first stage, four different fitness functions are evaluated and in the second stage using one of the fitness functions global and composite matching have been compared. The achievements will contribute both to the academic and business world.     

Density Based Problem Space Search for the Capacitated Clustering p-Median Problem

In the Capacitated Clustering Problem (CCP), a given set of n weighted points is to be partitioned into p clusters such that, the total weight of the points in each cluster does not exceed a given cluster capacity. The objective is to find a set of p centers that minimises total scatter of points allocated to them. In this paper a new constructive method, a general framework to improve the performance of greedy constructive heuristics, and a problem space search procedure for the CCP are proposed. The constructive heuristic finds patterns of natural subgrouping in the input data using concept of density of points. Elements of adaptive computation and periodic construction–deconstruction concepts are implemented within the constructive heuristic to develop a general framework for building efficient heuristics. The problem-space search procedure is based on perturbations of input data for which a controlled perturbation strategy, intensification and diversification strategies are developed. The implemented algorithms are compared with existing methods on a standard set of bench-marks and on new sets of large-sized instances. The results illustrate the strengths of our algorithms in terms of solution quality and computational efficiency.