Rapporti tecnici


Lista dei rapporti tecnici dell'anno 2013

Frangioni, Antonio and Furini, Fabio and Gentile, Claudio
Approximated Perspective Relaxations: a Project&Lift Approach
November 4, 2014
UnipiEprints view

The Perspective Reformulation (PR) of a Mixed-Integer NonLinear Program with semi-continuous variables is obtained by replacing each term in the (separable) objective function with its convex envelope. Solving the corresponding Perspective Relaxation requires appropriate techniques. Under some rather restrictive assumptions, the <i>Projected PR</i> can be defined where the integer variables are eliminated by projecting the solution set on the space of the continuous variables only. This approach produces a simple piecewise-convex problem with the same structure as the original one; however, this prevents the use of general-purpose solvers, in that some variables are then only implicitly represented in the formulation. We show how to construct an <i>Approximated</i> Projected PR whereby the projected formulation is &quot;lifted&quot; back to the original variable space, with the integer variables expressing one piece of the obtained piecewise-convex function; in some cases, this produces a reformulation of the original problem with exactly the same size and structure as the standard continuous relaxation but with a substantially improved bound. While the bound can be weaker than that of the PR, this approach can be applied in many more cases and allows direct use of off-the-shelf MIQP software; this is shown to be beneficial in different applications. In the process we also relax some of the other restrictive assumptions of the original development, such as the need for the objective function to be quadratic and the need for the left endpoint of the domain of the variables to be non-negative.

Monreale, Anna and Wang, Wendy and Pratesi, Francesca and Rinzivillo, Salvatore and Pedreschi, Dino and Andrienko, Gennady and Andrienko, Natalia
Differential Privacy in Distributed Mobility Analytics
November 4, 2014
UnipiEprints view

Movement data are sensitive, because people’s whereabouts may allow re- identification of individuals in a de-identified database and thus can potentially reveal intimate personal traits, such as religious or sexual preferences. In this paper, we focus on a distributed setting in which movement data from individ- ual vehicles are collected and aggregated by a centralized station. We propose a novel approach to privacy-preserving analytical processing within such a dis- tributed setting, and tackle the problem of obtaining aggregated traffic information while preventing privacy leakage from data collection and aggregation. We study and analyze three different solutions based on the differential privacy model and on sketching techniques for efficient data compression. Each solution achieves different trade-off between privacy protection and utility of the transformed data. Using real-life data, we demonstrate the effectiveness of our approaches in terms of data utility preserved by the data transformation, thus bringing empirical evi- dence to the fact that the “privacy-by-design” paradigm in big data analytics has the potential of delivering high data protection combined with high quality even in massively distributed techno-social systems.

Ruggieri, Salvatore
Learning from Polyhedral Sets
October 22, 2014
UnipiEprints view

Parameterized linear systems allow for modelling and reasoning over classes of polyhedra. Collections of squares, rectangles, polytopes, and so on, can readily be defined by means of linear systems with parameters. In this paper, we investigate the problem of learning a parameterized linear system whose class of polyhedra includes a given set of example polyhedral sets and it is minimal.

Serban, Tudor and Coppola, Massimo
Data parallel patterns on CPU/GPU mix
October 22, 2014
UnipiEprints view

We propose a model that uses a small set of quite simple parameters to devise a proper partitioning of the available data parallel tasks between CPU cores and GPU cores. The model takes into account both hardware and application dependent parameters. In particular, it eventually computes the percentage of tasks to be executed on CPU cores and GPU cores to achieve the better performance figures. Different experimental results on state-of-the-art CPU/GPU architectures are shown that assess the model properties.

Galli, Laura and Letchford, Adam N.
A Compact Variant of the QCR Method for 0-1 Quadratically Constrained Quadratic Programs
October 22, 2014
UnipiEprints view

<i>Quadratic Convex Reformulation</i> (QCR) is a technique that was originally proposed for 0-1 quadratic programs, and then extended to various other problems. It is used to convert non-convex instances into convex ones, in such a way that the bound obtained by solving the continuous relaxation of the reformulated instance is as strong as possible.<br />In this paper, we focus on the case of <i>0-1 quadratically constrained quadratic programs</i>. The variant of QCR previously proposed for this case involves the addition of a quadratic number of auxiliary continuous variables. We show that, in fact, at most one additional variable is needed. Some computational results are also presented.

