Application-oriented Mixed Integer Non-Linear Programming

In the most recent years there is a renovate interest for Mixed Integer Non-Linear Programming (MINLP) problems. This can be explained for different reasons: (i) the performance of solvers handling non-linear constraints was largely improved; (ii) the awareness that most of the applications from the real-world can be modeled as an MINLP problem; (iii) the challenging nature of this very general class of problems. It is well-known that MINLP problems are NP-hard because they are the generalization of MILP problems, which are NP-hard themselves. However, MINLPs are, in general, also hard to solve in practice. We address to non-convex MINLPs, i.e. having non-convex continuous relaxations: the presence of non-convexities in the model makes these problems usually even harder to solve. The aim of this Ph.D. thesis is to give a flavor of different possible approaches that one can study to attack MINLP problems with non-convexities, with a special attention to real-world problems. In Part 1 of the thesis we introduce the problem and present three special cases of general MINLPs and the most common methods used to solve them. These techniques play a fundamental role in the resolution of general MINLP problems. Then we describe algorithms addressing general MINLPs. Parts 2 and 3 contain the main contributions of the Ph.D. thesis. In particular, in Part 2 four different methods aimed at solving different classes of MINLP problems are presented. Part 3 of the thesis is devoted to real-world applications: two different problems and approaches to MINLPs are presented, namely Scheduling and Unit Commitment for Hydro-Plants and Water Network Design problems. The results show that each of these different methods has advantages and disadvantages. Thus, typically the method to be adopted to solve a real-world problem should be tailored on the characteristics, structure and size of the problem. Part 4 of the thesis consists of a brief review on tools commonly used for general MINLP problems, constituted an integral part of the development of this Ph.D. thesis (especially the use and development of open-source software). We present the main characteristics of solvers for each special case of MINLP.

The changing politics of preference formation in international trade negotiations: the European Union in the Doha Round

This research seeks to provide an explanation for variations of “politics” of preference formation in international trade negotiations. Building on the ‘policy determines politics’ argument, I hypothesize the existence of a causal relationship between issue-characteristics and their variations with politics dynamics and their variations. More specifically, this study seeks to integrate into a single analytical framework two dimensions along which variations in the “politics of preference formation” can be organized: configurations of power relationships among the relevant actors in the structures within which they interact as well as the logic and the motivations of the actors involved in the policy making process. To do so, I first construct a four-cell typology of ‘politics of preference formation’ and, then, I proceed by specifying that the type of state-society configurations as well as the type of actors’ motivations in the “politics of preference formation” depend, respectively, on the degree to which a policy issue is perceived as politically salient and on the extent to which the distributional implications of such an issue can be calculated by the relevant stakeholders in the policy making process. The empirical yardstick against which the validity of the theoretical argument proposed is tested is drawn from evidence concerning the European Union’s negotiating strategy in four negotiating areas in the context of the so-called WTO’s Doha Development Round of multilateral trade negotiations: agriculture, competition, environment and technical assistance and capacity building.

Hardware and software development of a multichannel readout board named CARLOSrx for the ALICE experiment

ALICE, that is an experiment held at CERN using the LHC, is specialized in analyzing lead-ion collisions. ALICE will study the properties of quarkgluon plasma, a state of matter where quarks and gluons, under conditions of very high temperatures and densities, are no longer confined inside hadrons. Such a state of matter probably existed just after the Big Bang, before particles such as protons and neutrons were formed. The SDD detector, one of the ALICE subdetectors, is part of the ITS that is composed by 6 cylindrical layers with the innermost one attached to the beam pipe. The ITS tracks and identifies particles near the interaction point, it also aligns the tracks of the articles detected by more external detectors. The two ITS middle layers contain the whole 260 SDD detectors. A multichannel readout board, called CARLOSrx, receives at the same time the data coming from 12 SDD detectors. In total there are 24 CARLOSrx boards needed to read data coming from all the SDD modules (detector plus front end electronics). CARLOSrx packs data coming from the front end electronics through optical link connections, it stores them in a large data FIFO and then it sends them to the DAQ system. Each CARLOSrx is composed by two boards. One is called CARLOSrx data, that reads data coming from the SDD detectors and configures the FEE; the other one is called CARLOSrx clock, that sends the clock signal to all the FEE. This thesis contains a description of the hardware design and firmware features of both CARLOSrx data and CARLOSrx clock boards, which deal with all the SDD readout chain. A description of the software tools necessary to test and configure the front end electronics will be presented at the end of the thesis.

