Skip to main content

2022 | Book

Learning and Intelligent Optimization

16th International Conference, LION 16, Milos Island, Greece, June 5–10, 2022, Revised Selected Papers

Editors: Dimitris E. Simos, Varvara A. Rasskazova, Francesco Archetti, Ilias S. Kotsireas, Panos M. Pardalos

Publisher: Springer International Publishing

Book Series : Lecture Notes in Computer Science


About this book

This book constitutes the refereed proceedings of the 16th International Conference on Learning and Intelligent Optimization, LION 16, which took place in Milos Island, Greece, in June 2022.
The 36 full papers and 3 short papers presented in this volume were carefully reviewed and selected from 60 submissions. LION deals with automatic solver configuration, parallel methods, intelligent optimization, nature-inspired algorithms, hard combinatorial optimization problems, DC learning, computational intelligence, and others. The contributions were organized in topical sections as follows: Invited Papers; Contributed Papers.

Table of Contents


Invited Papers

Optimal Scheduling of the Leaves of a Tree and the SVO Frequencies of Languages

We define and study algorithmically a novel optimization problem related to the sequential scheduling of the leaves of a binary tree in a given order, and its generalization in which the optimum order is sought. We assume that the scheduling process starts at the root of the tree and continues breadth-first in parallel, albeit with possible intervening lock and unlock steps, which define the scheduling cost. The motivation for this problem comes from modeling language generation in the brain. We show that optimality considerations in this problem provide a new explanation for an intriguing phenomenon in linguistics, namely that certain ways of ordering the subject, verb, and object in a sentence are far more common in world languages than others.

Christos H. Papadimitriou, Denis Turcu
From Design of Experiments to Combinatorics of Disasters: A Conceptual Framework for Disaster Exercises

In this paper, we present a conceptual framework for disaster exercises covering the modelling, generation and post-analysis of conducted exercises. Our proposed conceptual framework makes use of a combinatorial approach for actual disaster exercise generation from the literature. In particular, the scenarios in a disaster exercise generated by our framework collectively provide certain combinatorial sequence coverage guarantees and are also minimizing the overall number of scenarios. These coverage guarantees make the created scenarios ideal for the assessment of relief strategies and allow for easy generation of more extensive and effective exercises and training programs. We explain all the individual stages of our proposed framework and how they are mapped to particular steps in the disaster exercise design process.

Bernhard Garn, Klaus Kieseberg, Berina Celic, Dimitris E. Simos
Separating Two Polyhedra Utilizing Alternative Theorems and Penalty Function

The separation of two polyhedra by a family of parallel hyperplanes is a well-known problem with important applications in operations research,statistics and functional analysis. In this paper, we introduce a new algorithm for constructing a family of parallel hyperplanes that separates two disjoint polyhedra given by a system of linear inequalities. To do this, we consider the alternative system and introduce its dual problem using the alternative theorem. We can find its minimum-norm solution by combining the objective function and constraints into a penalty function. Since our objective function is only once differentiable, we propose an extension of Newton’s method to solve the unconstrained objective optimization. The computational outcomes demonstrate the efficacy of the proposed method.

Saeed Ketabchi, Hossein Moosaei, Mario R. Guarracino, Milan Hladík

Contributed Papers

A Composite Index Method for Optimization Benchmarking

We propose a multi-criteria Composite Index Method (CIM) to compare the performance of alternative approaches to solving an optimization problem. The CIM is convenient in those situations when neither approach dominates the other when tested on different sizes of problem instances. The CIM takes problem instance size and multiple performance criteria into consideration within a weighting scheme to produce a single number that measures the relative improvement of one alternative over the other. Different weights are given to each dimension based on their relative importance as determined by the end user. We summarize the successful application of the CIM to an $${\mathcal {N}\mathcal {P}}$$ N P -hard combinatorial optimization problem known as the backhaul profit maximization problem (BPMP). Using the CIM we tested a series of eleven techniques for improving solution time using CPLEX to solve two different BPMP models proposed in the literature.

Yulan Bai, Eli Olinick
Optimal Energy Management of Microgrid Using Multi-objective Optimisation Approach

The use of several distributed generators as well as the energy storage system in a local microgrid require an energy management system to maximize system efficiency, by managing generation and loads. The main purpose of this work is to find the optimal set-points of distributed generators and storage devices of a microgrid, minimizing simultaneously the energy costs and the greenhouse gas emissions. A multi-objective approach called Pareto-search Algorithm based on direct multi-search is proposed to ensure optimal management of the microgrid. According to the non-dominated resulting points, several scenarios are proposed and compared. The effectiveness of the algorithm is validated, giving a compromised choice between two criteria: energy cost and GHG emissions.

