Section 6

A VNS approach for a variant of the Antibandwidth problem

Sergio Cavero, Eduardo G. Pardo, Abraham Duarte

The Cyclic Antibandwidth Problem (CAB) is an optimization problem, belonging to the graph layout family of problems, which consists in finding an embedding of a candidate graph in a cycle host graph, in order to maximize the minimum distance between any pair of adjacent vertices measured in the cycle. Real-world applications of this problem include the scheduling of sensors in networks, and the design of circuits. The CAB is known to be NP-hard, however it has been solved in an exact way for some kind of candidate graphs such as paths, cycles or meshes. For general graphs, two heuristics procedures have been proposed in the last decade. The first approach was based on a Memetic Algorithm and, the second one, on an Artificial Bee Colony methodology combined with a Tabu Search. No previous approaches based on Variable Neighborhood Search have been proposed. In this research, we tackle the CAB by testing the performance of different variants of VNS for this problem. The strategies proposed were compared with the previous methods in the state of the art and the results obtained, over a preliminary dataset of instances, indicate that the proposal is competitive when compared with previous methods.
Acknowledgments: Supported by the Ministerio de Ciencia, Innovaci├│n y Universidades (Grant Ref. PGC2018-095322-B-C22) and Comunidad de Madrid and European Regional Development Fund (Grant Ref. P2018/TCS-4566)

Reduced Variable Neighbourhood Search for the generation of controlled circular data

Sergio Consoli, Domenico Perrotta, Marco Turchi

A number of artificial intelligence and machine learning problems need to be formulated within a directional space, where classical Euclidean geometry does not apply or needs to be readjusted into the circle. This is typical, for example, in computational linguistics and natural language processing, where language models based on Bag-of-Words, Vector Space, orWord Embedding, are largely used for tasks like document classification, information retrieval and recommendation systems, among others. In these contexts, for assessing document clustering and outliers detection applications, it is often necessary to generate data with directional properties and units that follow some model assumptions and possibly form close groups. In the following we propose a Reduced Variable Neighbourhood Search heuristic which is used to generate high-dimensional data controlled by the desired properties aimed at representing several real-world contexts. The whole problem is formulated as a non-linear continuous optimization problem, and it is shown that the proposed Reduced Variable Neighbourhood Search is able to generate high-dimensional solutions to the problem in short computational time. A comparison with the state-of-the-art local search routine used to address this problem shows the greater efficiency of the approach presented here.

DOI: 10.1007/978-3-030-69625-2_7

Less is more approach for solving the p-center problem

Nenad Mladenovi─ç, Dragan Urosevic

The p-center problem is one of the most popular problems in a discrete location theory. Given a set of potential facility locations with cardinality n and a set of users located in known points. One needs to select p, out of n facilities to minimize the maximum distance from users to facilities. Since the problem is NP-hard, many heuristics approaches have been tried out in the literature. In this report, we propose a Less is more approach (LIMA) and a Variable neighborhood search (VNS) to solve it. Besides effectiveness (precision) and efficiency (speed) in comparing the two algorithms, LIMA introduces simplicity as well, which is usually measured by the number of ingredients that are used in the algorithm. As with any other min-max problem, it has many plateaux and an additional objective is needed to overcome them. On 40 well-studied test instances from the literature, we were able to improve 7 best-known solutions in less time and less simplicity.