Articoli / Downloadable papers

Branching interval algebra: An almost complete picture
A. Bertagnon, M. Gavanelli, A. Passantino, G. Sciavicco, S. Trevisani. Information and Computation. (Free download until December 18, 2021)


Maddalena Nonato, Davide Bertozzi, Marco Gavanelli, Andrea Peano.

A network model for routing-fault-free wavelength selection in WRONoCs design

Electronic Notes in Discrete Mathematics, Volume 64, February 2018, Pages 285–294.


Abstract: Emerging technologies in on-chip communication domain bring about new combinatorial optimization problems at design automation. We address the Wavelength Selection Problem in Wavelength-Routed Optical Networks-on-Chip (WRONoCs), where wavelengths act as signal carriers for initiator-to-target communication, so that signals are the least interfering and routing faults are prevented. We present this novel engineering problem and model it as a constrained shortest path on acyclic networks, propose a graph-based mathematical formulation and an iterative procedure on incremental graphs to solve the model on realistic data.

Marco Gavanelli, Maddalena Nonato, Andrea Peano. An ASP approach for the valves positioning optimization in a water distribution system. Journal of Logic and Computation 2013; doi: 10.1093/logcom/ext065

PDF pdf.png


Positioning of valves is a real-life issue in Water Distribution System (WDS) design and, currently, it is usually addressed by hydraulic engineers either by hand or by means of genetic algorithms, that give no assurance of optimality. Since a given valves placement identifies a sectorization of the WDS in several isolable portions, the valves positioning problem can be seen as a variant of the well known graph partitioning problem, which is a hard combinatorial problem. Cattafi et al. (2011, TPLP, 11, 731–747) showed recently that Computational Logic can provide technologies and techniques that can be exploited to model and achieve the optimal partition of the water network (i.e. the optimal positioning of valves). In particular, the authors tackled the optimization of the valves positioning through a two player game model, giving a Constraint Logic Programming formalization to solve it effectively. The aim of this article, instead, is to investigate the potential of Answer Set Programming in this practical application; evaluation is in terms both of language expressivity and solving efficiency. Results are discussed for different ASP models and a comparison with the CLP(FD) technique shown by Cattafi et al. (2011, TPLP, 11, 731–747) will be given.
Keywords: Answer set programming, isolation system design, valves positioning, hydroinformatics.

Marco Gavanelli, Maddalena Nonato, Andrea Peano, Stefano Alvisi, and Marco Franchini. Genetic algorithms for scheduling devices operation in a water distribution system in response to contamination events. In J.-K. Hao and M. Middendorf, editors, EvoCop 2012, volume 7245 of Lecture Notes in Computer Science, pages 124-135, Berlin Heidelberg, 2012. Springer-Verlag.

PDF pdf.png ©Springer-Verlag, Berlin Heidelberg, 2012. This is the author's version of the work. It is posted here by permission of Springer-Verlag for your personal use. Not for redistribution. The definitive version was published in J.-K. Hao and M. Middendorf (Eds.): EvoCOP 2012, LNCS 7245, pp. 124-135, 2012 and is available at

This paper heuristically tackles a challenging scheduling problem arising in the field of hydraulic distribution systems in case of a contamination event, that is, optimizing the scheduling of a set of tasks so that the consumed volume of contaminated water is minimized. Each task consists of manually activating a given device, located on the hydraulic network of the water distribution system. In practice, once contamination has been detected, a given number of response teams move along the network to operate each device on site. The consumed volume of contaminated water depends on the time at which each device is operated, according to complex hydraulic laws, so that the value associated to each schedule must be evaluated by a hydraulic simulation.

We explore the potentials of Genetic Algorithms as a viable tool for tackling this optimization-simulation problem. In particular, we compare different encodings and propose ad hoc cross over operators that exploit the combinatorial structure of the feasible region, featuring hybridization with Mixed Integer Linear Programming.

Computational results are provided for a real life hydraulic network of average size, showing the effectiveness of the approach. Indeed, we greatly improve upon common sense inspired solutions which are adopted in practice.

Keywords: Hybrid Genetic Algorithms, Simulation-Optimization, Scheduling

Marco Alberti, Massimiliano Cattafi, Federico Chesani, Marco Gavanelli, Evelina Lamma, Paola Mello, Marco Montali, and Paolo Torroni. A computational logic application framework for service discovery and contracting. International Journal of Web Services Research, 8(3):1-25, July-September 2011.

PDF pdf.png This paper appears in International Journal of Web Services Research July-September 2011, Vol. 8, No. 3 edited by Liang-Jie Zhang © 2011, IGI Global, Posted by permission of the publisher.

In Semantic Web technologies, searching for a service means to identify components that can potentially satisfy the user needs in terms of inputs and outputs (discovery), and devise a fruitful interaction with the customer (contracting). In this paper, we present an application framework that encompasses both the discovery and the contracting steps, in a unified search process. In particular, we accommodate service discovery by ontology-based reasoning, and contracting by reasoning about behavioural interfaces, published in a formal language. To this purpose, we consider a formal approach grounded on Computational Logic. We define, illustrate and evaluate a framework, called SCIFF Reasoning Engine (SRE), which can establish if a Semantic Web Service and a requester can fruitfully inter-operate, by computing a possible interaction plan based on the behavioural interfaces of both. The same operational machinery used for contracting can be used for runtime verification.


Keywords: Web services, semantic discovery, contracting, rules, analysis, abductive logic programming, proof procedure, interoperability

