Dipartimento di Matematica e Informatica - Tesi di Dottorato
Permanent URI for this collectionhttps://lisa.unical.it/handle/10955/103
Questa collezione raccoglie le Tesi di Dottorato afferenti al Dipartimento di Matematica e Informatica dell'Università della Calabria.
Browse
80 results
Search Results
Item A Logic-based Framework for Characterizing Nexus of Similarity within Knowledge Bases(Università della Calabria, 2024-04-04) Ricioppo, Aldo; Terracina, Giorgio; Manna, MarcoComplex challenges frequently necessitate the establishment of significant connections among diverse entities. For instance, selecting the optimal CV, finding a suitable apartment or deciphering the causal factors behind a specific disorder are just a few examples, and each of them requires deep understanding of what characterizes a set of entities. In addition to the aforementioned examples, having to recognize similarities between entities is a recurring phenomenon in a multitude of real-world scenarios. Researchers from different fields have presented various methodologies over the last century to evaluate these similarities, commonly called similarity. In recent times, momentum has increased with the advent of “Google Sets”, leading to the fervent development of strategies to amplify a given set of entities while preserving their original shared interconnected properties. As a consequence, current methodologies can encompass, in a way or another, relevant interconnected properties shared by entities, a concept we term the nexus of similarity. Machines have demonstrated considerable prowess in handling similarity evaluations, often returning numerical scores as a result, and set expansions, thus giving the end user the opportunity to observe entities similar to those he was looking for. However, there is a notable gap in formally characterizing the nexus of similarity in a way that is intelligible by machines and interpretable by human intellect, especially considering that the attempts that have gained the most traction thus far are often bound to cases very specific, such as those made with respect to RDF graphs. To address these gaps, our endeavor contributes significantly to the existing literature. We aim to construct a novel framework grounded in logical constructs, designed to systematically and autonomously delineate the nexus of similarity. Our framework extends not only to pairs of entities but also to sets of tuples of entities, which we term anonymous relations, within a knowledge base. Furthermore, our analysis encompasses an in-depth examination of the computational complexity inherent in the proposed framework. Such an investigation affords a thorough insight into its feasibility and a subsequent evaluation of scalability. Both are critical components for the framework’s practical application. In summary, our study pioneers a novel, knowledge-driven approach capable of characterizing nexus of similarity and that can be used as a means to perform entity set expansion in a manner clear and intelligible to humans. Two of the principal components integral to our framework will be the semantic resources, specifically selective knowledge bases, that in their essence are knowledge bases equipped with a particular supplementary algorithm, and the explanation languages, of which we will take into consideration one in particular, which in our opinion has all the ideal characteristics to be considered a language suitable to reveal the nexus of similarity as best as possible. During the work, we will also justify our design choices. With the help of these means we aim to fill the perceptible gap in the characterization of nexus of similarity. At the same time, we will show how some of the current approaches to entity set expansion do not notice that by their very nature this kind of expansions should take the form of a taxonomy rather than a chain. To resolve this other gap, we will introduce the concept of expansion graph.Item Balancing the average weighted completion times of two classes of jobs: a new scheduling problem(Università della Calabria, 2023-11-29) Avolio, Matteo; Terracina, Giorgio; Fuduli, AntonioExploring a new area of the scheduling theory and inspired by a real application in an academic context, in this thesis we introduce a new single-machine two-agent scheduling problem, aimed at balancing the average weighted completion times of two different classes of jobs, one per agent. Differently from the common multiagent cases, which are generally of the competing type, this problem could be interpreted as a cooperative type problem. In fact, even if the two agents share the same machine, they cooperate to optimize the unique global objective function, in order to balance their average weighted completion times. While for the case with identical jobs and unitary weight we present an exact algorithm providing an optimal solution in linear time, for the general case we prove the NP-hardness of the problem and we propose a mathematical formulation as a variant of the well known quadratic assignment problem. By applying the Glover linearization, we obtain a mixed integer linear program exploited to design a Lagrangian heuristics based on solving, at each iteration, a linear assignment problem. Since the proposed algorithm has revealed to be able to solve instances up to 500 jobs, in order to face larger scale instances (up to 2000 jobs) we also propose a genetic algorithm.Item Expanding the Frontiers in GenAI and XAI: Innovative Architectures and Applications(Università della Calabria, 2024-09-27) Adorneto, Carlo; Greco, Gianluigi; Terracina, GiorgioGenerative Artificial Intelligence (GenAI) and Explainable Artificial Intelligence (XAI) have attracted significant interest in recent years due to their potential and their capacity to drive and inspire further research. This thesis explores new frontiers in these fields by presenting a collection of innovative architectures and applications. In the realm of GenAI, this work introduces GIDnets, a generative neural network aimed at solving inverse design problems through latent space exploration, showcasing improvements over existing methods. Furthermore, the research explores the application of latent space conditioning and transformers for automatic medical report generation. The thesis also investigates the role of generative agents, based on Large Language Models (LLMs), in agent-based modeling, offering insights into their validation and the emerging challenges. One of the notable challenges addressed is the complexity of opinion diffusion in social environments, highlighting its potential as a promising application scenario for generative agents. In the domain of XAI, this thesis illustrates the impact of computational methods on data interpretation, particularly when data science and Deep Learning (DL) are employed to gain insights in the biomedical field. Despite advancements, explaining DL models remains a debated issue. SHAP (SHapley Additive exPlanations) is demonstrated as a powerful tool for extracting insights from these black-box models and its application in bankruptcy prediction and natural disaster event scenarios will be discussed. Additionally, a new deep learning algorithm based on XAI is proposed for feature selection in genomics. This algorithm utilizes a new SHAP-inspired metric to identify and quantify the impact of genes, significantly enhancing the prediction accuracy for chronic lymphocytic leukemia. The innovative approaches presented in this thesis advance the state-of-the-art in GenAI and XAI, showcasing the potential of these technologies to enable the design of practical solutions across various domains.Item Optimizing Evaluation of Logic Programs: Extended Compilation & Enhanced Rewritings(Università della Calabria, 2023-11-29) Mazzotta, Giuseppe; Terracina, Giorgio; Ricca, FrancescoItem SPARQL-QA: A system for Question Answering over RDF(S) Knowledge Bases(Università della Calabria, 2023-04-29) Borroto Santana, Manuel Alejandro; Terracina, Giorgio; Ricca, FrancescoItem Enhancing DLV for reasoning over streams: the LDSR language and its expressiveness(Università della Calabria, 2024-04-09) Morelli, Maria Concetta; Terracina, Giorgio; Manna, Marco; Perri, SimonaItem Design and Implementation of an ASP-based Stream Reasoner(Università della Calabria, 2023-07-04) Mastria, Elena; Calimeri, Francesco; Perri, Simona; Zangari, JessicaStream Reasoning (SR) is a relatively young research field that evolved from Stream Processing (SP) more than a decade ago. It focuses on studying and developing advanced approaches and techniques for the continuous application of inference techniques to highly dynamic data streams. Data streams are (theoretically) infinite streams of information that dynamically change over time. These are generated by sources (e.g., sensors, devices, social networks, etc.) that monitor a physical or virtual environment, continuously reporting the relative state and changes. While SP aims at quickly processing data streams while answering continuous queries on their elements, SR tackles inferencing new information taking into account the content of data streams along with background knowledge on the application domain. Recently, SR has been studied in several fields, and has become more and more relevant in diverse application scenarios, such as IoT, Smart Cities, Emergency Management, and Healthcare. In such types of context, applications require complex query answering in a minimal amount of time. This amount is defined from the application domain at hand and is typically real-time (< 1 second) or near real-time(< 1 minute). Therefore, an SR system (i.e., stream reasoner) must be able to perform complex reasoning tasks while efficiently processing heterogeneous data streams together with large background knowledge bases. Different SR approaches have been proposed in fields such as Data Stream Management Systems (DSMS), Complex Event Processing (CEP), Semantic Web, and Knowledge Representation and Reasoning (KRR). Among declarative KRR paradigms, Answer Set Programming (ASP) is a well-established formalism developed in the area of logic programming and non-monotonic reasoning. Thanks to the availability of robust and efficient implementations, ASP is successfully employed outside of academia to implement several real-world applications. Recently, ASP gained attention as a basis for SR, and significant steps in this direction have been taken. Several ASP-based solutions have been proposed: some combining SP and ASP implementations into a single engine, others natively extending ASP with SR constructs. However, existing ASP-based stream reasoners appear not mature enough concerning the desirable requirements for SR. This thesis focuses on designing and implementing a novel, reliable ASPbased stream reasoner. The main goal is to obtain a system featuring the following properties: (i) efficiently scale over real-world application domains; (ii) support a language that inherits the highly declarative nature and ease of use from ASP; (iii) easily extendable with new constructs that are relevant for practical SR scenarios. Therefore, we herein present the stream reasoner I-DLVsr. The input language is a straightforward extension of ASP with constructs to reason over data streams. The implementation relies on a tight interaction between two state-of-the-art solutions in ASP and SP: I2-DLV and Apache Flink, respectively. We tested I-DLV-sr on several real-world and synthetic domains to explore its capabilities in modeling SR scenarios and assess its performance. In the conducted experiments, the system obtained good results, proving the viability of the proposed approach and the robustness of the implementation herein presented.Item Crowdshipping in dynamic pickup and delivery problems(Università della Calabria, 2023-11-23) Stoia, Sara; Terracina, Giorgio; Laganà, Demetrio; Vocaturo, FrancescaItem Global Optimization and Fractal Curves(Università della Calabria, 2022-07-13) Nasso, Maria Chiara; Crupi, Felice; Sergeev, YaroslavIl presente lavoro di tesi è principalmente dedicato all'ottimizzazione globale e in particolare a metodi numerici di ottimizzazione globale basati su frattali. Viene affrontato lo studio teorico di alcune curve frattali, vengono proposti nuovi algoritmi che si basano su approcci frattali per ridurre la dimensione del problema e vengono introdotti nuovi metodi di ottimizzazione globale basati sulla tecnica del Local Tuning. Ciascuno dei nuovi metodi proposti è stato implementato e studiato dal punto di vista teorico. Inoltre, gli esperimenti numerici, condotti su diverse centinaia di funzioni test, tratte dalla letteratura e generate in maniera random confermano i vantaggi degli algoritmi presentati.Item Optimizing inventory and distribution in supply chain management(Università della Calabria, 2020-01-13) Paradiso, Rosario; Laganà, Demetrio; Leone, NicolaNella presente tesi di dottorato sono studiati due problemi (e relative generalizzazioni e varianti) di particolare interesse nel campo della Logistica e della Ricerca Operativa. Il primo problema trattato è il Multi Trip Vehicle Routing Problem with TimeWindows (MTVRP). Si tratta di una generalizzazione del classico Vehicle Routing Problem (VRP) in cui ogni veicolo può essere utilizzato più volte durante l’orizzonte di pianificazione. Questa caratteristica, che complica notevolmente il problema, trova applicazione in diversi contesti di last mile deliveries o urban logistics nei quali è preferibile utilizzare vettori elettrici, con limitata capacità di trasporto. Queste caratteristiche si traducono in un numero limitato di visite o in una ridotta lunghezza (temporale o spaziale) delle rotte che questi veicoli possono percorrere, rendendo necessario il riutilizzo degli stessi veicoli nella pianificazione. Nel Capitolo 2 viene proposto un metodo esatto, capace di risolvere cinque diverse varianti del problema che incorporano diverse caratteristiche motivate da applicazioni reali. Per ogni variante, il metodo proposto risulta esse migliore degli algoritmi esatti presenti in letteratura, in termini di tempo computazionale e numero di istanze risolte. Inoltre, per le prima volta vengono risolte istanze fino a 50 clienti. Nel Capitolo 3, viene studiato e definito un problema affine al MTVRP, denominato Installation Planning of Offshore Wind Farm Problem (IPOWF). Il problema nasce nel contesto della costruzione di parchi eolici off-shore: dopo la fase di progettazione in cui vengono definite tutte le specifiche (numero, tipo e posizione delle turbine), il parco deve essere costruito avendo a disposizione una flotta di vascelli che vengono utilizzati per eseguire le operazioni necessarie alla costruzione di ogni turbina. L’obbiettivo è schedulare le operazioni e definire le rotte dei vascelli in modo da completare il parco, minimizzando il costo dovuto all’utilizzo dei vascelli stessi (costo di noleggio) e il costo di mancata produzione energetica derivante dalle turbine non completate. Inoltre, le condizioni meteo devono essere tenute in considerazione, dal momento che alcune operazioni possono essere eseguite solo in presenza di condizioni controllate di agitazione ondosa. La fase di definizione delle rotte dei vascelli risulta, di fatto, un MTVRP dal momento che i vascelli hanno bisogno di tornare nel porto di provenienza per caricare risorse, prima di procedere verso la turbina successiva. Il problema è stato studiato in collaborazione con Vattenfall, una delle maggiore aziende a livello mondiale operanti nel settore. Grazie a questa collaborazione è stato possibile e testare l’approccio su dati reali. Per risolvere il problema sono stati definiti dei modelli di programmazione lineare intera (Mixed Integer Linear Programming models, MILPs). Alcuni di questi sono utilizzati per trovare soluzioni ammissibili in tempi ragionevoli. Le ipotesi alla base di tali modelli non incidono sull’ammissibilità delle soluzioni del problema originario. Tuttavia, per valutare la qualità delle soluzioni sono definiti dei modelli di lower bound basati su rilassamenti del problema. L’approccio è in grado di fornire soluzioni con gap di ottimalità inferiori del 2%. I Capitoli 4 e 5 sono dedicati al secondo problema trattato in questa tesi, ovvero a una variante del classico Inventory Routing Problem (IRP). IRP è il problema di ottimizzazione sotteso al paradigma gestionale Vendor Management System, una politica di gestione di parte della catena logistica in cui il vendor ha il controllo dei livelli di inventario dei propri clienti e del relativo rifornimento, assicurando il soddisfacimento della domanda. Si tratta quindi di un problema in cui decisioni relative al livello di inventario e al trasporto vengono prese in modo integrato al fine di minimizzare i costi del sistema. L’IRP è un problema definito su un orizzonte temporale finito e su una rete logistica caratterizzata da un nodo vendor (deposito o impianto di produzione) e da un insieme di nodi clienti che "consumano" un prodotto ad un tasso noto, e che devono essere riforniti per non andare in stock out. Anche il tasso di produzione dei prodotti presso il vendor è noto. La domanda presso i clienti deve essere soddisfatta utilizzando le quantità rese disponibili dal vendor che sono distribuite mediante una flotta di veicoli capacitati, posizionati presso il vendor stesso. Inoltre, sia clienti che il vendor possono accumulare scorte di inventario senza eccedere una capacità massima. L’obbiettivo è quello di stabilire le rotte dei veicoli e le quantità da trasportare presso i clienti durante il periodo di pianificazione, garantendo il soddisfacimento della domanda per ogni periodo e minimizzando il costo di trasporto e il costo di inventario totale (presso i clienti e presso il vendor). In questa tesi, viene studiata una versione di IRP in cui la pianificazione periodica è fatta su un intervallo di tempo "illimitato". Questo tipo di problema viene generalmente identificato come il Cyclic Inventory Routing Problem (CIRP). La pianificazione periodica è tipica nei sistemi nei produzione in cui si cerca di standardizzare le operazioni. Sistemi logistici che sposano politiche manageriali di lean production ne sono un esempio. Nel Capitolo 4 viene studiata una variante del CIRP. Per questo problema viene proposto un algoritmo esatto di branch-and-cut capace di risolvere istanze fino a 50 clienti. Nel Capitolo 5 vengono proposte delle classi di math-euristiche (matheuristic) per risolvere il CIRP mediante la risoluzione di una formulazione basata su variabili di rotta. Le rotte sono definite a priori risolvendo dei VRPs. Per le rotte generate sono definiti dei rapporti di prestazione. L’approccio proposto viene comparato con le soluzioni e i lower bounds forniti da un algoritmo esatto di branchand- cut che risolve una formulazione basata su variabili di flusso. I risultati mostrano che l’approccio basato sulle classi di math-eurisitche è in grado di fornire soluzioni di alta qualità, molto spesso migliori di quelle fornite dall’algoritmo di branch-and-cut, con tempi computazoinali contenuti.