Search

Recently, hybrid metaheuristics have become a trend in operations research. A successful example combines the Greedy Randomized Adaptive Search Procedures (GRASP) and data mining techniques, where frequent patterns found in high‐quality solutions can lead to an efficient exploration of the search space, along with a significant reduction of computational time. In this paper, a GRASP‐based state‐of‐the‐art heuristic for the minimum latency problem is improved by means of data mining techniques. Computational experiments showed that the hybrid heuristic with data mining was able to match or improve the solution quality for a large number of instances, together with a substantial reduction of running time. Besides, 32 new best‐known solutions are introduced to the literature. To support our results, statistical significance tests, analyses over the impact of mined patterns, comparisons based on running time as stopping criterion, and time‐to‐target plots are provided. [ABSTRACT FROM AUTHOR]

Given a graph G = (V, E) and a threshold γ ∈ (0, 1], the maximum cardinality quasi- clique problem consists in finding a maximum cardinality subset C* of the vertices in V such that the density of the graph induced in G by C* is greater than or equal to the threshold γ. This problem has a number of applications in data mining, e.g., in social networks or phone call graphs. We propose a matheuristic for solving the maximum cardinality quasi-clique problem, based on the hybridization of a biased random-key genetic algorithm (BRKGA) with an exact local search strategy. The newly proposed approach is compared with a pure biased random-key genetic algorithm, which was the best heuristic in the literature at the time of writing. Computational results show that the hybrid BRKGA outperforms the pure BRKGA. [ABSTRACT FROM AUTHOR]

A clean map visualization requires the fewest possible overlaps and depends on how labels are attached to point features. In this paper, we address the cartographic label placement variant problem whose objective is to label a set of points maximizing the number of conflict‐free points. Thus, we propose a hybrid data mining heuristic to solve the point‐feature cartographic label placement problem based on a clustering search (CS) heuristic, a state‐of‐the‐art method for this problem. Although several works have investigated the combination of data mining and multistart metaheuristics, this is the first time data mining has been used to improve CS and simulated annealing based heuristics. Computational experiments showed that the proposed hybrid heuristic was able to reach better cost solutions than the original strategy, with the same time effort. The proposed heuristic also could find almost all known optimal solutions and improved most of the best results for the set of large instances reported so far in the literature. [ABSTRACT FROM AUTHOR]

In communication network design, connections with few edges reduce the probability of delays and increase confidence. The 2‐path network design problem (2‐PNDP) raised in this context and aimed to build up a minimum‐cost network to satisfy a set of pairs of demands using a path with at most two edges. In this work, we propose two strategies that incorporate integer linear programming (ILP) into a state‐of‐the‐art heuristic for solving the 2‐PNDP. Our approaches collect information from specific components of the original heuristic and use it to reduce the solution space explored by the ILP solver, accelerating its resolution and improving the solution quality. Computational experiments conducted on a set of instances from the literature have shown the benefit of these combinations, achieving better solutions in almost all cases. [ABSTRACT FROM AUTHOR]

The scope of this work is the application of data mining techniques to improve the performance of metaheuristics in the combinatorial optimization scenario. Data mining techniques have been coupled with metaheuristics in order to obtain patterns of suboptimal solutions that are used to guide the heuristic search for better-cost solutions in less computational time. This kind of hybridization has been successfully explored to solve several optimization problems, for which the solutions and their patterns are limitedly characterized by sets of elements. The challenge of this work is to extend this hybrid approach to a broader domain. We therefore propose a hybrid data mining heuristic to solve the one-commodity pickup-and-delivery traveling salesman problem, for which solutions are defined by sequences of elements. Computational experiments, conducted on a set of instances from the literature, showed that the hybrid heuristic reached better-costs solutions faster than the original strategy. This way, it was evidenced that not only problems whose solutions are represented by sets of elements can benefit from the hybridization of metaheuristics with data mining, but also problems whose solutions are represented by a sequence of elements. [ABSTRACT FROM AUTHOR]

The main drawback of most metaheuristics is the absence of effective stopping criteria. Most implementations of such algorithms stop after performing a given maximum number of iterations or a given maximum number of consecutive iterations without improvement in the best-known solution value, or after the stabilization of the set of elite solutions found along the search. We propose effective probabilistic stopping rules for randomized metaheuristics such as GRASP (Greedy Randomized Adaptive Search Procedures). We show how the probability density function of the solution values obtained along the iterations of such algorithms can be used to implement stopping rules based on the tradeoff between solution quality and the time needed to find a solution that might improve the best solution found. We show experimentally that, in the particular case of GRASP heuristics, the solution values obtained along its iterations fit a normal distribution that may be used to give an online estimation of the number of solutions obtained in forthcoming iterations that might be at least as good as the incumbent. This estimation is used to validate the stopping rule based on the tradeoff between solution quality and the time needed to find a solution that might improve the incumbent. The robustness of this strategy is illustrated and validated by a thorough computational study reporting results obtained with GRASP implementations to four different combinatorial optimization problems. [ABSTRACT FROM AUTHOR]