Bellia, Marco and Occhiuto, Maria Eugena
Java SAM Typed Closures: A Sound and Complete Type Inference System for Nominal Types (Extended Version)
October 22, 2014
UnipiEprints view

The last proposal for Java closures, as emerged in JSR 000335, is mainly innovative in: (1)Use of nominal types, SAM types, for closures; (2) Introduction of target types and compatibility for a contextual typing of closures; (3) Need for a type inference that reconstructs the omitted type annotations of closures and closure arguments. The paper provides a sound and complete type system, with nominal types, for such a type inference and discusses role and formalization of targeting and of compatibility in the designed inference process.

Frangioni, Antonio and Galli, Laura and Scutellà, Maria Grazia
Delay-Constrained Shortest Paths: Approximation Algorithms and Second-Order Cone Models
October 22, 2014
UnipiEprints view

Real-time traffic with stringent Quality of Service requirements is becoming more and more prevalent in contemporary telecommunication networks. When maximum packet delay has to be considered, optimal delay-constrained routing requires not only choosing a path, but also reserving resources (transmission capacity) along its arcs, as the delay is a nonlinear function of both kinds of components. So far only simple versions of the problem have been considered in the literature where all arcs are reserved the same capacity (this is referred to as ERA, i.e., Equal Rate Allocations) and have the same capacity reservation cost, because in such a restricted case polynomial time exact algorithms can be devised, whereas the general problem is $\Mcnp$-hard. We first extend the polynomial-time approaches for the ERA version of the problem with unit arc costs by deriving a pseudo-polynomial time algorithm for the integer arc costs case and a FPTAS for the general arc costs case. We then show that, under the main latency models proposed in the literature, the general problem can be formulated as a mixed-integer Second-Order Cone (SOCP) program, and therefore solved with off-the-shelf technology. We compare two formulations: one based on standard big-M constraints, and an improved one where Perspective Reformulation techniques are used to tighten the continuous relaxation. Extensive computational experiments on both real-world networks and randomly-generated realistic ones show that the ERA approach is extremely fast and provides a surprisingly effective heuristic for the general problem whenever it manages to find a solution at all, but it fails for a significant fraction of the instances that the SOCP models can solve. We therefore propose a three-pronged approach that combines the fast running time of the ERA algorithm and the effectiveness of the SOCP models, and show that the combined approach is capable of solving realistic-sized instances at different levels of network load in a time compatible with real-time usage in an operating environment.

Cappanera, Paola and Scutellà, Maria Grazia
Joint assignment, scheduling and routing models to Home Care optimization: a pattern based approach
October 22, 2014
UnipiEprints view

The design of efficient Home Care Services is a quite recent and challenging problem motivated by the ever increasing age of population and the consequent need to reduce hospitalization costs. We are given a weekly planning horizon, a set of operators each characterized by a skill and a set of patients each requiring a set of visits also characterized by a skill. We propose an integrated model that jointly addresses the following problems: (i) the assignment of operators to patients guaranteeing the appropriate levels of skill; (ii) the scheduling of visits in the planning horizon; and (iii) the determination of a set of tours indicating the sequence of patients each operator must visit in every day of the week. Several variants of this model are investigated. All of them use the pattern as a key tool to formulate the problem. A pattern is an a priori given profile specifying a possible schedule for a given set of visits possibly characterized by differnt skills. Computational results on a set of real instances are analysed. They show that the selection of the pattern generation policy is crucial to solve large instances efficiently.

Nanni, Mirco and Trasarti, Roberto and Monreale, Anna and Grossi, Valerio and Pedreschi, Dino
Distributed monitoring of cluster quality for car insurance customer segmentation
October 22, 2014
UnipiEprints view

