The Linear Ordering Problem (LOP) is a fundamental combinatorial optimization problem with important applications in areas such as economics, social choice, and machine learning. Its most prominent use is the triangulation of economic input-output tables, which helps identify critical industries in an economy. Most existing algorithms have been evaluated on benchmarks derived from outdated macroeconomic data, which no longer reflect the structure of contemporary economies. Furthermore, LOP instances often exhibit many distinct global optima that can differ substantially from one another, creating challenges for applications that rely on a single solution. To address these limitations, we introduce a novel benchmark suite derived from up-to-date real-world economic data and an algorithmic scheme that leverages state-of-the-art LOP metaheuristics to generate diverse sets of high-quality solutions, together with metrics for assessing both quality and diversity. Experiments were conducted to report results on the proposed benchmark suite under both the traditional single-solution setting and the newly introduced multi-solution scenario

In this work, by using an adiabatic principle and the Maximum Cut Problem, we investigate the evolution of problem instances from a given initial instance to a given final instance. The path followed goes from one instance to the next by using a statistical concept of distance such that the transition is smooth in the sense that this distance is short. In other words, the process takes place in the instance space by following a trajectory of minimal change. During the process we study the evolution of the similarity between consecutive instances and the movement of the global optima. In particular, we investigated whether a smooth path in the instance space always exists between the initial and the final instance. This allow us to discuss a number of statistical results that are of general interest for the understanding of the instance space of difficult combinatorial optimization problems.

In this paper, we introduce SMorph, a new methodology for combinatorial optimization that works in the instance space of the problem at hand. Indeed, given the problem instance to solve, SMorph builds a simplified instance whose optimum is easy to locate, then it iteratively evolves this instance towards the target one by alternating two steps: optimization and smooth transformation of the current instance. The knowledge acquired in each iteration is transferred to next one, while the entire process is designed with the aim of improving the last optimization step. Although the abstract search scheme of SMorph is general enough to be instantiated for a variety of combinatorial optimization problems, here we present an implementation for the well-known Linear Optimization Problem (LOP). Experiments have been conducted on a set of commonly adopted benchmark instances of the LOP, and the results validate the proposed approach.

Abstract The continuous growth of data production in almost all scientific areas raises new problems in data access and management, especially in a scenario where the end-users, as well as the resources that they can access, are worldwide distributed. This work is focused on the data caching management in a Data Lake infrastructure in the context of the High Energy Physics field. We are proposing an autonomous method, based on Reinforcement Learning techniques, to improve the user experience and to contain the maintenance costs of the infrastructure.

Partial conditional probability assessments are having renewed attention and the merging of several sources of information is one of the more compelling needs associated with them. We focus here on the consequent task of correcting inconsistent probabilistic databases. We propose an efficient method for correcting incoherent (i.e. inconsistent) conditional probability assessments, that has a polynomial space complexity, differently from methods based on probabilistic satisfiability problems (PSAT) which require an exponential amount of memory space. This method uses Mixed Integer Programming (MIP) procedure to minimize the L1 distance between probability assessments and exploits the presence of the so-called “zero layers”. Through a simple prototypical example, we illustrate the feasibility and the peculiarities of the proposed procedure. Finally, we show some experimental results obtained through randomly generated incoherent assessments.

Low budget black-box optimization is a relevant topic in many practical applications with expensive objective functions or tight real-time constraints. Recently, there has been a growing interest in addressing combinatorial permutation problems in a low budget and black-box scenario. In this context, most of the previously proposed algorithms learn a probabilistic model which guides the search by trying to somehow indicate the most effective areas of the permutation search space. However, the large size and the inherent discontinuity of the permutation space may lessen the effectiveness of this approach when a low, or very low, budget of evaluations is considered. Moving from this consideration, in this work we present a simpler elitist trajectory-based algorithm for low budget black-box optimization of permu-tation problems. The proposed algorithm, namely FAT-RLS, is based on three core ideas: a randomized local search scheme, an adaptive perturbation strength and the use of a tabu structure. A series of experiments held on commonly adopted benchmark problems clearly shows that FAT-RLS obtains better or compara-ble effectiveness with respect to the previous proposals. Moreover, its negligible computational overhead is of particular interest in mission critical situations where tight real-time constraints have to be matched.

Generative Adversarial Network (GAN) is a family of machine learning algorithms designed to train neural networks able to imitate real data distributions. Unfortunately, GAN suffers from problems such as gradient vanishing and mode collapse. In Multi-Objective Evolutionary Generative Adversarial Network (MO-EGAN) these problems were addressed using an evolutionary technique combined with Multi-Objective selection, obtaining better results on synthetic datasets at the expense of larger computation times. In this works, we present the Smart MultiObjective Evolutionary Generative Adversarial Network (SMO-EGAN) algorithm, which reduces the computational cost of MO-EGAN and achieves better results on real data distributions.

In the era of big data, data volumes continue to grow in several different domains, from business to scientific fields. Sensors, edge devices, scientific applications and detectors generate huge amounts of data that are distributed for their nature. In order to extract value from such data requires a typical pipeline made of two main steps: first, the processing and then the data access. One of the main features for data access is fast response time, whose order of magnitude can vary a lot depending on the specific type of processing as well as processing patterns. The optimization of the access layer becomes more and more important while dealing with a geographically distributed environment where data must be retrieved from remote servers of a data lake. From the infrastructural perspectives, caching systems are used to mitigate latency and to serve better popular data. Thus, the role of the cache becomes a key to have an effective and efficient data access. In this article, we propose a Reinforcement Learning approach, using the Q-Learning technique, to improve the performances of a cache system in terms of data management. The proposed method uses two agents with different objectives and actions to control the addition and the eviction of files in the cache. The aim of this system is to increase the throughput reducing, at the same time, the cache costs, such as the amount of data written, and network utilization. Moreover, we tested our method in a context of data analysis, with information taken from High Energy Physics (HEP) workflow.

