Efficient certification of feasibility and objective value of linear programs and its applications

The use of linear programming in various areas has increased with the significant improvement of specialized solvers. Linear programs are used as such to model practical problems, or as subroutines in algorithms such as formal proofs or branch-and-cut frameworks. In many situations a certified answer is needed, for example the guarantee that the linear program is feasible or infeasible, or a provably safe bound on its objective value. Most of the available solvers work with floating-point arithmetic and are thus subject to its shortcomings such as rounding errors or underflow, therefore they can deliver incorrect answers. While adequate for some applications, this is unacceptable for critical applications like flight controlling or nuclear plant management due to the potential catastrophic consequences. We propose a method that gives a certified answer whether a linear program is feasible or infeasible, or returns unknown'. The advantage of our method is that it is reasonably fast and rarely answers unknown'. It works by computing a safe solution that is in some way the best possible in the relative interior of the feasible set. To certify the relative interior, we employ exact arithmetic, whose use is nevertheless limited in general to critical places, allowing us to rnremain computationally efficient. Moreover, when certain conditions are fulfilled, our method is able to deliver a provable bound on the objective value of the linear program. We test our algorithm on typical benchmark sets and obtain higher rates of success compared to previous approaches for this problem, while keeping the running times acceptably small. The computed objective value bounds are in most of the cases very close to the known exact objective values. We prove the usability of the method we developed by additionally employing a variant of it in a different scenario, namely to improve the results of a Satisfiability Modulo Theories solver. Our method is used as a black box in the nodes of a branch-and-bound tree to implement conflict learning based on the certificate of infeasibility for linear programs consisting of subsets of linear constraints. The generated conflict clauses are in general small and give good rnprospects for reducing the search space. Compared to other methods we obtain significant improvements in the running time, especially on the large instances.

Portfolio Approaches in Constraint Programming

Recent research has shown that the performance of a single, arbitrarily efficient algorithm can be significantly outperformed by using a portfolio of —possibly on-average slower— algorithms. Within the Constraint Programming (CP) context, a portfolio solver can be seen as a particular constraint solver that exploits the synergy between the constituent solvers of its portfolio for predicting which is (or which are) the best solver(s) to run for solving a new, unseen instance. In this thesis we examine the benefits of portfolio solvers in CP. Despite portfolio approaches have been extensively studied for Boolean Satisfiability (SAT) problems, in the more general CP field these techniques have been only marginally studied and used. We conducted this work through the investigation, the analysis and the construction of several portfolio approaches for solving both satisfaction and optimization problems. We focused in particular on sequential approaches, i.e., single-threaded portfolio solvers always running on the same core. We started from a first empirical evaluation on portfolio approaches for solving Constraint Satisfaction Problems (CSPs), and then we improved on it by introducing new data, solvers, features, algorithms, and tools. Afterwards, we addressed the more general Constraint Optimization Problems (COPs) by implementing and testing a number of models for dealing with COP portfolio solvers. Finally, we have come full circle by developing sunny-cp: a sequential CP portfolio solver that turned out to be competitive also in the MiniZinc Challenge, the reference competition for CP solvers.

New integer programming models for balanced multi-country kep

Le persone che soffrono di insufficienza renale terminale hanno due possibili trattamenti da affrontare: la dialisi oppure il trapianto di organo. Nel caso volessero seguire la seconda strada, oltre che essere inseriti nella lista d'attesa dei donatori deceduti, possono trovare una persona, come il coniuge, un parente o un amico, disposta a donare il proprio rene. Tuttavia, non sempre il trapianto è fattibile: donatore e ricevente possono, infatti, presentare delle incompatibilità a livello di gruppo sanguigno o di tessuto organico. Come risposta a questo tipo di problema nasce il KEP (Kidney Exchange Program), un programma, ampiamente avviato in diverse realtà europee e mondiali, che si occupa di raggruppare in un unico insieme le coppie donatore/ricevente in questa stessa situazione al fine di operare e massimizzare scambi incrociati di reni fra coppie compatibili. Questa tesi approffondisce tale questione andando a valutare la possibilità di unire in un unico insieme internazionale coppie donatore/ricevente provenienti da più paesi. Lo scopo, naturalmente, è quello di poter ottenere un numero sempre maggiore di trapianti effettuati. Lo studio affronta dal punto di vista matematico problematiche legate a tale collaborazione: i paesi che eventualmente accettassero di partecipare a un simile programma, infatti, devono avere la garanzia non solo di ricavarne un vantaggio, ma anche che tale vantaggio sia equamente distribuito fra tutti i paesi partecipanti.

