Pragmatic Estimation of the Elasticity of Demand in Hospitality from Noisy Reservations
Transactions on Engineering and Computing Sciences - Vol. 11, No. 3, 2023, pag. 26-47.
Publication Date: June 25, 2023
Abstract:
In hotels, future prices should be determined based on predictions of future demand and the responses of clients to price changes. Price changes will actively affect future demand. If this effect is neglected, opportunities for promptly and accurately setting prices will be lost, as well as potential increased profits. The role of elasticity of demand in setting optimal prices is well-developed in Economics, but the practical estimation of elasticity for a specific hotel from data about the pickup of reservations is worth investigating. In this paper, we highlight the risk of estimations based on a single A/B test and propose practical rules and pragmatic experiments.
The analysis is based on statistics but simplified so that the results can be easily applied in single hotels without excessive disruption of daily operations. After defining rules to derive error bars on the estimates, we experiment in different situations, including estimations from scratch or by gradually tracking abrupt or seasonal changes, that are more realistic for a hotel in operation. Our methods can be useful to hotel managers who wish to decide about prices based on measuring the response of their potential customers, in a data-driven manner and based on statistically significant estimates.
Keywords: Pickup elasticity of demand, Revenue management, Optimal room pricing, Rule of thumb
Free downloadable PDF: DOI: 10.14738/tecs.113.14739. TECS-Battiti-14739.pdf
RoomTetris in room committing: why the role of minimum-length-of-stay requirements should be revisited
INTERNATIONAL JOURNAL OF CONTEMPORARY HOSPITALITY MANAGEMENT, v. 33, n. 11 (2021), p. 4017-4034
Abstract:
Purpose
– This study aims to analyze how different room-committing practices affect the occupancy and profitability of hotels and it critically reviews the role of minimum-length-of-stay (MLOS) requirements given these findings.
Design/methodology/approach
– The approach uses statistical analysis of simplified contexts to develop understanding, and simulations of more complex situations to confirm the relevance in realistic contexts.
Findings
– The study demonstrates that proper solutions of the room-committing problem improve occupancy and profitability, in particular, for hotels working in high-season and high-occupancy situations. Smart committing algorithms diminish the role of MLOS requirements. More demand can be accepted without sacrificing late-arriving long reservations.
Originality/value
– To the best of the authors’ knowledge, this work, building upon a previous one cited in this paper, is the first to rigorously study the room-committing problem and to demonstrate its relevance in practical situations and its implications on MLOS rules. Keywords Hotel management, Hotel procedures, Optimal algorithms, Room-committing problem, Simulation-based optimization, Information technology, Optimization
Free downloadable PDF: DOI: 10.1108/IJCHM-11-2020-1364
RoomTetris: an optimal procedure for committing rooms to reservations in hotels
JOURNAL OF HOSPITALITY AND TOURISM TECHNOLOGY, v. 11, n. 4 (2020), p. 589-602
Abstract:
Purpose
Many hotels allocate guests to specific rooms immediately after reservation. This happens because individual rooms are sold (and there is no concept of room type) or because the assignment is done by hand at reservation or because of a connection with a channel manager, which is immediately fixing the room number after a reservation request. This early allocation is suboptimal, and it causes the unnecessary rejection of some reservations when the hotel has a high occupancy level. The purpose of this paper is to investigate different room allocation algorithms, including an optimal one (called RoomTetris), aiming at higher occupancy levels and profitability.
Design/methodology/approach
The methodology is based on theoretical results and experimentation. The optimality or the proposed RoomTetris algorithm is demonstrated. Experiments are executed in different contexts, including realistic ones, through the adoption of a hotel simulator, to measure the improvements in the occupancy rate of the optimal and heuristic strategies with respect to random or sub-optimal assignments of rooms.
Findings
The main results are that smart allocation algorithms can greatly reduce the rejection rate (reservation requests which cannot be fit into the hotel room plan) and improve the occupancy level, the percentage of available rooms or beds sold for the various periods.
Research limitations/implications
This analysis can be extended by considering cancellations and overbookings. A second possibility to add flexibility in room allocation for hotels having more than one type of rooms is that the hotel can upgrade and offer a high-price room to the customer, which given an even large flexibility to fix rooms by shifting customers to other compatible types. In addition, more complex integrations with revenue management can also be considered, for cases in which the cost of a room depends on the number of guests.
Practical implications
Given that the difference in occupancy rate of the optimal algorithm is particularly large in high season and high-request periods, periods which are usually associated to higher rates and higher volumes, the proposed algorithm will improve the main financial performance indicators such as revenue per available room by an even bigger multiplier, depending on the hotel pricing policy. Because the room allocation process can be completely automated, the adoption of appropriate smart allocation algorithms represents a low-hanging fruit to be picked by efficient hotel managers.
Originality/value
To the best of the knowledge this is the first proposal of an optimal algorithm (with proof of optimality) for the considered problem.
Free downloadable PDF: DOI: 10.1108/JHTT-08-2019-0108
Learning Modulo Theories for preference elicitation in hybrid domains
in ARTIFICIAL INTELLIGENCE, v. 295, (2021), p. 10345401-10345418. - URL: DOI: 10.1016/j.artint.2021.103454.
PDF: (local preprint copy) CLEO_paper.pdf
Combining intelligent heuristics with simulators in hotel revenue management
Annals of Mathematics and Artificial Intelligence (2020) 88:71–90.
Abstract:
Revenue Management uses data-driven modelling and optimization methods to decide what to sell, when to sell, to whom to sell, and for which price, in order to increase revenue and profit. Hotel Revenue Management is a very complex context characterized by nonlinearities, many parameters and constraints, and stochasticity, in particular in the demand by customers. It suffers from the curse of dimensionality (Bellman 2015): when the number of variables increases (number of rooms, number possible prices and capacities, number of reservation rules and constraints) exact solutions by dynamic programming or by alternative global optimization techniques cannot be used and one has to resort to intelligent heuristics, i.e., methods which can improve current solutions but without formal guarantees of optimality. Effective heuristics can incorporate “learning” (“reactive” schemes) that update strategies based on the past history of the process, the past reservations received up to a certain time and the previous steps in the iterative optimization process. Different approaches can be classified according to the specific model considered (stochastic demand and hotel rules), the control mechanism (the pricing policy) and the optimization technique used to determine improving or optimal solutions. In some cases, model definitions, control mechanism and solution techniques are strongly interrelated: this is the case of dynamic programming, which demands suitably simplified problem formulations. We design a flexible discrete-event simulator for the hotel reservation process and experiment different approaches though measurements of the expected effect on profit (obtained by carefully separating a “training” phase from the final “validation” phase obtained from different simulations). The experimental results show the effectiveness of intelligent heuristics with respect to exact optimization methods like dynamic programming, in particular for more constrained situations (cases when demand tends to saturate hotel room availability), when the simplifying assumptions needed to make the problem analytically treatable do not hold.
https://doi.org/10.1007/s10472-019-09651-9
The final publication is available electronically at Springer Verlag
PDF Preprint: AMAI-hotels.pdf
HotelSimu: a Parametric Simulator for Hotel Dynamic Pricing
Oct 2018, submitted
PDF: hotelsimu.pdf
Machine learning and intelligent optimization in tourism and hospitality: “Rocket Science” without the need of scientists
Feb 16, 2018, White Paper, University of Trento
PDF: white-paper-battiti-brunato.pdf
Feature Selection based on the Neighborhood Entropy
IEEE Transactions on Neural Networks and Learning Systems, Accepted for publication, 2018.
Manuscript Number: TNNLS-2017-P-7709.R2
Print ISSN:
Online ISSN:
Digital Object Identifier:
PDF: nefs.pdf
Salary Prediction in the IT Job Market with Few High-Dimensional Samples: A Spanish Case Study
INTERNATIONAL JOURNAL OF COMPUTATIONAL INTELLIGENCE SYSTEMS, v. 2018, n. 11.1 (2018), p. 1192-1209. DOI: 10.2991/ijcis.11.1.90
PDF: technoempleo.pdf
Proceedings of the 11th Learning and Intelligent international OptimizatioN conference LION-11 held in Nizhny Novgorod, Russia in June 19-21, 2017
Springer Verlag, in press, 2017.
PDFs: 435851 Cover 435851 Preface 435851 Book Authors
A Reactive Self-Tuning Scheme for Multilevel Graph PArtitioning
Applied Mathematics and Computation, 318 (2018), pag. 227-244.
Interactive sparse optimization of unknown combinatorial utility functions through machine learning
Journal of Artificial Intelligence Research, under revision.
PDF: combPrefOpt.pdf
Extreme Reactive Portfolio (XRP): Tuning an Algorithm Population for Global Optimization
Proceedings of Learning and Intelligent OptimizatioN Conference LION 10, Ischia Island (Napoli), Italy, 29 May - 1 June, 2016
Springer Verlag, in press.
Digital Object Identifier:
PDF: battiti-lion2016.pdf
The LION way: machine Learning for Intelligent OptimizatioN: a source of power for innovation in business
Tutorial at NUMTA 2016, Numerical Computations: Theory and Algorithms Pizzo Calabro, Italy 19-25 June 2016.
GENOPT 2016: Design and Results of a GENeralizationbased Challenge in Global OPTimization
Proceedings of NUMTA 2016, Numerical Computations: Theory and Algorithms, Pizzo Calabro, Italy 19-25 June 2016, The American Institute of Physics (AIP) Conference Proceedings.
Digital Object Identifier:
Optimization by Populations of Collaborative Local Searchers
Proceedings of NUMTA 2016, Numerical Computations: Theory and Algorithms, Pizzo Calabro, Italy 19-25 June 2016, The American Institute of Physics (AIP) Conference Proceedings.
A Telescopic Binary Learning Machine for Training Neural Networks
IEEE Transactions on Neural Networks and Learning Systems, Accepted for publication, 2016.
Manuscript Number: TNNLS-2015-P-5760
Print ISSN: 2162-237X
Online ISSN: 2162-2388
Digital Object Identifier: 10.1109/TNNLS.2016.2537300
URL: DOI: 10.1109/TNNLS.2016.2537300
PDF preprint: battiti-blm-ieee-tnnls.pdf
X-MIFS: Exact Mutual information for Feature Selection
Proc. 2016 International Joint Conference on Neural Networks (IJCNN) , July 24-29, Vancover, Canada, 2016, pages 3469-3476
PDF: (preprint) battiti-wcci2016.pdf
978-1-5090-0620-5/16/2016 IEEE
CoRSO (Collaborative Reactive Search Optimization): Blending Combinatorial and Continuous Local Search
INFORMATICA, 2016, Vol. 27, No. 2, pages 299-322
DOI: http://dx.doi.org/10.15388/Informatica.2016.86
PDF: (local preprint copy) informatica-2016.pdf
The LION way. Machine Learning plus Intelligent Optimization.
R. Battiti and M. Brunato
LIONlab, University of Trento, Italy, Version 2.0, Apr 2015.
BibTex:
@book{LIONway2015
author = "Roberto Battiti and Mauro Brunato",
title = "The LION way. Machine Learning {\em plus} Intelligent Optimization",
publisher = "LIONlab, University of Trento, Italy",
year = "2014",
isbn = "978-14-960340-2-1"
}
Abstract: This book is about learning for problem solving. [...] Human problem solving is strongly connected to learning. Learning takes places when the problem at hand is not well known at the beginning, and its structure becomes more and more clear when more experience with the problem is available. [...] What is critical for men is critical also in many human-developed problem solving strategies. It is not surprising that many methods for solving problems in Artificial Intelligence, Operations Research and related areas, follow the search scheme [...]
We aim at giving the main principles and at developing some fresh intuition for the approaches. We like mathematics but we also think that hiding the underlying motivations and sources of inspiration takes some color out of the scientific work [...]. On the other hand, pictures and hand-waving can be very dangerous in isolation and we try to avoid these pitfalls by giving also the basic equations when possible, or by at least directing the reader to the bibliographic references for deepening a topic. The point of view of the book is to look at the zoo of different optimization beasts to underline opportunities for learning and self-tuning strategies.
(From the Introduction)
BibTex:
@BOOK{BBM2008,
AUTHOR = {Roberto Battiti and Mauro Brunato and Franco Mascia},
TITLE = {Reactive Search and Intelligent Optimization},
PUBLISHER = {Springer Verlag},
YEAR = {2008},
series = {Operations research/Computer Science Interfaces},
note = {ISBN: 978-0-387-09623-0},
ulr = {http://www.springer.com/978-0-387-09623-0}
}
Preprint of book (PDF) Reactive-Search-and-Intelligent-Optimization-Battiti-Brunato-Mascia-preprint.pdf
Stochastic Local Search for Direct Training of Threshold Networks
Proc. 2015 International Joint Conference on Neural Networks , pag. 1-8, 2015.
journal link ( DOI: 10.1109/IJCNN.2015.7280770 )
PDF: (local copy) battiti-ijcnn2015.pdf
Link to IJCNN Conference: IJCNN 2015 - Killarney
Hybridization of Decomposition and Local Search for Multiobjective Optimization
IEEE Transaction on Cybernetics , vol. 44, no. 10, October 2014, pag. 1808-1820.
DOI: 10.1109/TCYB.2013.2295886
PDF: (local cache copy) hybridization-2014.pdf
Link to IEEE publication: IEEE Xplore Digital Library
Discovering Non-Redundant Overlapping Biclusters on Gene Expression Data,
Proceedings The IEEE 13th International Conference on Data Mining series (ICDM 2013) , Dallas, Texas / December 7-10, 2013, pages 747-756. IEEE Computer Society . DOI 10.1109/ICDM.2013.36
PDF proofs: biclustering-icdm2013.pdf
Learning to diversify in complex interactive Multiobjective Optimization
Best Paper Award MIC 2013: The X Metaheuristics International Conference , Singapore, Aug 5-8, 2013, Singapore.
MIC 2013 website
PDF (preprint) MIC-BEST-paper.pdf
Active learning of Pareto fronts with disconnected feasible decision and objective spaces
MIC 2013: The X Metaheuristics International Conference , Singapore, Aug 5-8, 2013, Singapore.
MIC 2013 website
PDF (preprint) MIC-ALPI.pdf
Active learning of Pareto fronts
IEEE Transactions on Neural Networks and Learning Systems , Volume:25 , Issue: 3, March 2014 Page(s): 506 - 519 ISSN : 2162-237X INSPEC Accession Number: 14111769
Digital Object Identifier: 10.1109/TNNLS.2013.2275918
PDF (preprint) alp-2014.pdf
Abstract: This work introduces the Active Learning of Pareto fronts (ALP) algorithm, a novel approach to recover the Pareto front of a multi-objective optimization problem. ALP casts the identification of the Pareto front into a supervised machine learning task. This approach enables an analytical model of the Pareto front to be built. The computational effort in generating the supervised information is reduced by an active learning strategy. In particular, the model is learnt from a set of informative training objective vectors. The training objective vectors are approximated Pareto-optimal vectors obtained by solving different scalarized problem instances. The experimental results show that ALP achieves an accurate Pareto front approximation with a lower computational effort than state-of-the-art Estimation of Distribution Algorithms and widely-known genetic techniques.
A flexible cluster-oriented alternative clustering algorithm for choosing from the Pareto front of solutions
Machine Learning , Accepted: 3 April 2013.
Published online: 24 April 2013 at (springer.com) DOI 10.1007/s10994-013-5350-y
PDF (preprint) cognac_journal.pdf
Abstract:
Supervised alternative clustering is the problem of finding a set of clusterings which are of high quality
and different from a given negative clustering. The task is therefore a clear multi-objective optimization
problem. Optimizing two conflicting objectives at the same time requires dealing with trade-offs. Most
approaches in the literature optimize these objectives sequentially (one objective after another one)
or indirectly (by some heuristic combination of the objectives). Solving a multi-objective optimization
problem in these ways can result in solutions which are dominated, and not Pareto-optimal. We develop a
direct algorithm, called COGNAC, which fully acknowledges the multiple objectives, optimizes them directly
and simultaneously, and produces solutions approximating the Pareto front. COGNAC performs the recombination
operator at the cluster level instead of at the object level, as in the traditional genetic algorithms.
It can accept arbitrary clustering quality and dissimilarity objectives and provides solutions dominating
those obtained by other state-of-the-art algorithms. Based on COGNAC, we propose another algorithm called
SGAC for the sequential generation of alternative clusterings where each newly found alternative clustering
is guaranteed to be different from all previous ones. The experimental results on widely used benchmarks
demonstrate the advantages of our approach.
Index Terms: Alternative clustering, Multi-objective optimization, Cluster-oriented recombination Genetic algorithms
A Repeated Local Search Algorithm for BiClustering of Gene Expression Data
In: E. Hancock and M. Pelillo (Eds.): Proceedings of SIMBAD 2013, LNCS 7953, pp. 281-296, 2013. , Springer Verlag.
PDF (preprint) simbad-2013.pdf
Abstract:
Given a gene expression data matrix where each cell is the
expression level of a gene under a certain condition, biclustering is the
problem of searching for a subset of genes that coregulate and coexpress
only under a subset of conditions. The traditional clustering algorithms
cannot be applied for biclustering as one cannot measure the similarity
between genes (or rows) and conditions (or columns) by normal geometric
similarities. Identifying a network of collaborating genes and a subset of
experimental conditions which activate the specific network is a crucial
part of the problem. In this paper, the BIClustering problem is solved
through a REpeated Local Search algorithm, called BICRELS. The
experiments on real datasets show that our algorithm is not only fast
but it also significantly outperforms other state-of-the-art algorithms.
Index Terms: biclustering, co-clustering, local search, gene expression,
microarray.
MOEA/D-ACO: A Multiobjective Evolutionary Algorithm Using Decomposition and Ant Colony
IEEE Transaction on Cybernetics ,
VOL. 43, NO. 6, DECEMBER 2013, pag. 1845-1859.
Digital Object Identifier 10.1109/TSMCB.2012.2231860
10.1109/TSMCB.2012.2231860 IEEE Explore
PDF (local cache copy) ACOD-published.pdf
Abstract:
Combining ant colony optimization (ACO) and
multiobjective evolutionary algorithm based on decomposition
(MOEA/D), this paper proposes a multiobjective evolutionary
algorithm, MOEA/D-ACO. Following other MOEA/D-like algorithms,
MOEA/D-ACO decomposes a multiobjective optimization
problem into a number of single objective optimization problems.
Each ant (i.e. agent) is responsible for solving one subproblem.
All the ants are divided into a few groups and each ant has several
neighboring ants. An ant group maintains a pheromone matrix
and an individual ant has a heuristic information matrix. During
the search, each ant also records the best solution found so far
for its subproblem. To construct a new solution, an ant combines
information from its group's pheromone matrix, its own heuristic
information matrix and its current solution. An ant checks the
new solutions constructed by itself and its neighbors, and updates
its current solution if it has found a better one in terms of
its own objective. Extensive experiments have been conducted
in this paper to study and compare MOEA/D-ACO with other
algorithms on two set of test problems. On the multiobjective 0-1
knapsack problem, MOEA/D-ACO outperforms MOEA/D-GA on
all the nine test instances. We also demonstrate that the heuristic
information matrices in MOEA/D-ACO are crucial to the good
performance of MOEA/D-ACO for the knapsack problem. On the
biobjective traveling salesman problem, MOEA/D-ACO performs
much better than BicriterionAnt on all the 12 test instances.
We also evaluate the effects of grouping, neighborhood and the
location information of current solutions on the performance
of MOEA/D-ACO. The work in this paper shows that reactive
search optimization scheme, i.e., the "learning while optimizing"
principle, is effective in improving multiobjective optimization
algorithms.
Index TermsAnt colony optimization (ACO) , decomposition , multiobjective 0-1 knapsack problem (MOKP) ,
multiobjective optimization , multiobjective traveling salesman problem (MTSP) , reactive search optimization (RSO).
A Cluster-Oriented Genetic Algorithm for Alternative Clustering
Proceedings The IEEE International Conference on Data Mining series (ICDM 2012) , Bruxelles, Belgium, Dec 10-13, 2012.
PDF proofs: PID2565417.pdf
Abstract:
Supervised alternative clusterings is the problem
of finding a set of clusterings which are of high quality and
different from a given negative clustering. The task is therefore
a clear multi-objective optimization problem. Optimizing two
conflicting objectives requires dealing with trade-offs. Most
approaches in the literature optimize these objectives sequentially
or indirectly, resulting in solutions which are dominated.
We develop a multi-objective algorithm, called COGNAC, able
to optimize the objectives directly and simultaneously and
producing solutions approximating the Pareto front. COGNAC
performs the recombination operator at the cluster level instead
of the object level as in traditional genetic algorithms. It can
accept arbitrary clustering quality and dissimilarity objectives
and provide solutions dominating those of other state-of-the-art
algorithms. COGNAC can also be used to generate a sequence
of alternative clusterings, each of which is guaranteed to be
different from all previous ones.
Keywords: alternative clustering; multi-objective optimization;
cluster-oriented; genetic algorithm.
Reactive Business Intelligence. From Data to Models to Insight.
R. Battiti and M. Brunato,
Reactive Search Srl, Italy, February 2011.
ISBN: 978-88-905795-0-9
Abstract:
It is obvious, you can see it! Think about how many times you intuitively associate clarity and real
understanding with vision. The word intelligence itself derives from the Latin verb intelligere (coming
from intus legere, "reading into something," a close cousin of "insight"), again related to reading and
seeing. Humans are innately visual creatures and a big portion of our brain is devoted to processing
visual information. Our ancestors needed to be very fast to identify predators in the jungle and to react
accordingly. They did not survive and transmit genes if they did not. We need to be very fast to transform
huge amounts of information into insight, knowledge, engineering designs, choices, decisions.
We decided to unite in this book aspects related to modeling and aspects related to visualizing data
and models. We are concerned with explanations of our world which can be used, used to predict, used
to build tools. This means measuring objects and events, mining and analyzing massive amounts of
data, and discovering interesting relationships emerging from the data. Visual analytics is a term used
to denote analytical reasoning facilitated by interactive visual interfaces. The effort is surely related to
data mining, the process of automatically extracting interesting patterns from massive amounts of data.
We prefer the term Reactive Business Intelligence (RBI) to underline its practical orientation and
the fast reaction implied by two basic learning components, one connecting the user to the software, a
second one internal to the software, through automated and intelligent self-tuning methods. A connection
between visualization and problem-solving strategies is also at the heart of RBI: the decision maker
can be, and should be, in an interactive loop, rapidly reacting to first results and visualizations to direct
the subsequent efforts to suit his needs and preferences.
(From the Introduction)
The material in this book is now extended and updated in our
LION way but pls contact me
if you are still interested in this particular book.
R-evo: A Reactive Evolutionary Algorithm for the Maximum Clique Problem
IEEE Transactions on Evolutionary Computation , Volume: 15 Issue:6, page(s): 770-782, ISSN: 1089-778X, Digital Object Identifier: 10.1109/TEVC.2010.2043363, December 2011.
link to IEEE Transactions on Evolutionary Computation paper
PDF proofs: revo-2011.pdf
Abstract: see also AbstractPlus
An evolutionary algorithm with guided mutation (EA/G) has been proposed recently for solving the maximum clique problem.
In the framework of estimation-of-distribution algorithms, guided mutation uses a model distribution to generate offspring
by combining the local information of solutions found so far with global statistical information. Each individual
is then subjected to a Marchiori's repair heuristic, based on randomized extraction and greedy expansion, to ensure
that it represents a legal clique. A novel reactive and evolutionary algorithm R-EVO proposed in this paper starts
from the same evolutionary framework but considers more complex individuals, which modify tentative solutions by
local search with memory, according to the reactive search optimization (RSO) principles. In particular,
the estimated distribution is used to periodically initialize the state of each individual based on the previous
statistical knowledge extracted from the population. We demonstrate that the combination of the estimation-of-distribution
concept with RSO produces significantly better results than EA/G for many test instances and it is remarkably
robust with respect to the setting of the algorithm parameters. R-EVO adopts a drastically simplified
low-knowledge version of reactive local search (RLS), with a simple internal diversification mechanism
based on tabu-search, with a prohibition parameter proportional to the estimated best clique size.
R-EVO is competitive with the more complex full-knowledge RLS-EVO that adopts the original RLS algorithm.
For most of the benchmark instances, the hybrid scheme version produces significantly better results than EA/G
for comparable or a smaller central processing unit time.
Proceedings of Learning and Intelligent OptimizatioN LION 4, Jan 18-22, 2010, Venice, Italy. Lecture Notes in Computer Science Volume 6073, 2010, DOI: 10.1007/978-3-642-13800-3, pag. 232-246
Digital version available: SpringerLink site
Handling concept drift in preference learning for interactive decision making.
Proceedings of HaCDAIS 2010: International Workshop on Handling Concept Drift in Adaptive Information Systems, Barcelona, Spain, Sep 2010. Mykola Pechenizkiy and Indre Zliobaite (Eds.), pag. 29-40. (online publications)
Digital version available: hacdais2010.pdf , workshop page .
An Investigation of Reinforcement Learning for Reactive Search Optimization.
Youssef Hamadi and Eric Monfroy (Eds.)Autonomous Search, Springer Verlag, 2011.
Digital version available: autonomous-chapter10.pdf
Active Learning of Combinatorial Features for Interactive Optimization.
Proceedings of LION5, Learning and Intelligent OptimizatioN, Rome - Italy, Jan 17-21, Springer Verlag, (Editor Carlos A.Coello Coello), volume 6683, series: Lecture Notes in Computer Science, 2011, pages 336-350.
link to Springer book , link to Springer book paper ,
Digital version available: LION5-campigotto-pub.pdf
An On/Off Lattice Approach to Protein Structure Prediction from Contact Maps.
. Proceedings Pattern Recognition in Bioinformatics (PRIB2010), Lecture Notes in Bioinformatics (LNBI), 2010
Digital version available: prib2010.pdf
Reactive Search Optimization: Learning While Optimizing. An Experiment in Interactive Multi-Objective Optimization.
Proceedings of MIC2009, VIII Metaheuristic International Conference, 2010.
Digital version available: mic2009.pdf
Reactive Search Optimization: Learning while Optimizing
Michel Gendreau and Jean-Yves Potvin (Eds.), Handbook of Metaheuristics (2nd edition), Series: International Series in Operations Research & Management Science, Vol. 146, 2010. Springer Science+Business Media, LLC 2010, pag. 543--571.
DOI 10.1007/978-1-4419-1665-5_18
Digital version available: handbook2009.pdf , Springer link
Brain-Computer Evolutionary Multi-Objective Optimization (BC-EMO): a genetic algorithm adapting to the decision maker
IEEE Transactions on Evolutionary Computation, Vol. 14, Issue 15, pag. 671 - 687, 2010. Digital Object Identifier : 10.1109/TEVC.2010.2058118
PDF proofs: bcemo.pdf
BC-EMO.tgz Software for Brain-Computer Evolutionary Multi-Objective Optimization (BC-EMO): a genetic algorithm adapting to the decision maker.
R-EVO: a Reactive Evolutionary Algorithm for the Maximum Clique Problem
IEEE Transactions on Evolutionary Computation, 2010.
PDF proofs: ieee-tevo.pdf
Abstract: An evolutionary algorithm with guided mutation (EA/G) has been proposed recently for solving the maximum clique problem. In the framework of estimation-of-distribution algorithms (EDA), guided mutation uses a model distribution to generate offspring by combining the local information of solutions found so far with global statistical information. Each individual is then subjected to a Marchiori's repair heuristic, based on randomized extraction and greedy expansion, to ensure that it represents a legal clique. A novel reactive and evolutionary algorithm (R-EVO) proposed in this paper starts from the same evolutionary framework but considers more complex individuals, which modify tentative solutions by local search with memory, according to the Reactive Search Optimization (RSO) principles. In particular, the estimated distribution is used to periodically initialize the state of each individual based on the previous statistical knowledge extracted from the population. We demonstrate that the combination of the estimation-of-distribution concept with RSO produces significantly better results than EA/G for many test instances and it is remarkably robust w.r.t. the setting of the algorithm parameters. R-EVO adopts a drastically simplified low-knowledge version of Reactive Local Search (RLS), with a simple internal diversification mechanism based on tabu-search, with a prohibition parameter proportional to the estimated best clique size. REVO is competitive with the more complex full-knowledge RLSEVO which adopts the original RLS algorithm. For most of the benchmark instances, the hybrid scheme version produces significantly better results than EA/G for comparable or a smaller CPU time.
Index Terms: Maximum Clique, Reactive Search Optimization (RSO), Estimation of Distribution, guided mutation
Grapheur: A Software Architecture for Reactive and Interactive Optimization
Proceedings Learning and Intelligent OptimizatioN LION 4, Jan 18-22, 2010, Venice, Italy. Lecture Notes in Computer Science Volume 6073, 2010, DOI: 10.1007/978-3-642-13800-3, pag. 232-246
Digital version available: grapheur-lion4.pdf
Graph and hyper-graph partitioning
Invited presentation at the 9th Haifa Workshop on Interdisciplinary Applications of Graph Theory, Combinatorics and Algorithms, 20-21 May 2009, Haifa (Israel)
Slides: haifa.pdf.
Brain-machine optimization: learning objective functions by interacting with the final user
European Chapter on Combinatorial Optimization (ECCO) XXII , May 17-19, 2009, Jerusalem (Israel)
Slides: ecco09.pdf.
Reactive and Dynamic Local Search for Max-Clique: Engineering Effective Building Blocks.
Computers and Operations Research 37, issue 3 (March 2010) 534 -- 542
Digital version available (preprint): COR.pdf , permanent link to published version(DOI doi:10.1016/j.cor.2009.02.013 ) .
Abstract: This paper presents results of an ongoing investigation about how different algorithmic building blocks contribute to solving the Max- imum Clique problem. We consider greedy constructions, plateau searches, and more complex schemes based on dynamic penalties and/or prohibitions, in particular the recently proposed technique of Dynamic Local Search and the previously proposed Reactive Local Search (RLS). We design a variation of the original RLS algorithm where the role of long-term memory is increased (RLS-LTM). In addition, we consider in detail the effect of the low-level implementation choices on the CPU time per iteration. We present experimental results on randomly gen- erated graphs with different statistical properties, showing the crucial effects of the implementation, the robustness of different techniques, and their empirical scalability.
Reinforcement Learning and Reactive Search: an adaptive MAX-SAT solver,
in ECAI 08: 18th European Conference on Artificial Intelligence, Patras, Greece, Jul 21-25, 2008.
Digital version available: reinforcement_ECAI08.pdf
Abstract: This paper investigates Reinforcement Learning (RL) applied to online parameter tuning in Stochastic Local Search (SLS) methods. In particular, a novel application of RL is proposed in the Reactive Tabu Search (RTS) scheme, where the appropriate amount of diversification in prohibition-based local search is adapted in a fast online manner to the characteristics of a task and of the local configuration. The experimental tests demonstrate promising results onMaximumSatisfiability (MAX-SAT) instances when compared with state-of-the-art SLS SAT solvers, such us AdaptNovelty+, rSAPS and gNovelty+.
Penalties may have collateral effects. A MAX-SAT analysis.
, in Workshop on Modeling and Solving Problems with Constraints (in conjunction with the 18th European Conference on Artificial Intelligence, ECAI 2008), Patras, Greece, Jul 21-22, 2008.
Digital version available: sideEffects_ECAI08.pdf
Abstract: Many incomplete approaches for MAX-SAT have been proposed in the last years. The objective of this investigation is not so much horse-racing (beating the competition on selected benchmarks) but understanding the qualitative differences between the various methods. In particular, we focus on reactive search schemes where taskdependent and local properties in the configuration space are used for the dynamic on-line tuning of local search parameters and we consider the choice between prohibition-based and penalty-based approaches. To abstract from implementation details we focus on the search trajectory characteristics and study the trade-off between diversification and bias after starting from a local minimizer. We then study the warping effects on the fitness surface of weight-update schemes and the resulting dynamics, through an exhaustive analysis of small MAX-SAT instances, and of the average evolution of individual trajectories. The results are compatible with the conclusion that penalty-based schemes achieve diversification from a starting local optimum through a complex method with global and potentially dangerous collateral effects, while prohibition-based schemes reach comparable or better results in a more direct and controllable manner. In the final part of this paper, we consider long runs of the complete algorithms on selectedMAX-SAT instances, which confirm the competitiveness of prohibition-based reactive approaches.
.
An Algorithm Portfolio for the Sub-Graph Isomorphism Problem
Proceedings of Stochastic Local Search 2007, Lecture Notes in Computer Science. Volume 4638/2007, Springer 2007, Pages 106-120.
Digital version available: Springer page , preprint: battiti_mascia_portfolio.pdf
Abstract: This work presents an algorithm for the sub-graph isomorphism problem based on a new pruning technique for directed graphs. During the tree search, the method checks if a new association between two vertices is compatible by considering the structure of their local neighborhoods, represented as the number of limited-length paths of different type originating from each vertex. In addition, randomized versions of the algorithms are studied experimentally by deriving their runtime distributions. Finally, algorithm portfolios consisting of multiple instances of the same randomized algorithm are proposed and analyzed. The experimental results on benchmark graphs demonstrate that the new pruning method is competitive w.r.t. recently proposed techniques. Significantly better results are obtained on sparse graphs. Furthermore, even better results are obtained by the portfolios, when both the average and standard deviation of solution times are considered.
Learning and Intelligent Optimization Second International Conference, LION 2007 II, Trento, Italy, December 8-12, 2007. Selected Papers Series: Lecture Notes in Computer Science
Subseries: Theoretical Computer Science and General Issues , Vol. 5313
Maniezzo, Vittorio; Battiti, Roberto; Watson, Jean-Paul (Eds.)
2008, XII, 243 p., Softcover
ISBN: 978-3-540-92694-8
Springer book page
Learning while Optimizing an Unknown Fitness Surface.
Proc. 2nd Learning and Intelligent Optimization Workshop (LION2007 II, Trento, Italy, December 2007), pag. 25-40. LNCS 5313 - Springer, December 2008.
Digital version available: lionII-LSPI.pdf
Springer book page (DOI: 10.1007/978-3-540-92695-5_3)
On Effectively Finding Maximal Quasi-Cliques in Graphs.
Proc. 2nd Learning and Intelligent Optimization Workshop (LION2007 II, Trento, Italy, December 2007). LNCS 5313 - Springer, December 2008.
Digital version available: lionII-quasi.pdf
Springer book page
RASH: A Self-adaptive Random Search Method.
In: Carlos Cotta, Marc Sevaux, and Kenneth Sörensen (Eds.), Adaptive and Multilevel Metaheuristics. Studies in Computational Intelligence, Vol. 136, Springer, 2008. ISBN: 978-3-540-79437-0
Digital version available: RASH.pdf
Springer book page
Weak Data Secrecy via Obfuscation in Network Coding Based Content Distribution.
Accepted to the IFIP Wireless Days Conference, Dubai, United Arab Emirates, November 24-28 2008
Digital version available: ifip-2008.pdf
An efficient weak secrecy scheme for network coding data dissemination in VANET - Invited Paper.
In Proceedings of the IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC 2008), Cannes, France, September 15-18 2008, pages 1-5.
Digital version available: GCCCB08-VANET-PIMRC.pdf , IEEE Proceedings web site
Abstract: Vehicular networks create a new communication paradigm that enables to exploit the movement of cars to disseminate content. If network coding is used, vehicles have much more flexibility in content sharing and the system stability and scalability are promoted also in presence of mobility. Along this line, we propose an efficient mechanism to provide secrecy of the information. Traditional approaches based on encryption decrease the cooperation willingness of intermediate nodes, which have no expectation of recovering the file. Our scheme is based on obfuscation by processing and polluting the original file so that only the intended recipients, informed of corrupted blocks, can recover the information timely. We present several alternatives to efficiently provide weak secrecy and to foster cooperation. We simulate the file distribution in a vehicular network and show that the proposed scheme enhances content distribution in term of downloading speed and it is much more efficient than the ones that use encryption.
Social Networking and Game Theory to foster Cooperation.
Input paper at the 2nd ENISA Workshop on Authentication Interoperability Languages held at the ENISA/EEMA European eIdentity conference, Paris, France, June 12-13, 2007.
Digital version available: CB07-ENISA.pdf
R-EVO: a Reactive Evolutionary Algorithm for the Maximum Clique Problem
Technical report DIT-07-034 Università di Trento, May 2007
Digital version available: DIT-07-034.pdf
REACTIVE SEARCH: MACHINE LEARNING FOR MEMORY-BASED HEURISTICS
Chapter 21 in: Teofilo F. Gonzalez (Ed.), Approximation Algorithms and Metaheuristics , Taylor & Francis Books (CRC Press), Washington, DC, 2007, pag. 21-1 -- 21-17
Digital version available: chap21.pdf
Abstract: Most state-of-the-art heuristics are characterized by a certain number of choices and free parameters, whose appropriate setting is a subject that raises issues of research methodology. In some cases, these parameters are tuned through a feedback loop that includes the user as a crucial learning component: depending on preliminary algorithm tests some parameter values are changed by the user, and different options are tested until acceptable results are obtained. Therefore, the quality of results is not automatically transferred to different instances and the feedback loop can require a lengthy \trial and error" process every time the algorithm has to be tuned for a new application. Parameter tuning is therefore a crucial issue both in the scientific development and in the practical use of heuristics. In some cases the role of the user as an intelligent (learning) part makes the reproducibility of heuristic results difficult and, as a consequence, the competitiveness of alternative techniques depends in a crucial way on the user's capabilities. Reactive Search advocates the use of simple sub-symbolic machine learning to automate the parameter tuning process and make it an integral (and fully documented) part of the algorithm. If learning is performed on line, task-dependent and local properties of the configuration space can be used by the algorithm to determine the appropriate balance between diversification (looking for better solutions in other zones of the configuration space) and intensification (exploring more intensively a small but promising part of the configuration space). In this way a single algorithm maintains the exibility to deal with related problems through an internal feedback loop that considers the previous history of the search. In the following, we shall call reaction the act of modifying some algorithm parameters in response to the search algorithm's behavior during its execution, rather than between runs. Therefore, a reactive heuristic is a technique with the ability of tuning some important parameters during execution by means of a machine learning mechanism. It is important to notice that such heuristics are intrinsically history-dependent; thus, the practical success of this approach in some cases raises the need of a sounder theoretical foundation of non-Markovian search techniques.
Digital Reputation for Virtual Communities
Chapter 85 in: Teofilo F. Gonzalez (Ed.), Approximation Algorithms and Metaheuristics , Taylor & Francis Books (CRC Press), Washington, DC, 2007, pag. 85-1 -- 85-16.
Digital version available: chap85.pdf
Abstract: A virtual community can be defined as a group of people sharing a common interest or goal who interact over a virtual medium, most commonly the Internet. Virtual communities are characterized by an absence of face-to-face interaction between participants which makes the task of measuring the trustworthiness of other participants harder than in nonvirtual communities. This is due to the anonymity that the Internet provides, coupled with the loss of audiovisual cues that help in the establishment of trust. As a result, digital reputation management systems are an invaluable tool for measuring trust in virtual communities. Trust is an important component of all human interactions whether they take place online or not. There is an implicit assumption of trust in each interaction that we participate in that involves some investment on our part. The Merriam-Webster dictionary defines trust as assured reliance on the character, ability, strength, or truth of someone or something. Even more pertinent to virtual communities is an alternative definition which states that trust is a dependence on something future or contingent; reliance on future payment for property (as merchandise) delivered. These definitions illustrate that the basis of trust is an expectation of future payment or reward and that the transaction partner will behave in an honest fashion and fulfill their obligations. The processes behind the creation of trust can be classified into four broad categories: 1. Personality-based trust. A person's innate disposition to trust others. 2. Cognitive trust. Through recognition of the characteristics of the transaction partner. 3. Institution-based trust. A buyer's perception that effective (third-party) institutional mechanisms are in place to facilitate transaction success. 4. Transaction-based trust. That relies on a participant's past behavior to assess their trustworthiness. Personality-based trust does not have a significant use in virtual communities where decisions on trust aremade algorithmically.Most cognitive factors that formtrust in real-life interactions such as the manner of a person, their body language, and the intonations of their speech are also absent in virtual communities. However, there are alternative formsof cognition that can be used instead. These are almost invariably based on the virtual identity of the communitymember. In most purely online contexts, as opposed to contexts where the online identity is linked to a nononline identity such as with online banking, there are virtually no costs to creating a new virtual identity.Obtaining an e-mail address on any of the free web-based e-mail services such asYahoo,Hotmail, Gmail is trivial andwith each one comes a new virtual identity.While these services are increasingly adopting strategies such as requiring image reading to counter automated registrationspamprograms, it is not difficult tocreate say adozen accounts in 10 min.Andas the e-Bay scam case showed, that is all a malicious user needs to surmount simple feedback systems and commit online fraud. Enforcing trust in virtual communities is hard not only because of the difficulties in recognizing the trustworthiness of participants but also because of the lack of adequate monitoring and appropriate sanctions for dishonest behavior. This lack of institution-based trust is because there are not enough trusted third parties with the power to punish to ensure honesty of all the players. This problem is exacerbated in decentralized virtual communities and electronic marketplaces. An organization like e-Bay with a centralized infrastructure can act as the trusted third party to at least store feedback information in a reliable fashion even though the information itself may not be reliable. The problem becomes much harder with decentralized systems such as peer-to-peer (P2P) networks where the absence of a centralized authority is a defining feature of the system. Hence, it appears that the best strategy for creating trust in virtual communities is through transactionbased trust where feedback on participants' past behavior is collected and aggregated to decide their trustworthiness. A transaction-based trust strategy is far from perfect and suffers from many of the same shortcomings as the other strategies. For instance, the lack of verifiable identities can make a transactionbased system vulnerable to manipulation. However, as many recent proposals have shown such strategies are not contingent upon a trusted third party and the community as a whole provides the institutional basis for trust. Hence, if the problem of identity can be solved, transaction-based systems are capable of providing the solution for virtual communities. Transaction-based trust creation strategies are also commonly known as reputation-based trust management systems or just reputation systems. Some authors use the term reputation systems narrowly to include only those systems that monitor past transactions of participants to compute their trustworthiness. This information is then shared with other participants who decide whether or not to interact with the target participant on its basis. We use the term in a more general sense to include recommendations systems that recommend items as well as systems that perform distributed authentication by inferring trustworthiness. All these systems have one feature in common: the collection and aggregation of feedback in order to rate objects or people. Reputation systems research lies at the intersection of several disciplines including evolutionary biology, economics (game theory and mechanism design), sociology (social network theory), and computer science (e-commerce, P2P systems, cryptography, etc.). In this chapter, we survey the approaches taken by researchers fromthese disciplines to provide the context for digital reputation schemes. We begin by listing the various applications of digital reputation systems. This is followed by a discussion of what motivates the participants of a virtual community to cooperate with each other.We then look at what are the requirements of a good reputation system. This is followed by a more detailed analysis of the components of reputation systems.We classify different types of feedback and their role in constructing reputations. We discuss second-order reputation and the motivations for providing feedback.Reputationmodifying factors such as transaction context are looked at next followed by a discussion on howreputations can be interpreted.We conclude by looking at several specific digital reputation systems that have been proposed.
Achieving optimal performance in IEEE 802.11 wireless LANs with the combination of link adaptation and adaptive backoff
Computer Networks 51 (2007), pag. 1574-1600.
Digital version available: cn2007.pdf (DOI doi:10.1016/j.comnet.2006.08.018)
Abstract: IEEE 802.11 is one of the most popular wireless LAN standards. In the paper, we propose a simple analytical model, which helps one obtain deep insight into the mechanism of achieving optimal performance by using IEEE 802.11 DCF (Distributed Coordination Function) protocol. The first contribution of this paper is the analysis of the optimal operation point where maximum goodput can be achieved. Through the analysis, we answer some fundamental questions about the existence and the uniqueness of the optimal operation point; about the maximum system goodput can be achieved; about the existence of a simple rule to check out if the system operates under the optimal state or not; and how do the data transmission rates, which is dependent on the selected physical transmission mode, and packet transmission errors, caused by channel fading and (or) interference, affect the final system performance. Another contribution is the proposal of a simple distributed adaptive scheme "LABS'' (i.e., Link adaptation and Adaptive Backoff Scheme), which makes the system operate under the optimal operation point and, at the same time, achieves some pre-defined target service differentiation ratio between different traffic flows. In the LABS, two adaptive schemes are combined: one is the so called "Link Adaptation'' scheme, which dynamically selects an optimal modulation mode at a given time so as to improve the achieved system goodput; the other one is the so called "Adaptive Backoff'' scheme, which adaptively adjusts the minimum contention window size of each sending node to guarantee that the system operates under (or near) the optimal operation point. Results obtained in the paper are relevant to both theoretical research and implementation of real systems.
ScienzAzienda 2006 Scienza e tecnologia per l'innovazione e lo sviluppo
Atti del convegno
8 maggio 2006 Facoltà di Scienze Matematiche Fisiche e Naturali, Università di Trento
Digital version available: sa.pdf
Reputation Lending for Virtual Communities
Proceedings. 22nd International Conference on Data Engineering Workshops, 03-07 April 2006 (Digital Object Identifier: 10.1109/ICDEW.2006.128)
Digital version available: lending.pdf
Abstract: Reputation management schemes have recently emerged as a mechanism for improving trust and security in peer-topeer networks. A new entrant in a network with reputation management can either be given the benefit of doubt and be treated like a trusted (or semi-trusted) peer until it misbehaves or it can be assumed to be untrusted and have to earn the trust of others. The former case provides an incentive for misbehaving peers to cast off their old identity and assume a new one regularly. The latter case presents the problem of new peers being unable to bootstrap and to gain a foothold in the network. In this paper, we present a mechanism in which existing peers can choose to "lend" part of their reputation to new peers that they know in order to give them a start. This mechanism mirrors the real world where a reference or an introduction often gives one a foothold into an otherwise closed group. If the new peer behaves well, the old peer is rewarded for adding value to the group and if the new peer misbehaves the old peer loses the reputation it lent. In this way, existing peers have a stake in introducing new peers into the network and get a return on their investment for introducing honest peers.
"May I borrow Your Filter?" Exchanging Filters to Combat Spam in a Community
20th International Conference on Advanced Information Networking and Applications, AINA 2006, April 2006, Vienna.
IEEE Computer Society, Los Alamitos, CA, USA, Volume 2, 18-20 Page(s):489 - 493
Digital version available: aina2006.pdf
Abstract: Leveraging social networks in computer systems can be effective in dealing with a number of trust and security issues. Spam is one such issue where the "wisdom of crowds" can be harnessed by mining the collective knowledge of ordinary individuals. In this paper, we present a mechanism through which members of a virtual community can exchange information to combat spam. Previous attempts at collaborative spam filtering have concentrated on digest-based indexing techniques to share digests or fingerprints of emails that are known to be spam. We take a different approach and allow users to share their spam filters instead, thus dramatically reducing the amount of traffic generated in the network. The resultant diversity in the filters and cooperation in a community allows it to respond to spam in an autonomic fashion. As a test case for exchanging filters we use the popular SpamAssassin spam filtering software and show that exchanging spam filters provides an alternative method to improve spam filtering performance.
DIGITAL REPUTATION FOR VIRTUAL COMMUNITIES
Technical Report # DIT-05-066, Universita' di Trento, Oct 2005
Digital version available: TR-05-066.pdf
Abstract: In this report we provide an overview of digital reputation management systems for virtual communities. We begin with a discussion on the how trust is created in the real world. We then highlight how the process of trust creation differs in the virtual world. Next, we talk about the different ways in which digital reputations are useful to virtual communities such as incentivizing cooperation and punishing malicious users, providing recommendations or as a form of distributed authentication. We then discuss how evolutionary biology and game theory have informed research in reputation systems. This is followed by a discussion of the various components of reputation such as context, the forms of evidence, .rst and second order reputation and architectural considerations including the role of distributed hash tables in decentralized reputation management systems. We conclude with a discussion of some reputation management systems such as complaints-based trust, EigenTrust, PeerTrust and ROCQ.
On Partitioning of Hypergraphs
Discrete Mathematics 307 (2007) 1737 - 1753
Digital version (preprint) available: hyperlast.pdf (DOI doi:10.1016/j.disc.2006.09.022 )
Abstract: We study Edge-Isoperimetric Problems (EIP) for hypergraphs and extend some technique in this area from graphs to hypergraphs. In particular, we establish some new results on a relationship between the EIP and some extremal poset problems, and apply them to obtain an exact solution of the EIP for certain hypergraph families. We also show how to solve the EIP on hypergraphs in some cases when the link to posets does not work. Another outcome of our results is a new series of hypergraphs admitting nested solutions in the EIP. The obtained results can be used for checking the quality of heuristics for hypergraph partitioning.
Identifying Intrusions in Computer Networks with Principal Component Analysis
Proceedings of ARES 2006 (The First International Conference on Availability, Reliability and Security), 20-22 Apr 2006, Vienna, Austria, IEEE Computer Society, Los Alamitos, CA, USA. Pages 270-277.
Digital version available: ares2006.pdf
Abstract: Most current anomaly Intrusion Detection Systems (IDSs) detect computer network behavior as normal or abnormal but cannot identify the type of attacks. Moreover, most current intrusion detection methods cannot process large amounts of audit data for real-time operation. In this paper, we propose a novel method for intrusion identification in computer networks based on Principal Component Analysis (PCA). Each network connection is transformed into an input data vector. PCA is employed to reduce the dimensionality of the data vectors and identification is handled in a low dimensional space with high efficiency and low use of system resources. The normal behavior is pro- filed based on normal data for anomaly detection and models of each type of attack are built based on attack data for intrusion identification. The distance between a vector and its reconstruction onto those reduced subspaces representing the different types of attacks and normal activities is used for identification. The method is tested with network data from MIT Lincoln labs for the 1998 DARPA Intrusion Detection Evaluation Program and testing results show that the model is promising in terms of identification accuracy and computational efficiency for real-time intrusion identification.
Reactive and dynamic local search for Max-Clique, does the complexity pay off?
Technical Report DIT-06-027, Informatica e Telecomunicazioni, University of Trento, Apr 2006.
Digital version available: rls-dls.pdf
Abstract: This paper presents some preliminary results of an ongoing investigation about how different algorithmic building blocks contribute to solving theMaximumClique problem. In detail, we consider greedy constructions, plateau searches, and more complex schemes based on dynamic penalties and/or prohibitions, in particular the recently proposed technique of Dynamic Local Search and the previously proposed Reactive Local Search. The experimental results consider both the empirical hardness, measured by the iterations needed to reach empirical maxima, and the CPU time per iteration.
A Memory-Based RASH Optimizer
Proceedings of the AAAI-06 workshop on Heuristic Search, Memory Based Heuristics and Their applications , July 17, Boston.
Digital version available: mrash-aaai.pdf
Abstract: This paper presents a memory-based algorithm for global optimization of multivariate functions of continuous variables. The proposed algorithm, M-RASH, is based on the RASH (Reactive Affine Shaker) heuristic, an adaptive search algorithm based only on point-wise function evaluations. MRASH is an extension of RASH in which promising starting points for local search trails are suggested online by using Bayesian Locally Weighted Regression. Both techniques maintain memory about the previous history of the search to guide the future exploration, but in very different ways. RASH compiles the previous experience into the shape of a local search area where sample points are drawn, while locally-weighted regression saves the entire previous history to be mined extensively when an additional sample point is generated. Because of the high computational cost related to the regression model, it is applied only to evaluate the potential of an initial point for a local search run. The experimental results show that M-RASH is indeed capable of leading to good results for a smaller number of function evaluations.
Proceedings of Tridentcom (First International Conference on Testbeds and Research Infrastructures for the Development of Networks and Communities), Feb 23-25 2005, Trento Italy
IEEE Computer Society, Los Alamitos, CA, USA, ISBN 0-7695-2219-X
The Gregarious Particle Swarm Optimizer (G-PSO)
Proceedings of ACM Genetic and Evolutionary Computation Conference (GECCO) 2006 , July 8-12, 2006, Seattle, Washington, USA. ACM.
Digital version available: g-pso.pdf
Abstract: This paper presents a gregarious particle swarm optimiza- tion algorithm (G-PSO) in which the particles explore the search space by aggressively scouting the local minima with the help of only social knowledge. To avoid premature con- vergence of the swarm, the particles are re-initialized with a random velocity when stuck at a local minimum. Further- more, G-PSO adopts a "reactive" determination of the step size, based on feedback from the last iterations. This is in contrast to the basic particle swarm algorithm, in which the particles explore the search space by using both the individ- ual "cognitive" component and the "social" knowledge and no feedback is used for the self-tuning of algorithm parame- ters. The novel scheme presented, besides generally improv- ing the average optimal values found, reduces the computa- tion effort.
"Reputation management: experiments on the robustness of ROCQ"
In Proceedings of the 7th International Symposium on Autonomous Decentralized Systems (ISADS 2005) - First International Workshop on Autonomic Communication for Evolvable Next Generation Networks (WAGEN), Chengdu, China, 4-8 April 2005. IEEE Computer Society, 2005, pages 725-730.
Digital version available: isads2005.pdf
WIKIREP: DIGITAL REPUTATION IN VIRTUAL COMMUNITIES
DIT Technical Report DIT-05-050, University of Trento, Italy, June 2005.
Digital version available: wikireptr-DIT-05-050.pdf Accepted for publication in Proceedings: CONGRESSO ANNUALE AICA 2005 , Comunita' virtuale dalla ricerca all'impresa, dalla formazione al cittadino, Udine, 5-7 ottobre 2005.
Abstract: We present a framework for applying digital reputations to collaborative environments, where multiple authors contribute to the same document. In our mechanism readers evaluate a single document, and reputation data derived from the feedbacks affect multiple authors and document versions. The digital reputation encourages contribution and provides motivation for active participation, leading to better quality of the content and to better user experience. Our approach is applicable to user-managed communities, distributed moderation systems, and other collaborative contexts. The underlying ideas of our scheme are: separate ratings for different versions of the same document, inheritance of previous ratings for newer versions, and appropriate allocation of credit to versions and authors. We describe in detail both the algorithms used to compute reputations, and our implementation, WikiRep, a reputation-enabled Wiki application.
Do not be afraid of local minima: Affine Shaker and Particle Swarm
DIT Technical Report DIT-05-049, University of Trento, Italy, May 2005.
Digital version available: pso.pdf
Abstract: Stochastic local search techniques are powerful and flexible methods to optimize difficult functions. While each method is characterized by search trajectories produced through a randomized selection of the next step, a notable difference is caused by the interaction of different searchers, as exemplified by the Particle Swarm methods. In this paper we evaluate two extreme approaches, Particle Swarm Optimization, with interaction between the individual "cognitive" component and the "social" knowledge, and Repeated Affine Shaker, without any interaction between searchers but with an aggressive capability of scouting out local minima. The results, unexpected to the authors, show that Affine Shaker provides remarkably efficient and effective results when compared with PSO, while the advantage of Particle Swarm is visible only for functions with a very regular structure of the local minima leading to the global optimum and only for specific experimental conditions.
Intelligent Backbone Swarms for scalable, disruption tolerant wireless networking
Proceedings, 2005 IEEE Swarm Intelligence Symposium (SIS-05) June 8-10, 2005 Pasadena, California, USA, IEEE press, page 432 -- 435
Digital version available: swarm.pdf
Abstract: In this paper, we propose a swarm intelligence strategy for constructing a mobile backbone multicasting network which leads to improved scalability and connectivity compared to conventional flat networks. The strategy combines a simple clustering technique and On Demand Multicast Protocol (ODMRP). Also we show benefits of the mobile backbone network through a simulation study.
Performance Analysis of a Service-dependant Handoff Scheme in Voice/Data Integrated Cellular Mobile Systems
Computer Networks, Volume 50, Issue 5, Pages 707-730 (April 2006)
Digital version available: COMNET-2005.pdf
Abstract: In this paper, we propose and analyze a service-dependent handoff and channel allocation scheme in voice and data integrated cellular mobile systems, which combines the ideas of "Variable Bandwidth" and "Preemptive Priority" together. In the scheme, voice and data traffic are considered. According to the variations of the offered traffic intensity at each cell, both a voice and a data call in service can occupy a full-rate channel or a half-rate channel. In order to guarantee the Quality of Service (QoS) for both voice and data traffic, channel resources are fairly shared between voice and data calls according to an optimal channel allocation scheme, which minimizes the difference between the average bandwidth of a voice call in service and that of a data call in service. To minimize the forced termination of a voice call, a voice call can preempt a data call in service if all the calls in the channel pool of the current cell are already assigned with half-rate service. The interrupted data call returns back to the queue specially prepared for data traffic. By analysis, we obtain the most important system performance measures. Comparisons with the scheme, which only supports "Preemptive Priority" without "Variable Bandwidth" supporting, shows that if the total arrival rate for originating calls is not very heavy, the new scheme can provide lower blocking probability and forced termination probability for both voice and data traffic, and shorter average total transmission time for a successfully completed data call.
Statistical Learning Theory for Location Fingerprinting in Wireless LANs
Computer Networks, 47 (6), 2005, pages 825-845
Digital version available: ComNet.pdf
Abstract: In this paper, techniques and algorithms developed in the framework of Statistical Learning Theory are applied to the problem of determining the location of a wireless device by measuring the signal strength values from a set of access points (location fingerprinting). Statistical Learning Theory provides a rich theoretical basis for the development of models starting from a set of examples. Signal strength measurement is part of the normal operating mode of wireless equipment, in particular Wi-Fi, so that no special-purpose hardware is required. The proposed techniques, based on the Support Vector Machine paradigm, have been implemented and compared, on the same data set, with other approaches considered in scientic literature. Tests performed in a real-world environment show that results are comparable, with the advantage of a low algorithmic complexity in the normal operating phase. Moreover, the algorithm is particularly suitable for classification, where it outperforms the other techniques.
Dynamic Self-management of Autonomic Systems: The Reputation, Quality and Credibility (RQC) Scheme
Proceedings of The 1st IFIP TC6 WG6.6 International Workshop on Autonomic Communication ( WAC2004, Berlin, 18-19 Oct 2004 ), Lecture Notes on Computer Science LNCS 3457, Michael Smirnov (Ed.), pag. 165-178, Springer, Berlin, 2005.
Digital version available: wac2004.pdf
Abstract: In this paper, we present a feedback-based system for managing trust and detecting malicious behavior in autonomically behaving networks. Like other distributed trust management systems, nodes rate the interactions they have with other nodes and this information is stored in a distributed fashion.
Two crucial insights motivate our work. We recognize as separate entities the trust placed in a node, {\em reputation}, and the trust placed in the recommendations made by a node, {\em credibility}. We also introduce the concept of quality of a trust rating. Together, these two factors enhance the ability of each node to decide how much confidence it can place in a rating provided to it by a third party.
We implement our scheme on a structured P2P network, Pastry, though our results can be extended to generic autonomic communication systems. Experimental results considering different models for malicious behavior indicate the contexts in which the RQC scheme performs better than existing schemes.
Wireless on-demand network systems
Proceedings of the First Working Conference on Wireless On-demand Network Systems, WONS 2004 Madonna di Campiglio, Italy, January 21 - 23, 2004
Springer, LNCS vol. 2928, pages 402, 2004
Analysis of the IEEE 802.11 DCF with Service Differentiation Support in Non-saturation Conditions
Lecture Notes in Computer Science Volume 3266 / 2004 Quality of Service in the Emerging Networking Panorama: Fifth International Workshop on Quality of Future Internet Services, QofIS 2004, Barcelona, Spain.
Editors: Josep Sol--Pareta, Michael Smirnov, Piet Van Mieghem, et al.
Publisher: Springer-Verlag Heidelberg
ISSN: 0302-9743, pp. 64 - 73.
Digital version (preprint) available: QoFIS2004final.pdf
Abstract: Although the performance analysis of the IEEE 802.11 Distributed Coordination Function (DCF) in saturation state has been extensively studied in the literature, little work is present on performance analysis in non-saturation state. In this paper, a simple model is proposed to analyze the performance of IEEE 802.11 DCF with service differentiation support in non-saturation states, which helps to obtain a deeper insight into the IEEE 802.11 DCF. Based on the proposed model, we can approximately evaluate the most important system performance measures, such as packet delays, which provide one with an important tool to predict and optimize the system performance. Moreover, a practical method to meet packet delay requirements is presented based on our theoretical results. Comparisons with simulations show that this method achieves the specified packet delay requirements with good accuracy.
A Traffic Engineering Scheme for QoS Routing in G-MPLS Networks Based on Transmission Quality
In 8th IFIP Working Conference on Optical Network Design and Modelling - ONDM 2004 proceedings, 2004
"Quality of Service in IP over WDM considering both service differentiation and transmission quality". Proceedings "IEEE International Conference on Communications - ICC 2004", Paris - France, 20-24 June, 2004. IEEE, URL : http://www.icc2004.org/.
Digital preprint version available: qoswdm.pdf
Reducing the number of hops between communication peers in a bluetooth scatternet Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC2004) 21-25 March 2004, Atlanta, Georgia, USA. IEEE, Page(s):207 - 212. Vol.1
Digital preprint version available: wcnc2004.pdf
Wireless LANs: from WarChalking to Open Access Networks Monet (Mobile Networks and Applications), special issue dedicated to WMASH, guest editors: Giuseppe Bianchi, Sung Ju Lee, Parviz Kermani, no. 10, 275--287, 2005.
Digital version available: Battiti-Orava_05.ps , monet-2005.pdf
WILMA: An Open Lab for 802.11 HotSpots
Lecture Notes in Computer Science
Publisher: Springer Berlin / Heidelberg
ISSN: 0302-9743
Subject: Computer Science
Volume 2775 / 2003
Title: PersonalWireless Communications
ISBN: 3-540-20123-8
DOI: 10.1007/b12004
Chapter: pp. 163 - 168
Digital version available: LNCS
Abstract:
WILMA (Wireless Internet and Location Management
Architecture) is an ongoing research project based in Trento, Italy, whose aim
is the study of the management of 802.11-based HotSpot Networks and the value
added services that can be provided through such an infrastructure.
The WILMA project (www.wilmaproject.org)
is supported by the Province of Trento under Grant N. 437, issued on March 3,
2002.
Performance Analysis of An Enhanced IEEE 802.11 Distributed Coordination Function Supporting Service Differentiation G. Kerlsson and M.I.Simirnov (Eds.): "Quality for all", QofIS 2003, LNCS 2811, pp. 152-161, 2003, Springer-Verlag Berlin.
Digital version available: QoFIS2003.pdf
Abstract: As one of the fastest growing wireless access technologies, Wireless LANs (WLANs) must evolve to support adequate degrees of service differentiation. Unfortunately, current WLAN standards like IEEE 802.11 Distributed Coordination Function (DCF) lack this ability. Work is in progress to define an enhanced version capable of supporting QoS for multimedia traffic at the MAC layer. In this paper, we aim at gaining insight into two mechanisms to differentiate among traffic categories, i.e., scaling the minimum contention window size and the length of the packet payload according to the priority of each traffic flow. We propose an analysis model to compute the throughput and packet transmission delays. In additions, we derive approximations to get simpler but more meaningful relationships among different parameters. Comparisons with simulation results show that a very good accuracy of performance evaluation can be achieved by using the proposed analysis model.
Dynamic Load Balancing in WDM Networks
special issue di Optical Networks Magazine "Dynamic Optical Networking: Around the Corner or Light Years Away?", Sep 2003.
Digital version available: ONM.pdf
Abstract: In this paper new load balancing techniques are proposed based on IP-like routing, where the forwarding mechanism is only driven by the destination address. The aim of this work is to consider the applicability of this approach in the context of optical networks. The proposed algorithm (RSNE | Reverse Subtree Neighborhood Ex- ploration) implements a local search technique where the basic step is the modi cation of a single entry in the routing table of a node. A randomized method with reduced computational complexity (fRSNE | fast RSNE) is also presented and analyzed. Both schemes allow an incremental imple- mentation where local search steps are continuously performed as tra.c conditions change. Experiments under static and dynamic (time varying) tra.c scenar- ios show a rapid reduction of the congestion. The performance of the incremental scheme while tracking a changing tra.c matrix is compara- ble to that obtainable through the complete re-optimization of the tra.c, while the randomized implementation is particularly e.cient when scaling properties are considered.
Partially persistent dynamic sets for history-sensitive heuristics.
in: Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Challenges, M. H. Goldwasser, D. S. Johnson And C.C. McGeoch, DIMACS Series in Discrete Mathematics and Theoretical Computer Science Volume 59, 2002, pag. 1 --21
Preprint available: persistent-challenge.ps
Abstract: Effective heuristic algorithms for combinatorial problems are based on integrating local neighborhood search with history-sensitive schemes, where the information collected during the previous search phase is used to direct the future effort. In particular, some algorithms (like REM tabu search and reactive tabu search) need to detect whether a configuration has already been encountered during the previous phase of the search. This letter analyzes the use of persistent dynamic sets for this purpose and discusses the advantages of this option with respect to popular but less efficient realizations. In particular, when combined with hashing, the method complexity per search iteration is of $O(L)$ average-case time and $O(1)$ amortized space, when the search space is given by $L$-bit binary strings. A concrete realization of the abstract data type through a C++ class is presented. The obtained memory occupation and timing results are analyzed for selected ``dictionary'' benchmark tasks and for the use of the structure to support history--sensitive heuristic algorithms.
PILGRIM: A Location Broker and Mobility-Aware Recommendation System
Proceedings of PerCom2003 the first IEEE Annual Conference on Pervasive Computing and Communications - Fort Worth (TX), USA, March 2003, edited by Das S., March 23-26, 2003. IEEE Computer Society, p. 265-272. URL : http://www.percom.org/
Digital version available: percom2003.pdf
Abstract: Mobile computing adds a mostly unexplored dimension to data mining: user's position is a relevant piece of information, and recommendation systems, selecting and ranking links of interest to the user, have the opportunity to take location into account. In this paper, a mobility-aware recommendation system that considers the location of the user to filter recommended links is proposed. To avoid the potential problems and costs of insertion by hand, a new middleware layer, the location broker, maintains a historic database of locations and corresponding links used in the past and develops models relating resources to their spatial usage pattern. These models are used to calculate a preference metric when the current user is asking for resources of interest. Mobility scenarios are described and analyzed in terms of possible user requirements. The features of the PILGRIM mobile recommendation system are outlined together with a preliminary experimental evaluation of different metrics.
Abstract
ACM Journal of Experimental Algorithmics , Vol. 2, Paper 2, 1997.