Tabu search and GRASP for the maximum diversity problem

In this paper, we develop new heuristic procedures for the maximum diversity problem (MDP). This NP-hard problem has a significant number of practical applications such as environmental balance, telecommunication services or genetic engineering. The proposed algorithm is based on the tabu search methodology and incorporates memory structures for both construction and improvement. Although proposed in seminal tabu search papers, memory-based constructions have often been implemented in naïve ways that disregard important elements of the fundamental tabu search proposals. We will compare our tabu search construction with a memory-less design and with previous algorithms recently developed for this problem. The constructive method can be coupled with a local search procedure or a short-term tabu search for improved outcomes. Extensive computational experiments with medium and large instances show that the proposed procedure outperforms the best heuristics reported in the literature within short computational times.     

New heuristics for the maximum diversity problem

The maximum diversity problem (MDP) consists of identifying, in a population, a subset of elements, characterized by a set of attributes, that present the most diverse characteristics among the elements of the subset. The identification of such solution is an NP-hard problem. Some heuristics are available to obtain approximate solutions for this problem. In this paper, we propose different GRASP heuristics for the MDP, using distinct construction procedures and including a path-relinking technique. Performance comparison among related work and the proposed heuristics is provided. Experimental results show that the new GRASP heuristics are quite robust and are able to find high-quality solutions in reasonable computational times. G.C. Silva’s work sponsored by CAPES MSc scholarship. L.S. Ochi’s work sponsored by CNPq research grants 304103/2003-9 and 550059/2005-9. S.L. Martins’s work sponsored by CNPq research grant 475124/03-0. A. Plastino’s work sponsored by CNPq research grants 300879/00-8 and 475124/03-0.     

Multi-armed bandit-based hyper-heuristics for combinatorial optimization problems

There are significant research opportunities in the integration of Machine Learning (ML) methods and Combinatorial Optimization Problems (COPs). In this work, we focus on metaheuristics to solve COPs that have an important learning component. These algorithms must explore a solution space and learn from the information they obtain in order to find high-quality solutions. Among the metaheuristics, we study Hyper-Heuristics (HHs), algorithms that, given a number of low-level heuristics, iteratively select and apply heuristics to a solution. The HH we consider has a Markov model to produce sequences of low-level heuristics, which we combine with a Multi-Armed Bandit Problem (MAB)-based method to learn its parameters. This work proposes several improvements to the HH metaheuristic that yields a better learning for solving problem instances. Specifically, this is the first work in HHs to present Exponential Weights for Exploration and Exploitation (EXP3) as a learning method, an algorithm that is able to deal with adversarial settings. We also present a case study for the Vehicle Routing Problem with Time Windows (VRPTW), for which we include a list of low-level heuristics that have been proposed in the literature. We show that our algorithms can handle a large and diverse list of heuristics, illustrating that they can be easily configured to solve COPs of different nature. The computational results indicate that our algorithms are competitive methods for the VRPTW (2.16% gap on average with respect to the best known solutions), demonstrating the potential of these algorithms to solve COPs. Finally, we show how algorithms can even detect low-level heuristics that do not contribute to finding better solutions to the problem.     

Revisiting dynamic programming for finding optimal subtrees in trees

In this paper we revisit an existing dynamic programming algorithm for finding optimal subtrees in edge weighted trees. This algorithm was sketched by Maffioli in a technical report in 1991. First, we adapt this algorithm for the application to trees that can have both node and edge weights. Second, we extend the algorithm such that it does not only deliver the values of optimal trees, but also the trees themselves. Finally, we use our extended algorithm for developing heuristics for the k-cardinality tree problem in undirected graphs G with node and edge weights. This NP-hard problem consists of finding in the given graph a tree with exactly k edges such that the sum of the node and the edge weights is minimal. In order to show the usefulness of our heuristics we conduct an extensive computational analysis that concerns most of the existing problem instances. Our results show that with growing problem size the proposed heuristics reach the performance of state-of-the-art metaheuristics. Therefore, this study can be seen as a cautious note on the scaling of metaheuristics.     

A comprehensive review and evaluation of permutation flowshop heuristics

