Algorithms

Editorial

Jump to: Research, Review

3 pages, 166 KiB

Open AccessEditorial

Special Issue “2021 Selected Papers from Algorithms’ Editorial Board Members”

by Frank Werner

Algorithms 2021, 14(12), 357; https://doi.org/10.3390/a14120357 - 9 Dec 2021

Cited by 1 | Viewed by 2192

Abstract

This is the second edition of a special issue of Algorithms that is of a rather different nature compared to other Special Issues in the journal, which are usually dedicated to a particular subject in the area of algorithms [...] Full article

(This article belongs to the Special Issue 2021 Selected Papers from Algorithms Editorial Board Members)

Research

Jump to: Editorial, Review

39 pages, 670 KiB

Open AccessArticle

Matheuristics and Column Generation for a Basic Technician Routing Problem

by Nicolas Dupin, Rémi Parize and El-Ghazali Talbi

Algorithms 2021, 14(11), 313; https://doi.org/10.3390/a14110313 - 27 Oct 2021

Cited by 10 | Viewed by 3517

Abstract

This paper considers a variant of the Vehicle Routing Problem with Time Windows, with site dependencies, multiple depots and outsourcing costs. This problem is the basis for many technician routing problems. Having both site-dependency and time window constraints lresults in difficulties in finding [...] Read more.

This paper considers a variant of the Vehicle Routing Problem with Time Windows, with site dependencies, multiple depots and outsourcing costs. This problem is the basis for many technician routing problems. Having both site-dependency and time window constraints lresults in difficulties in finding feasible solutions and induces highly constrained instances. Matheuristics based on Mixed Integer Linear Programming compact formulations are firstly designed. Column Generation matheuristics are then described by using previous matheuristics and machine learning techniques to stabilize and speed up the convergence of the Column Generation algorithm. The computational experiments are analyzed on public instances with graduated difficulties in order to analyze the accuracy of algorithms for ensuring feasibility and the quality of solutions for weakly to highly constrained instances. The results emphasize the interest of the multiple types of hybridization between mathematical programming, machine learning and heuristics inside the Column Generation framework. This work offers perspectives for many extensions of technician routing problems. Full article

(This article belongs to the Special Issue 2021 Selected Papers from Algorithms Editorial Board Members)

► Show Figures

Graphical abstract

27 pages, 9272 KiB

Open AccessArticle

Machine Learning-Based Prediction of the Seismic Bearing Capacity of a Shallow Strip Footing over a Void in Heterogeneous Soils

by Mohammad Sadegh Es-haghi, Mohsen Abbaspour, Hamidreza Abbasianjahromi and Stefano Mariani

Algorithms 2021, 14(10), 288; https://doi.org/10.3390/a14100288 - 30 Sep 2021

Cited by 5 | Viewed by 2917

Abstract

The seismic bearing capacity of a shallow strip footing above a void displays a complex dependence on several characteristics, linked to geometric problems and to the soil properties. Hence, setting analytical models to estimate such bearing capacity is extremely challenging. In this work, [...] Read more.

The seismic bearing capacity of a shallow strip footing above a void displays a complex dependence on several characteristics, linked to geometric problems and to the soil properties. Hence, setting analytical models to estimate such bearing capacity is extremely challenging. In this work, machine learning (ML) techniques have been employed to predict the seismic bearing capacity of a shallow strip footing located over a single unsupported rectangular void in heterogeneous soil. A dataset consisting of 38,000 finite element limit analysis simulations has been created, and the mean value between the upper and lower bounds of the bearing capacity has been computed at the varying undrained shear strength and internal friction angle of the soil, horizontal earthquake accelerations, and position, shape, and size of the void. Three machine learning techniques have been adopted to learn the link between the aforementioned parameters and the bearing capacity: multilayer perceptron neural networks; a group method of data handling; and a combined adaptive-network-based fuzzy inference system and particle swarm optimization. The performances of these ML techniques have been compared with each other, in terms of the following statistical performance indices: coefficient of determination (

R^{2}

); root mean square error (

RMSE

); mean absolute percentage error; scatter index; and standard bias. Results have shown that all the ML techniques perform well, though the multilayer perceptron has a slightly superior accuracy featuring noteworthy results (

R^{2} =

0.9955 and

RMSE =

0.0158). Full article

(This article belongs to the Special Issue 2021 Selected Papers from Algorithms Editorial Board Members)

► Show Figures

Figure 1

7 pages, 214 KiB

Open AccessArticle

Use of the Codon Table to Quantify the Evolutionary Role of Random Mutations

by Mihaly Mezei

