Decomposition and reformulation of integer linear programming problems

This thesis deals with an investigation of Decomposition and Reformulation to solve Integer Linear Programming Problems. This method is often a very successful approach computationally, producing high-quality solutions for well-structured combinatorial optimization problems like vehicle routing, cutting stock, p-median and generalized assignment . However, until now the method has always been tailored to the specific problem under investigation. The principal innovation of this thesis is to develop a new framework able to apply this concept to a generic MIP problem. The new approach is thus capable of auto-decomposition and autoreformulation of the input problem applicable as a resolving black box algorithm and works as a complement and alternative to the normal resolving techniques. The idea of Decomposing and Reformulating (usually called in literature Dantzig and Wolfe Decomposition DWD) is, given a MIP, to convexify one (or more) subset(s) of constraints (slaves) and working on the partially convexified polyhedron(s) obtained. For a given MIP several decompositions can be defined depending from what sets of constraints we want to convexify. In this thesis we mainly reformulate MIPs using two sets of variables: the original variables and the extended variables (representing the exponential extreme points). The master constraints consist of the original constraints not included in any slaves plus the convexity constraint(s) and the linking constraints(ensuring that each original variable can be viewed as linear combination of extreme points of the slaves). The solution procedure consists of iteratively solving the reformulated MIP (master) and checking (pricing) if a variable of reduced costs exists, and in which case adding it to the master and solving it again (columns generation), or otherwise stopping the procedure. The advantage of using DWD is that the reformulated relaxation gives bounds stronger than the original LP relaxation, in addition it can be incorporated in a Branch and bound scheme (Branch and Price) in order to solve the problem to optimality. If the computational time for the pricing problem is reasonable this leads in practice to a stronger speed up in the solution time, specially when the convex hull of the slaves is easy to compute, usually because of its special structure.

Algorithms for UAS insertion in civil air space

One of the most interesting challenge of the next years will be the Air Space Systems automation. This process will involve different aspects as the Air Traffic Management, the Aircrafts and Airport Operations and the Guidance and Navigation Systems. The use of UAS (Uninhabited Aerial System) for civil mission will be one of the most important steps in this automation process. In civil air space, Air Traffic Controllers (ATC) manage the air traffic ensuring that a minimum separation between the controlled aircrafts is always provided. For this purpose ATCs use several operative avoidance techniques like holding patterns or rerouting. The use of UAS in these context will require the definition of strategies for a common management of piloted and piloted air traffic that allow the UAS to self separate. As a first employment in civil air space we consider a UAS surveillance mission that consists in departing from a ground base, taking pictures over a set of mission targets and coming back to the same ground base. During all mission a set of piloted aircrafts fly in the same airspace and thus the UAS has to self separate using the ATC avoidance as anticipated. We consider two objective, the first consists in the minimization of the air traffic impact over the mission, the second consists in the minimization of the impact of the mission over the air traffic. A particular version of the well known Travelling Salesman Problem (TSP) called Time-Dependant-TSP has been studied to deal with traffic problems in big urban areas. Its basic idea consists in a cost of the route between two clients depending on the period of the day in which it is crossed. Our thesis supports that such idea can be applied to the air traffic too using a convenient time horizon compatible with aircrafts operations. The cost of a UAS sub-route will depend on the air traffic that it will meet starting such route in a specific moment and consequently on the avoidance maneuver that it will use to avoid that conflict. The conflict avoidance is a topic that has been hardly developed in past years using different approaches. In this thesis we purpose a new approach based on the use of ATC operative techniques that makes it possible both to model the UAS problem using a TDTSP framework both to use an Air Traffic Management perspective. Starting from this kind of mission, the problem of the UAS insertion in civil air space is formalized as the UAS Routing Problem (URP). For this reason we introduce a new structure called Conflict Graph that makes it possible to model the avoidance maneuvers and to define the arc cost function of the departing time. Two Integer Linear Programming formulations of the problem are proposed. The first is based on a TDTSP formulation that, unfortunately, is weaker then the TSP formulation. Thus a new formulation based on a TSP variation that uses specific penalty to model the holdings is proposed. Different algorithms are presented: exact algorithms, simple heuristics used as Upper Bounds on the number of time steps used, and metaheuristic algorithms as Genetic Algorithm and Simulated Annealing. Finally an air traffic scenario has been simulated using real air traffic data in order to test our algorithms. Graphic Tools have been used to represent the Milano Linate air space and its air traffic during different days. Such data have been provided by ENAV S.p.A (Italian Agency for Air Navigation Services).