Customer segmentation is one of the most traditional and valued tasks in customer relationship management (CRM). In this paper, we explore the problem in the context of the car insurance industry, where the mobility behavior of customers plays a key role: different mobility needs, driving habits and skills imply also different requirements (level of coverage provided by the insurance) and risks (of accidents). In the present work, we describe a methodology to extract several indicators describing the driving profile of customers, and provide a clustering-oriented instantiation of the segmentation problem, based on such indicators. Then, we consider the availability of a continuous flow of fresh mobility data sent by the circulating vehicles, aiming at keeping our segments constantly up-to-date. We tackle a major scalability issue that emerges in this con- text when the number of customers is large, namely the communication bottleneck, by proposing and implementing a sophisticated distributed monitoring solution, which reduces the communications between vehicles and company servers to the essential. Finally, we validate the framework on a large database of real mobility data, coming from GPS devices of private cars.

Bartoloni, Leonardo and Canciani, Andrea and Cisternino, Antonio and Morelli, Davide
Extending a probabilistic language based upon Sampling Functions to model correlation
October 22, 2014
UnipiEprints view

Probability is permeating many applications of computer science, ranging from probabilistic reasoning to stochastic simulations. Therefore, researchers have started working on domain specific languages to target probabilistic computations, in order to support better understanding and development of probabilistic models. Among the proposed approaches sampling functions is one of the most promising: distributions are described as functional mappings from the unit interval (0,1] to probability domains which allows expressing a very broad class of distributions. The key advantage of this approach lies in its ability of lifting operations on values into operations on related distributions. The current state of the art frameworks, however, lack the ability to properly express variable correlation in a clean and composable way, which is a major issue of many real-world problems. In this paper we present LiXely, a probabilistic DSL which extends the sampling functions approach by providing explicit means for expressing variable correlation in a composable way and its implementation in F#.

Calamoneri, Tiziana and Frangioni, Antonio and Sinaimeri, Blerina
Pairwise Compatibility Graphs of Caterpillars
October 22, 2014
UnipiEprints view

A graph G = (V, E) is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers dmin and dmax such that each leaf lu of T corresponds to a vertex u of V and there is an edge (u, v) in E if and only if dmin <= dT,w(lu, lv) <= dmax where dT,w(lu, lv) is the sum of the weights of the edges on the unique path from lu to lv in T. In this paper, we focus our attention on PCGs for which the witness tree is a caterpillar. We first give some properties of graphs that are PCGs of a caterpillar. We formulate this problem as an integer linear programming problem and we exploit this formulation to show that for the wheels on n vertices Wn, n = 7, ... , 11, the witness tree cannot be a caterpillar. Related to this result, we conjecture that no wheel is PCG of a caterpillar. Finally, we state a more general result proving that any pairwise compatibility graph admits a full binary tree as witness tree T.

Cacchiani, Valentina and Galli, Laura and Toth, Paolo
A Tutorial on Train Timetabling and Train Platforming Problems
October 22, 2014
UnipiEprints view

In this tutorial, we give an overview of two fundamental problems arising in the optimization of a railway system: the Train Timetabling Problem (TTP) and the Train Platforming Problem (TPP). These problems correspond to two main phases that are usually optimized in close sequence. First, in the TTP phase, a schedule of the trains in a railway network is determined. A schedule consists of the arrival and departure times of each train at each (visited) station. Second, in the TPP phase, one needs to determine a topping platform and a routing for each train inside each (visited) station, according to the schedule found in the TTP phase. Due to the complexity of the two problems, an integrated approach is generally hopeless for real-world instances. Hence, the two phases are considered separately and optimized in sequence. Although there exist several versions for both problems, depending on the infrastructure manager and train operators requirements, we do not aim at presenting all of them, but rather at introducing the reader to the topic using small examples. We present models and solution approaches for the two problems in a didactic way and always refer the reader to the corresponding articles for technical details.

Cioni, Lorenzo
An iterative procedure for the Paretian ranking of competing projects
October 22, 2014
UnipiEprints view

In this Technical Report we present an iterative procedure for the evaluation, from a set of decsion makers, of a set of projects according to a given set of criteria. The proposed procedure uses Pareto principles and a Borda classical voting method and aimsat attaining fair allocations whenever this is possible.

