Algorithms for network design and routing problems

In this thesis we study three combinatorial optimization problems belonging to the classes of Network Design and Vehicle Routing problems that are strongly linked in the context of the design and management of transportation networks: the Non-Bifurcated Capacitated Network Design Problem (NBP), the Period Vehicle Routing Problem (PVRP) and the Pickup and Delivery Problem with Time Windows (PDPTW). These problems are NP-hard and contain as special cases some well known difficult problems such as the Traveling Salesman Problem and the Steiner Tree Problem. Moreover, they model the core structure of many practical problems arising in logistics and telecommunications. The NBP is the problem of designing the optimum network to satisfy a given set of traffic demands. Given a set of nodes, a set of potential links and a set of point-to-point demands called commodities, the objective is to select the links to install and dimension their capacities so that all the demands can be routed between their respective endpoints, and the sum of link fixed costs and commodity routing costs is minimized. The problem is called non- bifurcated because the solution network must allow each demand to follow a single path, i.e., the flow of each demand cannot be splitted. Although this is the case in many real applications, the NBP has received significantly less attention in the literature than other capacitated network design problems that allow bifurcation. We describe an exact algorithm for the NBP that is based on solving by an integer programming solver a formulation of the problem strengthened by simple valid inequalities and four new heuristic algorithms. One of these heuristics is an adaptive memory metaheuristic, based on partial enumeration, that could be applied to a wider class of structured combinatorial optimization problems. In the PVRP a fleet of vehicles of identical capacity must be used to service a set of customers over a planning period of several days. Each customer specifies a service frequency, a set of allowable day-combinations and a quantity of product that the customer must receive every time he is visited. For example, a customer may require to be visited twice during a 5-day period imposing that these visits take place on Monday-Thursday or Monday-Friday or Tuesday-Friday. The problem consists in simultaneously assigning a day- combination to each customer and in designing the vehicle routes for each day so that each customer is visited the required number of times, the number of routes on each day does not exceed the number of vehicles available, and the total cost of the routes over the period is minimized. We also consider a tactical variant of this problem, called Tactical Planning Vehicle Routing Problem, where customers require to be visited on a specific day of the period but a penalty cost, called service cost, can be paid to postpone the visit to a later day than that required. At our knowledge all the algorithms proposed in the literature for the PVRP are heuristics. In this thesis we present for the first time an exact algorithm for the PVRP that is based on different relaxations of a set partitioning-like formulation. The effectiveness of the proposed algorithm is tested on a set of instances from the literature and on a new set of instances. Finally, the PDPTW is to service a set of transportation requests using a fleet of identical vehicles of limited capacity located at a central depot. Each request specifies a pickup location and a delivery location and requires that a given quantity of load is transported from the pickup location to the delivery location. Moreover, each location can be visited only within an associated time window. Each vehicle can perform at most one route and the problem is to satisfy all the requests using the available vehicles so that each request is serviced by a single vehicle, the load on each vehicle does not exceed the capacity, and all locations are visited according to their time window. We formulate the PDPTW as a set partitioning-like problem with additional cuts and we propose an exact algorithm based on different relaxations of the mathematical formulation and a branch-and-cut-and-price algorithm. The new algorithm is tested on two classes of problems from the literature and compared with a recent branch-and-cut-and-price algorithm from the literature.

I fattori alla base dell'instabilità dei prezzi agricoli sui mercati internazionali

Fra il 2006 e il 2008, molte commodity hanno fatto registrare rapidi e intensi aumenti di prezzo sui mercati internazionali. Fra queste, anche alcuni prodotti agricoli alla base dell’alimentazione umana. Il presente lavoro concentra l’attenzione su alcune commodity - frumento, riso, mais e semi di soia - riportando le loro quotazioni mensili a partire dal 2002, quindi con un largo anticipo rispetto al manifestarsi del fenomeno. L’obiettivo principale del lavoro è offrire una valida interpretazione dell’instabilità de prezzo di questi prodotti, individuando i fattori che sono alla base della volatilità e sottolineandone le implicazioni economiche e politiche a livello globale. La metodologia usata è duplice e composta da un’attenta analisi descrittiva dei fattori che hanno agito sulla domanda e sull’offerta dei prodotti in questione e un’analisi quantitativa, facendo ricorso alle tecniche statistiche proprie delle serie storiche.

Le scelte di investimento delle aziende agricole e la PAC post-2013: valutazione di scenari mediante un modello real options