A novel map-matching procedure for low-sampling GPS data with applications to traffic flow analysis

An extensive sample (2%) of private vehicles in Italy are equipped with a GPS device that periodically measures their position and dynamical state for insurance purposes. Having access to this type of data allows to develop theoretical and practical applications of great interest: the real-time reconstruction of traffic state in a certain region, the development of accurate models of vehicle dynamics, the study of the cognitive dynamics of drivers. In order for these applications to be possible, we first need to develop the ability to reconstruct the paths taken by vehicles on the road network from the raw GPS data. In fact, these data are affected by positioning errors and they are often very distanced from each other (~2 Km). For these reasons, the task of path identification is not straightforward. This thesis describes the approach we followed to reliably identify vehicle paths from this kind of low-sampling data. The problem of matching data with roads is solved with a bayesian approach of maximum likelihood. While the identification of the path taken between two consecutive GPS measures is performed with a specifically developed optimal routing algorithm, based on A* algorithm. The procedure was applied on an off-line urban data sample and proved to be robust and accurate. Future developments will extend the procedure to real-time execution and nation-wide coverage.

Reliable and Variation-Tolerant Interconnection Network for Low Power MPSOCS

Multi-Processor SoC (MPSOC) design brings to the foreground a large number of challenges, one of the most prominent of which is the design of the chip interconnection. With a number of on-chip blocks presently ranging in the tens, and quickly approaching the hundreds, the novel issue of how to best provide on-chip communication resources is clearly felt. Scaling down of process technologies has increased process and dynamic variations as well as transistor wearout. Because of this, delay variations increase and impact the performance of the MPSoCs. The interconnect architecture inMPSoCs becomes a single point of failure as it connects all other components of the system together. A faulty processing element may be shut down entirely, but the interconnect architecture must be able to tolerate partial failure and variations and operate with performance, power or latency overhead. This dissertation focuses on techniques at different levels of abstraction to face with the reliability and variability issues in on-chip interconnection networks. By showing the test results of a GALS NoC testchip this dissertation motivates the need for techniques to detect and work around manufacturing faults and process variations in MPSoCs’ interconnection infrastructure. As a physical design technique, we propose the bundle routing framework as an effective way to route the Network on Chips’ global links. For architecture-level design, two cases are addressed: (I) Intra-cluster communication where we propose a low-latency interconnect with variability robustness (ii) Inter-cluster communication where an online functional testing with a reliable NoC configuration are proposed. We also propose dualVdd as an orthogonal way of compensating variability at the post-fabrication stage. This is an alternative strategy with respect to the design techniques, since it enforces the compensation at post silicon stage.

Analisi e ottimizzazione del servizio di raccolta e trasporto dei rifiuti anche in relazione alle tematiche ambientali: un'applicazione alla rete urbana di Bologna

Questo studio, che è stato realizzato in collaborazione con Hera, è un'analisi della gestione dei rifiuti a Bologna. La ricerca è stata effettuata su diversi livelli: un livello strategico il cui scopo è quello di identificare nuovi metodi per la raccolta dei rifiuti in funzione delle caratteristiche del territorio della città, un livello analitico che riguarda il miglioramento delle applicazioni informatiche di supporto, e livello ambientale che riguarda il calcolo delle emissioni in atmosfera di veicoli adibiti alla raccolta e al trasporto dei rifiuti. innanzitutto è stato necessario studiare Bologna e lo stato attuale dei servizi di raccolta dei rifiuti. È incrociando questi componenti che in questi ultimi tre anni sono state effettuate modifiche nel settore della gestione dei rifiuti. I capitoli seguenti sono inerenti le applicazioni informatiche a sostegno di tali attività: Siget e Optit. Siget è il programma di gestione del servizio, che attualmente viene utilizzato per tutte le attività connesse alla raccolta di rifiuti. È un programma costituito da moduli diversi, ma di sola la gestione dati. la sperimentazione con Optit ha aggiunto alla gestione dei dati la possibilità di avere tali dati in cartografia e di associare un algoritmo di routing. I dati archiviati in Siget hanno rappresentato il punto di partenza, l'input, e il raggiungimento di tutti punti raccolta l'obiettivo finale. L'ultimo capitolo è relativo allo studio dell'impatto ambientale di questi percorsi di raccolta dei rifiuti. Tale analisi, basata sulla valutazione empirica e sull'implementazione in Excel delle formule del Corinair mostra la fotografia del servizio nel 2010. Su questo aspetto Optit ha fornito il suo valore aggiunto, implementando nell'algoritmo anche le formule per il calcolo delle emissioni.