Yahia Amoura, Ana I. Pereira, José Lima, Ângela Ferreira, Fouad Boukli-Hacene
A Stochastic Alternating Balance k-Means Algorithm for Fair Clustering

In the application of data clustering to human-centric decision-making systems, such as loan applications and advertisement recommendations, the clustering outcome might discriminate against people across different demographic groups, leading to unfairness. A natural conflict occurs between the cost of clustering (in terms of distance to cluster centers) and the balance representation of all demographic groups across the clusters, leading to a bi-objective optimization problem that is nonconvex and nonsmooth. To determine the complete trade-off between these two competing goals, we design a novel stochastic alternating balance fair k-means (SAfairKM) algorithm, which consists of alternating classical mini-batch k-means updates and group swap updates. The number of k-means updates and the number of swap updates essentially parameterize the weight put on optimizing each objective function. Our numerical experiments show that the proposed SAfairKM algorithm is robust and computationally efficient in constructing well-spread and high-quality Pareto fronts both on synthetic and real datasets.

Suyun Liu, Luis Nunes Vicente
Binary Black Widow Optimization Algorithm for Feature Selection Problems

In this research work, we study the ability of a nature-inspired algorithm called the Black Widow Optimization (BWO) algorithm to solve feature selection (FS) problems. We use the BWO as a base algorithm and propose a new algorithm called the Binary Black Widow Optimization (BBWO) algorithm to solve FS problems. The evaluation method used in the algorithm is the wrapper method, designed to keep a degree of balance between two objectives: (i) minimize the number of selected features, (ii) maintain a high level of accuracy. We use the k-nearest-neighbor (KNN) machine learning algorithm in the learning stage to evaluate the accuracy of the solutions generated by the BBWO. This study has two main contributions: (a) applying the BBWO algorithm to solve FS problems efficiently, and (b) test results. The performance of the BBWO is tested on twenty-eight UCI benchmark datasets and the test results were compared with six well-known FS algorithms (namely, the BPSO, BMVO, BGWO, BMFO, BWOA, and BBAT algorithms). The test results show that the BBWO is as good as, or even better in some cases than the FS algorithms compared against. The obtained results can be used as new a benchmark and provide new insights about existing FS solutions.

Ahmed Al-Saedi, Abdul-Rahman Mawlood-Yunis
Learning to Solve a Stochastic Orienteering Problem with Time Windows

Reinforcement learning (RL) has seen increasing success at solving a variety of combinatorial optimization problems. These techniques have generally been applied to deterministic optimization problems with few side constraints, such as the traveling salesperson problem (TSP) or capacitated vehicle routing problem (CVRP). With this in mind, the recent IJCAI AI for TSP competition challenged participants to apply RL to a difficult routing problem involving optimization under uncertainty and time windows. We present the winning submission to the challenge, which uses the policy optimization with multiple optima (POMO) approach combined with efficient active search and Monte Carlo roll-outs. We present experimental results showing that our proposed approach outperforms the second place approach by 1.7%. Furthermore, our computational results suggest that solving more realistic routing problems may not be as difficult as previously thought.

Fynn Schmitt-Ulms, André Hottung, Meinolf Sellmann, Kevin Tierney
ML-Based Approach for Accelerating Global Search Algorithm for Solving Multicriteria Problems

The paper considers a new approach to solving multicriterial optimization problems on the base of criteria scalarization, dimensionality reduction via Peano curves and efficient global search algorithm. The novelty of the approach consists in application of machine learning methods combined with utilizing a posteriori information for acceleration of the search. Effectiveness of the proposed approach has been demonstrated by means of solving a set of multiextremal multicriterial optimization problems.

Konstantin Barkalov, Vladimir Grishagin, Evgeny Kozinov
The Skewed Kruskal Algorithm

Kruskal algorithm is one of the most efficient algorithms to compute a minimum spanning tree (MST) of a given weighted unoriented and connected graph. The edge list is sorted and edges are iteratively selected from it until a MST is found. To improve its performance, edge sorting can be interleaved with edge selection, so that only the relevant part of the edge list is actually sorted. Filtering techniques can also be used so that the size of some parts of the edge list is reduced before sorting and selection. Here we examine a further idea, i.e. to produce an unbalanced initial partition, with the aim of early guessing which part of the edge list actually needs being considered for filtering, sorting and edge selection.

Ermanno Righini, Giovanni Righini
Bounds for Sparse Solutions of K-SVCR Multi-class Classification Model

