Publications

The documents on this page are preprints or authors' personal copies. The copyright for the published documents rests with the author(s) and the journals or conferences where they were published. If you have comments or thoughts on any of these papers, please send me an email!

2018

    Journals
  • Ferdinando Fioretto, William Yeoh, Enrico Pontelli. "Distributed Constraint Optimization Problems and Applications: A Survey". In Journal of Artificial Intelligence Research (JAIR), 2018.
    Downloads: [pdf] [BibTex] | Links: [web] Show more
    Abstract: The field of Multi-Agent System (MAS) is an active area of research within Artificial Intelligence, with an increasingly important impact in industrial and other real-world applications. Within a MAS, autonomous agents interact to pursue personal interests and/or to achieve common objectives. Distributed Constraint Optimization Problems (DCOPs) have emerged as one of the prominent agent architectures to govern the agents’ autonomous behavior, where both algorithms and communication models are driven by the structure of the specific problem. During the last decade, several extensions to the DCOP model have enabled them to support MAS in complex, real-time, and uncertain environments. This survey aims at providing an overview of the DCOP model, giving a classification of its multiple extensions and addressing both resolution methods and applications that find a natural mapping within each class of DCOPs. The proposed classification suggests several future perspectives for DCOP extensions, and identifies challenges in the design of efficient resolution algorithms, possibly through the adaptation of strategies from different areas.
  • Ferdinando Fioretto, William Yeoh. "AI buzzwords explained: distributed constraint optimization problems". In AI Matters, 2018.
    Downloads: [pdf] [BibTex] | Links: [web] Show more
    Abstract: The power network is the largest operating machine on earth, generating more than US$400bn a year1 keeping the lights on for our homes, offices, and factories. A significant concern in power networks is for the energy providers to be able to generate enough power to supply the demands at any point in time. Short terms demand peaks are however hard to predict and, thus, in the modern smart electricity grid, the energy providers can exploit the demand-side flexibility of the consumers to reduce the peaks in load demand.
  • Ferdinando Fioretto, Enrico Pontelli, William Yeoh, Rina Dechter. "Accelerating Exact and Approximate Inference for (Distributed) Discrete Optimization with GPUs". In Constraints, 2018.
    Downloads: [pdf] [BibTex] | Links: [web] [github] Show more
    Abstract: Discrete optimization is a central problem in artificial intelligence. The optimization of the aggregated cost of a network of cost functions arises in a variety of problems including Weighted Constraint Programs (WCSPs), Distributed Constraint Optimization (DCOP), as well as optimization in stochastic variants such as the tasks of finding the most probable explanation (MPE) in belief networks. Inference-based algorithms are powerful techniques for solving discrete optimization problems, which can be used independently or in combination with other techniques. However, their applicability is often limited by their compute intensive nature and their space requirements. This paper proposes the design and implementation of a novel inference-based technique, which exploits modern massively parallel architectures, such as those found in Graphical Processing Units (GPUs), to speed up the resolution of exact and approximated inference-based algorithms for discrete optimization. The paper studies the proposed algorithm in both centralized and distributed optimization contexts. The paper demonstrates that the use of GPUs provides significant advantages in terms of runtime and scalability, achieving up to two orders of magnitude in speedups and showing a considerable reduction in execution time (up to 345 times faster) with respect to a sequential version.
  • Conferences
  • Ferdinando Fioretto, Hong Xu, Sven Koenig, TK Satish Kumar. " Solving Multiagent Constraint Optimization Problems on the Constraint Composite Graph". In International Conference on Principles and Practice of Multi-Agent Systems (PRIMA), 2018.
    Downloads: [pdf] [BibTex] | Links: [web] [request code] Show more
    Abstract: We introduce the Constraint Composite Graph (CCG) for Distributed Constraint Optimization Problems (DCOPs), a popular paradigm used for the description and resolution of cooperative multi-agent problems. The CCG is a novel graphical representation of DCOPs on which agents can coordinate their assignments to solve the distributed problem suboptimally. By leveraging this representation, agents are able to reduce the size of the problem. We propose a novel variant of Max- Sum—a popular DCOP incomplete algorithm—called CCG-Max-Sum, which is applied to CCGs, and demonstrate its efficiency and effectiveness on DCOP benchmarks based on several network topologies.
  • Khoi Hoang, Ferdinando Fioretto, William Yeoh, Enrico Pontelli, Roie Zivan. "A large neighboring search schema for multi-agent optimization". In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), 2018.
    Downloads: [pdf] [BibTex] | Links: [web] [request code] Show more
    Abstract: The Distributed Constraint Optimization Problem (DCOP) is an elegant paradigm for modeling and solving multi-agent problems which are distributed in nature, and where agents cooperate to optimize a global objective within the confines of localized communication. Since solving DCOPs optimally is NP-hard, recent effort in the development of DCOP algorithms has focused on incomplete methods. Unfortunately, many of such proposals do not provide quality guarantees or provide a loose quality assessment. Thus, this paper proposes the Distributed Large Neighborhood Search (DLNS), a novel iterative local search framework to solve DCOPs, which provides guarantees on solution quality refining lower and upper bounds in an iterative process. Our experimental analysis of DCOP benchmarks on several important classes of graphs illustrates the effectiveness of DLNS in finding good solutions and tight upper bounds in both problems with and without hard constraints.
  • Ferdinando Fioretto, Chansoo Lee, Pascal Van Hentenryck. "Constrained-based Differential Privacy for Private Mobility". In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2018.
    Downloads: [pdf] [slides] [BibTex] | Links: [web] [request code] Show more
    Abstract: Ubiquitous mobile and wireless communication systems have the potential to revolutionize transportation systems, making accurate mobility traces and activity-based patterns available to optimize their design and operations. It also poses significant privacy risks, potentially revealing highly sensitive personal information. This paper studies the use of differential privacy to release mobility data that can be used for smart transportation systems. It shows that existing approaches do not provide the desired fidelity for practical uses. To remedy this critical limitation, the paper proposes the idea of optimization-based differential privacy that casts the production of a private dataset as an optimization problem that minimizes the impact of added Laplacian noise on the algorithmic task at hand. When applied to a city-level multi-modal transit system, experimental results show that the design and operations of the transportation system have similar performance measures when optimized over the real and private datasets. The results also indicate that optimization-based differential privacy may improve the accuracy of state-of-art privacy methods by an order of magnitude.
  • Ferdinando Fioretto, Pascal Van Hentenryck. "Constrained-based Differential Privacy: Releasing Optimal Power Flow Benchmarks Privately". In Proceedings of the International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR), 2018.
    Downloads: [pdf] [slides] [BibTex] | Links: [web] [request code] Show more
    Abstract: This paper considers the problem of releasing optimal power flow benchmarks that maintain the privacy of customers (loads) using the notion of Differential Privacy. It is motivated by the observation that traditional differential-privacy mechanisms are not accurate enough: The dded noise fundamentally changes the nature of the underlying optimization and often leads to test cases with no solution. To remedy this limitation, the paper introduces the framework of Constraint-Based Differential Privacy (CBDP) that leverages the post-processing immunity of differential privacy to improve the accuracy of traditional mechanisms. More precisely, CBDP solves an optimization problem to satisfies the problem-specific constraints by redistributing the noise. The paper shows that CBDP enjoys desirable theoretical properties and produces orders of magnitude improvements on the largest set of test cases available.
  • Ferdinando Fioretto, Hong Xu, Sven Koenig, TK Satish Kumar. "Constraint Composite Graph-Based Lifted Message Passing for Distributed Constraint Optimization Problems". In International Symposium on Artificial Intelligence and Mathematics (ISAIM), 2018.
    Downloads: [pdf] [slides] [BibTex] | Links: [web] [request code] Show more
    Abstract: The Distributed Constraint Optimization Problem (DCOP) offers a powerful approach for the description and resolution of cooperative multi-agent problems. In this model, a group of agents coordinates their actions to optimize a global objective function, taking into account their local preferences. In the majority of DCOP algorithms, agents operate on three main graphical representations of the problem: (a) the constraint graph, (b) the pseudo-tree, or (c) the factor graph. In this paper, we introduce the Constraint Composite Graph (CCG) for DCOPs, an alternative graphical representation on which agents can coordinate their assignments to solve the distributed problem suboptimally. By leveraging this repre- sentation, agents are able to reduce the size of the problem. We propose a novel variant of Max-Sum–a popular DCOP incomplete algorithm–called CCG-Max-Sum, which is applied to CCGs. We also demonstrate the efficiency and effective- ness of CCG-Max-Sum on DCOP benchmarks based on several network topologies.
  • Workshops
  • Ferdinando Fioretto, Hong Xu, Sven Koenig, TK Satish Kumar. " Solving Multiagent Constraint Optimization Problems on the Constraint Composite Graph". In Proceedings of the International Workshop on Optimisation in Multi-Agent Systems (OPTMAS), 2018.
    Downloads: [pdf] [slides] [BibTex] | Links: [web] [github] [request code] Show more
    Abstract: The Distributed Constraint Optimization Problem (DCOP) offers a powerful approach for the description and resolution of cooperative multi-agent problems. In this model, a group of agents coordinates their actions to optimize a global objective function, taking into account their local preferences. In the majority of DCOP algorithms, agents operate on three main graphical representations of the problem: (a) the constraint graph, (b) the pseudo-tree, or (c) the factor graph. In this paper, we introduce the Constraint Composite Graph (CCG) for DCOPs, an alternative graphical representation on which agents can coordinate their assignments to solve the distributed problem suboptimally. By leveraging this representation, agents are able to reduce the size of the problem. We propose a novel variant of Max-Sum—a popular DCOP incomplete algorithm—called CCG-Max-Sum, which is applied to CCGs. We also demonstrate the efficiency and effectiveness of CCG-Max-Sum on DCOP benchmarks based on several network topologies.
  • Pre-prints
  • Ferdinando Fioretto, Pascal Van Hentenryck. "Differential Private Stream Processing of Energy Consumption". CoRR abs/1808.01949, 2018.
    Downloads: [pdf] [BibTex] | Links: [web] Show more
    Abstract: A number of applications benefit from continuously releasing streams of personal data statistics. The process, however, poses significant privacy risks. Motivated by an application in energy systems, this paper presents OptStream, a novel algorithm for releasing differential private data streams. OptStream is a 4-step procedure consisting of sampling, perturbation, reconstruction, and post-processing modules. The sampling module selects a small set of points to access privately in each period of interest, the perturbation module adds noise to the sampled data points to guarantee privacy, the reconstruction module re-assembles the non-sampling data points from the perturbed sampled points, and the post-processing module uses convex optimization over the private output of the previous modules, as well as the private answers of additional queries on the data stream, to ensure consistency of the data's salient features. OptStream is used to release a real data stream from the largest transmission operator in Europe. Experimental results show that OptStream not only improves the accuracy of the state-of-the-art by at least one order of magnitude on this application domain, but it is also able to ensure accurate load forecasting based on the private data.

