Facility location problems (FLPs) are a family of optimisation problems with significant social impact. This class of problems has been the subject of study since the 1960s, with classical approaches including the Weber problem and the p -Median problem. Currently, more complex variations of these problems are being investigated. In particular, the Induced p -Median Problem with Upgrades (IpMU) represents a variation of the classical p -Median problem, where the concepts of transport cost and time are separated as distinct metrics in the input graph of the problem. Furthermore, the problem includes a budget which allows one to relax the graph costs, reducing the cost of the edges, thus improving the associated routes between the designated medians and the customers. In this study, a metaheuristic algorithm, based on the Greedy Randomized Adaptive Search Procedure (GRASP), is proposed. A two-phase resolution scheme is defined, studying the median problem and the upgrading problem independently. In this approach, a larger set of state-of-the-art instances was analysed to ensure a fair comparison with previous proposals. In addition, the characteristics of the instances were studied to assess their complexity. The results obtained are promising when compared to the state-of-the-art, which is based entirely on mathematical programming models. The execution time was improved on average by two orders of magnitude for the harder instances, and the best known result was obtained in more than 99% of the tested instances.

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.

The quality of software projects is measured by different attributes such as efficiency, security, robustness, or understandability, among others. In this paper, we focus on maintainability by studying the optimization of software modularity, which is one of the most important aspects in this regard. Specifically, we study two well-known and closely related multi-objective optimization problems: the Equal-size Cluster Approach Problem (ECA) and the Maximizing Cluster Approach Problem (MCA). Each of these two problems looks for the optimization of several conflicting and desirable objectives in terms of modularity. To this end, we propose a method based on the Multi-Objective Variable Neighborhood Search (MO-VNS) methodology in combination with a constructive procedure based on Path-Relinking. As far as we know, this is the first time that a method based on MO-VNS is proposed for the MCA and ECA problems. To enhance the performance of the proposed algorithm, we present three advanced strategies: an incremental evaluation of the objective functions, an efficient exploration of promising areas in the search space, and an analysis of the objectives that better serve as guiding functions during the search phase. Our proposal has been validated by experimentally comparing the performance of our algorithm with the best previous state-of-the-art method for the problem and three reference methods for multi-objective optimization. The experiments have been performed on a set of 124 real software instances previously reported in the literature.

Reproducibility of experiments is a complex task in stochastic methods such as evolutionary algorithms or metaheuristics in general. Many works from the literature give general guidelines to favor reproducibility. However, none of them provide both a practical set of steps or software tools to help in this process. In this article, we propose a practical methodology to favor reproducibility in optimization problems tackled with stochastic methods. This methodology is divided into three main steps, where the researcher is assisted by software tools which implement state-of-the-art techniques related to this process. The methodology has been applied to study the double-row facility layout problem (DRFLP) where we propose a new algorithm able to obtain better results than the state-of-the-art methods. To this aim, we have also replicated the previous methods in order to complete the study with a new set of larger instances. All the produced artifacts related to the methodology and the study of the target problem are available in Zenodo.

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.

Diversity and dispersion problems deal with selecting a subset of elements from a given set in such a way that their diversity is maximized. This study considers a practical location problem recently proposed in the context of max–min dispersion models. It is called the generalized dispersion problem, and it models realistic applications by introducing capacity and cost constraints. We propose two effective linear formulations for this problem, and develop a hybrid metaheuristic algorithm based on the variable neighborhood search methodology, to solve real instances. Extensive numerical computational experiments are performed to compare our hybrid metaheuristic with the state-of-art heuristic, and with integer linear programming formulations (ILP). Results on public benchmark instances show the superiority of our proposal with respect to the previous algorithms. Our extensive experimentation reveals that ILP models are able to optimally solve medium-size instances with the Gurobi optimizer, although metaheuristics outperform ILP both in running time and quality in large-size instances.

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

Abstract This article proposes a linear integer programming formulation and several heuristics based on GRASP and path relinking for the antibandwidth problem. In the antibandwidth problem, one is given an undirected graph with n nodes and must label the nodes in a way that each node receives a unique label from the set {1, 2,…, n }, such that, among all adjacent node pairs, the minimum difference between the node labels is maximized. Computational results show that only small instances of this problem can be solved exactly (to optimality) with a commercial integer programming solver and that the heuristics find high‐quality solutions in much less time than the commercial solver. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 58(3), 171–189 2011

In this paper we consider the problem of finding a global optimum of an unconstrained multimodal function within the framework of adaptive memory programming, focusing on an integration of the Scatter Search and Tabu Search methodologies. Computational comparisons are performed on a test-bed of 11 types of problems. For each type, four problems are considered, each one with dimension 50, 100, 200 and 500 respectively; thus totalling 44 instances. Our results show that the Scatter Tabu Search procedure is competitive with the state-of-the-art methods in terms of the average optimality gap achieved.

The max-cut problem consists of finding a partition of the nodes of a weighted graph into two subsets such that the sum of the weights on the arcs connecting the two subsets is maximized. This is an NP-hard problem that can also be formulated as an integer quadratic program. Several solution methods have been developed since the 1970s and applied to a variety of fields, particularly in engineering and layout design. We propose a heuristic method based on the scatter-search methodology for finding approximate solutions to this optimization problem. Our solution procedure incorporates some innovative features within the scatter-search framework: (1) the solution of the maximum diversity problem to increase diversity in the reference set, (2) a dynamic adjustment of a key parameter within the search, and (3) the adaptive selection of a combination method. We perform extensive computational experiments to first study the effect of changes in critical scatter-search elements and then to compare the efficiency of our proposal with previous solution procedures.

The Max-Cut problem consists of finding a partition of the graph nodes into two subsets, such that the sum of the edge weights having endpoints in different subsets is maximized. This NP-hard problem for non planar graphs has different applications in areas such as VLSI and ASIC design. This paper proposes an evolutionary hybrid algorithm based on low-level hybridization between Memetic Algorithms and Variable Neighborhood Search. This algorithm is tested and compared with the results, found in the bibliography, obtained by other hybrid metaheuristics for the same problem. Achieved experimental results show the suitability of the approach, and that the proposed hybrid evolutionary algorithm finds near-optimal solutions. Moreover, on a set of standard test problems, new best known solutions were produced for several instances.