Applications of High Speed Configurable Logic Devices in Modern Particle Physics Experiments

Several activities were conducted during my PhD activity. For the NEMO experiment a collaboration between the INFN/University groups of Catania and Bologna led to the development and production of a mixed signal acquisition board for the Nemo Km3 telescope. The research concerned the feasibility study for a different acquisition technique quite far from that adopted in the NEMO Phase 1 telescope. The DAQ board that we realized exploits the LIRA06 front-end chip for the analog acquisition of anodic an dynodic sources of a PMT (Photo-Multiplier Tube). The low-power analog acquisition allows to sample contemporaneously multiple channels of the PMT at different gain factors in order to increase the signal response linearity over a wider dynamic range. Also the auto triggering and self-event-classification features help to improve the acquisition performance and the knowledge on the neutrino event. A fully functional interface towards the first level data concentrator, the Floor Control Module, has been integrated as well on the board, and a specific firmware has been realized to comply with the present communication protocols. This stage of the project foresees the use of an FPGA, a high speed configurable device, to provide the board with a flexible digital logic control core. After the validation of the whole front-end architecture this feature would be probably integrated in a common mixed-signal ASIC (Application Specific Integrated Circuit). The volatile nature of the configuration memory of the FPGA implied the integration of a flash ISP (In System Programming) memory and a smart architecture for a safe remote reconfiguration of it. All the integrated features of the board have been tested. At the Catania laboratory the behavior of the LIRA chip has been investigated in the digital environment of the DAQ board and we succeeded in driving the acquisition with the FPGA. The PMT pulses generated with an arbitrary waveform generator were correctly triggered and acquired by the analog chip, and successively they were digitized by the on board ADC under the supervision of the FPGA. For the communication towards the data concentrator a test bench has been realized in Bologna where, thanks to a lending of the Roma University and INFN, a full readout chain equivalent to that present in the NEMO phase-1 was installed. These tests showed a good behavior of the digital electronic that was able to receive and to execute command imparted by the PC console and to answer back with a reply. The remotely configurable logic behaved well too and demonstrated, at least in principle, the validity of this technique. A new prototype board is now under development at the Catania laboratory as an evolution of the one described above. This board is going to be deployed within the NEMO Phase-2 tower in one of its floors dedicated to new front-end proposals. This board will integrate a new analog acquisition chip called SAS (Smart Auto-triggering Sampler) introducing thus a new analog front-end but inheriting most of the digital logic present in the current DAQ board discussed in this thesis. For what concern the activity on high-resolution vertex detectors, I worked within the SLIM5 collaboration for the characterization of a MAPS (Monolithic Active Pixel Sensor) device called APSEL-4D. The mentioned chip is a matrix of 4096 active pixel sensors with deep N-well implantations meant for charge collection and to shield the analog electronics from digital noise. The chip integrates the full-custom sensors matrix and the sparsifification/readout logic realized with standard-cells in STM CMOS technology 130 nm. For the chip characterization a test-beam has been set up on the 12 GeV PS (Proton Synchrotron) line facility at CERN of Geneva (CH). The collaboration prepared a silicon strip telescope and a DAQ system (hardware and software) for data acquisition and control of the telescope that allowed to store about 90 million events in 7 equivalent days of live-time of the beam. My activities concerned basically the realization of a firmware interface towards and from the MAPS chip in order to integrate it on the general DAQ system. Thereafter I worked on the DAQ software to implement on it a proper Slow Control interface of the APSEL4D. Several APSEL4D chips with different thinning have been tested during the test beam. Those with 100 and 300 um presented an overall efficiency of about 90% imparting a threshold of 450 electrons. The test-beam allowed to estimate also the resolution of the pixel sensor providing good results consistent with the pitch/sqrt(12) formula. The MAPS intrinsic resolution has been extracted from the width of the residual plot taking into account the multiple scattering effect.