Applying the reactive programming paradigm: Toward a more declarative application development approach

After almost 10 years from “The Free Lunch Is Over” article, where the need to parallelize programs started to be a real and mainstream issue, a lot of stuffs did happened: • Processor manufacturers are reaching the physical limits with most of their approaches to boosting CPU performance, and are instead turning to hyperthreading and multicore architectures; • Applications are increasingly need to support concurrency; • Programming languages and systems are increasingly forced to deal well with concurrency. This thesis is an attempt to propose an overview of a paradigm that aims to properly abstract the problem of propagating data changes: Reactive Programming (RP). This paradigm proposes an asynchronous non-blocking approach to concurrency and computations, abstracting from the low-level concurrency mechanisms.

Aggregate Programming in Scala: a Core Library and Actor-Based Platform for Distributed Computational Fields

La programmazione aggregata è un paradigma che supporta la programmazione di sistemi di dispositivi, adattativi ed eventualmente a larga scala, nel loro insieme -- come aggregati. L'approccio prevalente in questo contesto è basato sul field calculus, un calcolo formale che consente di definire programmi aggregati attraverso la composizione funzionale di campi computazionali, creando i presupposti per la specifica di pattern di auto-organizzazione robusti. La programmazione aggregata è attualmente supportata, in modo più o meno parziale e principalmente per la simulazione, da DSL dedicati (cf., Protelis), ma non esistono framework per linguaggi mainstream finalizzati allo sviluppo di applicazioni. Eppure, un simile supporto sarebbe auspicabile per ridurre tempi e sforzi d'adozione e per semplificare l'accesso al paradigma nella costruzione di sistemi reali, nonché per favorire la ricerca stessa nel campo. Il presente lavoro consiste nello sviluppo, a partire da un prototipo della semantica operazionale del field calculus, di un framework per la programmazione aggregata in Scala. La scelta di Scala come linguaggio host nasce da motivi tecnici e pratici. Scala è un linguaggio moderno, interoperabile con Java, che ben integra i paradigmi ad oggetti e funzionale, ha un sistema di tipi espressivo, e fornisce funzionalità avanzate per lo sviluppo di librerie e DSL. Inoltre, la possibilità di appoggiarsi, su Scala, ad un framework ad attori solido come Akka, costituisce un altro fattore trainante, data la necessità di colmare l'abstraction gap inerente allo sviluppo di un middleware distribuito. Nell'elaborato di tesi si presenta un framework che raggiunge il triplice obiettivo: la costruzione di una libreria Scala che realizza la semantica del field calculus in modo corretto e completo, la realizzazione di una piattaforma distribuita Akka-based su cui sviluppare applicazioni, e l'esposizione di un'API generale e flessibile in grado di supportare diversi scenari.

Reactive programming: un caso di studio

L'obiettivo di questa tesi è analizzare e testare la programmazione reattiva, paradigma di programmazione particolarmente adatto per lo sviluppo di applicazioni altamente interattive. La progettazione di sistemi reattivi implica necessariamente l'utilizzo di codice asincrono e la programmazione reattiva (RP) offre al programmatore semplici meccanismi per gestirlo. In questa tesi, la programmazione reattiva è stata utilizzata e valutata mediante la realizzazione di un progetto real-world chiamato AvvocaTimer. Verrà affrontata la progettazione, implementazione e collaudo di una parte del sistema attraverso l'approccio reattivo e, successivamente, confrontata con la prima versione, realizzata con i metodi attualmente usati per gestire codice asincrono, per analizzare vantaggi e/o svantaggi derivanti dall'utilizzo del nuovo paradigma.

Integrazione di piattaforme d'esecuzione e simulazione in una toolchain Scala per aggregate programming

La tesi è calata nell'ambito dell'Aggregate Programming e costituita da una prima parte introduttiva su questo ambito, per poi concentrarsi sulla descrizione degli elaborati prodotti e infine qualche nota conclusiva unitamente a qualche possibile sviluppo futuro. La parte progettuale consiste nell'integrazione del framework Scafi con il simulatore Alchemist e con una piattaforma di creazione e di esecuzione di sistemi in ambito Spatial Computin, con lo scopo di potenziare la toolchain esistente per Aggregate Programming. Inoltre si riporta anche un breve capitolo per l'esecuzione del framework scafi sviluppato in scala sulla piattaforma Android.