The support vector classification-regression machine for k-class classification (K-SVCR) is a novel multi-class classification approach based on the “1-versus-1-versus-rest” structure. In this work, we suggested an efficient model by proposing the p-norm $$(0<p< 1)$$ ( 0 < p < 1 ) instead of the 2-norm for the regularization term in the objective function of K-SVCR that can be used for feature selection. We derived lower bounds for the absolute value of nonzero entries in every local optimal solution of the p-norm based model. Also, we provided upper bounds for the number of nonzero components of the optimal solutions. We explored the link between solution sparsity, regularization parameters, and the p-choice.

Hossein Moosaei, Milan Hladík
Integer Linear Programming in Solving an Optimization Problem at the Mixing Department of the Metallurgical Production

The paper is devoted to investigate of the optimization problem on the mixing department processes at the metallurgical production. The problem is to unload transportation ladles into the iron ladles in such a way, to provide a timely and continues exchange between domain department and the mixing one, as well as between mixing department and converter shop-floor. This stage of technological chain plays the most important role for timely delivery of iron ladles to the converter shop-floor and for execution of the production plan in general.To solve the problem under consideration there proposed an integer linear programming model, which takes into account all technological restrictions on the mixing department processes. There constructed a special set of variables, which allowed one to formalize both a complex system of constraints an objective function.To demonstrate an effectiveness and powerful of the proposed approach, there were carried out a computational experiment using real-world data on the mixing department processes at the metallurgical production.

Damir N. Gainanov, Dmitriy A. Berenov, Egor A. Nikolaev, Varvara A. Rasskazova
Realtime Gray-Box Algorithm Configuration

A solver’s runtime and the quality of the solutions it generates are strongly influenced by its parameter settings. Finding good parameter configurations is a formidable challenge, even for fixed problem instance distributions. However, when the instance distribution can change over time, a once effective configuration may no longer provide adequate performance. Realtime algorithm configuration (RAC) offers assistance in finding high-quality configurations for such distributions by automatically adjusting the configurations it recommends based on instances seen so far. Existing RAC methods treat the solver to be configured as a black box, meaning the solver is given a configuration as input, and it outputs either a solution or runtime as an objective function for the configurator. However, analyzing intermediate output from the solver can enable configurators to avoid wasting time on poorly performing configurations. To this end, we propose a gray-box approach that utilizes intermediate output during evaluation and implement it within the RAC method CPPL. We apply cost sensitive machine learning with pairwise comparisons to determine whether ongoing evaluations can be terminated to free resources. We compare our realtime gray-box configurator to a black-box equivalent on several experimental settings and show that our approach reduces the total solving time in several scenarios.

Dimitri Weiss, Kevin Tierney
Dynamic Urban Solid Waste Management System for Smart Cities

Increasing population in cities combined with efforts to obtain more sustainable living spaces will require a smarter Solid Waste Management System (SWMS). A critical step in SWMS is the collection of wastes, generally associated with expensive costs faced by companies or municipalities in this sector. Some studies are being developed for the optimization of waste collection routes, but few consider inland cities as model regions. Here, the model region considered for the route optimization using Guided Local Search (GLS) algorithm was Bragança, a city in the northeast region of Portugal. The algorithm used in this work is available in open-source Google OR-tools. Results show that waste collection efficiency is affected by the upper limit of waste in dumpsters. Additionally, it is demonstrated the importance of dynamic selection of dumpsters. For instance, efficiency decreased 10.67% for the best upper limit compared to the traditional collection in the regular selection of dumpsters (levels only). However, an improvement of 50.45% compared to traditional collection was observed using dynamic selection of dumpsters to be collected. In other words, collection cannot be improved only by letting dumpsters reach 90% of waste level. In fact, strategies such as the dynamic selection here presented, can play an important role to save resources in a SWMS.

Adriano S. Silva, Thadeu Brito, Jose L. Diaz de Tuesta, José Lima, Ana I. Pereira, Adrián M. T. Silva, Helder T. Gomes
Single MCMC Chain Parallelisation on Decision Trees

Decision trees are highly famous in machine learning and usually acquire state-of-the-art performance. Despite that, well-known variants like CART, ID3, random forest, and boosted trees miss a probabilistic version that encodes prior assumptions about tree structures and shares statistical strength between node parameters. Existing work on Bayesian decision trees depend on Markov Chain Monte Carlo (MCMC), which can be computationally slow, especially on high dimensional data and expensive proposals. In this study, we propose a method to parallelise a single MCMC decision tree chain on an average laptop or personal computer that enables us to reduce its run-time through multi-core processing while the results are statistically identical to conventional sequential implementation. We also calculate the theoretical and practical reduction in run time, which can be obtained utilising our method on multi-processor architectures. Experiments showed that we could achieve 18 times faster running time provided that the serial and the parallel implementation are statistically identical.

Efthyvoulos Drousiotis, Paul G. Spirakis
An Extension of NSGA-II for Scaling up Multi-objective Spatial Zoning Optimization

