In the last few decades, graph domination problems have attracted the attention of both academics and practitioners. In these problems, a subset of vertices is selected such that every vertex in the graph is either in the subset or adjacent to at least one selected vertex. One of the most extended variants is the Roman Domination Problem (RDP), where vertices are assigned values to ensure coverage under specific protection rules. This research addresses the Double Roman Domination Problem (DROMDP), a more restrictive extension of RDP in which stronger domination conditions are imposed to guarantee coverage even under potential vertex failures. In this paper, an algorithm based on the Iterated Local Search (ILS) framework is proposed, considering the use of two constructive procedures, two local search methods, and two perturbation mechanisms to find high-quality solutions. The results obtained are compared with the state-of-the-art method, based on Ant Colony Optimization, with ILS emerging as the most competitive algorithm for DROMDP. These results are supported by an extensive computational experimentation, including an ablation study of the different components, statistical tests, and a Bayesian analysis on the probability of ILS for being the best algorithm for any instance.

Scatter search (SS) is a well-established metaheuristic for hard combinatorial optimization problems. SS is characterized by its versatility and ease of context adaptation and implementation. Although the literature includes SS parallelization schemes for specific problems, a general parallel framework for scatter search has not been developed and tested. We introduce three SS parallel designs, each focusing on a different task, namely, reducing computational time, increasing search exploration, and balancing search intensification and diversification. The proposed designs are tested on problems where the state of the art is a traditional (sequential) SS approach. This testing platform helps us assess the contributions of the parallel computing strategies to solution speed and quality. Our publicly available code is designed to be adapted to optimization problems that are not considered here. The results show promising avenues for establishing a general framework of SS parallelization. • Several designs for parallelizing scatter search are proposed. • The new parallel designs are tested on three combinatorial optimization problems. • Computational results assess the performance of the parallel designs. • The advantages and disadvantages of each parallel design are discussed.

This research proposes the use of metaheuristics for solving the Target Set Selection (TSS) problem. This problem emerges in the context of influence maximization problems, in which the objective is to maximize the number of active users when spreading information throughout a social network. Among all the influence maximization variants, TSS introduces the concept of reward of each user, which is the benefit associated to its activation. Therefore, the problem tries to maximize the reward obtained among all active users by selecting an initial set of users. Each user has also associated an activation cost, and the total sum of activation costs of the initial set of selected users cannot exceed a certain budget. In particular, two Path Relinking approaches are proposed, comparing them with the best method found in the state of the art. Additionally, a more challenging set of instances are derived from real-life social networks, where the best previous method is not able to find a feasible solution. The experimental results show the efficiency and efficacy of the proposal, supported by non-parametric statistical tests.

Abstract Several problems are emerging in the context of communication networks and most of them must be solved in reduced computing time since they affect to critical tasks. In this research, the monitor placement problem is tackled. This problem tries to cover the communications of an entire network by locating a monitor in specific nodes of the network, in such a way that every link remains surveyed. In case that a solution cannot be generated in the allowed computing time, a penalty will be assumed for each link uncovered. The problem is addressed by considering the variable neighborhood search framework, proposing a novel constructive method, an intelligent local search to optimize the improvement phase, and an intensified shake to guide the search to more promising solutions. The proposed algorithm is compared with a hybrid search evolutionary algorithm over a set of instances derived from real‐life networks to prove its performance.

Abstract This paper deals with an interesting facility location problem known as the bi-objective p -Median and p -Dispersion problem ( BpMD problem). The BpMD problem seeks to locate p facilities to service a set of n demand points, and the goal is to minimize the total distance between facilities and demand points and, simultaneously, maximize the minimum distance between all pairs of hosted facilities. The problem is addressed with a novel path relinking approach, called reactive path relinking, which hybridizes two of the most extended path relinking variants: interior path relinking and exterior path relinking. Additionally, the proposal is adapted to a multi-objective perspective for finding a good approximation of the Pareto front. Computational results prove the superiority of the proposed algorithm over the best procedures found in the literature.

Metaheuristic optimization is at the heart of the intersection between computer science and operations research. The INFORMS Journal of Computing has been fundamental in advancing the ideas behind metaheuristic methodologies. Fred Glover’s “Tabu Search—Part I” was published more than 30 years ago in the first volume of the then ORSA Journal on Computing. This article, one of the most cited in the area of heuristic optimization, paved the way for many contributions to the methodology and practice of operations research. As a continuation of this stream of research, we describe a new scatter search design for multiobjective optimization. The design includes a short-term memory tabu search and a path relinking combination method. We show how the strategies and mechanisms within scatter search and tabu search can be combined to produce a highly effective approach to multiobjective optimization.

Abstract In recent years, the relevance of cybersecurity has been increasingly evident to companies and institutions, as well as to final users. Because of that, it is important to ensure the robustness of a network. With the aim of improving the security of the network, it is desirable to find out which are the most critical nodes in order to protect them from external attackers. This work tackles this problem, named the α‐separator problem, from a heuristic perspective, proposing an algorithm based on the Greedy Randomized Adaptive Search Procedure (GRASP). In particular, a novel approach for the constructive procedure is proposed, where centrality metrics derived from social network analysis are used as a greedy criterion. Furthermore, the quality of the provided solutions is improved by means of a combination method based on Path Relinking (PR). This work explores different variants of PR, also adapting the most recent one, Exterior PR, for the problem under consideration. The combination of GRASP + PR allows the algorithm to obtain high‐quality solutions within a reasonable computing time. The proposal is supported by a set of intensive computational experiments that show the quality of the proposal, comparing it with the most competitive algorithm found in the state of art.

We study the problem of minimizing the profile of a graph and develop a solution method by following the tenets of scatter search. Our procedure exploits the network structure of the problem and includes strategies that produce a computationally efficient and agile search. Among several mechanisms, our search includes path relinking as the basis for combining solutions to generate new ones. The profile minimization problem (PMP) is NP‐Hard and has relevant applications in numerical analysis techniques that rely on manipulating large sparse matrices. The problem was proposed in the early 1970s but the state‐of‐the‐art does not include a method that could be considered powerful by today's computing standards. Extensive computational experiments show that we have accomplished our goal of pushing the envelope and establishing a new standard in the solution of the PMP. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 65(1), 10–21. 2015