Section 9

A Variable Neighborhood Search approach for the Maximum Quasi-clique Problem

Raúl Martín-Santamaría, J. Manuel Colmenar

Graph analysis is a critical discipline due its numerous practical applications, such as, social network analysis, coding theory and scheduling. Any social network can be modeled as a Graph G = (V,E), in which users are represented as nodes and each relationship between different users is represented as an edge. One of the most interesting problems in social networks is finding a cluster of highly influential users, or tightly knit communities, where every user is related in some way to every single other in the same cluster. This problem is known as finding the maximum clique. In practice, this may be too restrictive, therefore the constraint can be relaxed to include nodes which are connected to most nodes in the cluster but not necessarily all. This variant is known as the maximum quasi-clique problem (MQCP). Note that the maximum clique problem is a subset of the MQCP, in which the edges of the cluster must be maximum. In this work, the authors present an efficient approach using the Variable Neighborhood Search scheme, using a novel set of constructive heuristics. Results are promising in relation with the state of the art, spending competitive computation times.

Using K-means and Variable Neighborhood Search for Automatic Summarization of Scientific Articles

Iskander Akhmetov, Nenad Mladenovic, Rustam Mussabayev

This work presents a method for summarizing scientific arti-cles from the arXive dataset using Variable Neighborhood Search (VNS)heuristics to automatically find the best summaries in terms of ROUGE-1 score we could assemble from scientific article text sentences. Thenvectorizing the sentences using BERT pre-trained language model andaugmenting the vectors with topic embeddings obtained by applying theK-means algorithm. Finally, training the Random Forest classificationmodel to find sentences suitable for the summary and compile a sum-mary from the selected sentences. The described algorithm producedsummaries with high ROUGE-1 scores (0.45 on average), so we are head-ing for further developments on a larger dataset.

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


Transmit beampattern design for target tracking using variable neighbourhood search algorithm

Marko Đogatović, Milorad Stanojević, Vesna Radonjić Đogatović, Nenad Mladenović

Multiple-input multiple-output (MIMO) radar with colocated antennas is convenient for effective shaping the transmitting beam based on sub-array division. This research is dedicated to the transmit beamforming for colocated MIMO radar with the aim of applying to target tracking. MIMO radar beampattern shape impacts the performance of target tracking. Our goal is to obtain the transmit cross-correlation matrix by minimizing the objective function formulated as difference between a desired and the actual transmit beampattern. We also assume that power distribution across the transmit antennas is uniform. Transmit cross-correlation matrix is used to assign transmit power through adjusting the correlation between antennas. The desired transmit beampattern can be of arbitrary shape. Considering that the proposed optimization problem is nonconvex and hard to solve, we use continuous variable neighbourhood search algorithm to design transmit beampattern as similar as possible to the desired one. Numerical results illustrate performance of the algorithm for solving the proposed problem.

Less Is More Approach in Optimization - A Road to Artificial Intelligence

Nenad Mladenović, Jun Pei, Panos M. Pardalos

The main idea of Less is more approach (LIMA) is using as fewer as possible ingredients to provide the best possible outcome. This approach has been used successfully almost in all the scientific and art disciplines. Recently, the idea has also been successfully explored in solving hard optimization problems. In this note we first define the dominance relation between two algorithms that includes their simplicity as well. Then we propose the general LIMA algorithm and discuss automatic ways to include common ingredients of all search algorithms, increasing the algorithms complexity in a systematic way. That kind of approach may represent a road from Optimization to Artificial Intelligence.