Among decision problems in spatial management planning, marine spatial planning (MSP) has lately gained popularity. One of the difficulties in MSP is to determine the best place for a new activity while taking into account the locations of current activities. This paper presents the results of the extension of one multi-objective evolutionary-based algorithm (MOEA), non-dominated sorting genetic algorithm-II (NSGA-II) solved the multi-objective spatial zoning optimization problem. The proposed algorithm aims to maximize the interest of the area of the zone dedicated to the new activity while maximizing its spatial compactness. The extended NSGA-II, unlike the traditional one, makes use of a different stop condition, four crossover operators, three mutation operators, and repairing operators. This algorithm is developed for the raster data and it computes solutions for the multi-objective spatial zoning optimization model at a large scale. The proposed NSGA-II has revealed a good performance in comparison with the exact method tested on a small scale. To improve the performance of the algorithm, its parameters are calibrated and tuned using the Multi-Response Surface Methodology (MRSM) method. Analysis of variance (ANOVA) was used to determine the effective and non-effective factors and correctness of the regression models. Finally, conclusions are made and future research works are recommended.

Mohadese Basirati, Romain Billot, Patrick Meyer
Competitive Supply Allocation in a Distribution Network Under Overproduction

The paper aims to deal with the reallocating supply problem that result from the order promising process under overproduction. To this end, we develop a competitive distribution model to facilitate decision-making for order managers and to provide an intelligent support tool. The basis of the distribution model structure is a non-linear constrained optimization program that intends to minimize the costs of competing suppliers in case of an overproduction strategy. We obtain explicit conditions for orders relocation under affine delivery costs. An explicit form of conditions on the current delivery pattern will allow one to develop intelligent tools for decision-making support in the field of order management.

Alexander Krylatov, Yulia Lonyagina, Anastasiya Raevskaya
Safe-Exploration of Control Policies from Safe-Experience via Gaussian Processes

Control of many real-life systems strongly relies on the knowledge of a domain expert, who usually adopts a safe control policy to deal with uncertainty. The term safe means that the policy is aimed at avoiding system’s disruptions or relevant deviations from the desired behaviour, usually at the cost of sub-optimal performances. This paper proposes a statistically-sound approach which exploits the collected experience to safe-explore new policies by assuming a reasonable risk in terms of safety while improving performances. Gaussian Process regression is the core of the approach, providing a probabilistic approximation of both system’s dynamics and performances, depending on historical data related to the application of the safe policy. Being a probabilistic model, Gaussian Process provides both an estimate of the level of safety and, more important, the associated predictive uncertainty, which is crucial for implementing the safe-exploration of new efficient policies. The approach allows to avoid the typically expensive implementation of a digital twin of the system, required in the case of simulation-optimization approaches, as well as the formulation as a stochastic programming problem. Results on two case studies, inspired by real-life systems, are presented, showing an improvement in terms of performances with respect the initial safe policy, with reasonable safety of the systems.

Antonio Candelieri, Andrea Ponti, Francesco Archetti
Bayesian Optimization in Wasserstein Spaces

Bayesian Optimization (BO) is a sample efficient approach for approximating the global optimum of black-box and computationally expensive optimization problems which has proved its effectiveness in a wide range of engineering and machine learning problems. A limiting factor in its applications is the difficulty of scaling over 15–20 dimensions. It has been remarked that global optimization problems often have a lower intrinsic dimensionality which can be exploited to construct a feature mapping the original problem into low dimension manifold. In this paper we take a novel approach mapping the original problem into a space of discrete probability distributions endowed with a Wasserstein metric. In this new approach both the Gaussian process model and the acquisition function work in a 1-dimensional Wasserstein (WST) space. The results in the WST space are then mapped back to the original space using a neural network. Computational results show that, at least for high dimension additive test functions, the exploration in the Wasserstein space is significantly more effective.

Antonio Candelieri, Andrea Ponti, Francesco Archetti
Network Vulnerability Analysis in Wasserstein Spaces

The main contribution of this paper is the proposal of a new family of vulnerability measures based on a probabilistic representation framework in which the network and its components are modelled as discrete probability distributions. The resulting histograms are embedded in a space endowed with a metric given by the Wasserstein distance. This representation enables the synthesis of a set of discrete distributions through a barycenter and the clustering of distributions. We show that analyzing the networks as discrete probability distributions in the Wasserstein space enables the definition of a new family of vulnerability measures and the assessment of the criticality of each component. Computational results on real-life networks confirm the validity of our basic assumption that distributional representation can capture the topological information embedded in a network graph and yield more meaningful metrics than vulnerability measures based on average values. The computation of the Wasserstein distance is equivalent to the solution of a min-flow problem: its computational complexity has limited its diffusion outside the imaging science community. To avoid this computational bottleneck in this paper, we focus on a statistical approach that drastically reduces the computational hurdles. This approach has been implemented in a software tool HistDAWass. The linear complexity of this approach has also enabled the analysis of large-scale networks.