Algorithms 2021, 14(9), 270; https://doi.org/10.3390/a14090270 - 17 Sep 2021

Cited by 1 | Viewed by 2027

Abstract

The various biases affecting RNA mutations during evolution is the subject of intense research, leaving the extent of the role of random mutations undefined. To remedy this lacuna, using the codon table, the number of codons representing each amino acid was correlated with [...] Read more.

The various biases affecting RNA mutations during evolution is the subject of intense research, leaving the extent of the role of random mutations undefined. To remedy this lacuna, using the codon table, the number of codons representing each amino acid was correlated with the amino acid frequencies in different branches of the evolutionary tree. The correlations were seen to increase as evolution progressed. Furthermore, the number of RNA mutations that resulted in a given amino acid mutation were found to be correlated with several widely used amino acid similarity tables (used in sequence alignments). These correlations were seen to increase when the observed codon usage was factored in. Full article

(This article belongs to the Special Issue 2021 Selected Papers from Algorithms Editorial Board Members)

25 pages, 1354 KiB

Open AccessArticle

A New Constructive Heuristic Driven by Machine Learning for the Traveling Salesman Problem

by Umberto Junior Mele, Luca Maria Gambardella and Roberto Montemanni

Algorithms 2021, 14(9), 267; https://doi.org/10.3390/a14090267 - 14 Sep 2021

Cited by 11 | Viewed by 4745

Abstract

Recent systems applying Machine Learning (ML) to solve the Traveling Salesman Problem (TSP) exhibit issues when they try to scale up to real case scenarios with several hundred vertices. The use of Candidate Lists (CLs) has been brought up to cope with the [...] Read more.

Recent systems applying Machine Learning (ML) to solve the Traveling Salesman Problem (TSP) exhibit issues when they try to scale up to real case scenarios with several hundred vertices. The use of Candidate Lists (CLs) has been brought up to cope with the issues. A CL is defined as a subset of all the edges linked to a given vertex such that it contains mainly edges that are believed to be found in the optimal tour. The initialization procedure that identifies a CL for each vertex in the TSP aids the solver by restricting the search space during solution creation. It results in a reduction of the computational burden as well, which is highly recommended when solving large TSPs. So far, ML was engaged to create CLs and values on the elements of these CLs by expressing ML preferences at solution insertion. Although promising, these systems do not restrict what the ML learns and does to create solutions, bringing with them some generalization issues. Therefore, motivated by exploratory and statistical studies of the CL behavior in multiple TSP solutions, in this work, we rethink the usage of ML by purposely employing this system just on a task that avoids well-known ML weaknesses, such as training in presence of frequent outliers and the detection of under-represented events. The task is to confirm inclusion in a solution just for edges that are most likely optimal. The CLs of the edge considered for inclusion are employed as an input of the neural network, and the ML is in charge of distinguishing when such edge is in the optimal solution from when it is not. The proposed approach enables a reasonable generalization and unveils an efficient balance between ML and optimization techniques. Our ML-Constructive heuristic is trained on small instances. Then, it is able to produce solutions—without losing quality—for large problems as well. We compare our method against classic constructive heuristics, showing that the new approach performs well for TSPLIB instances up to 1748 cities. Although ML-Constructive exhibits an expensive constant computation time due to training, we proved that the computational complexity in the worst-case scenario—for the solution construction after training—is

O (n^{2} log n^{2})

, n being the number of vertices in the TSP instance. Full article

(This article belongs to the Special Issue 2021 Selected Papers from Algorithms Editorial Board Members)

► Show Figures

Figure 1

22 pages, 1981 KiB

Open AccessArticle

Scheduling Multiprocessor Tasks with Equal Processing Times as a Mixed Graph Coloring Problem

by Yuri N. Sotskov and Evangelina I. Mihova

Algorithms 2021, 14(8), 246; https://doi.org/10.3390/a14080246 - 19 Aug 2021

Cited by 3 | Viewed by 2736

Abstract

This article extends the scheduling problem with dedicated processors, unit-time tasks, and minimizing maximal lateness

L_{\max}

for integer due dates to the scheduling problem, where along with precedence constraints given on the set [...] Read more.

This article extends the scheduling problem with dedicated processors, unit-time tasks, and minimizing maximal lateness

L_{\max}

for integer due dates to the scheduling problem, where along with precedence constraints given on the set

V = {v_{1}, v_{2}, \dots, v_{n}}

of the multiprocessor tasks, a subset of tasks must be processed simultaneously. Contrary to a classical shop-scheduling problem, several processors must fulfill a multiprocessor task. Furthermore, two types of the precedence constraints may be given on the task set

V

. We prove that the extended scheduling problem with integer release times