In this work we present a review and comparative evaluation of heuristics and metaheuristics for the well-known permutation flowshop problem with the makespan criterion. A number of reviews and evaluations have already been proposed. However, the evaluations do not include the latest heuristics available and there is still no comparison of metaheuristics. Furthermore, since no common benchmarks and computing platforms are used, the results cannot be generalised. We propose a comparison of 25 methods, ranging from the classical Johnson's algorithm or dispatching rules to the most recent metaheuristics, including tabu search, simulated annealing, genetic algorithms, iterated local search and hybrid techniques. For the evaluation we use the standard test of Taillard [Eur. J. Operation. Res. 64 (1993) 278] composed of 120 instances of different sizes. In the evaluations we use the experimental design approach to obtain valid conclusions on the effectiveness and efficiency of the different methods tested.     

Iterated greedy for the maximum diversity problem

The problem of choosing a subset of elements with maximum diversity from a given set is known as the maximum diversity problem. Many algorithms and methods have been proposed for this hard combinatorial problem, including several highly sophisticated procedures. By contrast, in this paper we present a simple iterated greedy metaheuristic that generates a sequence of solutions by iterating over a greedy construction heuristic using destruction and construction phases. Extensive computational experiments reveal that the proposed algorithm is highly effective as compared to the best-so-far metaheuristics for the problem under consideration.     

Competitive genetic algorithms for the open-shop scheduling problem

For more than two machines, and when preemption is forbidden, the computation of minimum makespan schedules for the open-shop problem is NP-hard. Compared to the flow-shop and the job-shop, the open-shop has free job routes which lead to a much larger solution space, to smaller gaps between the optimal makespan and the lower bounds, and to disappointing results for the algorithms based on the disjunctive graph model. For instance, the best existing branch and bound method cannot solve some 7 ×7 hard instances to optimality, and all published metaheuristics (working by reversing some disjunctions already fixed) do not better than some greedy or steepest-descent heuristics which need a much smaller computational effort. In this context, the intrinsic parallelism of genetic algorithms (GAs) seems well adapted, for detecting global optima disseminated among many quasi-optimal schedules. This paper presents several GAs for the open-shop problem. It is shown that even simple and fast versions can compete with the best known heuristics and metaheuristics, thanks to two key-features: a population in which each individual has a distinct makespan, and a special procedure which reorders every new chromosome. Using problem-specific heuristics, it is possible to design more powerful GAs which give excellent results, even on the hardest benchmarks of the literature: for instance, all hard open instances from Taillard are broken, except one for which the best known solution is improved.     

A benchmark library and a comparison of heuristic methods for the linear ordering problem

The linear ordering problem consists of finding an acyclic tournament in a complete weighted digraph of maximum weight. It is one of the classical NP-hard combinatorial optimization problems. This paper surveys a collection of heuristics and metaheuristic algorithms for finding near-optimal solutions and reports about extensive computational experiments with them. We also present the new benchmark library LOLIB which includes all instances previously used for this problem as well as new ones.     

An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem

The well-known Shortest Path problem (SP) consists in finding a shortest path from a source to a destination such that the total cost is minimized. The SP models practical and theoretical problems. However, several shortest path applications rely on uncertain data. The Robust Shortest Path problem (RSP) is a generalization of SP. In the former, the cost of each arc is defined by an interval of possible values for the arc cost. The objective is to minimize the maximum relative regret of the path from the source to the destination. This problem is known as the minmax relative regret RSP and it is NP-Hard. We propose a mixed integer linear programming formulation for this problem. The CPLEX branch-and-bound algorithm based on this formulation is able to find optimal solutions for all instances with 100 nodes, and has an average gap of 17 % on the instances with up to 1,500 nodes. We also develop heuristics with emphasis on providing efficient and scalable methods for solving large instances for the minmax relative regret RSP, based on Pilot method and random-key genetic algorithms. To the best of our knowledge, this is the first work to propose a linear formulation, an exact algorithm and metaheuristics for the minmax relative regret RSP.     

Using Genetic Algorithms and Heuristics for Job Shop Scheduling with Sequence-Dependent Setup Times

In this work a new heuristic solution technique for the Resource-Constrained Project Scheduling Problem (RCPSP) is proposed. This technique is a hybrid multi-pass method that combines random sampling procedures with a backward–forward method. The impact of each component of the algorithm is evaluated through a step-wise computational analysis which in addition permits the value of their parameters to be specified. Furthermore, the performance of the new technique is evaluated against the best currently available heuristics using a well known set of instances. The results obtained point out that the new technique greatly outperforms both the heuristics and metaheuristics currently available for the RCPSP being thus competitive with the best heuristic solution techniques for this problem.     