Andrea Ponti, Antonio Irpino, Antonio Candelieri, Anna Bosio, Ilaria Giordani, Francesco Archetti
BERT Self-Learning Approach with Limited Labels for Document Classification

The remarkable production speed of documents and, consequently, the volume of unstructured data stored in the Brazilian Government facilities requires processes that enable the capacity of classifying documents. This requirement is compliant with the existing archival legislation. In this sense, Natural Language Processing (NLP) stands as an important asset related to document classification, considering the reality of current document production, where there is a considerable number of unlabeled documentary samples. The Self-Learning approach applied to the BERT fine-tuning step delivers a model capable of classifying a partially labeled set of data according to the Requirements Model for Computerized Document Management Systems (e-ARQ Brazil). The developed model was capable of reaching a human-level performance, outperforming Active Learning and BERT in a series of defined confidence levels.

Carlos Eduardo de Lima Joaquim, Thiago de Paulo Faleiros
Autonomous Learning Rate Optimization for Deep Learning

A significant question in deep learning is: what should that learning rate be? The answer to this question is often tedious and time consuming to obtain, and a great deal of arcane knowledge has accumulated in recent years over how to pick and modify learning rates to achieve optimal training performance. Moreover, the long hours spent carefully crafting the perfect learning rate can be more demanding than optimizing network architecture itself. Advancing automated machine learning, we propose a new answer to the great learning rate question: the Autonomous Learning Rate Controller. Source code is available at .

Xiaomeng Dong, Tao Tan, Michael Potter, Yun-Chan Tsai, Gaurav Kumar, V. Ratna Saripalli, Theodore Trafalis
Optimizing Data Augmentation Policy Through Random Unidimensional Search

It is no secret among deep learning researchers that finding the optimal data augmentation strategy during training can mean the difference between state-of-the-art performance and a run-of-the-mill result. To that end, the community has seen many efforts to automate the process of finding the perfect augmentation procedure for any task at hand. Unfortunately, even recent cutting-edge methods bring massive computational overhead, requiring as many as 100 full model trainings to settle on an ideal configuration. We show how to achieve equivalent performance using just 6 trainings with Random Unidimensional Augmentation. Source code is available at .

Xiaomeng Dong, Michael Potter, Gaurav Kumar, Yun-Chan Tsai, V. Ratna Saripalli, Theodore Trafalis
Evaluating Student Behaviour on the MathE Platform - Clustering Algorithms Approaches

The MathE platform is an online educational platform that aims to help students who struggle to learn college mathematics as well as students who wish to deepen their knowledge on subjects that rely on a strong mathematical background, at their own pace. The MathE platform is currently being used by a significant number of users, from all over the world, as a tool to support and engage students, ensuring new and creative ways to encourage them to improve their mathematical skills. This paper is addressed to evaluate the students’ performance on the Linear Algebra topic, which is a specific topic of the MathE platform. In order to achieve this goal, four clustering algorithms were considered; three of them based on different bio-inspired techniques and the k-means algorithm. The results showed that most students choose to answer only basic level questions, and even within that subset, they make a lot of mistakes. When students take the risk of answering advanced questions, they make even more mistakes, which causes them to return to the basic level questions. Considering these results, it is now necessary to carry out an in-depth study to reorganize the available questions according to other levels of difficulty, and not just between basic and advanced levels as it is.

Beatriz Flamia Azevedo, Ana Maria A. C. Rocha, Florbela P. Fernandes, Maria F. Pacheco, Ana I. Pereira
Unsupervised Training for Neural TSP Solver

There has been a growing number of machine learning methods for approximately solving the travelling salesman problem. However, these methods often require solved instances for training or use complex reinforcement learning approaches that need a large amount of tuning. To avoid these problems, we introduce a novel unsupervised learning approach. We use a relaxation of an integer linear program for TSP to construct a loss function that does not require correct instance labels. With variable discretization, its minimum coincides with the optimal or near-optimal solution. Furthermore, this loss function is differentiable and thus can be used to train neural networks directly. We use our loss function with a Graph Neural Network and design controlled experiments on both Euclidean and asymmetric TSP. Our approach has the advantage over supervised learning of not requiring large labelled datasets. In addition, the performance of our approach surpasses reinforcement learning for asymmetric TSP and is comparable to reinforcement learning for Euclidean instances. Our approach is also more stable and easier to train than reinforcement learning.

Elīza Gaile, Andis Draguns, Emīls Ozoliņš, Kārlis Freivalds
Comparing Surrogate Models for Tuning Optimization Algorithms