r_{i} \geq 0

of the jobs

V

to minimize schedule length

C_{\max}

may be solved as an optimal mixed graph coloring problem that consists of the assignment of a minimal number of colors (positive integers)

{1, 2, \dots, t}

to the vertices

{v_{1}, v_{2}, \dots, v_{n}} = V

of the mixed graph

G = (V, A, E)

such that, if two vertices

v_{p}

and

v_{q}

are joined by the edge

[v_{p}, v_{q}] \in E

, their colors have to be different. Further, if two vertices

v_{i}

and

v_{j}

are joined by the arc

(v_{i}, v_{j}) \in A

, the color of vertex

v_{i}

has to be no greater than the color of vertex

v_{j}

. We prove two theorems, which imply that most analytical results proved so far for optimal colorings of the mixed graphs

G = (V, A, E)

, have analogous results, which are valid for the extended scheduling problems to minimize the schedule length or maximal lateness, and vice versa. Full article

(This article belongs to the Special Issue 2021 Selected Papers from Algorithms Editorial Board Members)

► Show Figures

Figure 1

16 pages, 353 KiB

Open AccessArticle

Computational Complexity and ILP Models for Pattern Problems in the Logical Analysis of Data

by Giuseppe Lancia and Paolo Serafini

Algorithms 2021, 14(8), 235; https://doi.org/10.3390/a14080235 - 9 Aug 2021

Cited by 6 | Viewed by 2406

Abstract

Logical Analysis of Data is a procedure aimed at identifying relevant features in data sets with both positive and negative samples. The goal is to build Boolean formulas, represented by strings over {0,1,-} called patterns, which can be used to classify new [...] Read more.

Logical Analysis of Data is a procedure aimed at identifying relevant features in data sets with both positive and negative samples. The goal is to build Boolean formulas, represented by strings over {0,1,-} called patterns, which can be used to classify new samples as positive or negative. Since a data set can be explained in alternative ways, many computational problems arise related to the choice of a particular set of patterns. In this paper we study the computational complexity of several of these pattern problems (showing that they are, in general, computationally hard) and we propose some integer programming models that appear to be effective. We describe an ILP model for finding the minimum-size set of patterns explaining a given set of samples and another one for the problem of determining whether two sets of patterns are equivalent, i.e., they explain exactly the same samples. We base our first model on a polynomial procedure that computes all patterns compatible with a given set of samples. Computational experiments substantiate the effectiveness of our models on fairly large instances. Finally, we conjecture that the existence of an effective ILP model for finding a minimum-size set of patterns equivalent to a given set of patterns is unlikely, due to the problem being NP-hard and co-NP-hard at the same time. Full article

(This article belongs to the Special Issue 2021 Selected Papers from Algorithms Editorial Board Members)

24 pages, 2751 KiB

Open AccessArticle

A General Cooperative Optimization Approach for Distributing Service Points in Mobility Applications

by Thomas Jatschka, Günther R. Raidl and Tobias Rodemann

Algorithms 2021, 14(8), 232; https://doi.org/10.3390/a14080232 - 6 Aug 2021

Cited by 4 | Viewed by 2781

Abstract

This article presents a cooperative optimization approach (COA) for distributing service points for mobility applications, which generalizes and refines a previously proposed method. COA is an iterative framework for optimizing service point locations, combining an optimization component with user interaction on a large [...] Read more.

This article presents a cooperative optimization approach (COA) for distributing service points for mobility applications, which generalizes and refines a previously proposed method. COA is an iterative framework for optimizing service point locations, combining an optimization component with user interaction on a large scale and a machine learning component that learns user needs and provides the objective function for the optimization. The previously proposed COA was designed for mobility applications in which single service points are sufficient for satisfying individual user demand. This framework is generalized here for applications in which the satisfaction of demand relies on the existence of two or more suitably located service stations, such as in the case of bike/car sharing systems. A new matrix factorization model is used as surrogate objective function for the optimization, allowing us to learn and exploit similar preferences among users w.r.t. service point locations. Based on this surrogate objective function, a mixed integer linear program is solved to generate an optimized solution to the problem w.r.t. the currently known user information. User interaction, refinement of the matrix factorization, and optimization are iterated. An experimental evaluation analyzes the performance of COA with special consideration of the number of user interactions required to find near optimal solutions. The algorithm is tested on artificial instances, as well as instances derived from real-world taxi data from Manhattan. Results show that the approach can effectively solve instances with hundreds of potential service point locations and thousands of users, while keeping the user interactions reasonably low. A bound on the number of user interactions required to obtain full knowledge of user preferences is derived, and results show that with 50% of performed user interactions the solutions generated by COA feature optimality gaps of only 1.45% on average. Full article