2017

    Conferences
  • Atena M. Tabakhi, Tiep Le, Ferdinando Fioretto, William Yeoh "Preference Elicitation for DCOPs". In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), 2017.
    Downloads: [pdf] [BibTex] | Links: [web] [request code] Show more
    Abstract: Distributed Constraint Optimization Problems (DCOPs) offer a powerful approach for the description and resolution of cooperative multi-agent problems. In this model, a group of agents coordinate their actions to optimize a global objective function, taking into account their preferences or constraints. A core limitation of this model is the assumption that the preferences of all agents or the costs of all constraints are specified a priori. Unfortunately, this assumption does not hold in a number of application domains where preferences or constraints must be elicited from the users. One of such domains is the Smart Home Device Scheduling (SHDS) problem. Motivated by this limitation, we make the following contributions in this paper: (1) We propose a general model for preference elicitation in DCOPs; (2) We propose several heuristics to elicit preferences in DCOPs; and (3) We empirically evaluate the effect of these heuristics on random binary DCOPs as well as SHDS problems.
  • Khoi D. Hoang, Ping Hou, Ferdinando Fioretto, William Yeoh, Roie Zivan, Makoto Yokoo. "Infinite-Horizon Proactive Dynamic DCOPs". In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2017.
    Downloads: [pdf] [slides] [BibTex] | Links: [web] [request code] Show more
    Abstract: The Distributed Constraint Optimization Problem (DCOP) formulation is a powerful tool for modeling multi-agent coordination problems. Researchers have recently extended this model to Proactive Dynamic DCOPs (PD-DCOPs) to capture the inherent dynamism present in many coordination problems. The PD-DCOP formulation is a finite-horizon model that assumes a finite horizon is known a priori. It ignores changes to the problem after the horizon and is thus not guaranteed to find optimal solutions for infinite-horizon problems, which often occur in the real world. Therefore, we (i) propose the Infinite-Horizon PD-DCOP (IPD- DCOP) model, which extends PD-DCOPs to handle infinite horizons; (ii) exploit the convergence properties of Markov chains to determine the optimal solution to the problem after it has converged; (iii) propose three distributed greedy algorithms to solve IPD-DCOPs; (iv) provide theoretical quality guarantees on the new model; and (v) empirically evaluate both proactive and reactive algorithms to determine the tradeoffs between the two classes. The final contribution is important as, thus far, researchers have exclusively evaluated the two classes of algorithms in isolation. As a result, it is difficult to identify the characteristics of problems that they excel in. Our results are the first in this important direction.
  • Ferdinando Fioretto, William Yeoh, Enrico Pontelli. "A Multiagent System Approach to Scheduling Devices in Smart Homes". In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2017.
    Downloads: [pdf] [slides] [BibTex] | Links: [web] [github] Show more
    Abstract: Demand-side management (DSM) in the smart grid allows customers to make autonomous decisions on their energy consumption, helping energy providers to reduce the energy peaks in load demand. The automated scheduling of smart devices in residential and commercial buildings plays a key role in DSM. Due to data privacy and user autonomy, such an approach is best implemented through distributed multi-agent systems. This paper makes the following contributions: (i) It introduces the Smart Home Device Scheduling (SHDS) problem, which formalizes the device scheduling and coordination problem across multiple smart homes as a multi-agent system; (ii) It describes a mapping of this problem to a distributed constraint optimization problem; (iii) It proposes a distributed algorithm for the SHDS problem; and (iv) It presents empirical results from a physically distributed system of Raspberry Pis, each capable of controlling smart devices through hardware interfaces, as well as larger scale synthetic experiments.
  • Ferdinando Fioretto, William Yeoh, Enrico Pontelli, Ye Ma, Satishkumar Ranade. "A Distributed Constraint Optimization (DCOP) Approach to the Economic Dispatch with Demand Response". In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2017.
    Downloads: [pdf] [slides] [BibTex] | Links: [web] [request code] Show more
    Abstract: With the growing complexity of the current power grid, there is an increasing need for intelligent operations coordinating energy supply and demand. A key feature of the smart grid vision is that intelligent mechanisms will coordinate the production, transmission, and consumption of energy in a distributed and reliable way. Economic Dispatch (ED) and Demand Response (DR) are two key problems that need to be solved to achieve this vision. In traditional operations, ED and DR are implemented separately, despite the strong inter-dependencies between these two problems. Therefore, we propose an integrated approach to solve the ED and DR problems that simultaneously maximizes the benefits of customers and minimizes the generation costs, and introduce an effective multi-agent-based algorithm, based on Distributed Constraint Optimization Problems (DCOPs), acting on direct control of both generators and dispatchable loads. To cope with the high complexity of the problem, our solution employs General Purpose Graphical Processing Units (GPGPUs) to speed up the computational runtime. We empirically evaluate the proposed algorithms on standard IEEE bus systems and test the stability of the proposed solution with a state-of-the-art power system simulator on the IEEE 30-bus system.
  • Book Chapters
  • William Kluegel, Muhammad Aamir Iqbal, Ferdinando Fioretto, William Yeoh, Enrico Pontelli: "A Realistic Dataset for the Smart Home Device Scheduling Problem for DCOPs". In Proceedings of the International Workshop on Optimisation in Multi-Agent Systems (OPTMAS), 2017.
    Downloads: [pdf] [BibTex] | Links: [web] [github] *Most visionary paper award* Show more
    Abstract: The field of Distributed Constraint Optimization has gained momentum in recent years thanks to its ability to address various applications related to multi-agent cooperation. While techniques for solving Distributed Constraint Optimization Problems (DCOPs) are abundant and have matured substantially since the field inception, the number of DCOP realistic applications available to assess the performance of DCOP algorithms is lagging behind. To contrast this background we (i) introduce the Smart Home Device Scheduling (SHDS) problem, which describe the problem of coordinating smart devices schedules across multiple homes as a multi-agent system, (ii) detail the physical models adopted to simulate smart sensors, smart actuators, and homes' environments, and (iii) introduce a DCOP realistic benchmark for SHDS problems.
  • Porag Chowdhury, Russell Y. Folk, Ferdinando Fioretto, Christopher Kiekintveld, William Yeoh. "Investigation of Learning Strategies for the SPOT Broker in Power TAC". In Agent-Mediated Electronic Commerce. Designing Trading Strategies and Mechanisms for Electronic Markets, 2017.
    Downloads: [pdf] [BibTex] | Links: [web] [request code] Show more
    Abstract: The Power TAC simulation emphasizes the strategic problems that broker agents face in managing the economics of a smart grid. The brokers must make trades in multiple markets and, to be successful, brokers must make many good predictions about future supply, demand, and prices in the wholesale and tariff markets. In this paper, we investigate the feasibility of using learning strategies to improve the performance of our broker, SPOT. Specifically, we investigate the use of decision trees and neural networks to predict the clearing price in the wholesale market and the use of reinforcement learning to learn good strategies for pricing our tariffs in the tariff market. Our preliminary results show that our learning strategies are promising ways to improve the performance of the agent for future competitions.
  • Workshops
  • William Kluegel, Muhammad Aamir Iqbal, Ferdinando Fioretto, William Yeoh, Enrico Pontelli: "A Realistic Dataset for the Smart Home Device Scheduling Problem for DCOPs". In Proceedings of the International Workshop on Optimisation in Multi-Agent Systems (OPTMAS), 2017.
    Downloads: [pdf] [slides] [BibTex] | Links: [web] [github] Show more
    Abstract: The field of Distributed Constraint Optimization has gained momentum in recent years thanks to its ability to address various applications related to multi-agent cooperation. While techniques for solving Distributed Constraint Optimization Problems (DCOPs) are abundant and have matured substantially since the field inception, the number of DCOP realistic applications available to assess the performance of DCOP algorithms is lagging behind. To contrast this background we (i) introduce the Smart Home Device Scheduling (SHDS) problem, which describe the problem of coordinating smart devices schedules across multiple homes as a multi-agent system, (ii) detail the physical models adopted to simulate smart sensors, smart actuators, and homes' environments, and (iii) introduce a DCOP realistic benchmark for SHDS problems.
  • Ferdinando Fioretto, William Yeoh, Enrico Pontelli. "A Multiagent System Approach to Scheduling Devices in Smart Homes". In Proceedings of the International Workshop on Artificial Intelligence for Smart Grids and Smart Buildings (AISGSB), 2017.
    Downloads: [pdf] [slides] [BibTex] | Links: [web] [request code] Show more
    Abstract: Demand-side management (DSM) in the smart grid allows customers to make autonomous decisions on their energy consumption, helping energy providers to reduce the peaks in load demand. The automated scheduling of smart devices in residential and commercial buildings plays a key role in DSM. Due to data privacy and user autonomy, such an approach is best implemented through distributed multi-agent systems. This paper makes the following contributions: (i) It introduces the Smart Home Device Scheduling (SHDS) problem, which formalizes the device scheduling and coordination problem across multiple smart homes as a multi-agent system; (ii) It describes a mapping of this problem to a distributed constraint optimization problem; (iii) It proposes a distributed algorithm for the SHDS problem; and (iv) It presents empirical results from a physically distributed sys- tem of Raspberry Pis, each capable of controlling smart devices through hardware interfaces.
  • Pre-prints
  • William Kluegel, Muhammad Aamir Iqbal, Ferdinando Fioretto, William Yeoh, Enrico Pontelli: "A Realistic Dataset for the Smart Home Device Scheduling Problem for DCOPs". CoRR abs/1702.06970, 2017.
    Downloads: [pdf] [BibTex] | Links: [web] [github] Show more
    Abstract: The field of Distributed Constraint Optimization has gained momentum in recent years thanks to its ability to address various applications related to multi-agent cooperation. While techniques for solving Distributed Constraint Optimization Problems (DCOPs) are abundant and have matured substantially since the field inception, the number of DCOP realistic applications available to assess the performance of DCOP algorithms is lagging behind. To contrast this background we (i) introduce the Smart Home Device Scheduling (SHDS) problem, which describe the problem of coordinating smart devices schedules across multiple homes as a multi-agent system, (ii) detail the physical models adopted to simulate smart sensors, smart actuators, and homes' environments, and (iii) introduce a DCOP realistic benchmark for SHDS problems.
  • Ferdinando Fioretto, Agostino Dovier, Enrico Pontelli, William Yeoh, Roie Zivan: "Solving DCOPs with Distributed Large Neighborhood Search". CoRR abs/1702.06915, 2017.
    Downloads: [pdf] [BibTex] | Links: [web] [request code] Show more
    Abstract: The field of Distributed Constraint Optimization has gained momentum in recent years, thanks to its ability to address various applications related to multi-agent cooperation. Nevertheless, solving Distributed Constraint Optimization Problems (DCOPs) optimally is NP-hard. Therefore, in large-scale, complex applications, incomplete DCOP algorithms are necessary. Current incomplete DCOP algorithms suffer of one or more of the following limitations: they (a) find local minima without providing quality guarantees; (b) provide loose quality assessment; or (c) are unable to benefit from the structure of the problem, such as domain-dependent knowledge and hard constraints. Therefore, capitalizing on strategies from the centralized constraint solving community, we propose a Distributed Large Neighborhood Search (D-LNS) framework to solve DCOPs. The proposed framework (with its novel repair phase) provides guarantees on solution quality, refining upper and lower bounds during the iterative process, and can exploit domain-dependent structures. Our experimental results show that D-LNS outperforms other incomplete DCOP algorithms on both structured and unstructured problem instances.