A two-phase tabu search based evolutionary algorithm for the maximum diversity problem

In this paper, we study the maximum diversity problem (MDP) which is equivalent to the quadratic unconstrained binary optimization (QUBO) problem with cardinality constraint. The MDP aims to select a subset of elements with given cardinality such that the sum of pairwise distances between any two elements in the selected subset is maximized. For solving this computationally challenging problem, we propose a two-phase tabu search based evolutionary algorithm (TPTS/EA), which integrates several distinguishing features to ensure the diversity and the quality of the evolution, such as a two-phase tabu search algorithm which consists of a dynamic candidate list (DCL) strategy-based traditional tabu search in the first phase and a solution-based tabu search procedure to refine the search in the second phase, and two path-relinking based recombination operators to generate new offspring solutions. Tested on three sets of totally 140 public instances in the literature, the study demonstrates the efficacy of the proposed TPTS/EA algorithm in terms of both solution quality and computational efficiency. Specifically, our proposed TPTS/EA algorithm is able to improve the previous best known results for 2 instances, while matching the previous best-known solutions for 130 instances. We also provide experimental evidences to highlight the beneficial effect of several important components in our TPTS/EA algorithm.     

A hybrid scatter search/electromagnetism meta-heuristic for project scheduling

In the last few decades, several effective algorithms for solving the resource-constrained project scheduling problem have been proposed. However, the challenging nature of this problem, summarised in its strongly NP-hard status, restricts the effectiveness of exact optimisation to relatively small instances. In this paper, we present a new meta-heuristic for this problem, able to provide near-optimal heuristic solutions for relatively large instances. The procedure combines elements from scatter search, a generic population-based evolutionary search method, and from a recently introduced heuristic method for the optimisation of unconstrained continuous functions based on an analogy with electromagnetism theory. We present computational experiments on standard benchmark datasets, compare the results with current state-of-the-art heuristics, and show that the procedure is capable of producing consistently good results for challenging instances of the resource-constrained project scheduling problem. We also demonstrate that the algorithm outperforms state-of-the-art existing heuristics.     

Solving a multicoloring problem with overlaps using integer programming

This paper presents a new generalization of the graph multicoloring problem. We propose a Branch-and-Cut algorithm based on a new integer programming formulation. The cuts used are valid inequalities that we could identify to the polytope associated with the model. The Branch-and-Cut system includes separation heuristics for the valid inequalities, specific initial and primal heuristics, branching and pruning rules. We report on computational experience with random instances.     

Experimental analysis of heuristics for the bottleneck traveling salesman problem

In this paper we develop efficient heuristic algorithms to solve the bottleneck traveling salesman problem (BTSP). Results of extensive computational experiments are reported. Our heuristics produced optimal solutions for all the test problems considered from TSPLIB, JM-instances, National TSP instances, and VLSI TSP instances in very reasonable running time. We also conducted experiments with specially constructed ‘hard’ instances of the BTSP that produced optimal solutions for all but seven problems. Some fast construction heuristics are also discussed. Our algorithms could easily be modified to solve related problems such as the maximum scatter TSP and testing hamiltonicity of a graph.     

An empirical study of hyperheuristics for managing very large sets of low level heuristics

Hyperheuristics give us the appealing possibility of abstracting the solution method from the problem, since our hyperheuristic, at each decision point, chooses between different low level heuristics rather than different solutions as is usually the case for metaheuristics. By assembling low level heuristics from parameterised components we may create hundreds or thousands of low level heuristics, and there is increasing evidence that this is effective in dealing with every eventuality that may arise when solving different combinatorial optimisation problem instances since at each iteration the solution landscape is amenable to at least one of the low level heuristics. However, the large number of low level heuristics means that the hyperheuristic has to intelligently select the correct low level heuristic to use, to make best use of available CPU time. This paper empirically investigates several hyperheuristics designed for large collections of low level heuristics and adapts other hyperheuristics from the literature to cope with these large sets of low level heuristics on a difficult real-world workforce scheduling problem. In the process we empirically investigate a wide range of approaches for setting tabu tenure in hyperheuristic methods, for a complex real-world problem. The results show that the hyperheuristic methods described provide a good way to trade off CPU time and solution quality.     