Ribosome-inactivating proteins and their immunotoxins for cancer therapy: insights into the mechanism of cell death

Ribosome-inactivating proteins (RIPs) are a family of plant toxic enzymes that permanently damage ribosomes and possibly other cellular substrates, thus causing cell death involving different and still not completely understood pathways. The high cytotoxic activity showed by many RIPs makes them ideal candidates for the production of immunotoxins (ITs), chimeric proteins designed for the selective elimination of unwanted or malignant cells. Saporin-S6, a type 1 RIP extracted from Saponaria officinalis L. seeds, has been extensively employed to construct anticancer conjugates because of its high enzymatic activity, stability and resistance to conjugation procedures, resulting in the efficient killing of target cells. Here we investigated the anticancer properties of two saporin-based ITs, anti-CD20 RTX/S6 and anti-CD22 OM124/S6, designed for the experimental treatment of B-cell NHLs. Both ITs showed high cytotoxicity towards CD20-positive B-cells, and their antitumor efficacy was enhanced synergistically by a combined treatment with proteasome inhibitors or fludarabine. Furthermore, the two ITs showed differencies in potency and ability to activate effector caspases, and a different behavior in the presence of the ROS scavenger catalase. Taken together, these results suggest that the different carriers employed to target saporin might influence saporin intracellular routing and saporin-induced cell death mechanisms. We also investigated the early cellular response to stenodactylin, a recently discovered highly toxic type 2 RIP representing an interesting candidate for the design and production of a new IT for the experimental treatment of cancer.

Many-core Algorithms for Combinatorial Optimization

Combinatorial Optimization is becoming ever more crucial, in these days. From natural sciences to economics, passing through urban centers administration and personnel management, methodologies and algorithms with a strong theoretical background and a consolidated real-word effectiveness is more and more requested, in order to find, quickly, good solutions to complex strategical problems. Resource optimization is, nowadays, a fundamental ground for building the basements of successful projects. From the theoretical point of view, Combinatorial Optimization rests on stable and strong foundations, that allow researchers to face ever more challenging problems. However, from the application point of view, it seems that the rate of theoretical developments cannot cope with that enjoyed by modern hardware technologies, especially with reference to the one of processors industry. In this work we propose new parallel algorithms, designed for exploiting the new parallel architectures available on the market. We found that, exposing the inherent parallelism of some resolution techniques (like Dynamic Programming), the computational benefits are remarkable, lowering the execution times by more than an order of magnitude, and allowing to address instances with dimensions not possible before. We approached four Combinatorial Optimization’s notable problems: Packing Problem, Vehicle Routing Problem, Single Source Shortest Path Problem and a Network Design problem. For each of these problems we propose a collection of effective parallel solution algorithms, either for solving the full problem (Guillotine Cuts and SSSPP) or for enhancing a fundamental part of the solution method (VRP and ND). We endorse our claim by presenting computational results for all problems, either on standard benchmarks from the literature or, when possible, on data from real-world applications, where speed-ups of one order of magnitude are usually attained, not uncommonly scaling up to 40 X factors.

Distributed Large-scale Mixed-Integer Optimization with Application to Energy and Multi-robot Networks

Several decision and control tasks in cyber-physical networks can be formulated as large- scale optimization problems with coupling constraints. In these "constraint-coupled" problems, each agent is associated to a local decision variable, subject to individual constraints. This thesis explores the use of primal decomposition techniques to develop tailored distributed algorithms for this challenging set-up over graphs. We first develop a distributed scheme for convex problems over random time-varying graphs with non-uniform edge probabilities. The approach is then extended to unknown cost functions estimated online. Subsequently, we consider Mixed-Integer Linear Programs (MILPs), which are of great interest in smart grid control and cooperative robotics. We propose a distributed methodological framework to compute a feasible solution to the original MILP, with guaranteed suboptimality bounds, and extend it to general nonconvex problems. Monte Carlo simulations highlight that the approach represents a substantial breakthrough with respect to the state of the art, thus representing a valuable solution for new toolboxes addressing large-scale MILPs. We then propose a distributed Benders decomposition algorithm for asynchronous unreliable networks. The framework has been then used as starting point to develop distributed methodologies for a microgrid optimal control scenario. We develop an ad-hoc distributed strategy for a stochastic set-up with renewable energy sources, and show a case study with samples generated using Generative Adversarial Networks (GANs). We then introduce a software toolbox named ChoiRbot, based on the novel Robot Operating System 2, and show how it facilitates simulations and experiments in distributed multi-robot scenarios. Finally, we consider a Pickup-and-Delivery Vehicle Routing Problem for which we design a distributed method inspired to the approach of general MILPs, and show the efficacy through simulations and experiments in ChoiRbot with ground and aerial robots.