Enhanced Mixed Integer Programming Techniques and Routing Problems

Mixed integer programming is up today one of the most widely used techniques for dealing with hard optimization problems. On the one side, many practical optimization problems arising from real-world applications (such as, e.g., scheduling, project planning, transportation, telecommunications, economics and finance, timetabling, etc) can be easily and effectively formulated as Mixed Integer linear Programs (MIPs). On the other hand, 50 and more years of intensive research has dramatically improved on the capability of the current generation of MIP solvers to tackle hard problems in practice. However, many questions are still open and not fully understood, and the mixed integer programming community is still more than active in trying to answer some of these questions. As a consequence, a huge number of papers are continuously developed and new intriguing questions arise every year. When dealing with MIPs, we have to distinguish between two different scenarios. The first one happens when we are asked to handle a general MIP and we cannot assume any special structure for the given problem. In this case, a Linear Programming (LP) relaxation and some integrality requirements are all we have for tackling the problem, and we are ``forced" to use some general purpose techniques. The second one happens when mixed integer programming is used to address a somehow structured problem. In this context, polyhedral analysis and other theoretical and practical considerations are typically exploited to devise some special purpose techniques. This thesis tries to give some insights in both the above mentioned situations. The first part of the work is focused on general purpose cutting planes, which are probably the key ingredient behind the success of the current generation of MIP solvers. Chapter 1 presents a quick overview of the main ingredients of a branch-and-cut algorithm, while Chapter 2 recalls some results from the literature in the context of disjunctive cuts and their connections with Gomory mixed integer cuts. Chapter 3 presents a theoretical and computational investigation of disjunctive cuts. In particular, we analyze the connections between different normalization conditions (i.e., conditions to truncate the cone associated with disjunctive cutting planes) and other crucial aspects as cut rank, cut density and cut strength. We give a theoretical characterization of weak rays of the disjunctive cone that lead to dominated cuts, and propose a practical method to possibly strengthen those cuts arising from such weak extremal solution. Further, we point out how redundant constraints can affect the quality of the generated disjunctive cuts, and discuss possible ways to cope with them. Finally, Chapter 4 presents some preliminary ideas in the context of multiple-row cuts. Very recently, a series of papers have brought the attention to the possibility of generating cuts using more than one row of the simplex tableau at a time. Several interesting theoretical results have been presented in this direction, often revisiting and recalling other important results discovered more than 40 years ago. However, is not clear at all how these results can be exploited in practice. As stated, the chapter is a still work-in-progress and simply presents a possible way for generating two-row cuts from the simplex tableau arising from lattice-free triangles and some preliminary computational results. The second part of the thesis is instead focused on the heuristic and exact exploitation of integer programming techniques for hard combinatorial optimization problems in the context of routing applications. Chapters 5 and 6 present an integer linear programming local search algorithm for Vehicle Routing Problems (VRPs). The overall procedure follows a general destroy-and-repair paradigm (i.e., the current solution is first randomly destroyed and then repaired in the attempt of finding a new improved solution) where a class of exponential neighborhoods are iteratively explored by heuristically solving an integer programming formulation through a general purpose MIP solver. Chapters 7 and 8 deal with exact branch-and-cut methods. Chapter 7 presents an extended formulation for the Traveling Salesman Problem with Time Windows (TSPTW), a generalization of the well known TSP where each node must be visited within a given time window. The polyhedral approaches proposed for this problem in the literature typically follow the one which has been proven to be extremely effective in the classical TSP context. Here we present an overall (quite) general idea which is based on a relaxed discretization of time windows. Such an idea leads to a stronger formulation and to stronger valid inequalities which are then separated within the classical branch-and-cut framework. Finally, Chapter 8 addresses the branch-and-cut in the context of Generalized Minimum Spanning Tree Problems (GMSTPs) (i.e., a class of NP-hard generalizations of the classical minimum spanning tree problem). In this chapter, we show how some basic ideas (and, in particular, the usage of general purpose cutting planes) can be useful to improve on branch-and-cut methods proposed in the literature.