Tuning an algorithm requires to evaluate it under different configurations on several problem instances. Such evaluations are costly. A way to reduce the configuration time when developing tuners is to use surrogate models, which map configuration-instance pairs to the approximate algorithm performance and thus allow to replace algorithm runs by fast calls to the model. Most applications of surrogate models found in the literature focus on predicting algorithm running time; much less effort has been devoted to predicting the quality of solutions of optimization algorithms. In this paper, we present a comparative study of surrogate models for predicting solution quality. We evaluate several surrogate models from the literature, including random forests, gradient boosting methods, and neural networks, and compare ways of handling different classes of parameters, data imputation strategies, and codification of instances. We demonstrate for two heuristic algorithms that the best models can accurately reproduce effects observed when tuning with the ground truth. Our code is available ( ).

Gustavo Delazeri, Marcus Ritt, Marcelo de Souza
Search and Score-Based Waterfall Auction Optimization

Online advertising is a major source of income for many online companies. One common approach is to sell online advertisements via waterfall auctions, through which a publisher makes sequential price offers to ad networks. The publisher controls the order and prices of the waterfall in an attempt to maximize his revenue. In this work, we propose a methodology to learn a waterfall strategy from historical data by wisely searching in the space of possible waterfalls and selecting the one leading to the highest revenues. The contribution of this work is twofold; First, we propose a novel method to estimate the valuation distribution of each user, with respect to each ad network. Second, we utilize the valuation matrix to score our candidate waterfalls as part of a procedure that iteratively searches in local neighborhoods. Our framework guarantees that the waterfall revenue improves between iterations ultimately converging into a local optimum. Real-world demonstrations are provided to show that the proposed method improves the total revenue of real-world waterfalls, as compared to manual expert optimization. Finally, the code and the data are available here .

Dan Halbersberg, Matan Halevi, Moshe Salhov
Survey on KNN Methods in Data Science

The k-nearest neighbors (KNN) algorithm remains a useful and widely applied approach. In the recent years, we have seen many advances in KNN methods, but few research works give a holistic account of all aspects of KNN and the progress made. This paper is a brief survey on modern KNN methods and their role in data science. Furthermore, we survey: the challenges, how they are approached in the literature, the impact of the distance metric, several KNN variations, as well as query methods.

Panos K. Syriopoulos, Sotiris B. Kotsiantis, Michael N. Vrahatis
Constrained Shortest Path and Hierarchical Structures

The Constrained Shortest Path (CSP) problem is as follows. An n-vertex graph is given, two weights are assigned to each edge: “cost” and “length”. It is required to find a min-cost bounded-length path between a given pair of vertices. The problem is NP-hard even when the lengths of all edges are the same. Therefore, various approximation algorithms have been proposed in the literature for it. The constraint on path length can be accounted for by considering one aggregated edge weight equals to the linear combination of the cost and length. By varying the value of the Lagrange multiplier in the linear combination, a feasible solution delivers a minimum to the objective function with new weights. At the same time, as usually, the Dijkstra’s algorithm or its modifications are used to construct a shortest path with the current weights of the edges. However, in the large graphs, this approach may turn out to be time-consuming. In this paper, we propose to search a solution, not in the original graph but in the specially constructed hierarchical structures (HS). We show that the shortest path in the HS is constructed with O(m)-time complexity, where m is the number of edges/arcs of the graph, and the approximate solution in the case of integer costs and lengths is found with $$O(m\log n)$$ O ( m log n ) -time complexity. In result of a priori analysis of the algorithm its accuracy estimation turned out to depend on the parameters of the problem and can be significant. Therefore, to evaluate the algorithm’s effectiveness, we conducted a numerical experiment on the graph of roads of megalopolis and randomly constructed metric unit-disk graphs (UDGs). The numerical experiment results show that in the HS, solution is built 10–100 times faster than in the methods which use Dijkstra’s like algorithm to build a min-weight path in the original graph.

Adil Erzin, Roman Plotnikov, Ilya Ladygin
Investigation of Graph Neural Networks for Instance Segmentation of Industrial Point Cloud Data