Development of predictive energy management strategies for hybrid electric vehicles supported by connectivity

Nowadays, the spreading of the air pollution crisis enhanced by greenhouse gases emission is leading to the worsening of the global warming. In this context, the transportation sector plays a vital role, since it is responsible for a large part of carbon dioxide production. In order to address these issues, the present thesis deals with the development of advanced control strategies for the energy efficiency optimization of plug-in hybrid electric vehicles (PHEVs), supported by the prediction of future working conditions of the powertrain. In particular, a Dynamic Programming algorithm has been developed for the combined optimization of vehicle energy and battery thermal management. At this aim, the battery temperature and the battery cooling circuit control signal have been considered as an additional state and control variables, respectively. Moreover, an adaptive equivalent consumption minimization strategy (A-ECMS) has been modified to handle zero-emission zones, where engine propulsion is not allowed. Navigation data represent an essential element in the achievement of these tasks. With this aim, a novel simulation and testing environment has been developed during the PhD research activity, as an effective tool to retrieve routing information from map service providers via vehicle-to-everything connectivity. Comparisons between the developed and the reference strategies are made, as well, in order to assess their impact on the vehicle energy consumption. All the activities presented in this doctoral dissertation have been carried out at the Green Mobility Research Lab} (GMRL), a research center resulting from the partnership between the University of Bologna and FEV Italia s.r.l., which represents the industrial partner of the research project.

Wireless Network Analytics for Next Generation Spectrum Awareness

The importance of networks, in their broad sense, is rapidly and massively growing in modern-day society thanks to unprecedented communication capabilities offered by technology. In this context, the radio spectrum will be a primary resource to be preserved and not wasted. Therefore, the need for intelligent and automatic systems for in-depth spectrum analysis and monitoring will pave the way for a new set of opportunities and potential challenges. This thesis proposes a novel framework for automatic spectrum patrolling and the extraction of wireless network analytics. It aims to enhance the physical layer security of next generation wireless networks through the extraction and the analysis of dedicated analytical features. The framework consists of a spectrum sensing phase, carried out by a patrol composed of numerous radio-frequency (RF) sensing devices, followed by the extraction of a set of wireless network analytics. The methodology developed is blind, allowing spectrum sensing and analytics extraction of a network whose key features (i.e., number of nodes, physical layer signals, medium access protocol (MAC) and routing protocols) are unknown. Because of the wireless medium, over-the-air signals captured by the sensors are mixed; therefore, blind source separation (BSS) and measurement association are used to estimate the number of sources and separate the traffic patterns. After the separation, we put together a set of methodologies for extracting useful features of the wireless network, i.e., its logical topology, the application-level traffic patterns generated by the nodes, and their position. The whole framework is validated on an ad-hoc wireless network accounting for MAC protocol, packet collisions, nodes mobility, the spatial density of sensors, and channel impairments, such as path-loss, shadowing, and noise. The numerical results obtained by extensive and exhaustive simulations show that the proposed framework is consistent and can achieve the required performance.

Automated service provisioning in programmable network infrastructures

Modern networks are undergoing a fast and drastic evolution, with software taking a more predominant role. Virtualization and cloud-like approaches are replacing physical network appliances, reducing the management burden of the operators. Furthermore, networks now expose programmable interfaces for fast and dynamic control over traffic forwarding. This evolution is backed by standard organizations such as ETSI, 3GPP, and IETF. This thesis will describe which are the main trends in this evolution. Then, it will present solutions developed during the three years of Ph.D. to exploit the capabilities these new technologies offer and to study their possible limitations to push further the state-of-the-art. Namely, it will deal with programmable network infrastructure, introducing the concept of Service Function Chaining (SFC) and presenting two possible solutions, one with Openstack and OpenFlow and the other using Segment Routing and IPv6. Then, it will continue with network service provisioning, presenting concepts from Network Function Virtualization (NFV) and Multi-access Edge Computing (MEC). These concepts will be applied to network slicing for mission-critical communications and Industrial IoT (IIoT). Finally, it will deal with network abstraction, with a focus on Intent Based Networking (IBN). To summarize, the thesis will include solutions for data plane programming with evaluation on well-known platforms, performance metrics on virtual resource allocations, novel practical application of network slicing on mission-critical communications, an architectural proposal and its implementation for edge technologies in Industrial IoT scenarios, and a formal definition of intent using a category theory approach.