Analisi e riprogettazione dei processi aziendali: aspetti metodologici ed esperienze applicative

Il lavoro tratta l’applicazione di due progetti di Reengineering, in un caso l’obiettivo era quello di ottimizzare il processo di fatturazione passiva di un’azienda operante nel settore della ceramica, nell’altro quello di supportare un Gruppo, operante nel settore logistico, nella valutare l’opportunità di accentramento dei servizi ICT, mitigando gli impatti derivati dai possibili cambiamenti. Questo lavoro è stato preparato durante un periodo di Stage della durata di sei mesi effettuato presso la società di consulenza Revision SRL. Nella prima parte della tesi, attraverso un’analisi della letteratura di riferimento, si sono indagati i principali fattori che interagiscono in un processo di Change management, si è anche effettuato un approfondimento delle tematiche di Business Process Reengineering, i cui principi hanno guidato l’intervento effettuato. La ricerca ha teso ad evidenziare da un lato le radici e gli elementi innovativi che contraddistinguono questo approccio metodologico e dall’altro a sottolineare le possibili cause di insuccesso di un progetto di BPR. La sezione si conclude con la formalizzazione delle metodologia e degli strumenti utilizzati nella conduzione dei progetti. Nella seconda parte del lavoro, insieme alla descrizione del primo caso vengono presentate le varie fasi della riprogettazione, dalla analisi della situazione iniziale, effettuata tramite un questionario e delle interviste dirette al personale addetto, alla identificazione delle criticità, fino alla presentazione e alla valutazione delle nuove configurazioni del processo. Il lavoro è arricchito dall’analisi e dall’applicazione delle tecnologie informatiche/informative di supporto alla nuova configurazione descritta. Nella terza parte, a completamento dell’elaborato, viene presentato il secondo progetto analizzato dove, dopo una fase di analisi della situazione iniziale ancora tramite questionario ed interviste dirette, si riportano le considerazioni fatte in merito alla possibilità di accentramento dei servizi ICT del gruppo analizzato.

La citta' dell'attesa : un carcere trattamentale per la societa' contemporanea