Monreale, Anna and Nanni, Mirco and Grossi, Valerio and Trasarti, Roberto and Pedreschi, Dino
Privacy in Distributed Monitoring
October 22, 2014
UnipiEprints view

In many emerging applications, such as real-time traffic monitoring, financial analysis, sensor network monitoring an important task is the continuos monitoring of stream data. In these contexts where large amount of data arrive continually the data processing requires to access often valuable personal information. As a consequence, the entire monitoring process could put at risk the privacy of people represented in the stream data. In this paper, we study the privacy issues in distributed systems during the monitoring of thresholds functions, where several nodes contribute with their data to the monitoring of a specific event. We provide a privacy-preserving framework suitable to find an acceptable trade-off among privacy protection, data quality and system performance. Using real-life data from GPS devices of private cars, we demonstrate the effectiveness of our approach in a case study consisting of the monitoring of customers mobility behaviors; in other words, we show how techniques for efficient communication can be used while preserving the individual privacy of the actors who are participating to the collective analysis.

Bigi, Giancarlo and Passacantando, Mauro
Twelve monotonicity conditions arising from algorithms for equilibrium problems
October 22, 2014
UnipiEprints view

In the last years many solution methods for equilibrium problems (EPs) have been developed. Several different monotonicity conditions have been exploited to prove convergence. The paper investigates all the relationships between them in the framework of the so-called abstract EP. The analysis is further detailed for variational inequalities and linear equilibrium problems, which include also Nash equilibrium problems with quadratic payoffs.

Buono, Daniele and De Matteis, Tiziano and Mencagli, Gabriele and Vanneschi, Marco
Towards a Methodology for Parallel Data Stream Processing: application to Parallel Stream Join
October 22, 2014
UnipiEprints view

This paper deals with high-performance Parallel Data Stream Processing methodologies and implementation techniques. Data Stream Processing (DaSP) is referred to in the most general and interesting sense: on-line (often real-time) applications working on multiple, nondeterministic streams, with unlimited or unknown length and highly variable arrival rate, whose elements must processed efficiently “on the fly”. Traditional high-performance solutions are not sufficient to meet the critical requirements of high throughput and low latency with acceptable memory size: typical DaSP applications require quite novel parallelism models, as well as related design and implementation techniques on the emerging highly parallel architectures. The aim of this paper is to give an original contribution to the design and implementation of parallel DaSP applications. The contribution is twofold: (1) the definition of an approach to a new general model for data-parallel DaSP computations according to a paradigm called Data Stream Parallelism, (2) the application of this approach to the parallel Stream Join problem, showing that the most interesting parallelizations in the literature are particular cases of our approach and that, compared to them, better throughput and latency are achieved by our implementation on multicore architectures.

Cioni, Lorenzo
A multicriteria method for a pluarality of deciders
October 22, 2014
UnipiEprints view

In this technical report we present a multicriteria method for a plurality of deciders. The method is designed as a decision aiding tool to allow the deciders to rank the alternatives of a given set A according to the criteria of the set C so to define the set of the best alternatives.<br />

Bigi, Giancarlo and Passacantando, Mauro
D-gap functions and descent techniques for solving quilibrium problems
October 22, 2014
UnipiEprints view

A new algorithm for solving equilibrium problems with differentiable bifunctions is provided. The algorithm is based on descent directions of a suitable family of D-gap functions. Its convergence is proved under assumptions which do not guarantee the equivalence between the stationary points of the D-gap functions and the solutions of the equilibrium problem. Moreover, the algorithm does not require to set parameters according to thresholds which depend on regularity properties of the equilibrium bifunction. Finally, the results of preliminary numerical tests on Nash equilibrium problems with quadratic payoffs are reported.



NOTA. Da gennaio 2015 il Technical reports possono essere inseriti nel deposito Open Access UnipiEprints.
Una volta pubblicati saranno visibili anche in queste pagine. Il vecchio sistema TR non è più mantenuto.

Dati importati da UnipiEprints