Classical and new heuristics for the open-shop problem: A computational evaluation

We study the problem of constructing minimum makespan schedules for the Open-Shop problem. This paper presents two new heuristics: the first one is a list scheduling algorithm with two priorities. The second is based on the construction of matchings in a bipartite graph. We develop several versions of these two heuristics. A computational evaluation shows that around 90% of randomly generated instances are solvable optimally, whereas classical (list scheduling) heuristics achieve less than 20% on average. Therefore, our algorithms make most Open-Shop instances easy to solve in practice, and this raises the problem of generating hard instances. We extend the evaluation to two kinds of such instances: the results are not so good, but remain better than classical heuristics.     

A tour construction heuristic for the travelling salesman problem

The tour construction heuristic that generates initial tours for the tour improvement heuristics plays an important role in solving the travelling salesman problem (TSP). With the help of an effective tour construction heuristic, the performance of a heuristic can be improved. In this study we present a new tour construction algorithm, the construction priority (CP). We incorporate the performance of the CP into metaheuristics such as tabu search, genetic algorithm, space smoothing, and noising methods. The performance of the CP is empirically compared with the nearest neighbour (NN) approach. Extensive computational comparison shows that the CP is considerably more effective compared to NN.     

A new enhancement of the Clarke and Wright savings heuristic for the capacitated vehicle routing problem

In this work we are concerned with the Clarke–Wright savings method for the classical capacitated vehicle routing problem. This is an NP-hard problem and numerous heuristic solution methods have been proposed. They can be classified as the classical ones and metaheuristics. Recent developments have shown that classical heuristics do not compare with the best metaheuristic implementations. However, some of them are very fast and simple to implement. This explains the popularity of the Clarke–Wright savings method in practice and the motivation behind its enhancements. We follow this line of research and propose a new enhancement which differs from the previous ones in its saving criterion: Customer demands are considered in addition to distances. Based on the extensive computational experiments we can say that the new method is not only very fast but also very accurate.     

Large neighborhood search for LNG inventory routing

Liquefied Natural Gas (LNG) is steadily becoming a common mode for commercializing natural gas. Due to the capital intensive nature of LNG projects, the optimal design of LNG supply chains is extremely important from a profitability perspective. Motivated by the need for a model that can assist in the design analysis of LNG supply chains, we address an LNG inventory routing problem where optimized ship schedules have to be developed for an LNG project. In this paper, we present an arc-flow formulation based on the MIP model of Song and Furman (Comput. Oper. Res., 2010). We also present a set of construction and improvement heuristics to solve this model efficiently. The heuristics are evaluated based on a set of realistic test instances that are very large relative to the problem instances seen in recent literature related to this problem. Extensive computational results indicate that the proposed methods are computationally efficient in finding optimal or near optimal solutions and are substantially faster than state-of-the-art commercial optimization software.     

Heuristics for flight and maintenance planning of mission aircraft

Flight and Maintenance Planning (FMP) of mission aircraft addresses the question of which available aircraft to fly and for how long, and which grounded aircraft to perform maintenance operations on, in a group of aircraft that comprise a unit. The objective is to achieve maximum fleet availability of the unit over a given planning horizon, while also satisfying certain flight and maintenance requirements. The application of exact methodologies for the solution of the problem is quite limited, as a result of their excessive computational requirements. In this work, we prove several important properties of the FMP problem, and we use them to develop two heuristic procedures for solving large-scale FMP instances. The first heuristic is based on a graphical procedure which is currently used for generating flight and maintenance plans of mission aircraft by many Air Force organizations worldwide. The second heuristic is based on the idea of splitting the original problem into smaller sub-problems and solving each sub-problem separately. Both heuristics have been roughly sketched in earlier works that have appeared in the related literature. The present paper develops the theoretical background on which these heuristics are based, provides in detail the algorithmic steps required for their implementation, analyzes their worst-case computational complexity, presents computational results illustrating their computational performance on random problem instances, and evaluates the quality of the solutions that they produce. The size and parameter values of some of the randomly tested problem instances are quite realistic, making it possible to infer the performance of the heuristics on real world problem instances. Our computational results demonstrate that, under careful consideration, even large FMP instances can be handled quite effectively. The theoretical results and insights that we develop establish a fundamental background that can be very useful for future theoretical and practical developments related to the FMP problem.