The concept of Digital Twins (DTs) was introduced 15 years ago. There have been many research methodologies and software to implement DTs in different industries including manufacturing, construction, product design, and other fields. DTs help quantify operational risks, improve production time, assist predictive maintenance, enable real-time remote monitoring and thus better financial decision-making. The generation of DTs for existing industrial sites necessitates the use of laser scanners for the acquisition of point cloud data that capture the existing (as-is) conditions. Currently, human modelers manually segment point cloud data by overlaying 3D CAD models on top of the laser scans or validating laser scanned point clouds with 2D documentation and drawings. Our previous work has achieved effective point cloud processing with techniques such as instance segmentation and class segmentation of the collected and registered industrial point cloud data. Instance Segmentation is an important method of clearly partitioning each object to a human-understandable point cluster in complex laser scanned data, creating a Geometric Digital Twin of Industrial Facilities. The industrial point cloud data consists of pipes, valves, cylinders, and various other combinations of geometric shapes. Segmenting such data is a difficult task as the data is too complex to visualize and understand. In our previous work, CLOI-NET, which is the state-of-the-art architecture for instance segmentation of industrial point clouds, achieves instance segmentation with average accuracy of 70% using graph connectivity algorithms. This proved that there is scope for more accurate instance segmentation of complex industrial point cloud data with a focus on identifying topological connectivity between components of the point cloud (e.g., a piping network). Also, there have been many research methods, for instance segmentation in city-scale and indoor environments classifying cars, people, buildings, trees, roads, using different types of neural networks with satisfactory performance having average accuracy upto 85%. In this paper, we discuss the best algorithms/networks like Graphical Neural Networks and 3D-CNNs and how they can be used to perform instance segmentation of industrial data, which will eventually lead to a better version of DT implementation specifically for industrial point cloud data.

Sandeep Jalui, Evangelia Agapaki
Fitness Landscape Ruggedness Impact on PSO in Dealing with Three Variants of the Travelling Salesman Problem

Fitness landscape analysis has gained quite some attention in understanding the behaviour of metaheuristics. Swarm intelligence is a type of metaheuristics that has grown considerably on the algorithmic side over the past decade. Nevertheless, only little attention has been paid to understanding the behaviour of algorithms on different fitness landscapes, especially in combinatorial optimization. Our aim in this paper is to re-motivate the importance of this issue. Moreover, by considering particle swarm optimization (PSO), we present a first investigation on its adaptation to three variants of the travelling salesman problem and how its performance is correlated with the ruggedness of the problem instances. The results show that PSO performance deteriorates with the increase in the number of cities and the ruggedness of the instances.

Abtin Nourmohammadzadeh, Malek Sarhani, Stefan Voß
A Multi-UAVs’ Provider Model for the Provision of 5G Service Chains: A Game Theoretic Approach

In the last years, the use of Flying Ad-hoc Networks (FANET) to extend and improve the capability of 5G networks, especially in scenarios characterized by poor or completely inexistent structured networks, has been very successful. The possibility to mount, on board of an Unmanned Aerial Vehicle (UAV), a Computing Element, giving it the possibility to host virtual functions (VFs) and provide data processing services, has allowed 5G networks to be able to extend their functionalities closer to the user, in the so-called Edge Network. In this paper, we present a multi-UAVs’ providers network based model describing the provisioning of service chains to users and devices on the ground. The objective of each provider in the proposed model is to establish the optimal service chain flows to manage and send to, or receive by, other providers in order to maximize its revenue while minimizing the total execution, execution request and transmission costs, under the constraints that the total costumer demand, for each service chain, are satisfied, as well as the capacity constraints. We formulate the nonlinear optimization problem as a non-cooperative game in which each player (provider) is rational and acts selfishly. In particular, we analyzed the Generalized Nash Equilibrium Problem (GNEP), and the equivalent formulation of the GNEP by means of Variational Inequality theory is also provided. Finally, an illustrative numerical example is presented and analyzed.

Giorgia Maria Cappello, Gabriella Colajanni, Patrizia Daniele, Laura Galluccio, Christian Grasso, Giovanni Schembra, Laura Rosa Maria Scrimali
Metabolic Syndrome Risk Forecasting on Elderly with ML Techniques

Metabolic syndrome is a disorder that affects the overall function of the human body. It is manifested by elevated levels of cholesterol and triglycerides, a significant reduction in energy levels, weight gain with visceral fat deposition in the abdomen, and menstrual disorders while increasing the risk of cardiovascular disease, autoimmune diseases and diabetes. A public dataset is exploited to evaluate the metabolic syndrome (MetS) occurrence risk in the elderly using Machine Learning (ML) techniques concerning Accuracy, Recall and Area Under Curve (AUC). The stacking method achieved the best performance. Finally, our purpose is to identify subjects at risk and promote earlier intervention to avoid the future development of MetS.

Elias Dritsas, Sotiris Alexiou, Konstantinos Moustakas
Airport Digital Twins for Resilient Disaster Management Response

Airports are constantly facing a variety of hazards and threats from natural disasters to cybersecurity attacks and airport stakeholders are confronted with making operational decisions under irregular conditions. We introduce the concept of the foundational twin, which can serve as a resilient data platform, incorporating multiple data sources and enabling the interaction between an umbrella of twins. We then focus on providing data sources and metrics for each foundational twin, with an emphasis on the environmental airport twin for major US airports.