Negli ultimi decenni la Politica Agricola Comune (PAC) è stata sottoposta a diverse revisioni, più o meno programmate, che ne hanno modificato gli obiettivi operativi e gli strumenti per perseguirli. In letteratura economica agraria sono state eseguite diverse ricerche che affrontano analisi ex-ante sui possibili impatti delle riforme politiche, in particolare al disaccoppiamento, riguardo all’allocazione dei terreni alle diverse colture e all’adozione di tecniche di coltivazione più efficienti. Ma tale argomento, nonostante sia di grande importanza, non è stato finora affrontato come altri temi del mondo agricolo. Le principali lacune si riscontrano infatti nella carenza di analisi ex-ante, di modelli che includano le preferenze e le aspettative degli agricoltori. Questo studio valuta le scelte di investimento in terreno di un’azienda agricola di fronte a possibili scenari PAC post-2013, in condizioni di incertezza circa le specifiche condizioni in cui ciascuno scenario verrebbe a verificarsi. L’obiettivo è di ottenere indicazioni utili in termini di comprensione delle scelte di investimento dell’agricoltore in presenza di incertezza sul futuro. L’elemento maggiormente innovativo della ricerca consiste nell’applicazione di un approccio real options e nell’interazione tra la presenza di diversi scenari sul futuro del settore agricolo post-2013, e la componente di incertezza che incide e gravita su di essi. La metodologia adottata nel seguente lavoro si basa sulla modellizzazione di un’azienda agricola, in cui viene simulato il comportamento dell’azienda agricola in reazione alle riforme della PAC e alla variazione dei prezzi dei prodotti in presenza di incertezza. Mediante un modello di Real Option viene valutata la scelta della tempistica ottimale per investire nell’acquisto di terreno (caratterizzato da incertezza e irreversibilità). Dai risultati emerge come in presenza di incertezza all’agricoltore convenga rimandare la decisione a dopo il 2013 e in base alle maggiori informazioni disponibili eseguire l’investimento solo in presenza di condizioni favorevoli. La variazione dei prezzi dei prodotti influenza le scelte più dell’incertezza dei contributi PAC. Il Real Option sembra interpretare meglio il comportamento dell’agricoltore rispetto all’approccio classico del Net Present Value.

Chemical analysis and reactivity of biomass pyrolysis products. Application to the development of carbon-neutral biofuels and chemicals

In this dissertation the pyrolytic conversion of biomass into chemicals and fuels was investigated from the analytical point of view. The study was focused on the liquid (bio-oil) and solid (char) fractions obtainable from biomass pyrolysis. The drawbacks of Py-GC-MS described so far were partially solved by coupling different analytical configurations (Py-GC-MS, Py-GC-MIP-AED and off-line Py-SPE and Py-SPME-GC-MS with derivatization procedures). The application of different techniques allowed a satisfactory comparative analysis of pyrolysis products of different biomass and a high throughput screening on effect of 33 catalysts on biomass pyrolysis. As the results of the screening showed, the most interesting catalysts were those containing copper (able to reduce the high molecular weight fraction of bio-oil without large yield decrease) and H-ZSM-5 (able to entirely convert the bio-oil into “gasoline like” aromatic products). In order to establish the noxious compounds content of the liquid product, a clean-up step was included in the Py-SPE procedure. This allowed to investigate pollutants (PAHs) generation from pyrolysis and catalytic pyrolysis of biomass. In fact, bio-oil from non-catalytic pyrolysis of biomass showed a moderate PAHs content, while the use of H-ZSM-5 catalyst for bio-oil up-grading determined an astonishing high production of PAHs (if compared to what observed in alkanes cracking), indicating an important concern in the substitution fossil fuel with bio-oil derived from biomass. Moreover, the analytical procedures developed in this thesis were directly applied for the detailed study of the most useful process scheme and up-grading route to chemical intermediates (anhydrosugars), transportation fuels or commodity chemicals (aromatic hydrocarbons). In the applied study, poplar and microalgae biomass were investigated and overall GHGs balance of pyrolysis of agricultural residues in Ravenna province was performed. A special attention was put on the comparison of the effect of bio-char different use (fuel or as soil conditioner) on the soil health and GHGs emissions.

Heterogeneous multicore systems for signal processing