Architettura Alla domanda “cosa fa un architetto?” Non sono mai riuscito a dare una risposta soddisfacente ma leggendo gli scritti dei grandi architetti una cosa mi ha affascinato particolarmente: tutti raccontano di come nel progettare ci sia un equilibrio (scontro?) tra le conoscenze, le regole e la personale visione ed esperienza, in cui tutto si libera. Libeskind afferma di aver disegnato, in preda ad illuminazioni, più su tovagliolini da bar che su carta da disegno; Zumthor parla addirittura di momenti in cui si è come in preda ad un effetto di una droga: intuizioni! L’architetto progetta. Architetto come genio, particolarmente sensibile, quasi illuminato. “L’architettura non è per tutti”; mi chiedo allora non solo se esistono leggi, soluzioni o binari capaci di guidare anche chi è privo di tale estro ma se esiste un’Architettura comprensibile a tutti (anche alle generazioni future). Ancora una volta se penso ad un denominatore comune di benessere, una possibile guida, penso alla natura e ai suoi ritmi, un’Architettura che mantenga i legami con essa può forse ricordarci che siamo tutti ricchi. L’Architettura intesa come scoperta e non come invenzione, dunque onesta. Carcere Lo studio di una realtà come il carcere mi ha permesso di pormi numerose domande sul ruolo dell’Archittura, a partire dalla riflessione su ciò che significa e rappresenta il progetto architettonico. Studiando l’evoluzione delle carceri, legate indissolubilmente all’evoluzione del concetto di pena, è possibile dare molte risposte ai quesiti dovuti alle scelte progettuali. (costantemente stimolato dalle frequenti similitudini tra carcere e metropoli). Una contrapposizione dovuta al significato dell’abitare insieme al concetto di “qualità” rapportati al concetto di pena senza dimenticare le indicazioni delle norme di sicurezza. L’ Architettura intesa come ricerca del maggior benessere abitativo credo che debba comunque essere ricercata, anche nello spazio carcerario. Non vi è nessun paradosso se si pensa che lo scopo ultimo dello Stato è di voler reintegrare il detenuto in modo tale che non rappresenti più un pericolo e di conseguenza non gravi mai più sullo Stato stesso (troppo spesso chi è stato in carcere ci rientra dopo poco e per gli stessi motivi). “Le pene non possono consistere in trattamenti contrari al senso di umanità e devono tendere alla rieducazione del condannato”(art.27 Cost.) è da questa consapevolezza che dipende l’organizzazione della forma dello spazio e di tali strutture. Naturalmente il grande limite è imposto nel non creare situazioni di benessere tale da portare lo sprovveduto più disperato a commettere il crimine per poter godere dei servizi del carcere. Per questo motivo penso che una soluzione possa essere la ricerca di un equilibrio tra libertà degli spazi condivisi e i limiti dello spazio privato. A mio avviso tutte le esperienze positive devono avvenire in spazi collettivi insieme non solo agli altri carcerati ma anche con la società stessa (penso al Giardino degli incontri di Michelucci in cui c’è una attività teatrale gestita dagli enti comunali); mentre i limiti della reclusione penso debbano essere rappresentati dalla cella, da sempre momento di riflessione e di scoperta di sé stessi. Il detenuto impara a conoscere la società, impara a rispettarla ed una volta libero è più logico che sia disposto a ricambiare le attenzioni ricevute. La cella invece, deve rappresentare il momento in cui è forte il distacco con la società, in cui la si può guardare senza poterne fare parte: la cella come momento dell’attesa e non come comodo rifugio(seppur rispettando un livello di comfort ideale). Il disagio percepito non è da considerare una pena psicologica (anch’essa da evitare) o come un momento di purificazione (immaginario cristiano della colpa e dell’espiazione) ma più semplicemente come una fase del processo in grado (si spera) di recuperare il detenuto: è il desiderio e la consapevolezza di poter vivere insieme agli altri che porta al reinserimento. Di conseguenza è possibile dare una ulteriore risposta interessante; il carcere dovrà essere connesso alla città in modo tale che sia possibile l’interazione tra i due, inoltre permetterebbe alle persone in semi-libertà o in attesa di giudizio un più consono trattamento. Mettere in relazione città e carcere significa integrarli e completare le reciproche identità.

La trasparenza nelle organizzazioni sanitarie: comunicare i risultati

La raccolta e l’utilizzo in chiave comparativa di dati di performance sanitaria risponde, tra le altre esigenze, a bisogni di accountability. Si osserva infatti a livello internazionale la diffusione di politiche di pubblicizzazione della qualità dei risultati: uno studio della letteratura di settore consente di confrontare i fattori più rilevanti delle principali esperienze di reporting già realizzate in Paesi dai sistemi sanitari molto diversi. Nel contesto italiano l’attenzione ai diritti dell’utente di concerto con la riforma del sistema informativo sanitario si pongono come premesse alla potenziale diffusione di dati di performance alla cittadinanza. Una interpretazione delle fonti normative e della giurisprudenza tramite il principio di trasparenza pare sostenere la tesi di una doverosità di informazione in capo alle amministrazioni pubbliche; l’analisi dei possibili scenari di impatto delle politiche di comunicazione ne condiziona però l’attuazione ad una programmazione strutturata e consapevole.