2016

    Conferences
  • Khoi Hoang, Ferdinando Fioretto, Ping Hou, Makoto Yokoo, William Yeoh, Roie Zivan. "Proactive Dynamic Distributed Constraint Optimization". In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2016.
    Downloads: [pdf] [slides] [BibTex] | Links: [web] [request code] Show more
    Abstract: Current approaches that model dynamism in DCOPs solve a sequence of static problems, reacting to changes in the environment as the agents observe them. Such approaches thus ignore possible predictions on future changes. To overcome this limitation, we introduce Proactive Dynamic DCOPs (PD-DCOPs), a novel formalism to model dynamic DCOPs in the presence of exogenous uncertainty. In contrast to reactive approaches, PD-DCOPs are able to explicitly model the possible changes to the problem, and take such information into account proactively, when solving the dynamically changing problem. The additional expressivity of this formalism allows it to model a wider variety of distributed optimization problems. Our work presents both theoretical and practical contributions that advance current dynamic DCOP models: (i) we introduce the PD-DCOP model, which explicitly captures dynamic changes of the DCOP over time; (ii) we discuss the complexity of this new class of DCOPs; and (iii) we develop both exact and approximation algorithms with quality guarantees to solve PD-DCOPs proactively.
  • Tiep Le, Ferdinando Fioretto, William Yeoh, Tran Cao Son, and Enrico Pontelli. "ER-DCOPs: A Framework for DCOPs with Uncertainty in Constraint Utilities". In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2016.
    Downloads: [pdf] [slides] [BibTex] | Links: [web] [request code] Show more
    Abstract: Distributed Constraint Optimization Problems (DCOPs) have been used to model a number of multi-agent coordination problems. In DCOPs, agents are assumed to have complete information about the utility of their possible actions. However, in many real-world applications, such utilities are stochastic due to the presence of exogenous events that are beyond the direct control of the agents. This paper addresses this issue by extending the standard DCOP model to Expected Regret DCOP (ER-DCOP) for DCOP applications with uncertainty in constraint utilities. Different from other approaches, ER-DCOPs aim at minimizing the overall expected regret of the problem. The paper proposes the ER-DPOP algorithm for solving ER-DCOPs, which is complete and requires a linear number of messages with respect to the number of agents in the problem. We further present two implementations of ER-DPOP---GPU- and ASP-based implementations---that orthogonally exploit the problem structure and present their evaluations on random networks and power network problems.
  • Ferdinando Fioretto, William Yeoh, Enrico Pontelli. "Multi-Variable Agent Decomposition for DCOPs". In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2016.
    Downloads: [pdf] [slides] [BibTex] | Links: [web] [github] Show more
    Abstract: The application of DCOP models to large problems faces two main limitations: (i) Modeling limitations, as each agent can handle only a single variable of the problem; and (ii) Resolution limitations, as current approaches do not exploit the local problem structure within each agent. This paper proposes a novel Multi-Variable Agent (MVA) DCOP decomposition technique, which: (i) Exploits the co-locality of each agent's variables, allowing us to adopt efficient centralized techniques within each agent; (ii) Enables the use of hierarchical parallel models and proposes the use of GPUs; and (iii) Reduces the amount of computation and communication required in several classes of DCOP algorithms.
  • Ferdinando Fioretto, William Yeoh, Enrico Pontelli. "A Dynamic Programming-based MCMC Framework for Solving DCOPs with GPUs". In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), 2016.
    Downloads: [pdf] [slides] [BibTex] | Links: [web] [github] Show more
    Abstract: The field of Distributed Constraint Optimization (DCOP) has gained momentum in recent years, thanks to its ability to address various applications related to multi-agent coordination. Nevertheless, solving DCOPs is computationally challenging. Thus, in large scale, complex applications, incomplete DCOP algorithms are necessary. Recently, researchers have introduced a promising class of incomplete DCOP algorithms, based on sampling. However, this paradigm requires a multitude of samples to ensure convergence. This paper exploits the property that sampling is amenable to parallelization, and introduces a general framework, called Distributed MCMC (DMCMC), that is based on a dynamic programming procedure and uses Markov Chain Monte Carlo (MCMC) sampling algorithms to solve DCOPs. Additionally, DMCMC harnesses the parallel computing power of Graphical Processing Units (GPUs) to speed-up the sampling process. The experimental results show that DMCMC can find good solutions up to two order of magnitude faster than other incomplete DCOP algorithms.
  • Workshops
  • Atena M. Tabakhi, Ferdinando Fioretto, William Yeoh. "A Preliminary Study on Preference Elicitation in DCOPs for Scheduling Devices in Smart Buildings". In the 10th Workshop on Advances in Preference Handling (MPREF), 2016.
    Downloads: [pdf] [slides] [BibTex] | Links: [web] [request code] Show more
    Abstract: Distributed Constraint Optimization Problems (DCOPs) offer a powerful approach for the description and resolution of cooperative multi-agent problems. In such model a group of agents coordinate their actions to optimize a global objective function, taking into account their preferences and constraints. A core limitation of this model is the assumption that all agents’ preferences are specified a priori. Unfortunately, in a number of application domains, such knowledge is not assumed, and these values may become available only after being elicited from users in the domain. Motivated by the current developments in smart buildings we explore the effect of preference elicitation in scheduling smart appliances within a network of interconnected buildings, with the goal of reducing the users’ energy consumption costs, while taking into account the comfort of the occupants. This paper makes the following contributions: (1) It introduces the Smart Building Devices Scheduling (SBDS) problem and maps it as a DCOP; (2) It proposes a general model for preference elicitation in DCOPs; and (3) It empirically evaluates the effect of several heuristics to select a set of preferences to elicit in SBDS problems.
  • Porag Chowdhury, Russell Y. Folk, Ferdinando Fioretto, Christopher Kiekintveld, William Yeoh. "Investigation of Learning Strategies for the SPOT Broker in Power TAC". In the International Workshop on Agent Mediated Electronic Commerce and Trading Agents Design and Analysis (AMEC/TADA), 2016.
    Downloads: [pdf] [BibTex] | Links: [web] [request code] Show more
    Abstract: The Power TAC simulation emphasizes the strategic problems that broker agents face in managing the economics of a smart grid. The brokers must make trades in multiple markets and, to be successful, brokers must make many good predictions about future supply, demand, and prices in the wholesale and tariff markets. In this paper, we investigate the feasibility of using learning strategies to improve the performance of our broker, SPOT. Specifically, we investigate the use of decision trees and neural networks to predict the clearing price in the wholesale market and the use of reinforcement learning to learn good strategies for pricing our tariffs in the tariff market. Our preliminary results show that our learning strategies are promising ways to improve the performance of the agent for future competitions.
  • Khoi Hoang, Ferdinando Fioretto, Ping Hou, Makoto Yokoo, William Yeoh, Roie Zivan. "Proactive Dynamic DCOPs". In AAAI Workshop on AI for Smart Grids and Smart Buildings (AISGSB), 2016.
    Downloads: [pdf] [slides] [BibTex] | Links: [web] [request code]
    Abstract: The current approaches to model dynamism in DCOPs solve a sequence of static problems, reacting to the changes in the environment as the agents observe them. Such approaches, thus, ignore possible predictions on the environment evolution. To overcome such limitations, we introduce the Proactive Dynamic DCOP (PD-DCOP) model, a novel formalism to model dynamic DCOPs in the presence of exogenous uncertainty. In contrast to reactive approaches, PD-DCOPs are able to explicitly model the possible changes to the problem, and take such information into account proactively, when solving the dynamically changing problem.
  • Pre-prints
  • Ferdinando Fioretto, William Yeoh, Enrico Pontelli. "Distributed Constraint Optimization Problems and Applications: A Survey". In arXiv:1602.06347v1[cs.AI], 2016.
    Downloads: [pdf] [BibTex] | Links: [web] Show more
    Abstract: The field of Multi-Agent System (MAS) is an active area of research within Artificial Intelligence, with an increasingly important impact in industrial and other real-world applications. Within a MAS, autonomous agents interact to pursue personal interests and/or to achieve common objectives. Distributed Constraint Optimization Problems (DCOPs) have emerged as one of the prominent agent architectures to govern the agents’ autonomous behavior, where both algorithms and communication models are driven by the structure of the specific problem. During the last decade, several extensions to the DCOP model have enabled them to support MAS in complex, real-time, and uncertain environments. This survey aims at providing an overview of the DCOP model, giving a classification of its multiple extensions and addressing both resolution methods and applications that find a natural mapping within each class of DCOPs. The proposed classification suggests several future perspectives for DCOP extensions, and identifies challenges in the design of efficient resolution algorithms, possibly through the adaptation of strategies from different areas.
  • Ferdinando Fioretto, William Yeoh, Enrico Pontelli, Rina Dechter. "Accelerating Exact and Approximate Inference for (Distributed) Discrete Optimization with GPUs". In arXiv:1608.05288[cs.AI], 2016.
    Downloads: [pdf] [BibTex] | Links: [web] [request code] Show more
    Abstract: Discrete optimization is a central problem in artificial intelligence. The optimization of the aggregated cost of a network of cost functions arises in a variety of problems including (W)CSP, DCOP, as well as optimization in stochastic variants such as Bayesian networks. Inference-based algorithms are powerful techniques for solving discrete optimization problems, which can be used standalone or in combination with other techniques. However, their applicability is often limited by their high time and space requirements. Therefore, this paper proposes the design and implementation of an inference-based technique, which exploits modern massively parallel architectures, such as those found in modern Graphical Processing Units (GPUs), to speed up the resolution of exact and approximated inference-based algorithms for discrete optimization. The paper studies the proposed algorithm in both centralized and distributed optimization contexts. We show that the use of GPUs provides significant advantages in terms of runtime and scalability, achieving speedups of up to two orders of magnitude, showing a considerable reduction in runtime (up to 345 times faster) with respect to a serialized version.