Evangelia Agapaki
Strategies for Surviving Aggressive Multiparty Repeated Standoffs (Extended Abstract)

A multiparty standoff system, arises from a confrontation involving quarrelling parties for which no strategy may exist for any party to achieve victory and the parties cannot withdraw from the conflict without suffering a loss (which may even include their demise). In a repeated standoff the parties are pursuing in rounds an aggressive attack strategy, which may involve selecting opponents and “repeatedly firing shots” whose success depends on a random adversary. Each participating party has been pre-assigned a probability indicating the chance a given shot will succeed against an opponent.Eventually, every standoff terminates with the resulting system consisting in the limit (of the number of rounds) of isolated nodes. We consider confrontation strategies and analyze the resulting survivability of the participating parties. We investigate what strategy should co-operating parties follow so as to maximize the number of surviving nodes. We are also interested in what strategy should a given party (or group of parties) follow so as to maximize its chance of survival.

Evangelos Kranakis
A Hybridization of GRASP and UTASTAR for Solving the Vehicle Routing Problem with Pickups and Deliveries and 3D Loading Constraints

As urban centers grow, demand for goods transportation grows as well. The emergence of e-commerce has been a great catalyst, with online sales placing a big load on transportation companies. Current social conditions further amplify the effect. An unnoticed segment has been the delivery of large-size items in urban centers, where restrictions of different kinds impose the use of small vehicles. This research presents a novel combination of UTASTAR with Vehicle Routing Problem with Pickups and Deliveries and three-dimensional loading constraints to provide solutions. Scenarios of demand exceeding capacity are considered. A Decision Support System (DSS) is created to assist Decision Makers (DMs) of logistics companies get routing suggestions based on their priorities. The considerable size and weight of the items require careful handling of the smaller vehicles. The utilization of heuristic methods for routing expedites the solution process, enabling the formation of multiple solutions, which get ranked by the UTASTAR method on four criteria. The criteria values and thresholds are set indirectly by the DM. The model is tested on modified instances from the literature and a case study.

Themistoklis Stamadianos, Magdalene Marinaki, Nikolaos Matsatsinis, Yannis Marinakis
Packing Hypertrees and the k-cut Problem in Hypergraphs

We give a combinatorial algorithm to find a maximum packing of hypertrees in a capacitated hypergraph. Based on this we extend to hypergraphs several algorithms for the k-cut problem, that are based on packing spanning trees in a graph. In particular we give a $$\gamma $$ γ -approximation algorithm for hypergraphs of rank $$\gamma $$ γ , extending the work of Ravi and Sinha [24] for graphs. We also extend the work of Chekuri, Quanrud and Xu [7] in graphs, to give an algorithm for the k-cut problem in hypergraphs that is polynomial if k and the rank of the hypergraph are fixed. We also give a combinatorial algorithm to solve a linear programming relaxation of this problem in hypergraphs.

Mourad Baïou, Francisco Barahona
Maximizing the Eigenvalue-Gap and Promoting Sparsity of Doubly Stochastic Matrices with PSO

The eigenvalue-gap of doubly stochastic matrices with sparsity constraints is maximized using the unified particle swarm optimizer. This is possible through the use of an iterative normalization procedure that maps the search space of the swarm to the set of doubly stochastic matrices with given sparsity pattern. We extend the method to the problem of finding doubly-stochastic matrices of given dimensions that are as sparse as possible, and attain a given eigenvalue-gap target.

Panos K. Syriopoulos, Nektarios G. Kalampalikis, Michael N. Vrahatis
Value of Information in the Mean-Square Case and Its Application to the Analysis of Financial Time-Series Forecast

The advances and development of various machine learning techniques has lead to practical solutions in various areas of science, engineering, medicine and finance. The great choice of algorithms, their implementations and libraries has resulted in another challenge of selecting the right algorithm and tuning their parameters in order to achieve optimal or satisfactory performance in specific applications. Here we show how the value of information (V(I)) can be used in this task to guide the algorithm choice and parameter tuning process. After estimating the amount of Shannon’s mutual information between the predictor and response variables, V(I) can define theoretical upper bound of performance of any algorithm. The inverse function I(V) defines the lower frontier of the minimum amount of information required to achieve the desired performance. In this paper, we illustrate the value of information for the mean-square error minimization and apply it to forecasts of cryptocurrency log-returns.

Roman V. Belavkin, Panos Pardalos, Jose Principe
Learning and Intelligent Optimization
Dimitris E. Simos
Varvara A. Rasskazova
Francesco Archetti
Ilias S. Kotsireas
Panos M. Pardalos
Copyright Year
Electronic ISBN
Print ISBN

Premium Partner