This thesis explores the capabilities of heterogeneous multi-core systems, based on multiple Graphics Processing Units (GPUs) in a standard desktop framework. Multi-GPU accelerated desk side computers are an appealing alternative to other high performance computing (HPC) systems: being composed of commodity hardware components fabricated in large quantities, their price-performance ratio is unparalleled in the world of high performance computing. Essentially bringing “supercomputing to the masses”, this opens up new possibilities for application fields where investing in HPC resources had been considered unfeasible before. One of these is the field of bioelectrical imaging, a class of medical imaging technologies that occupy a low-cost niche next to million-dollar systems like functional Magnetic Resonance Imaging (fMRI). In the scope of this work, several computational challenges encountered in bioelectrical imaging are tackled with this new kind of computing resource, striving to help these methods approach their true potential. Specifically, the following main contributions were made: Firstly, a novel dual-GPU implementation of parallel triangular matrix inversion (TMI) is presented, addressing an crucial kernel in computation of multi-mesh head models of encephalographic (EEG) source localization. This includes not only a highly efficient implementation of the routine itself achieving excellent speedups versus an optimized CPU implementation, but also a novel GPU-friendly compressed storage scheme for triangular matrices. Secondly, a scalable multi-GPU solver for non-hermitian linear systems was implemented. It is integrated into a simulation environment for electrical impedance tomography (EIT) that requires frequent solution of complex systems with millions of unknowns, a task that this solution can perform within seconds. In terms of computational throughput, it outperforms not only an highly optimized multi-CPU reference, but related GPU-based work as well. Finally, a GPU-accelerated graphical EEG real-time source localization software was implemented. Thanks to acceleration, it can meet real-time requirements in unpreceeded anatomical detail running more complex localization algorithms. Additionally, a novel implementation to extract anatomical priors from static Magnetic Resonance (MR) scansions has been included.

Il corpo e l'individuo tra proprietà ed autodeterminazione. Con particolare riferimento al fenomeno delle biobanche

La bioetica è il luogo ideale per cercare risposte ai grandi interrogativi concernenti la vita, la morte e la cura dell'essere umano. I recenti dibattiti sull'uso, ed il temuto abuso, del corpo umano in medicina hanno messo in evidenza la necessità di una discussione approfondita sul potere di scelta che l'individuo può esercitare sulla propria mente e sul proprio corpo. Spinta dal desidero di indagare l'estensione di tale potere di scelta ho voluto analizzare le tematiche riguardanti “il corpo”, “l'individuo”, “la proprietà” e “l'autodeterminazione”. L'analisi è stata condotta individuando alcuni dei differenti significati che questi termini assumono nei diversi ambiti che la bioetica lambisce e mostrando, in particolare, la visione di tale realtà attraverso le lenti del giurista. A chi appartiene il corpo? Chi ha il potere di decidere su di esso? Il potere di scelta valica gli antichi i confini legati al corpo del paziente e coinvolge tessuti, organi e cellule staccati dal corpo umano, parti che un tempo erano considerati scarti operatori sono oggi divenuti tesori inestimabili per la ricerca. L'importanza assunta dai campioni biologici ha portato alla creazione di biobanche nelle quali sono raccolti, catalogati e il DNA studiato in campioni biologici Le biobanche riflettono le tensioni della bioetica e del biodititto. Lo studio delle biobanche riguarda, tra l'altro, la riceca dell'equilibrio tra le diverse esigenze meritevoli di tutela: in primo luogo il diritto alla privacy, diritto a che le “proprie informazioni” non vengano divulgate ed il diritto a non essere discriminato ed in secondo luogo le necessità dettate dalla ricerca e dalla scienza medica. Nel 2009 la rivista Times messo biobanche tra le 10 idee in grado di cambiare il mondo anche in considarazione della medicina personalizzata e del fatto che costituiscono una la speranza per la ricerca contro le malattie attuali e future.

A new global wheat marketmodel (GLOWMM) for the analysis of wheat export prices

Food commodity prices fluctuations have important impacts on poverty and food insecurity across the world. Conventional models have not provided a complete picture of recent price spikes in agricultural commodity markets, while there is an urgent need for appropriate policy responses. Perhaps new approaches are needed in order to better understand international spill-overs, the feedback between the real and the financial sectors and also the link between food and energy prices. In this paper, we present results from a new worldwide dynamic model that provides short and long-run impulse responses of wheat international prices to various real shocks.

Heterogeneous Multi-core Architectures for High Performance Computing