2015

    Journals
  • Ferdinando Fioretto, Agostino Dovier and Enrico Pontelli. "Constrained Community-based Gene Regulatory Network Inference". In ACM Transactions on Modeling and Computer Simulation (TOMACS), 2015.
    Downloads: [pdf] [appendix] [BibTex] | Links: [web] [github] Show more
    Abstract: The problem of gene regulatory network inference is a major concern of systems biology. In recent years, a novel methodology has gained momentum, called community network approach. Community networks integrate predictions from individual methods in a “metapredictor,” in order to compose the advantages of different methods and soften individual limitations. This article proposes a novel methodology to integrate prediction ensembles using constraint programming, a declarative modeling and problem solving paradigm. Constraint programming naturally allows the modeling of dependencies among components of the problem as constraints, facilitating the integration and use of different forms of knowledge. The new paradigm, referred to as constrained community network, uses constraints to capture properties of the regulatory networks (e.g., topological properties) and to guide the integration of knowledge derived from different families of network predictions. The article experimentally shows the potential of this approach: The addition of biological constraints can offer significant improvements in prediction accuracy.
  • Conferences
  • Ferdinando Fioretto, Tiep Le, William Yeoh, Enrico Pontelli and Tran Cao Son. "Exploiting GPUs in Solving (Distributed) Constraint Optimization Problems with Dynamic Programming". In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), 2015.
    Downloads: [pdf] [slides] [BibTex] | Links: [web] [github] Show more
    Abstract: This paper proposes the design and implementation of a dynamic programming based algorithm for (distributed) constraint optimization, which exploits modern massively parallel architectures, such as those found in modern Graphical Processing Units (GPUs). The paper studies the proposed algorithm in both centralized and distributed optimization contexts. The experimental analysis, performed on unstructured and structured graphs, shows the advantages of employing GPUs, resulting in enhanced performances and scalability.
  • Ferdinando Fioretto, William Yeoh and Enrico Pontelli. "Multi-Variable Agents Decomposition for DCOPs to Exploit Multi-Level Parallelism". In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2015.
    Downloads: [pdf] [BibTex] | Links: [web] [github] Show more
    Abstract: Current DCOP algorithms suffer from a major limiting assumption---each agent can handle only a single variable of the problem---which limits their scalability. This paper proposes a novel Multi-Variable Agent (MVA) DCOP decomposition, which: (i) Exploits co-locality of an agent's variables, allowing us to adopt efficient centralized techniques; (ii) Enables the use of hierarchical parallel models, such us those based on GPGPUs; and (iii) Empirically reduces the amount of communication required in several classes of DCOP algorithms. Experimental results show that our MVA decomposition outperforms non-decomposed DCOP algorithms, in terms of network load and scalability.
  • Ferdinando Fioretto, Federico Campeotto, Agostino Dovier, William Yeoh and Enrico Pontelli. "Large Neighborhood Search with Quality Guarantees for Distributed Constraint Optimization Problems". In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2015.
    Downloads: [pdf] [BibTex] | Links: [web] Show more
    Abstract: This paper proposes Distributed Large Neighborhood Search (D-LNS), an incomplete DCOP algorithm that builds on the strengths of centralized LNS. D-LNS: (i) is anytime; (ii) provides guarantees on solution quality (upper and lower bounds); and (iii) can learn online the best neighborhood to explore. Experimental results show that D-LNS outperforms other incomplete DCOP algorithms in random and scale-free network instances.
  • Ferdinando Fioretto. "Exploiting the Structure of Distributed Constraint Optimization Problems". In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), AAAI/SIGAI Doctoral Consortium, 2015.
    Downloads: [pdf] [BibTex] | Links: [web] Show more
    Abstract: In the proposed thesis, we study Distributed Constraint Optimization Problems (DCOPs), which are problems where several agents coordinate with each other to optimize a global cost function. The use of DCOPs has gained momentum, due to their capability of addressing complex and naturally distributed problems. A majority of the work in DCOP addresses the resolution problem by detaching the model from the resolution process, where they assume that each agent controls exclusively one variable of the problem (Burke et al. 2006). This assumption often is not reflected in the model specifications, and may lead to inefficient communication requirements. Another limitation of current DCOP resolution methods is their inability to capitalize on the presence of structural information, which may allow incoherent/unnecessary data to reticulate among the agents (Yokoo 2001). The purpose of the proposed dissertation is to study how to adapt and integrate insights gained from centralized solving techniques in order to enhance DCOP performance and scalability, enabling their use for the resolution of real-world complex problems. To do so, we hypothesize that one can exploit the DCOP structure in both problem modeling and problem resolution phases.
  • Ferdinando Fioretto. "Exploiting the Structure of Distributed Constraint Optimization Problems". In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Doctoral Mentoring Program, 2015.
    Downloads: [pdf] [BibTex] | Links: [web] Show more
    Abstract: In the proposed thesis, we study Distributed Constraint Optimization Problems (DCOPs), which are problems where several agents coordinate with each other to optimize a global cost function. The use of DCOPs has gained momentum, due to their capability of addressing complex and naturally distributed problems. However, the adoption of DCOP on large problems faces two main limitations: (1) Modeling limitations, as current resolution methods detach the model from the resolution process, assuming that each agent controls a single variable of the problem; and (2) Solving capabilities, as the inability of current approaches to capitalize on the presence of structural information which may allow incoherent/unnecessary data to reticulate among the agents as well as to exploit structure of the agent's local problems. The purpose of the proposed dissertation is to address such limitations, studying how to adapt and integrate insights gained from centralized solving techniques in order to enhance DCOP performance and scalability, enabling their use for the resolution of real-world complex problems. To do so, we hypothesize that one can exploit the DCOP structure in both problem modeling and problem resolution phases.
  • Workshops
  • Ferdinando Fioretto, Tiep Le, William Yeoh, Enrico Pontelli and Tran Cao Son. "Improving DPOP with Branch Consistency for Solving Distributed Constraint Optimization Problems". In Workshop on Optimisation in Multi-Agent Systems (OPTMAS), 2015.
    Downloads: [pdf] [BibTex] | Links: [web] Show more
    Abstract: The DCOP model has gained momentum in recent years thanks to its ability to capture problems that are naturally distributed and cannot be realistically addressed in a centralized manner. Dynamic programming based techniques have been recognized to be among the most effective techniques for building complete DCOP solvers (e.g., DPOP). Unfortunately, they also suffer from a widely recognized drawback: their messages are exponential in size. Another limitation is that most current DCOP algorithms do not actively exploit hard constraints, which are common in many real problems. This paper addresses these two limitations by introducing an algorithm, called BrC-DPOP, that exploits arc consistency and a form of consistency that applies to paths in pseudo-trees to reduce the size of the messages. Experimental results shows that BrC-DPOP uses messages that are up to one order of magnitude smaller than DPOP, and that it can scale up well, being able to solve problems that its counterpart can not.
  • Ferdinando Fioretto, Federico Campeotto, Agostino Dovier, William Yeoh and Enrico Pontelli. "Large Neighborhood Search with Quality Guarantees for Distributed Constraint Optimization Problems". In Workshop on Optimisation in Multi-Agent Systems (OPTMAS), 2015.
    Downloads: [pdf] [BibTex] | Links: [web] Show more
    Abstract: The field of Distributed Constraint Optimization has gained momentum in recent years, thanks to its ability to address various applications related to multi-agent cooperation. Nevertheless, solving Distributed Constraint Optimization Problems (DCOPs) optimally is NP-hard. Therefore, in large-scale applications, incomplete DCOP algorithms are desirable. Current incomplete search techniques have subsets of the following limitations: (a) they find local minima without quality guarantees; (b) they provide loose quality assessment; or (c) they cannot exploit certain problem structures such as hard constraints. Therefore, capitalizing on strategies from the centralized constraint reasoning community, we propose to adapt the Large Neighborhood Search (LNS) strategy to solve DCOPs, resulting in the general Distributed LNS (D-LNS) framework. The characteristics of this framework are as follows: (i) it is anytime; (ii) it provides quality guarantees by refining online upper and lower bounds on its solution quality; and (iii) it can learn online the best neighborhood to explore. Experimental results show that D-LNS outperforms other incomplete DCOP algorithms for both random and scale-free network instances.