Crossover operators are very important components in Evolutionary Computation. Here we are interested in crossovers for the permutation representation that find applications in combinatorial optimization problems such as the permutation flowshop scheduling and the traveling salesman problem. We introduce three families of permutation crossovers based on algebraic properties of the permutation space. In particular, we exploit the group and lattice structures of the space. A total of 34 new crossovers is provided. Algebraic and semantic properties of the operators are discussed, while their performances are investigated by experimentally comparing them with known permutation crossovers on standard benchmarks from four popular permutation problems. Three different experimental scenarios are considered and the results clearly validate our proposals.

Particle Swarm Optimization (PSO), though originally introduced for continuous search spaces, has been increasingly applied to combinatorial optimization problems. In this paper, we focus on the PSO applications to permutation-based problems. As far as we know, the most popular and general PSO sche mes for permutation solutions are those based on random key techniques. After highlighting the main criticalities of the random key approach, we introduce a discrete PSO variant for permutation-based optimization problems. By simulating search moves through a vector space, the proposed algorithm, Algebraic PSO (APSO), allows the original PSO design to be applied to the permutation search space. APSO directly represents both particle positions and velocities as permutations. The APSO search scheme is based on a general algebraic framework for combinatorial optimization based on strong mathematical foundations. However, in order to make this new scheme viable, some challenges have to be overcome: the choice of the order of the velocity terms, and the rationale behind the PSO inertial move. Design solutions have been proposed for both the issues. Furthermore, an alternative geometric interpretation of classical PSO dynamics allows to introduce a major APSO variant based on a novel concept of convex combination between permutation objects. In total, four APSO schemes have been introduced. Experiments have been held to compare the performances of the APSO schemes with respect to the random key based PSO schemes in literature. Widely adopted benchmark instances of four popular permutation problems have been considered. The experimental results clearly show that, with high statistical evidence, APSO outperforms its competitors and it reaches results comparable with state-of-the-art on most of the instances considered.

Crossover operators are very important tools in Evolutionary Computation. Here we are interested in crossovers for the permutation representation that find applications in combinatorial optimization problems such as the permutation flowshop scheduling and the traveling salesman problem. We introduce three families of permutation crossovers based on algebraic properties of the permutation space. In particular, we exploit the group and lattice structures of the space. A total of 14 new crossovers is provided. Algebraic and semantic properties of the operators are discussed, while their performances are investigated by experimentally comparing them with known permutation crossovers on standard benchmarks from four popular permutation problems. Three different experimental scenarios are considered and the results clearly validate our proposals.

Particle Swarm Optimization (PSO), though being originally introduced for continuous search spaces, has been increasingly applied to combinatorial optimization problems. In particular, we focus on the PSO applications to permutation problems. As far as we know, the most popular PSO variants that produce permutation solutions are those based on random key techniques. In this paper, after highlighting the main criticalities of the random key approach, we introduce a totally discrete PSO variant for permutation-based optimization problems. The proposed algorithm, namely Algebraic PSO (APSO), simulates the original PSO design in permutations search space. APSO directly represents the particle positions and velocities as permutations. The APSO search scheme is based on a general algebraic framework for combinatorial optimization previously, and successfully, introduced in the context of discrete differential evolution schemes. The particularities of the PSO design scheme arouse new challenges for the algebraic framework: the non-commutativity of the velocity terms, and the rationale behind the PSO inertial move. Design solutions have been proposed for both the issues, and two APSO variants are provided. Experiments have been held to compare the performances of the APSO schemes with respect to the random key based PSO schemes in literature. Widely adopted benchmark instances of four popular permutation problems have been considered. The experimental results clearly show, with high statistical evidence, that APSO outperforms its competitors.

This paper introduces an original algebraic approach to differential evolution (DE) algorithms for combinatorial search spaces. An abstract algebraic differential mutation for generic combinatorial spaces is defined by exploiting the concept of a finitely generated group. This operator is specialized for the permutations space by means of an original randomized bubble sort algorithm. Then, a discrete DE algorithm is derived for permutation problems and it is applied to the permutation flowshop scheduling problem with the total flowtime criterion. Other relevant components of the proposed algorithm are: a crossover operator for permutations, a novel biased selection strategy, a heuristic-based initialization, and a memetic restart procedure. Extensive experimental tests have been performed on a widely accepted benchmark suite in order to analyze the dynamics of the proposed approach and to compare it with the state-of-the-art algorithms. The experimental results clearly show that the proposed algorithm reaches state-of-the-art performances and, most remarkably, it is able to find some new best known results. Furthermore, the experimental analysis on the impact of the algorithmic components shows that the two main contributions of this paper, i.e., the discrete differential mutation and the biased selection operator, greatly contribute to the overall performance of the algorithm.

In this work, the Linear Ordering Problem (LOP) has been approached using a discrete algebraic-based Differential Evolution for the Linear Ordering Problem (LOP). The search space of LOP is composed by permutations of objects, thus it is possible to use some group theoretical concepts and methods. Indeed, the proposed algorithm is a combinatorial Differential Evolution scheme designed by exploiting the group structure of the LOP solutions in order to mimic the classical Differential Evolution behavior observed in continuous spaces. In particular, the proposed differential mutation operator allows to obtain both scaled and extended differences among LOP solutions represented by permutations. The performances have been evaluated over widely known LOP benchmark suites and have been compared to the state-of-the-art results.