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]