2014

    Conferences
  • Ferdinando Fioretto, Tiep Le, William Yeoh, Enrico Pontelli and Tran Cao Son. "Improving DPOP with Branch Consistency for Solving Distributed Constraint Optimization Problems". In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), 2014.
    Downloads: [pdf] [slides] [BibTex] | Links: [web] [github] Show more
    Abstract: The DCOP model has gained momentum in recent years thanks to its ability to capture problems that are naturally distributed and cannot be realistically addressed in a centralized manner. Dynamic programming based techniques have been recognized to be among the most effective techniques for building complete DCOP solvers (e.g., DPOP). Unfortunately, they also suffer from a widely recognized drawback: their messages are exponential in size. Another limitation is that most current DCOP algorithms do not actively exploit hard constraints, which are common in many real problems. This paper addresses these two limitations by introducing an algorithm, called BrC-DPOP, that exploits arc consistency and a form of consistency that applies to paths in pseudo-trees to reduce the size of the messages. Experimental results shows that BrC-DPOP uses messages that are up to one order of magnitude smaller than DPOP, and that it can scale up well, being able to solve problems that its counterpart can not.
  • Federico Campeotto, Agostino Dovier, Ferdinando Fioretto and Enrico Pontelli. "A GPU Implementation of Large Neighborhood Search for Solving Constraint Optimization Problems". In Proceedings of the European Conference of Artificial Intelligence (ECAI), 2014.
    Downloads: [pdf] [slides] [BibTex] | Links: [web] [request code] Show more
    Abstract: Constraint programming has gained prominence as an effective and declarative paradigm for modeling and solving complex combinatorial problems. Techniques based on local search have proved practical to solve real-world problems, providing a good compromise between optimality and efficiency. In spite of the natural presence of concurrency, there has been relatively limited effort to use novel massively parallel architectures, such as those found in modern Graphical Processing Units (GPUs), to speedup local search techniques in constraint programming. This paper describes a novel framework which exploits parallelism from a popular local search method (the Large Neighborhood Search method), using GPUs.
  • Ferdinando Fioretto, Federico Campeotto, Luca Da Rin Fioretto, William Yeoh, Enrico Pontelli. "GD-Gibbs: A GPU-based Sampling Algorithm for Solving Distributed Constraint Optimization Problems". In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2014.
    Downloads: [pdf] [BibTex] | Links: [web] [request code] Show more
    Abstract: Researchers have recently introduced a promising new class of Distributed Constraint Optimization Problem (DCOP) algorithms that is based on sampling. This paradigm is very amenable to parallelization since sampling algorithms require a lot of samples to ensure convergence, and the sampling process can be designed to be executed in parallel. This paper presents GPU-based D-Gibbs (GD-Gibbs), which extends the Distributed Gibbs (D-Gibbs) sampling algorithm and harnesses the power of parallel computation of GPUs to solve DCOPs. Experimental results show that GD-Gibbs is faster than several other benchmark algorithms on a distributed meeting scheduling problem.
  • Federico Campeotto, Alessandro Dal Palu', Agostino Dovier, Ferdinando Fioretto, Enrico Pontelli. "Exploring the Use of GPUs in Constraint Solving". In Proceedings of the Practical Aspects of Declarative Languages (PADL), 2014.
    Downloads: [pdf] [slides] [BibTex] | Links: [web] [request code] Show more
    Abstract: This paper presents an experimental study aimed at assessing the feasibility of parallelizing constraint propagation—with particular focus on arc-consistency—using Graphical Processing Units (GPUs). GPUs support a form of data parallelism that appears to be suitable to the type of processing required to cycle through constraints and domain values during consistency checking and propagation. The paper illustrates an implementation of a constraint solver capable of hybrid propagations (i.e., alternating CPU and GPU), and demonstrates the potential for competitiveness against sequential implementations.
  • Workshops
  • Federico Campeotto, Alessandro Dal Palu', Agostino Dovier, Ferdinando Fioretto, Enrico Pontelli. "Experimenting with FIASCO for protein structure prediction". In Workshop on Constraint-Based Methods for Bioinformatics (WCB), 2014
    Downloads: [pdf] [BibTex] | Links: [web] [request code] Show more
    Abstract: Constraint Programming (CP) [6] is a declarative programming methodology that has gained a predominant role in addressing large scale combinatorial and optimization problems. The CP paradigm provides the tools necessary to guide the modeling and resolution of search problems. In particular, it enables the declarative modeling (in terms of variables and constraints) of problems, the ability to rapidly propagate the effects of search decisions, and flexible and efficient procedures to explore the search space of possible solutions. The focus of this work is the use of constraint-based technology in the investigation of protein structures. We developed a system composed of two main parts: (1) a Graphical User Interface, to help the user, in particular users coming from Biology, in modeling protein structure studies with CP, and (2) a constraint solver targeted at protein structure analysis. Parts of the system have been presented in four previous works. In [1] a first prototype of the graphical interface has been presented, using a preliminary version of the solver later presented in [2] and, still improved, in [5]. This solver focused on one class of constraints targeting the problem of loop closure; our current work provides instead a comprehensive constraint system for modeling generic structural protein properties and investigating different types of problems (e.g., structure prediction, studies of flexibility). Moreover the solver makes use, in some parts, of GPU computation following the ideas presented in [4], as explained below.
  • Federico Campeotto, Alessandro Dal Palu', Agostino Dovier, Ferdinando Fioretto, Enrico Pontelli. "Towards a complete constraint solver on GPU". In Workshop on Parallel Methods for Search & Optimization (ParSearchOpt), 2014.
    Downloads: [pdf] [BibTex] | Links: [web] [request code] Show more
    Abstract: Constraint programming has gained prominence as an effective and declarative paradigm for modeling and solving complex combinatorial problems. In spite of the natural presence of concurrency, there has been relatively limited effort to use novel massively parallel architectures—such as those found in modern Graphical Processing Units (GPUs)—to speedup constraint programming algorithms. This paper presents an ongoing work for the development of a constraint solver which exploits GPU parallelism. The work is based on two previous results where constraint propagation and approximated search have been parallelized [5, 6]. We summarize these result and discuss the features we have planned to carry on.
  • 2013

      Journals
    • Federico Campeotto, Alessandro Dal Palu', Agostino Dovier, Ferdinando Fioretto, Enrico Pontelli. "A Constraint Solver for Flexible Protein Models". In Journal of Artificial Intelligence Research (JAIR), 2013.
      Downloads: [pdf] [BibTex] | Links: [web] Show more
      Abstract: This paper proposes the formalization and implementation of a novel class of constraints aimed at modeling problems related to placement of multi-body systems in the 3-dimensional space. Each multi-body is a system composed of body elements, connected by joint relationships and constrained by geometric properties. The emphasis of this investigation is the use of multi-body systems to model native conformations of protein structures---where each body represents an entity of the protein (e.g., an amino acid, a small peptide) and the geometric constraints are related to the spatial properties of the composing atoms. The paper explores the use of the proposed class of constraints to support a variety of different structural analysis of proteins, such as loop modeling and structure prediction. The declarative nature of a constraint-based encoding provides elaboration tolerance and the ability to make use of any additional knowledge in the analysis studies. The filtering capabilities of the proposed constraints also allow to control the number of representative solutions that are withdrawn from the conformational space of the protein, by means of criteria driven by uniform distribution sampling principles. In this scenario it is possible to select the desired degree of precision and/or number of solutions. The filtering component automatically excludes configurations that violate the spatial and geometric properties of the composing multi-body system. The paper illustrates the implementation of a constraint solver based on the multi-body perspective and its empirical evaluation on protein structure analysis problems.
    • Conferences
    • Ferdinando Fioretto, Enrico Pontelli. "Constraint Programming in Community-based Gene Regulatory Network Inference". In Proceedings of the Computational Methods in System Biology (CMSB), 2013.
      Downloads: [pdf] [slides] [BibTex] | Links: [web] [request code] *Best student paper award* Show more
      Abstract: Gene Regulatory Network (GRN) inference is a major objective of Systems Biology. The complexity of biological systems and the lack of adequate data have posed many challenges to the inference problem. Community networks integrate predictions from individual methods in a “meta predictor”, in order to compose the advantages of different methods and soften individual limitations. This paper proposes a novel methodology to integrate prediction ensembles using Constraint Programming, a declarative modeling paradigm, which allows the formulation of dependencies among components of the problem, enabling the integration of diverse forms of knowledge. The paper experimentally shows the potential of this method: the addition of biological constraints can offer improvements in the prediction accuracy, and the method shows promising results in assessing biological hypothesis using constraints.
    • Workshops
    • Ferdinando Fioretto, Enrico Pontelli. "Constraint Programming in Community-based Gene Regulatory Network Inference". In Workshop on Constraint-Based-Methods for Bioinformatics (WCB), 2013.
      Downloads: [pdf] [BibTex] | Links: [web] [request code] Show more
      Abstract: Gene Regulatory Network (GRN) inference is a major objective of Systems Biology. The complexity of biological systems and the lack of adequate data have posed many challenges to the inference problem. Community networks integrate predictions from individual methods in a “meta predictor”, in order to compose the advantages of different methods and soften individual limitations. This paper proposes a novel methodology to integrate prediction ensembles using Constraint Programming, a declarative modeling paradigm, which allows the formulation of dependencies among components of the problem, enabling the integration of diverse forms of knowledge. The paper experimentally shows the potential of this method: the addition of biological constraints can offer improvements in the prediction accuracy, and the method shows promising results in assessing biological hypothesis using constraints.
    • 2012

        Conferences
      • Federico Campeotto, Alessandro Dal Palu', Agostino Dovier, Ferdinando Fioretto and Enrico Pontelli. "A Filtering Technique for Fragment Assembly-based Proteins Loop Modeling with Constraints". In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), 2012.
        Downloads: [pdf] [BibTex] | Links: [web] [request code] Show more
        Abstract: Methods to predict the structure of a protein often rely on the knowledge of macro sub-structures and their exact or approximated relative positions in space. The parts connecting these sub-structures are called loops and, in general, they are characterized by a high degree of freedom. The modeling of loops is a critical problem in predicting protein conformations that are biologically realistic. This paper introduces a class of constraints that models a general multi-body system; we present a proof of NP-completeness and provide filtering techniques, inspired by inverse kinematics, that can drastically reduce the search space of potential conformations. The paper shows the application of the constraint in solving the protein loop modeling problem, based on fragments assembly.
      • Workshops
      • Federico Campeotto, Alessandro Dal Palu', Agostino Dovier, Ferdinando Fioretto and Enrico Pontelli. "Protein Loop Modelling via Constraints and Fragment Assembly". In Workshop on Constraint-Based-Methods for Bioinformatics (WCB), 2012.
        Downloads: [pdf] [BibTex] | Links: [web] [request code] Show more
        Abstract: Methods to predict the structure of a protein often rely on the knowledge of macro sub-structures and their exact or approximated relative positions in space. The parts connecting these sub-structures are called loops and, in general, they are characterized by a high degree of freedom. The modeling of loops is a critical problem in predicting protein conformations that are biologically realistic. This paper introduces a class of constraints that models a general multi-body system; we present a proof of NP-completeness and provide filtering techniques, inspired by inverse kinematics, that can drastically reduce the search space of potential conformations. The paper shows the application of the constraint in solving the protein loop modeling problem, based on fragments assembly.