Bilateral impairment of concurrent saccade programming in hemispatial neglect

When healthy observers make a saccade that is erroneously directed toward a distracter stimulus, they often produce a corrective saccade within 100ms after the end of the primary saccade. Such short inter-saccadic intervals indicate that programming of the secondary saccade has been initiated prior to the execution of the primary saccade and hence that the two saccades have been programmed concurrently. Here we show that concurrent saccade programming is bilaterally impaired in left spatial neglect, a strongly lateralized disorder of visual attention resulting from extensive right cerebral damage. Neglect patients were asked to make saccades to targets presented left or right of fixation while disregarding a distracter presented in the opposite hemifield. We examined those experimental trials on which participants first made a saccade to the distracter, followed by a secondary (corrective) saccade to the target. Compared to healthy and right-hemisphere damaged control participants the proportion of secondary saccades directing gaze to the target instead of bringing it even closer to the distracter was bilaterally reduced in neglect patients. In addition, the characteristic reduction of secondary saccade latency observed in both control groups was absent in neglect patients, whether the secondary saccade was directed to the left or right hemifield. This pattern is consistent with a severe, bilateral impairment of concurrent saccade programming in left spatial neglect.

Using human rights for sexual and reproductive health: improving legal and regulatory frameworks

This paper describes the development of a tool that uses human rights concepts and methods to improve relevant laws, regulations and policies related to sexual and reproductive health. This tool aims to improve awareness and understanding of States' human rights obligations. It includes a method for systematically examining the status of vulnerable groups, involving non-health sectors, fostering a genuine process of civil society participation and developing recommendations to address regulatory and policy barriers to sexual and reproductive health with a clear assignment of responsibility. Strong leadership from the ministry of health, with support from the World Health Organization or other international partners, and the serious engagement of all involved in this process can strengthen the links between human rights and sexual and reproductive health, and contribute to national achievement of the highest attainable standard of health.

Knowing the future: partial foreknowledge effects on the programming of prosaccades and antisaccades

Foreknowledge about the demands of an upcoming trial may be exploited to optimize behavioural responses. In the current study we systematically investigated the benefits of partial foreknowledge--that is, when some but not all aspects of a future trial are known in advance. For this we used an ocular motor paradigm with horizontal prosaccades and antisaccades. Predictable sequences were used to create three partial foreknowledge conditions: one with foreknowledge about the stimulus location only, one with foreknowledge about the task set only, and one with foreknowledge about the direction of the required response only. These were contrasted with a condition of no-foreknowledge and a condition of complete foreknowledge about all three parameters. The results showed that the three types of foreknowledge affected saccadic efficiency differently. While foreknowledge about stimulus-location had no effect on efficiency, task foreknowledge had some effect and response-foreknowledge was as effective as complete foreknowledge. Foreknowledge effects on switch costs followed a similar pattern in general, but were not specific for switching of the trial attribute for which foreknowledge was available. We conclude that partial foreknowledge has a differential effect on efficiency, most consistent with preparatory activation of a motor schema in advance of the stimulus, with consequent benefits for both switched and repeated trials.

Trial history biases the spatial programming of antisaccades

The historical context in which saccades are made influences their latency and error rates, but less is known about how context influences their spatial parameters. We recently described a novel spatial bias for antisaccades, in which the endpoints of these responses deviate towards alternative goal locations used in the same experimental block, and showed that expectancy (prior probability) is at least partly responsible for this 'alternate-goal bias'. In this report we asked whether trial history also plays a role. Subjects performed antisaccades to a stimulus randomly located on the horizontal meridian, on a 40° angle downwards from the horizontal meridian, or on a 40° upward angle, with all three locations equally probable on any given trial. We found that the endpoints of antisaccades were significantly displaced towards the goal location of not only the immediately preceding trial (n - 1) but also the penultimate (n - 2) trial. Furthermore, this bias was mainly present for antisaccades with a short latency of <250 ms and was rapidly corrected by secondary saccades. We conclude that the location of recent antisaccades biases the spatial programming of upcoming antisaccades, that this historical effect persists over many seconds, and that it influences mainly rapidly generated eye movements. Because corrective saccades eliminate the historical bias, we suggest that the bias arises in processes generating the response vector, rather than processes generating the perceptual estimate of goal location.