(This article belongs to the Special Issue 2021 Selected Papers from Algorithms Editorial Board Members)

► Show Figures

Figure 1

14 pages, 3208 KiB

Open AccessArticle

A Greedy Heuristic for Maximizing the Lifetime of Wireless Sensor Networks Based on Disjoint Weighted Dominating Sets

by Samir Balbal, Salim Bouamama and Christian Blum

Algorithms 2021, 14(6), 170; https://doi.org/10.3390/a14060170 - 31 May 2021

Cited by 8 | Viewed by 3416

Abstract

Dominating sets are among the most well-studied concepts in graph theory, with many real-world applications especially in the area of wireless sensor networks. One way to increase network lifetime in wireless sensor networks consists of assigning sensors to disjoint dominating node sets, which [...] Read more.

Dominating sets are among the most well-studied concepts in graph theory, with many real-world applications especially in the area of wireless sensor networks. One way to increase network lifetime in wireless sensor networks consists of assigning sensors to disjoint dominating node sets, which are then sequentially used by a sleep–wake cycling mechanism. This paper presents a greedy heuristic for solving a weighted version of the maximum disjoint dominating sets problem for energy conservation purposes in wireless sensor networks. Moreover, an integer linear programming model is presented. Experimental results based on a large set of 640 problem instances show, first, that the integer linear programming model is only useful for small problem instances. Moreover, they show that our algorithm outperforms recent local search algorithms from the literature with respect to both solution quality and computation time. Full article

(This article belongs to the Special Issue 2021 Selected Papers from Algorithms Editorial Board Members)

► Show Figures

Graphical abstract

24 pages, 1967 KiB

Open AccessArticle

Chaos and Stability in a New Iterative Family for Solving Nonlinear Equations

by Alicia Cordero, Marlon Moscoso-Martínez and Juan R. Torregrosa

Algorithms 2021, 14(4), 101; https://doi.org/10.3390/a14040101 - 24 Mar 2021

Cited by 16 | Viewed by 2738

Abstract

In this paper, we present a new parametric family of three-step iterative for solving nonlinear equations. First, we design a fourth-order triparametric family that, by holding only one of its parameters, we get to accelerate its convergence and finally obtain a sixth-order uniparametric [...] Read more.

In this paper, we present a new parametric family of three-step iterative for solving nonlinear equations. First, we design a fourth-order triparametric family that, by holding only one of its parameters, we get to accelerate its convergence and finally obtain a sixth-order uniparametric family. With this last family, we study its convergence, its complex dynamics (stability), and its numerical behavior. The parameter spaces and dynamical planes are presented showing the complexity of the family. From the parameter spaces, we have been able to determine different members of the family that have bad convergence properties, as attracting periodic orbits and attracting strange fixed points appear in their dynamical planes. Moreover, this same study has allowed us to detect family members with especially stable behavior and suitable for solving practical problems. Several numerical tests are performed to illustrate the efficiency and stability of the presented family. Full article

(This article belongs to the Special Issue 2021 Selected Papers from Algorithms Editorial Board Members)

► Show Figures

Figure 1

15 pages, 367 KiB

Open AccessEditor’s ChoiceArticle

An Improved Greedy Heuristic for the Minimum Positive Influence Dominating Set Problem in Social Networks

by Salim Bouamama and Christian Blum

Algorithms 2021, 14(3), 79; https://doi.org/10.3390/a14030079 - 28 Feb 2021

Cited by 16 | Viewed by 5628

Abstract

This paper presents a performance comparison of greedy heuristics for a recent variant of the dominating set problem known as the minimum positive influence dominating set (MPIDS) problem. This APX-hard combinatorial optimization problem has applications in social networks. Its aim is to identify [...] Read more.

This paper presents a performance comparison of greedy heuristics for a recent variant of the dominating set problem known as the minimum positive influence dominating set (MPIDS) problem. This APX-hard combinatorial optimization problem has applications in social networks. Its aim is to identify a small subset of key influential individuals in order to facilitate the spread of positive influence in the whole network. In this paper, we focus on the development of a fast and effective greedy heuristic for the MPIDS problem, because greedy heuristics are an essential component of more sophisticated metaheuristics. Thus, the development of well-working greedy heuristics supports the development of efficient metaheuristics. Extensive experiments conducted on a wide range of social networks and complex networks confirm the overall superiority of our greedy algorithm over its competitors, especially when the problem size becomes large. Moreover, we compare our algorithm with the integer linear programming solver CPLEX. While the performance of CPLEX is very strong for small and medium-sized networks, it reaches its limits when being applied to the largest networks. However, even in the context of small and medium-sized networks, our greedy algorithm is only 2.53% worse than CPLEX. Full article