Marco Gavanelli, Fabrizio Riguzzi, Michela Milano, Davide Sottara, Alessandro Cangini, and Paolo Cagnoli. An application of fuzzy logic to strategic environmental assessment. In Roberto Pirrone and Filippo Sorbello, editors, AI*IA 2011: Artificial Intelligence Around Man and Beyond - XIIth International Conference of the Italian Association for Artificial Intelligence, Palermo, Italy, September 15-17, 2011. Proceedings, volume 6934 of Lecture Notes in Artificial Intelligence, pages 324-335. Springer Verlag, 2011.

PDF pdf.png ©Springer-Verlag, Berlin Heidelberg, 2011. This is the author's version of the work. It is posted here by permission of Springer-Verlag for your personal use. Not for redistribution. The definitive version was published in AI*IA 2011: Artificial Intelligence Around Man and Beyond, Lecture Notes in Computer Science Volume 6934, 2011, pp 324-335 and is available at

Strategic Environmental Assessment (SEA) is used to evaluate the environmental effects of regional plans and programs. SEA expresses dependencies between plan activities (infrastructures, plants, resource extractions, buildings, etc.) and environmental pressures, and between these and environmental receptors. In this paper we employ fuzzy logic and many-valued logics together with numeric transformations for performing SEA. In particular, we discuss four models that capture alternative interpretations of the dependencies, combining quantitative and qualitative information. We have tested the four models and presented the results to the expert for validation. The interpretability of the results of the models was appreciated by the expert that liked in particular those models returning a possibility distribution in place of a crisp result.


Marco Gavanelli, Marco Alberti, and Evelina Lamma. Integration of abductive reasoning and constraint optimization in SCIFF. In Patricia M. Hill and David S. Warren, editors, 25th International Conference on Logic Programming (ICLP 2009), volume 5649 of Lecture Notes in Computer Science, pages 387-401, Berlin Heidelberg, 2009. Springer-Verlag.

PDF pdf.png ©Springer-Verlag, Berlin Heidelberg, 2009. This is the author's version of the work. It is posted here by permission of Springer-Verlag for your personal use. Not for redistribution. The definitive version was published in Patricia M. Hill and David S. Warren (Eds.): ICLP 2009, LNCS 5649, pp. 387-401, 2009 and is available at Springer-Verlag

Abductive Logic Programming (ALP) and Constraint Logic Programming (CLP) share the feature to constrain the set of possible solutions to a program via integrity or CLP constraints. These two frameworks have been merged in works by various authors, which developed efficient abductive proof-procedures empowered with constraint satisfaction techniques. However, while almost all CLP languages provide algorithms for finding an optimal solution with respect to some objective function (and not just any solution), the issue has received little attention in ALP.

In this paper we show how optimisation meta-predicates can be included in abductive proof-procedures, achieving in this way a significant improvement to research and practical applications of abductive reasoning.

In the paper, we give the declarative and operational semantics of an abductive proof-procedure that encloses constraint optimization meta-predicates, and we prove soundness in the three-valued completion semantics. In the proof-procedure, the abductive logic program can invoke optimisation meta-predicates, which can invoke abductive predicates, in a recursive way.

Keywords: Abductive Logic Programming, Constraint Logic Programming, Constraint Optimization, Constraint Handling Rules

Marco Gavanelli, Michela Milano, Sergio Storari, Luca Tagliavini, Paola Baldazzi, Marilena Manfredi, and Gianfranco Valastro. Greedy and exact algorithms for invitation planning in cancer screening. In N.T. Nguyen and R. Katarzyniak, editors, ”New Challenges in Applied Intelligence Technologies”, number 134 in Studies in Computational Intelligence. Springer-Verlag, Heidelberg, Germany, 2008.

PDF pdf.png ©Springer-Verlag, Berlin Heidelberg, 2008. This is the author's version of the work. It is posted here by permission of Springer-Verlag for your personal use. Not for redistribution. The definitive version was published in N.T. Nguyen and R. Katarzyniak, editors, "New Challenges in Applied Intelligence Technologies", number 134 in Studies in Computational Intelligence. Springer-Verlag, Heidelberg, Germany, 2008 and is available at


Cancer screening is a method of preventing cancer by early detecting and treating abnormalities. One of the most critical screening phase is invitation planning since screening resources are limited and there are many people to invite. For this reason, smart resource allocation approaches are needed.

In the paper, we propose and compare two solutions for smart invitation plan definition, one based on greedy approaches and one based on Constraint Programming techniques that enable the definition of the optimal invitation plan.


Keywords: Constraint Programming, Scheduling, Greedy Algorithm
ACM DL Author-ize serviceAn abductive framework for a-priori verification of web services pdf.png
Marco Alberti, Marco Gavanelli, Evelina Lamma, Federico Chesani, Paola Mello, Marco Montali
PPDP '06 Proceedings of the 8th ACM SIGPLAN international conference on Principles and practice of declarative programming, 2006
Marco Gavanelli and Michela Milano. On the need for a different backtracking rule when dealing with late evaluation. Electronic Notes in Theoretical Computer Science, 30(2):145-156, 1999.  .ps.gz
Constraint Satisfaction Problems (CSPs) represent a widely used framework for many real-life problems. Constraint Logic Programming (CLP) languages are an effective tool for modeling problems in terms of CSPs and solving them efficiently.

Lazy domain evaluation is a solving technique that has proven effective for solving CSPs, allowing the minimization of the number of constraint checks. However, exploiting lazy domain evaluation in CLP is not very effective, mainly because of the chronological backtracking rule used in CLP. After each backtracking step, in fact, all the obtained results are lost, even if they had nothing to do with the culprit of the failure. The intelligent backtracking rule widely studied in the past does not solve the problem either.

In this paper, we propose a backtracking rule useful for dealing efficiently and declaratively with lazy domain evaluation in CLP, and we show a simple implementation of a metainterpreter providing the depicted functionality.