Analytics and optimization for emergency healthcare processes

This thesis deals with the analysis and management of emergency healthcare processes through the use of advanced analytics and optimization approaches. Emergency processes are among the most complex within healthcare. This is due to their non-elective nature and their high variability. This thesis is divided into two topics. The first one concerns the core of emergency healthcare processes, the emergency department (ED). In the second chapter, we describe the ED that is the case study. This is a real case study with data derived from a large ED located in northern Italy. In the next two chapters, we introduce two tools for supporting ED activities. The first one is a new type of analytics model. Its aim is to overcome the traditional methods of analyzing the activities provided in the ED by means of an algorithm that analyses the ED pathway (organized as event log) as a whole. The second tool is a decision-support system, which integrates a deep neural network for the prediction of patient pathways, and an online simulator to evaluate the evolution of the ED over time. Its purpose is to provide a set of solutions to prevent and solve the problem of the ED overcrowding. The second part of the thesis focuses on the COVID-19 pandemic emergency. In the fifth chapter, we describe a tool that was used by the Bologna local health authority in the first part of the pandemic. Its purpose is to analyze the clinical pathway of a patient and from this automatically assign them a state. Physicians used the state for routing the patients to the correct clinical pathways. The last chapter is dedicated to the description of a MIP model, which was used for the organization of the COVID-19 vaccination campaign in the city of Bologna, Italy.

Ship performance modelling for least-CO2 emission routes

Decarbonization of maritime transport requires immediate action. In the short term, ship weather routing can provide greenhouse gas emission reductions, even for existing ships and without retrofitting them. Weather routing is based on making optimal use of both envi- ronmental information and knowledge about vessel seakeeping and performance. Combining them at a state-of-the-art level and making use of path planning in realistic conditions can be challenging. To address these topics in an open-source framework, this thesis led to the development of a new module called bateau , and to its combination with the ship routing model VISIR. bateau includes both hull geometry and propulsion modelling for various vessel types. It has two objectives: to predict the sustained speed in a seaway and to estimate the CO2 emission rate during the voyage. Various semi-empirical approaches were used in bateau to predict the ship hydro- and aerodynamical resistance in both head and oblique seas. Assuming that the ship sails at a constant engine load, the involuntary speed loss due to waves was estimated. This thesis also attempted to clarify the role played by the actual representation of the sea state. In particular, the influence of the wave steepness parameter was assessed. For dealing with ships with a greater superstructure, the wind added resistance was also estimated. Numerical experiments via bateau were conducted for both a medium and a large-size container ships, a bulk-carrier, and a tanker. The simulations of optimal routes were carried out for a feeder containership during voyages in the North Indian Ocean and in the South China Sea. Least-CO2 routes were compared to the least-distance ones, assessing the relative CO2 savings. Analysis fields from the Copernicus Marine Service were used in the numerical experiments.

Uncovering the encoding and transmission of behaviourally relevant information in neural activity

Most cognitive functions require the encoding and routing of information across distributed networks of brain regions. Information propagation is typically attributed to physical connections existing between brain regions, and contributes to the formation of spatially correlated activity patterns, known as functional connectivity. While structural connectivity provides the anatomical foundation for neural interactions, the exact manner in which it shapes functional connectivity is complex and not yet fully understood. Additionally, traditional measures of directed functional connectivity only capture the overall correlation between neural activity, and provide no insight on the content of transmitted information, limiting their ability in understanding neural computations underlying the distributed processing of behaviorally-relevant variables. In this work, we first study the relationship between structural and functional connectivity in simulated recurrent spiking neural networks with spike timing dependent plasticity. We use established measures of time-lagged correlation and overall information propagation to infer the temporal evolution of synaptic weights, showing that measures of dynamic functional connectivity can be used to reliably reconstruct the evolution of structural properties of the network. Then, we extend current methods of directed causal communication between brain areas, by deriving an information-theoretic measure of Feature-specific Information Transfer (FIT) quantifying the amount, content and direction of information flow. We test FIT on simulated data, showing its key properties and advantages over traditional measures of overall propagated information. We show applications of FIT to several neural datasets obtained with different recording methods (magneto and electro-encephalography, spiking activity, local field potentials) during various cognitive functions, ranging from sensory perception to decision making and motor learning. Overall, these analyses demonstrate the ability of FIT to advance the investigation of communication between brain regions, uncovering the previously unaddressed content of directed information flow.