(This article belongs to the Special Issue 2021 Selected Papers from Algorithms Editorial Board Members)

► Show Figures

Graphical abstract

12 pages, 310 KiB

Open AccessArticle

Online Facility Location in Evolving Metrics

by Dimitris Fotakis, Loukas Kavouras and Lydia Zakynthinou

Algorithms 2021, 14(3), 73; https://doi.org/10.3390/a14030073 - 25 Feb 2021

Cited by 7 | Viewed by 2423

Abstract

The Dynamic Facility Location problem is a generalization of the classic Facility Location problem, in which the distance metric between clients and facilities changes over time. Such metrics that develop as a function of time are usually called “evolving metrics”, thus Dynamic Facility [...] Read more.

The Dynamic Facility Location problem is a generalization of the classic Facility Location problem, in which the distance metric between clients and facilities changes over time. Such metrics that develop as a function of time are usually called “evolving metrics”, thus Dynamic Facility Location can be alternatively interpreted as a Facility Location problem in evolving metrics. The objective in this time-dependent variant is to balance the trade-off between optimizing the classic objective function and the stability of the solution, which is modeled by charging a switching cost when a client’s assignment changes from one facility to another. In this paper, we study the online variant of Dynamic Facility Location. We present a randomized

O (log m + log n)

-competitive algorithm, where m is the number of facilities and n is the number of clients. In the first step, our algorithm produces a fractional solution, in each timestep, to the objective of Dynamic Facility Location involving a regularization function. This step is an adaptation of the generic algorithm proposed by Buchbinder et al. in their work “Competitive Analysis via Regularization.” Then, our algorithm rounds the fractional solution of this timestep to an integral one with the use of exponential clocks. We complement our result by proving a lower bound of

Ω (m)

for deterministic algorithms and lower bound of

Ω (log m)

for randomized algorithms. To the best of our knowledge, these are the first results for the online variant of the Dynamic Facility Location problem. Full article

(This article belongs to the Special Issue 2021 Selected Papers from Algorithms Editorial Board Members)

► Show Figures

Figure 1

Review

Jump to: Editorial, Research

21 pages, 9131 KiB

Open AccessReview

Overview of Algorithms for Using Particle Morphology in Pre-Detonation Nuclear Forensics

by Tom Burr, Ian Schwerdt, Kari Sentz, Luther McDonald and Marianne Wilkerson

Algorithms 2021, 14(12), 340; https://doi.org/10.3390/a14120340 - 24 Nov 2021

Cited by 5 | Viewed by 3121

Abstract

A major goal in pre-detonation nuclear forensics is to infer the processing conditions and/or facility type that produced radiological material. This review paper focuses on analyses of particle size, shape, texture (“morphology”) signatures that could provide information on the provenance of interdicted materials. [...] Read more.

A major goal in pre-detonation nuclear forensics is to infer the processing conditions and/or facility type that produced radiological material. This review paper focuses on analyses of particle size, shape, texture (“morphology”) signatures that could provide information on the provenance of interdicted materials. For example, uranium ore concentrates (UOC or yellowcake) include ammonium diuranate (ADU), ammonium uranyl carbonate (AUC), sodium diuranate (SDU), magnesium diuranate (MDU), and others, each prepared using different salts to precipitate U from solution. Once precipitated, UOCs are often dried and calcined to remove adsorbed water. The products can be allowed to react further, forming uranium oxides UO3, U3O8, or UO2 powders, whose surface morphology can be indicative of precipitation and/or calcination conditions used in their production. This review paper describes statistical issues and approaches in using quantitative analyses of measurements such as particle size and shape to infer production conditions. Statistical topics include multivariate t tests (Hotelling’s

T^{2}

), design of experiments, and several machine learning (ML) options including decision trees, learning vector quantization neural networks, mixture discriminant analysis, and approximate Bayesian computation (ABC). ABC is emphasized as an attractive option to include the effects of model uncertainty in the selected and fitted forward model used for inferring processing conditions. Full article

(This article belongs to the Special Issue 2021 Selected Papers from Algorithms Editorial Board Members)

► Show Figures

Figure 1

Journal Menu

Journal Browser

2021 Selected Papers from Algorithms Editorial Board Members

Share This Special Issue

Special Issue Editor

Special Issue Information

Benefits of Publishing in a Special Issue

Published Papers (13 papers)

Editorial

Research

Review

Further Information

Guidelines

MDPI Initiatives

Follow MDPI