This thesis deals with heterogeneous architectures in standard workstations. Heterogeneous architectures represent an appealing alternative to traditional supercomputers because they are based on commodity components fabricated in large quantities. Hence their price-performance ratio is unparalleled in the world of high performance computing (HPC). In particular, different aspects related to the performance and consumption of heterogeneous architectures have been explored. The thesis initially focuses on an efficient implementation of a parallel application, where the execution time is dominated by an high number of floating point instructions. Then the thesis touches the central problem of efficient management of power peaks in heterogeneous computing systems. Finally it discusses a memory-bounded problem, where the execution time is dominated by the memory latency. Specifically, the following main contributions have been carried out: A novel framework for the design and analysis of solar field for Central Receiver Systems (CRS) has been developed. The implementation based on desktop workstation equipped with multiple Graphics Processing Units (GPUs) is motivated by the need to have an accurate and fast simulation environment for studying mirror imperfection and non-planar geometries. Secondly, a power-aware scheduling algorithm on heterogeneous CPU-GPU architectures, based on an efficient distribution of the computing workload to the resources, has been realized. The scheduler manages the resources of several computing nodes with a view to reducing the peak power. The two main contributions of this work follow: the approach reduces the supply cost due to high peak power whilst having negligible impact on the parallelism of computational nodes. from another point of view the developed model allows designer to increase the number of cores without increasing the capacity of the power supply unit. Finally, an implementation for efficient graph exploration on reconfigurable architectures is presented. The purpose is to accelerate graph exploration, reducing the number of random memory accesses.

Decomposition Methods and Network Design Problems

Decomposition based approaches are recalled from primal and dual point of view. The possibility of building partially disaggregated reduced master problems is investigated. This extends the idea of aggregated-versus-disaggregated formulation to a gradual choice of alternative level of aggregation. Partial aggregation is applied to the linear multicommodity minimum cost flow problem. The possibility of having only partially aggregated bundles opens a wide range of alternatives with different trade-offs between the number of iterations and the required computation for solving it. This trade-off is explored for several sets of instances and the results are compared with the ones obtained by directly solving the natural node-arc formulation. An iterative solution process to the route assignment problem is proposed, based on the well-known Frank Wolfe algorithm. In order to provide a first feasible solution to the Frank Wolfe algorithm, a linear multicommodity min-cost flow problem is solved to optimality by using the decomposition techniques mentioned above. Solutions of this problem are useful for network orientation and design, especially in relation with public transportation systems as the Personal Rapid Transit. A single-commodity robust network design problem is addressed. In this, an undirected graph with edge costs is given together with a discrete set of balance matrices, representing different supply/demand scenarios. The goal is to determine the minimum cost installation of capacities on the edges such that the flow exchange is feasible for every scenario. A set of new instances that are computationally hard for the natural flow formulation are solved by means of a new heuristic algorithm. Finally, an efficient decomposition-based heuristic approach for a large scale stochastic unit commitment problem is presented. The addressed real-world stochastic problem employs at its core a deterministic unit commitment planning model developed by the California Independent System Operator (ISO).

The market manipulation regime in the European Union

Market manipulation is an illegal practice that enables a person can profit from practices that artificially raise or lower the prices of an instrument in the financial markets. Its prohibition is based on the 2003 Market Abuse Directive in the EU. The current market manipulation regime was broadly considered as a big success except for enforcement and supervisory inconsistencies in the Member States at the initial. A review of the market manipulation regime began at the end of 2007, which became quickly incorporated into the wider EU crisis-era reform program. A number of weaknesses of current regime have been identified, which include regulatory gaps caused by the development of trading venues and financial products, regulatory gaps concerning cross-border and cross-markets manipulation (particular commodity markets), legal uncertainty as a result of various implementation, and inefficient supervision and enforcement. On 12 June 2014, a new regulatory package of market abuse, Market Abuse Regulation and Directive on criminal sanctions for market abuse, has been adopted. And several changes will be made concerning the EU market manipulation regime. A wider scope of the regime and a new prohibition of attempted market manipulation will ensure the prevention of market manipulation at large. The AMPs will be subject to strict scrutiny of ESMA to reduce divergences in implementation. In order to enhance efficiency of supervision and enforcement, powers of national competent authorities will be strengthened, ESMA is imposed more power to settle disagreement between national regulators, and the administrative and criminal sanctioning regimes are both further harmonized. In addition, the protection of fundamental rights is stressed by the new market manipulation regime, and some measures are provided to guarantee its realization. Further, the success EU market manipulation regime could be of significant reference to China, helping China to refine its immature regime.