Ferdinando Fioretto

2022

Journals

Conferences

IJCAI

"Integrating Machine Learning and Optimization to Boost Decision Making". Ferdinando Fioretto In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2022.
*Early Career Spotlight talk*
Downloads: [pdf] Show more

Abstract: This paper presents a conceptual review of our recent advancements on the integration of machine learning and optimization. It focuses on describing new hybrid machine learning and optimization methods to predict fast, approximate, solutions to combinatorial problems and to enable structural logical inference.

IJCAI

"Post-processing of Differentially Private Data: A Fairness Perspective". Keyu Zhu, Ferdinando Fioretto, Pascal Van Hentenryck In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2022.
Downloads: [pdf] | Links: [online] Show more

Abstract: Post-processing immunity is a fundamental property of differential privacy: it enables arbitrary data-independent transformations to differentially private outputs without affecting their privacy guarantees. Post-processing is routinely applied in data-release applications, including census data, which are then used to make allocations with substantial societal impacts. This paper shows that post-processing causes disparate impacts on individuals or groups and analyzes two critical settings: the release of differentially private datasets and the use of such private datasets for downstream decisions, such as the allocation of funds informed by US Census data. In the first setting, the paper proposes tight bounds on the unfairness of traditional post-processing mechanisms, giving a unique tool to decision-makers to quantify the disparate impacts introduced by their release. In the second setting, this paper proposes a novel post-processing mechanism that is (approximately) optimal under different fairness metrics, either reducing fairness issues substantially or reducing the cost of privacy. The theoretical analysis is complemented with numerical simulations on Census data.

IJCAI

"Differential Privacy and Fairness in Decisions and Learning Tasks: A Survey". Ferdinando Fioretto, Cuong Tran, Pascal Van Hentenryck, Keyu Zhu. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2022.
Downloads: [pdf] | Links: [online] Show more

Abstract: This paper surveys recent work in the intersection of differential privacy (DP) and fairness. It reviews the conditions under which privacy and fairness may have aligned or contrasting goals, analyzes how and why DP may exacerbate bias and unfairness in decision problems and learning tasks, and describes available mitigation measures for the fairness issues arising in DP systems. The survey provides a unified understanding of the main challenges and potential risks arising when deploying privacy-preserving machine-learning or decisions-making tasks under a fairness lens.

WWW

"End-to-end Learning for Fair Ranking Systems". James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck, Ziwei Zhu. In Proceedings of the ACM Web Conference (WWW), 2022.
Downloads: [pdf] [BibTex] | Links: [online] Show more

The learning-to-rank problem aims at ranking items to maximize exposure of those most relevant to a user query. A desirable property of such ranking systems is to guarantee some notion of fairness among specified item groups. While fairness has recently been considered in the context of learning-to-rank systems, current methods cannot provide guarantees on the fairness of the proposed ranking policies. This paper addresses this gap and introduces Smart Predict and Optimize for Fair Ranking (SPOFR), an integrated optimization and learning framework for fairness-constrained learning to rank. The end-to-end SPOFR framework includes a constrained optimization sub-model and produces ranking policies that are guaranteed to satisfy fairness constraints while allowing for fine control of the fairness-utility tradeoff. SPOFR is shown to significantly improve current state-of-the-art fair learning-to-rank systems with respect to established performance metrics.

AAAI

"Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep Learning Method". James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2022.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: The Jobs shop Scheduling Problem (JSP) is a canonical combinatorial optimization problem that is routinely solved for a variety of industrial purposes. It models the optimal scheduling of multiple sequences of tasks, each under a fixed order of operations, in which individual tasks require exclusive access to a predetermined resource for a specified processing time. The problem is NP-hard and computationally challenging even for medium-sized instances. Motivated by the increased stochasticity in production chains, this paper explores a deep learning approach to deliver efficient and accurate approximations to the JSP. In particular, this paper proposes the design of a deep neural network architecture to exploit the problem structure, its integration with Lagrangian duality to capture the problem constraints, and a post-processing optimization to guarantee solution feasibility.The resulting method, called JSP-DNN, is evaluated on hard JSP instances from the JSPLIB benchmark library. Computational results show that JSP-DNN can produce JSP approximations of high quality at negligible computational costs.

PMAPS

"Differentially-Private Heat and Electricity Markets Coordination". Lesia Mitridati, Emma Romei, Gabriela Hug, Ferdinando Fioretto In Proceedings of the International Conference on Probabilistic Methods Applied to Power Systems (PMAPS), 2022.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: Sector coordination between heat and electricity systems has been identified has an energy-efficient and cost-effective way to transition towards a more sustainable energy system. However, the coordination of sequential markets relies on the exchange of sensitive information between the market operators, namely time series of consumers' loads. To address the privacy concerns arising from this exchange, this paper introduces a novel privacy-preserving Stackelberg mechanism (w-PPSM) which generates differentially-private data streams with high fidelity. The proposed w-PPSM enforces the feasibility and fidelity of the privacy-preserving data with respect to the original problem through a post-processing phase in order to achieve a close-to-optimal coordination between the markets. Multiple numerical simulations in a realistic energy system demonstrate the effectiveness of the w-PPSM, which achieves up to two orders of magnitude reduction in the cost of privacy compared to a traditional differentially-private mechanism.

PMAPS

"Learning Solutions for Intertemporal Power Systems Optimization with Recurrent Neural Networks". Mostafa Mohammadian, Kyri Baker, My H. Dinh, Ferdinando Fioretto In Proceedings of the International Conference on Probabilistic Methods Applied to Power Systems (PMAPS), 2022.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: Learning mappings between system loading and optimal dispatch solutions has been a recent topic of interest in the power systems and machine learning communities. However, previous works have ignored practical power system constraints such as generator ramp limits and other intertemporal requirements. Additionally, optimal power flow runs are not performed independently of previous timesteps - in most cases, an OPF solution representing the current state of the system is heavily related to the OPF solution from previous timesteps. In this paper, we train a recurrent neural network, which embeds natural relationships between timesteps, to predict the optimal solution of convex power systems optimization problems with intertemporal constraints. In contrast to traditional forecasting methods, the computational benefits from this technique can allow operators to rapidly simulate forecasts of system operation and corresponding optimal solutions to provide a more comprehensive view of future system states.

Workshops

PPAI

"A Fairness Analysis on Private Aggregation of Teacher Ensembles" Cuong Tran, My H. Dinh, Kyle Beiter, Ferdinando Fioretto. In Privacy-Preserving Artificial Intelligence (PPAI)–at AAAI, 2022.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: The Private Aggregation of Teacher Ensembles (PATE) is an important private machine learning framework. It combines multiple learning models used as teachers for a student model that learns to predict an output chosen by noisy voting among the teachers. The resulting model satisfies differential privacy and has been shown effective in learning high-quality private models in semisupervised settings or when one wishes to protect the data labels. This paper asks whether this privacy-preserving framework introduces or exacerbates bias and unfairness and shows that PATE can introduce accuracy disparity among individuals and groups of individuals. The paper analyzes which algorithmic and data properties are responsible for the disproportionate impacts, why these aspects are affecting different groups disproportionately, and proposes guidelines to mitigate these effects. The proposed approach is evaluated on several datasets and settings.

Pre-prints

"SF-PATE: Scalable, Fair, and Private Aggregation of Teacher Ensembles". Cuong Tran, Keyu Zhu, Ferdinando Fioretto, Pascal Van Hentenryck. CoRR abs/2204.05157 [cs.LG], 2022.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: A critical concern in data-driven processes is to build models whose outcomes do not discriminate against some demographic groups, including gender, ethnicity, or age. To ensure non-discrimination in learning tasks, knowledge of the group attributes is essential. However, in practice, these attributes may not be available due to legal and ethical requirements. To address this challenge, this paper studies a model that protects the privacy of the individuals' sensitive information while also allowing it to learn non-discriminatory predictors. A key characteristic of the proposed model is to enable the adoption of off-the-selves and non-private fair models to create a privacy-preserving and fair model. The paper analyzes the relation between accuracy, privacy, and fairness, and the experimental evaluation illustrates the benefits of the proposed models on several prediction tasks. In particular, this proposal is the first to allow both scalable and accurate training of private and fair models for very large neural networks.

"Deadwooding∗: Robust Global Pruning for Deep Neural Networks". Sawinder Kaur, Ferdinando Fioretto, Asif Salekin. CoRR abs/2202.05226 [cs.LG], 2022.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: The ability of Deep Neural Networks to approximate highly complex functions is the key to their success. This benefit, however, often comes at the cost of a large model size, which challenges their deployment in resource-constrained environments. To limit this issue, pruning techniques can introduce sparsity in the models, but at the cost of accuracy and adversarial robustness. This paper addresses these critical issues and introduces Deadwooding, a novel pruning technique that exploits a Lagrangian Dual method to encourage model sparsity while retaining accuracy and ensuring robustness. The resulting model is shown to significantly outperform the state-of-the-art studies in measures of robustness and accuracy.

"Differential Privacy and Fairness in Decisions and Learning Tasks: A Survey". Ferdinando Fioretto, Cuong Tran, Pascal Van Hentenryck, Keyu Zhu. CoRR abs/2202.08187 [cs.LG, cs.AI], 2022.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: This paper surveys recent work in the intersection of differential privacy (DP) and fairness. It reviews the conditions under which privacy and fairness may have aligned or contrasting goals, analyzes how and why DP may exacerbate bias and unfairness in decision problems and learning tasks, and describes available mitigation measures for the fairness issues arising in DP systems. The survey provides a unified understanding of the main challenges and potential risks arising when deploying privacy-preserving machine-learning or decisions-making tasks under a fairness lens.

"Post-processing of Differentially Private Data: A Fairness Perspective". Keyu Zhu, Ferdinando Fioretto, Pascal Van Hentenryck. CoRR abs/2201.09425 [cs.CR, cs.AI], 2022.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: Post-processing immunity is a fundamental property of differential privacy: it enables arbitrary data-independent transformations to differentially private outputs without affecting their privacy guarantees. Post-processing is routinely applied in data-release applications, including census data, which are then used to make allocations with substantial societal impacts. This paper shows that post-processing causes disparate impacts on individuals or groups and analyzes two critical settings: the release of differentially private datasets and the use of such private datasets for downstream decisions, such as the allocation of funds informed by US Census data. In the first setting, the paper proposes tight bounds on the unfairness of traditional post-processing mechanisms, giving a unique tool to decision-makers to quantify the disparate impacts introduced by their release. In the second setting, this paper proposes a novel post-processing mechanism that is (approximately) optimal under different fairness metrics, either reducing fairness issues substantially or reducing the cost of privacy. The theoretical analysis is complemented with numerical simulations on Census data.

2021

Journals

IEEE-TPS

"Differentially Private Optimal Power Flow for Distribution Grids". Vladimir Dvorkin, Ferdinando Fioretto, Pascal Van Hentenryck, Pierre Pinson, Jalal Kazempour. In IEEE Transactions on Power Systems, 2021.
*2022 TPWRS Best Paper Award*
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: Although distribution grid customers are obliged to share their consumption data with distribution system operators (DSOs), a possible leakage of this data is often disregarded in operational routines of DSOs. This paper introduces a privacy-preserving optimal power flow (OPF) mechanism for distribution grids that secures customer privacy from unauthorised access to OPF solutions, e.g., current and voltage measurements. The mechanism is based on the framework of differential privacy that allows to control the participation risks of individuals in a dataset by applying a carefully calibrated noise to the output of a computation. Unlike existing private mechanisms, this mechanism does not apply the noise to the optimization parameters or its result. Instead, it optimizes OPF variables as affine functions of the random noise, which weakens the correlation between the grid loads and OPF variables. To ensure feasibility of the randomized OPF solution, the mechanism makes use of chance constraints enforced on the grid limits. The mechanism is further extended to control the optimality loss induced by the random noise, as well as the variance of OPF variables. The paper shows that the differentially private OPF solution does not leak customer loads up to specified parameters.

Conferences

NeurIPS

"Differentially Private Deep Learning under the Fairness Lens".
Cuong Tran, My H. Dinh, Ferdinando Fioretto.
In Conference on Neural Information Processing Systems (NeurIPS), 2021.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: Differential Privacy (DP) is an important privacy-enhancing technology for private machine learning systems. It allows to measure and bound the risk associated with an individual participation in a computation. However, it was recently observed that DP learning systems may exacerbate bias and unfairness for different groups of individuals. This paper builds on these important observations and sheds light on the causes of the disparate impacts arising in the problem of differentially private empirical risk minimization. It focuses on the accuracy disparity arising among groups of individuals in two well-studied DP learning methods: output perturbation and differentially private stochastic gradient descent. The paper analyzes which data and model properties are responsible for the disproportionate impacts, why these aspects are affecting different groups disproportionately and proposes guidelines to mitigate these effects. The proposed approach is evaluated on several datasets and settings.

NeurIPS

"Learning Hard Optimization Problems: A Data Generation Perspective". James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck. Conference on Neural Information Processing Systems (NeurIPS), 2021.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: Optimization problems are ubiquitous in our societies and are present in almost every segment of the economy. Most of these optimization problems are NP-hard and computationally demanding, often requiring approximate solutions for large-scale instances. Machine learning frameworks that learn to approximate solutions to such hard optimization problems are a potentially promising avenue to address these difficulties, particularly when many closely related problem instances must be solved repeatedly. Supervised learning frameworks can train a model using the outputs of pre-solved instances. However, when the outputs are themselves approximations, when the optimization problem has symmetric solutions, and/or when the solver uses randomization, solutions to closely related instances may exhibit large differences and the learning task can become inherently more difficult. This paper demonstrates this critical challenge, connects the volatility of the training data to the ability of a model to approximate it, and proposes a method for producing (exact or approximate) solutions to optimization problems that are more amenable to supervised learning tasks. The effectiveness of the method is tested on hard non-linear nonconvex and discrete combinatorial problems.

IJCAI

"Decision Making with Differential Privacy under the Fairness Lens". Cuong Tran, Ferdinando Fioretto, Pascal Van Hentenryck, Zhiyan Yao. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2021.
Downloads: TBA [pdf] [BibTex] | Links: [online] Show more

Abstract: Agencies, such as the U.S. Census Bureau, release data sets and statistics about groups of individuals that are used as input to a number of critical decision processes. To conform with privacy and confidentiality requirements, these agencies are often required to release privacy-preserving versions of the data. This paper studies the release of differentially private census datasets and analyzes their impact on some critical resource allocation tasks under a fairness perspective. The paper shows that, when the decisions take as input differentially private data, the noise added to achieve privacy disproportionately impacts some groups over others. The paper sheds light on the reason for these disproportionate impacts and proposes two approaches to mitigate these effects. Finally, the proposed approaches are evaluated on several resource allocation tasks that use differentially private census data.

IJCAI

"End-to-End Constrained Optimization Learning: A Survey". James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck, Bryan Wilder. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2021.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: This paper surveys the recent attempts at leveraging machine learning to solve constrained optimization problems. It focuses on surveying the work on integrating combinatorial solvers and optimization methods with machine learning architectures. These approaches hold the promise to develop new hybrid machine learning and optimization methods to predict fast, approximate, solutions to combinatorial problems and to enable structural logical inference. This paper presents a conceptual review of the recent advancements in this emerging area

IJCAI

"Differential Privacy of Hierarchical Census Data: An Optimization Approach". Ferdinando Fioretto, Pascal Van Hentenryck, Keyu Zhu. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2021.

Downloads: [pdf (Journal version)] [BibTex] | Links: [online] [request code] Show more

Abstract: This paper is motivated by applications of a Census Bureau interested in releasing aggregate socio-economic data about a large population without revealing sensitive information about any individual. The released information can be the number of individuals living alone, the number of cars they own, or their salary brackets. Recent events have identified some of the privacy challenges faced by these organizations. To address them, this paper presents a novel differential-privacy mechanism for releasing hierarchical counts of individuals. The counts are reported at multiple granularities (e.g., the national, state, and county levels) and must be consistent across all levels. The core of the mechanism is an optimization model that redistributes the noise introduced to achieve differential privacy in order to meet the consistency constraints between the hierarchical levels. The key technical contribution of the paper shows that this optimization problem can be solved in polynomial time by exploiting the structure of its cost functions. Experimental results on very large, real datasets show that the proposed mechanism provides improvements of up to two orders of magnitude in terms of computational efficiency and accuracy with respect to other state-of-the-art techniques.

AAMAS

"A Privacy-Preserving and Accountable Multi-agent Learning Framework". Anudit Nagar, Cuong Tran, Ferdinando Fioretto. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2021.
Downloads: [pdf] [BibTex] | Links: [request code] Show more

Abstract: Distributed multi-agent learning enables agents to cooperatively train a model without requiring to share their datasets. While this setting ensures some level of privacy, it has been shown that even when data is not directly shared, the training process is vulnerable to privacy attacks, including data reconstruction and model inversion attacks. Additionally, malicious agents that train on inverted labels or random data, may arbitrarily weaken the accuracy of the global model. This paper addresses these challenges and presents Privacy-preserving and Accountable Distributed Learning (PA-DL), a fully distributed framework that relies on Differential Privacy to guarantee strong privacy protection of the agents data, and Ethereum smart contracts to ensure accountability. The paper shows that PA-DL is resilient up to a 50% collusion attack in a malicious trust model and the experimental evaluation illustrates the benefits of the proposed model as a privacy-preserving and accountable distributed multi-agent learning system on several classification tasks.

AAAI

"Bias and Variance of Post-processing in Differential Privacy". Keyu Zhu, Pascal Van Hentenryck, Ferdinando Fioretto. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2021.
Downloads: [preprint] [BibTex] | Links: [request code] Show more

Abstract: Post-processing immunity is a fundamental property of differential privacy: it enables the application of arbitrary data-independent transformations to the results of differentially private outputs without affecting their privacy guarantees. When query outputs must satisfy domain constraints, post-processing can be used to project the privacy-preserving outputs onto the feasible region. Moreover, when the feasible region is convex, a widely adopted class of post-processing steps is also guaranteed to improve accuracy. Post-processing has been applied successfully in many applications including census data-release, energy systems, and mobility. However, its effects on the noise distribution is poorly understood: It is often argued that post-processing may introduce bias and increase variance. This paper takes a first step towards understanding the properties of post-processing. It considers the release of census data and examines, both theoretically and empirically, the behavior of a widely adopted class of post-processing functions.

AAAI

"Differentially Private and Fair Deep Learning: A Lagrangian Dual Approach". Cuong Tran, Ferdinando Fioretto, Pascal Van Hentenryck. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2021.
Downloads: [preprint] [BibTex] | Links: [request code] Show more

Abstract: A critical concern in data-driven decision making is to build models whose out- comes do not discriminate against some demographic groups, including gender, ethnicity, or age. To ensure non-discrimination in learning tasks, knowledge of the sensitive attributes is essential, while, in practice, these attributes may not be avail- able due to legal and ethical requirements. To address this challenge, this paper studies a model that protects the privacy of the individuals’ sensitive information while also allowing it to learn non-discriminatory predictors. The method relies on the notion of differential privacy and the use of Lagrangian duality to design neural networks that can accommodate fairness constraints while guaranteeing the privacy of sensitive attributes. The paper analyses the tension between accuracy, privacy, and fairness and the experimental evaluation illustrates the benefits of the proposed model on several prediction tasks.

CP

"Constrained-based Differential Privacy". (Keynote -- accompanying paper). Ferdinando Fioretto. In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), 2021.
Downloads: TBA [pdf] | Links: [online]

Workshops

TPDP

"Decision Making with Differential Privacy under the Fairness Lens" Cuong Tran, Ferdinando Fioretto. In Theory and Practice of Differential Privacy (TPDP)–at ICML, 2021.
Downloads: [pdf (IJCAI version)] | Links: [online]

PPAI

"Differentially Private and Fair Deep Learning: A Lagrangian Dual Approach”" Cuong Tran, Ferdinando Fioretto, Pascal Van Hentenryck. In AAAI Workshop on Privacy Preserving Artificial Intelligence (PPAI)–at AAAI, 2021.
Downloads: [pdf (AAAI version)] | Links: [online]

OptLMAS

"A Privacy-Preserving and Accountable Multi-agent Learning Framework" Anudit Nagar, Cuong Tran, Ferdinando Fioretto. In International Workshop on Learning and Optimisation in Multi-Agent Systems (OPTLearnMAS)–at AAMAS, 2021
Downloads: [pdf (Arxiv version)] | Links: [online]

Pre-prints

"Towards Understanding the Unreasonable Effectiveness of Learning AC-OPF Solutions". My H. Dinh, Ferdinando Fioretto, Mostafa Mohammadian, Kyri Baker. CoRR abs/2111.11168 [cs.LG], 2021.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: Optimal Power Flow (OPF) is a fundamental problem in power systems. It is computationally challenging and a recent line of research has proposed the use of Deep Neural Networks (DNNs) to find OPF approximations at vastly reduced runtimes when compared to those obtained by classical optimization methods. While these works show encouraging results in terms of accuracy and runtime, little is known on why these models can predict OPF solutions accurately, as well as about their robustness. This paper provides a step forward to address this knowledge gap. The paper connects the volatility of the outputs of the generators to the ability of a learning model to approximate them, it sheds light on the characteristics affecting the DNN models to learn good predictors, and it proposes a new model that exploits the observations made by this paper to produce accurate and robust OPF predictions.

"End-to-end Learning for Fair Ranking Systems". James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck, Ziwei Zhu. CoRR abs/2111.10723 [cs.LG], 2021.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: The learning-to-rank problem aims at ranking items to maximize exposure of those most relevant to a user query. A desirable property of such ranking systems is to guarantee some notion of fairness among specified item groups. While fairness has recently been considered in the context of learning-to-rank systems, current methods cannot provide guarantees on the fairness of the proposed ranking policies. This paper addresses this gap and introduces Smart Predict and Optimize for Fair Ranking (SPOFR), an integrated optimization and learning framework for fairness-constrained learning to rank. The end-to-end SPOFR framework includes a constrained optimization sub-model and produces ranking policies that are guaranteed to satisfy fairness constraints while allowing for fine control of the fairness-utility tradeoff. SPOFR is shown to significantly improve current state-of-the-art fair learning-to-rank systems with respect to established performance metrics.

"Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep Learning Method". James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck. CoRR abs/2110.06365 [cs.LG], 2021.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: The Jobs shop Scheduling Problem (JSP) is a canonical combinatorial optimization problem that is routinely solved for a variety of industrial purposes. It models the optimal scheduling of multiple sequences of tasks, each under a fixed order of operations, in which individual tasks require exclusive access to a predetermined resource for a specified processing time. The problem is NP-hard and computationally challenging even for medium-sized instances. Motivated by the increased stochasticity in production chains, this paper explores a deep learning approach to deliver efficient and accurate approximations to the JSP. In particular, this paper proposes the design of a deep neural network architecture to exploit the problem structure, its integration with Lagrangian duality to capture the problem constraints, and a post-processing optimization to guarantee solution feasibility.The resulting method, called JSP-DNN, is evaluated on hard JSP instances from the JSPLIB benchmark library. Computational results show that JSP-DNN can produce JSP approximations of high quality at negligible computational costs.

"A Fairness Analysis on Private Aggregation of Teacher Ensembles". Cuong Tran, My H. Dinh, Kyle Beiter, Ferdinando Fioretto. CoRR abs/2109.08630 [cs.LG], 2021.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: The Private Aggregation of Teacher Ensembles (PATE) is an important private machine learning framework. It combines multiple learning models used as teachers for a student model that learns to predict an output chosen by noisy voting among the teachers. The resulting model satisfies differential privacy and has been shown effective in learning high-quality private models in semisupervised settings or when one wishes to protect the data labels. This paper asks whether this privacy-preserving framework introduces or exacerbates bias and unfairness and shows that PATE can introduce accuracy disparity among individuals and groups of individuals. The paper analyzes which algorithmic and data properties are responsible for the disproportionate impacts, why these aspects are affecting different groups disproportionately, and proposes guidelines to mitigate these effects. The proposed approach is evaluated on several datasets and settings.

"Differentially Private Deep Learning under the Fairness Lens". Cuong Tran, My H. Dinh, Ferdinando Fioretto. CoRR abs/2106.02674 [cs.LG], 2021.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: Differential Privacy (DP) is an important privacy-enhancing technology for private machine learning systems. It allows to measure and bound the risk associated with an individual participation in a computation. However, it was recently observed that DP learning systems may exacerbate bias and unfairness for different groups of individuals. This paper builds on these important observations and sheds light on the causes of the disparate impacts arising in the problem of differentially private empirical risk minimization. It focuses on the accuracy disparity arising among groups of individuals in two well-studied DP learning methods: output perturbation and differentially private stochastic gradient descent. The paper analyzes which data and model properties are responsible for the disproportionate impacts, why these aspects are affecting different groups disproportionately and proposes guidelines to mitigate these effects. The proposed approach is evaluated on several datasets and settings.

"Learning Hard Optimization Problems: A Data Generation Perspective". James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck. CoRR abs/2106.02601 [cs.LG], 2021.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: Optimization problems are ubiquitous in our societies and are present in almost every segment of the economy. Most of these optimization problems are NP-hard and computationally demanding, often requiring approximate solutions for large-scale instances. Machine learning frameworks that learn to approximate solutions to such hard optimization problems are a potentially promising avenue to address these difficulties, particularly when many closely related problem instances must be solved repeatedly. Supervised learning frameworks can train a model using the outputs of pre-solved instances. However, when the outputs are themselves approximations, when the optimization problem has symmetric solutions, and/or when the solver uses randomization, solutions to closely related instances may exhibit large differences and the learning task can become inherently more difficult. This paper demonstrates this critical challenge, connects the volatility of the training data to the ability of a model to approximate it, and proposes a method for producing (exact or approximate) solutions to optimization problems that are more amenable to supervised learning tasks. The effectiveness of the method is tested on hard non-linear nonconvex and discrete combinatorial problems.

"A Privacy-Preserving and Trustable Multi-agent Learning Framework". Anudit Nagar, Cuong Tran, Ferdinando Fioretto. CoRR abs/2106.01242 [cs.LG], 2021.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: Distributed multi-agent learning enables agents to cooperatively train a model without requiring to share their datasets. While this setting ensures some level of privacy, it has been shown that, even when data is not directly shared, the training process is vulnerable to privacy attacks including data reconstruction and model inversion attacks. Additionally, malicious agents that train on inverted labels or random data, may arbitrarily weaken the accuracy of the global model. This paper addresses these challenges and presents Privacy-preserving and trustable Distributed Learning (PT-DL), a fully decentralized framework that relies on Differential Privacy to guarantee strong privacy protections of the agents' data, and Ethereum smart contracts to ensure trustability. The paper shows that PT-DL is resilient up to a 50% collusion attack, with high probability, in a malicious trust model and the experimental evaluation illustrates the benefits of the proposed model as a privacy-preserving and trustable distributed multi-agent learning system on several classification tasks.

"Decision Making with Differential Privacy under a Fairness Lens". strong>Ferdinando Fioretto, Cuong Tran, Pascal Van Hentenryck. CoRR abs/2105.07513 [cs.AI], 2021.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: Agencies, such as the U.S. Census Bureau, release data sets and statistics about groups of individuals that are used as input to a number of critical decision processes. To conform to privacy and confidentiality requirements, these agencies are often required to release privacy-preserving versions of the data. This paper studies the release of differentially private data sets and analyzes their impact on some critical resource allocation tasks under a fairness perspective. {The paper shows that, when the decisions take as input differentially private data}, the noise added to achieve privacy disproportionately impacts some groups over others. The paper analyzes the reasons for these disproportionate impacts and proposes guidelines to mitigate these effects. The proposed approaches are evaluated on critical decision problems that use differentially private census data.

"End-to-End Constrained Optimization Learning: A Survey". James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck, Bryan Wilder. CoRR abs/2103.16378 [cs.LG], 2021.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: This paper surveys the recent attempts at leveraging machine learning to solve constrained optimization problems. It focuses on surveying the work on integrating combinatorial solvers and optimization methods with machine learning architectures. These approaches hold the promise to develop new hybrid machine learning and optimization methods to predict fast, approximate, solutions to combinatorial problems and to enable structural logical inference. This paper presents a conceptual review of the recent advancements in this emerging area.

"Load Embeddings for Scalable AC-OPF Learning". Terrence W.K. Mak, Ferdinando Fioretto, Pascal Van Hentenryck. CoRR abs/2101.03973 [cs.LG], 2021.
Downloads: [pdf] [BibTex] | Links: [online] [request code] Show more

Abstract: AC Optimal Power Flow (AC-OPF) is a fundamental building block in power system optimization. It is often solved repeatedly, especially in regions with large penetration of renewable generation, to avoid violating operational limits. Recent work has shown that deep learning can be effective in providing highly accurate approximations of AC-OPF. However, deep learning approaches may suffer from scalability issues, especially when applied to large realistic grids. This paper addresses these scalability limitations and proposes a load embedding scheme using a 3-step approach. The first step formulates the load embedding problem as a bilevel optimization model that can be solved using a penalty method. The second step learns the encoding optimization to quickly produce load embeddings for new OPF instances. The third step is a deep learning model that uses load embeddings to produce accurate AC-OPF approximations. The approach is evaluated experimentally on large-scale test cases from the NESTA library. The results demonstrate that the proposed approach produces an order of magnitude improvements in training convergence and prediction accuracy.

2020

Journals

IEEE-TSG

"Differential Privacy for Power Grid Obfuscation". Ferdinando Fioretto, Terrence W.K. Mak, Pascal Van Hentenryck. In IEEE Transactions on Smart Grids, 2020.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: The availability of high-fidelity energy networks brings significant value to academic and commercial research. However, such releases also raise fundamental concerns related to privacy and security as they can reveal sensitive commercial information and expose system vulnerabilities. This paper investigates how to release the data for power networks where the parameters of transmission lines and transformers are obfuscated. It does so by using the framework of Differential Privacy (DP), that provides strong privacy guarantees and has attracted significant attention in recent years. Unfortunately, simple DP mechanisms often result in AC-infeasible networks. To address these concerns, this paper presents a novel differentially private mechanism that guarantees AC-feasibility and largely preserves the fidelity of the obfuscated power network. Experimental results also show that the obfuscation significantly reduces the potential damage of an attack carried by exploiting the released dataset.

IEEE-TSP

"Privacy-Preserving Power System Obfuscation: A Bilevel Optimization Approach". Terrence W.K. Mak, Ferdinando Fioretto, Lyndon Shi, Pascal Van Hentenryck. In IEEE Transactions on Power Systems, 2020.
*2021 TPWRS Best Paper Award*
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: This paper considers the problem of releasing optimal power flow (OPF) test cases that preserve the privacy of customers (loads) using the notion of Differential Privacy. It is motivated by the observation that traditional differential privacy algorithms are not suitable for releasing privacy preserving OPF test cases: The added noise fundamentally changes the nature of the underlying optimization and often leads to test cases with no solutions. To remedy this limitation, the paper introduces the OPF Load Indistinguishability (OLI) problem, which guarantees load privacy while satisfying the OPF constraints and remaining close to the optimal dispatch cost. The paper introduces an exact mechanism, based on bilevel optimization, as well as three mechanisms that approximate the OLI problem accurately. These mechanisms enjoy desirable theoretical properties, and the computational experiments show that they produce orders of magnitude improvements over standard approaches on an extensive collection of test cases.

Conferences

PRIMA

"The Smart Appliance Scheduling Problem: A Bayesian Optimization Approach". Atena Tabakhi, William Yeoh, Ferdinando Fioretto. In International Conference on Principles and Practice of Multi-Agent Systems (PRIMA), 2020.
Downloads: [pdf] [BibTex] | Links: [online] [request code] Show more

Abstract: Daily energy demand peaks induce high green house gas emissions and are deleterious to the power grid operations. The autonomous and coordinated control of smart appliances in residential buildings represents an effective solution to reduce peak demands. This coordination problem is challenging as it involves, not only, scheduling devices to minimize energy peaks, but also to comply with user’ preferences. Prior work assumed these preferences to be fully specified and known a priori, which is, however, unrealistic. To remedy this limitation, this paper introduces a Bayesian optimization approach for smart appliance scheduling when the users’ satisfaction with a schedule must be elicited, and thus considered expensive to evaluate. The paper presents a set of ad-hoc energy-cost based acquisition functions to drive the Bayesian optimization problem to find schedules that maximize the user’s satisfaction. The experimental results demonstrate the effectiveness of the proposed energy-cost based acquisition functions which improve the algorithm’s performance up to 26%.

ECML

"Lagrangian Duality for Constrained Deep Learning". Ferdinando Fioretto, Pascal Van Hentenryck, Terrence W.K. Mak, Cuong Tran, Federico Baldo, Michele Lombardi. In Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD), 2020.
Downloads: [pdf (ArXiv version)] [BibTex] | Links: [online] [GitHub] Show more

Abstract: This paper explores the potential of Lagrangian duality for learning applications that feature complex constraints. Such constraints arise in many science and engineering domains, where the task amounts to learning optimization problems which must be solved repeatedly and include hard physical and operational constraints. The paper also considers applications where the learning task must enforce constraints on the predictor itself, either because they are natural properties of the function to learn or because it is desirable from a societal standpoint to impose them. This paper demonstrates experimentally that Lagrangian duality brings significant benefits for these applications. In energy domains, the combination of Lagrangian duality and deep learning can be used to obtain state of the art results to predict optimal power flows, in energy systems, and optimal compressor settings, in gas networks. In transprecision computing, Lagrangian duality can complement deep learning to impose monotonicity constraints on the predictor without sacrificing accuracy. Finally, Lagrangian duality can be used to enforce fairness constraints on a predictor and obtain state-of-the-art results when minimizing disparate treatments.

IJCAI

"Differential Privacy for Stackelberg Games". Ferdinando Fioretto, Lesia Mitridati, Pascal Van Hentenryck. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2020.
Downloads: [pdf (ArXiv version)] [BibTex] | Links: [online] [request code] Show more

Abstract: This paper introduces a differentially private (DP) mechanism to protect the information exchanged during the coordination of sequential and interdependent markets. This coordination represents a classic Stackelberg game and relies on the exchange of sensitive information between the system agents. The paper is motivated by the observation that the perturbation introduced by traditional DP mechanisms fundamentally changes the underlying optimization problem and even leads to unsatisfiable instances. To remedy such limitation, the paper introduces the Privacy-Preserving Stackelberg Mechanism (PPSM), a framework that enforces the notions of feasibility and fidelity of the privacy-preserving information to the original problem objective. PPSM complies with the notion of differential privacy and ensures that the outcomes of the privacy-preserving coordination mechanism are close-to-optimality for each agent. Experimental results on several gas and electricity market benchmarks based on a real case study demonstrate the effectiveness of the approach.

IJCAI

"OptStream: Releasing Time Series Privately". Ferdinando Fioretto, Pascal Van Hentenryck. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2020.
Downloads: [pdf (journal version)] [BibTex] | Links: [online] [journal-version] [request code] Show more

Abstract: Many applications of machine learning and optimization operate on data streams. While these datasets are fundamental to fuel decision-making algorithms, often they contain sensitive information about individuals, and their usage poses significant privacy risks. Motivated by an application in energy systems, this paper presents OptStream, a novel algorithm for releasing differentially private data streams under the w-event model of privacy. OptStream is a 4-step procedure consisting of sampling, perturbation, reconstruction, and post-processing modules. First, the sampling module selects a small set of points to access in each period of interest. Then, the perturbation module adds noise to the sampled data points to guarantee privacy. Next, the reconstruction module reassembles non-sampled data points from the perturbed sample points. Finally, the post-processing module uses convex optimization over the privacy-preserving output of the previous modules, as well as the privacy-preserving answers of additional queries on the data stream, to improve accuracy by redistributing the added noise. OptStream is evaluated on a test case involving the release of a real data stream from the largest European transmission operator. Experimental results show that OptStream may not only improve the accuracy of state-of-the-art methods by at least one order of magnitude but also supports accurate load forecasting on the privacy-preserving data.

PSCC

"Privacy-Preserving Obfuscation for Distributed Power Systems". Terrence W.K. Mak, Ferdinando Fioretto, Pascal Van Hentenryck. In Proceedings of the Power System Computational Conference (PSCC), 2020.
Downloads: [pdf] [BibTex] | Links: [online] [request code] Show more

Abstract: This paper considers the problem of releasing privacy-preserving load data of a decentralized operated power system. The paper focuses on data used to solve Optimal Power Flow (OPF) problems and proposes a distributed algorithm that complies with the notion of Differential Privacy, a strong privacy framework used to bound the risk of re-identification. The problem is challenging since the application of traditional differential privacy mechanisms to the load data fundamentally changes the nature of the underlying optimization problem and often leads to severe feasibility issues. The proposed differentially private distributed algorithm is based on the Alternating Direction Method of Multipliers (ADMM) and guarantees that the released privacy-preserving data retains high fidelity and satisfies the AC power flow constraints. Experimental results on a variety of OPF benchmarks demonstrate the effectiveness of the approach.

AAAI

"Predicting AC Optimal Power Flows: Combining Deep Learning and Lagrangian Dual Methods". Ferdinando Fioretto, Terrence W.K. Mak, Pascal Van Hentenryck. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2020.
Downloads: [pdf] [BibTex] | Links: [online] [request code] Show more

Abstract: The Optimal Power Flow (OPF) problem is a fundamental building block for the optimization of electrical power systems. It is nonlinear and nonconvex and computes the generator setpoints for power and voltage, given a set of load demands. It is often needed to be solved repeatedly under various conditions, either in real-time or in large-scale studies. This need is further exacerbated by the increasing stochasticity of power systems due to renewable energy sources in front and behind the meter. To address these challenges, this paper presents a deep learning approach to the OPF. The learning model exploits the information available in the prior states of the system (which is commonly available in practical applications), as well as a dual Lagrangian method to satisfy the physical and engineering constraints present in the OPF. The proposed model is evaluated on a large collection of realistic power systems. The experimental results show that its predictions are highly accurate with average errors as low as 0.2%. Additionally, the proposed approach is shown to improve the accuracy of widely adopted OPF linear DC approximation by at least two orders of magnitude.

Pre-prints

"Bias and Variance of Post-processing in Differential Privacy". Keyu Zhu, Pascal Van Hentenryck, Ferdinando Fioretto. CoRR abs/2010.04327 [cs.LG], 2020.
Downloads: [pdf] [BibTex] | Links: [request code] Show more

Abstract: Post-processing immunity is a fundamental property of differential privacy: it enables the application of arbitrary data-independent transformations to the results of differentially private outputs without affecting their privacy guarantees. When query outputs must satisfy domain constraints, post-processing can be used to project the privacy-preserving outputs onto the feasible region. Moreover, when the feasible region is convex, a widely adopted class of post-processing steps is also guaranteed to improve accuracy. Post-processing has been applied successfully in many applications including census data-release, energy systems, and mobility. However, its effects on the noise distribution is poorly understood: It is often argued that post-processing may introduce bias and increase variance. This paper takes a first step towards understanding the properties of post-processing. It considers the release of census data and examines, both theoretically and empirically, the behavior of a widely adopted class of post-processing functions.

"Differentially Private and Fair Deep Learning: A Lagrangian Dual Approach". Cuong Tran, Ferdinando Fioretto, Pascal Van Hentenryck. CoRR abs/2009.12562 [cs.LG], 2020.
Downloads: [pdf] [BibTex] | Links: [request code] Show more

Abstract: A critical concern in data-driven decision making is to build models whose out- comes do not discriminate against some demographic groups, including gender, ethnicity, or age. To ensure non-discrimination in learning tasks, knowledge of the sensitive attributes is essential, while, in practice, these attributes may not be avail- able due to legal and ethical requirements. To address this challenge, this paper studies a model that protects the privacy of the individuals’ sensitive information while also allowing it to learn non-discriminatory predictors. The method relies on the notion of differential privacy and the use of Lagrangian duality to design neural networks that can accommodate fairness constraints while guaranteeing the privacy of sensitive attributes. The paper analyses the tension between accuracy, privacy, and fairness and the experimental evaluation illustrates the benefits of the proposed model on several prediction tasks.

"High-Fidelity Machine Learning Approximations of Large-Scale Optimal Power Flow". Minas Chatzos, Ferdinando Fioretto, Terrence W.K. Mak, Pascal Van Hentenryck. CoRR abs/2006.16356 [eess.SP/cs.LG], 2020.
Downloads: [pdf] [BibTex] | Links: [online] [request code] Show more

Abstract: The AC Optimal Power Flow (AC-OPF) is a key building block in many power system applications. It determines generator setpoints at minimal cost that meet the power demands while satisfying the underlying physical and operational constraints. It is non-convex and NP-hard, and computationally challenging for large-scale power systems. Motivated by the increased stochasticity in generation schedules and increasing penetration of renewable sources, this paper explores a deep learning approach to deliver highly efficient and accurate approximations to the AC-OPF. In particular, the paper proposes an integration of deep neural networks and Lagrangian duality to capture the physical and operational constraints. The resulting model, called OPF-DNN, is evaluated on real case studies from the French transmission system, with up to 3,400 buses and 4,500 lines. Computational results show that OPF-DNN produces highly accurate AC-OPF approximations whose costs are within 0.01% of optimality. OPF-DNN generates, in milliseconds, solutions that capture the problem constraints with high fidelity.

"Differential Privacy of Hierarchical Census Data: An Optimization Approach". Ferdinando Fioretto, Pascal Van Hentenryck, Keyu Zhu. CoRR abs/2006.15673 [CS.DB], 2020.
Downloads: [pdf] [BibTex] | Links: [online] [request code] Show more

Abstract: This paper is motivated by applications of a Census Bureau interested in releasing aggregate socio-economic data about a large population without revealing sensitive information about any individual. The released information can be the number of individuals living alone, the number of cars they own, or their salary brackets. Recent events have identified some of the privacy challenges faced by these organizations. To address them, this paper presents a novel differential-privacy mechanism for releasing hierarchical counts of individuals. The counts are reported at multiple granularities (e.g., the national, state, and county levels) and must be consistent across all levels. The core of the mechanism is an optimization model that redistributes the noise introduced to achieve differential privacy in order to meet the consistency constraints between the hierarchical levels. The key technical contribution of the paper shows that this optimization problem can be solved in polynomial time by exploiting the structure of its cost functions. Experimental results on very large, real datasets show that the proposed mechanism provides improvements of up to two orders of magnitude in terms of computational efficiency and accuracy with respect to other state-of-the-art techniques.

"Differentially Private Convex Optimization with Feasibility Guarantees". Vladimir Dvorkin, Ferdinando Fioretto, Pascal Van Hentenryck, Jalal Kazempour, Pierre Pinson. CoRR abs/2006.12338 [CS.CR], 2020.
Downloads: [pdf] [BibTex] | Links: [online] [request code] Show more

Abstract: This paper develops a novel differentially private framework to solve convex optimization problems with sensitive optimization data and complex physical or operational constraints. Unlike standard noise-additive algorithms, that act primarily on the problem data, objective or solution, and disregard the problem constraints, this framework requires the optimization variables to be a function of the noise and exploits a chance-constrained problem reformulation with formal feasibility guarantees. The noise is calibrated to provide differential privacy for identity and linear queries on the optimization solution. For many applications, including resource allocation problems, the proposed framework provides a trade-off between the expected optimality loss and the variance of optimization results.

"Differentially Private Optimal Power Flow for Distribution Grids". Vladimir Dvorkin, Ferdinando Fioretto, Pascal Van Hentenryck, Jalal Kazempour, Pierre Pinson. CoRR abs/2004.03921 [math.OC], 2020.
Downloads: [pdf] [BibTex] | Links: [online] [request code] Show more

Abstract: Although distribution grid customers are obliged to share their consumption data with distribution system operators (DSOs), a possible leakage of this data is often disregarded in operational routines of DSOs. This paper introduces a privacy-preserving optimal power flow (OPF) mechanism for distribution grids that secures customer privacy from unauthorised access to OPF solutions, e.g., current and voltage measurements. The mechanism is based on the framework of differential privacy that allows to control the participation risks of individuals in a dataset by applying a carefully calibrated noise to the output of a computation. Unlike existing private mechanisms, this mechanism does not apply the noise to the optimization parameters or its result. Instead, it optimizes OPF variables as affine functions of the random noise, which weakens the correlation between the grid loads and OPF variables. To ensure feasibility of the randomized OPF solution, the mechanism makes use of chance constraints enforced on the grid limits. The mechanism is further extended to control the optimality loss induced by the random noise, as well as the variance of OPF variables. The paper shows that the differentially private OPF solution does not leak customer loads up to specified parameters.

"Differential Privacy for Stackelberg Games". Ferdinando Fioretto, Lesia Mitridati, Pascal Van Hentenryck. CoRR abs/2002.00944 [math.OC/cs.CR], 2020.
Downloads: [pdf] [BibTex] | Links: [online] [request code] Show more

Abstract: This paper introduces a differentially private (DP) mechanism to protect the information exchanged during the coordination of sequential and interdependent markets. This coordination represents a classic Stackelberg game and relies on the exchange of sensitive information between the system agents. The paper is motivated by the observation that the perturbation introduced by traditional DP mechanisms fundamentally changes the underlying optimization problem and even leads to unsatisfiable instances. To remedy such limitation, the paper introduces the Privacy-Preserving Stackelberg Mechanism (PPSM), a framework that enforces the notions of feasibility and fidelity of the privacy-preserving information to the original problem objective. PPSM complies with the notion of differential privacy and ensures that the outcomes of the privacy-preserving coordination mechanism are close-to-optimality for each agent. Experimental results on several gas and electricity market benchmarks based on a real case study demonstrate the effectiveness of the approach.

"A Lagrangian Dual Framework for Deep Neural Networks with Constraints". Ferdinando Fioretto, Terrence W.K. Mak, Federico Baldo, Michele Lombardi, Pascal Van Hentenryck. CoRR abs/2001.09394 [cs.LG/stat.ML], 2020.
Downloads: [pdf] [BibTex] | Links: [online] [request code] Show more

Abstract: A variety of computationally challenging constrained optimization problems in several engineering disciplines are solved repeatedly under different scenarios. In many cases, they would benefit from fast and accurate approximations, either to support real-time operations or large-scale simulation studies. This paper aims at exploring how to leverage the substantial data being accumulated by repeatedly solving instances of these applications over time. It introduces a deep learning model that exploits Lagrangian duality to encourage the satisfaction of hard constraints. The proposed method is evaluated on a collection of realistic energy networks, by enforcing non-discriminatory decisions on a variety of datasets, and a transprecision computing application. The results illustrate the effectiveness of the proposed method that dramatically decreases constraint violations by the predictors and, in some applications, increases the prediction accuracy.

"Bilevel Optimization for Differentially Private Optimization". Ferdinando Fioretto, Terrence W.K. Mak, Pascal Van Hentenryck. CoRR abs/2001.09508 [math.OC/cs.AI,cs.CR], 2020.
Downloads: [pdf] [BibTex] | Links: [online] [request code] Show more

Abstract: This paper studies how to apply differential privacy to constrained optimization problems whose inputs are sensitive. This task raises significant challenges since random perturbations of the input data often render the constrained optimization problem infeasible or change significantly the nature of its optimal solutions. To address this difficulty, this paper proposes a bilevel optimization model that can be used as a post-processing step: It redistributes the noise introduced by a differentially private mechanism optimally while restoring feasibility and near-optimality. The paper shows that, under a natural assumption, this bilevel model can be solved efficiently for real-life large-scale nonlinear nonconvex optimization problems with sensitive customer data. The experimental results demonstrate the accuracy of the privacy-preserving mechanism and showcase significant benefits compared to standard approaches.

2019

Journals

JAIR

"OptStream: Releasing Time Series Privately". Ferdinando Fioretto, Pascal Van Hentenryck. In Journal of Artificial Intelligence Research (JAIR), 2019.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: Many applications of machine learning and optimization operate on data streams. While these datasets are fundamental to fuel decision-making algorithms, often they contain sensitive information about individuals, and their usage poses significant privacy risks. Motivated by an application in energy systems, this paper presents OptStream, a novel algorithm for releasing differentially private data streams under the w-event model of privacy. OptStream is a 4-step procedure consisting of sampling, perturbation, reconstruction, and post-processing modules. First, the sampling module selects a small set of points to access in each period of interest. Then, the perturbation module adds noise to the sampled data points to guarantee privacy. Next, the reconstruction module reassembles non-sampled data points from the perturbed sample points. Finally, the post-processing module uses convex optimization over the privacy-preserving output of the previous modules, as well as the privacy-preserving answers of additional queries on the data stream, to improve accuracy by redistributing the added noise. OptStream is evaluated on a test case involving the release of a real data stream from the largest European transmission operator. Experimental results show that OptStream may not only improve the accuracy of state-of-the-art methods by at least one order of magnitude but also supports accurate load forecasting on the privacy-preserving data.

IA

"Distributed multi-agent optimization for smart grids and home automation". Ferdinando Fioretto, Agostino Dovier, Enrico Pontelli. In Intelligenza Artificiale (IA), 2019.
Downloads: [pdf] [BibTex] | Links: [online] Show more

Abstract: Distributed Constraint Optimization Problems (DCOPs) have emerged as one of the prominent multi-agent architectures to govern the agents’ autonomous behavior in a cooperative multi-agent system (MAS) where several agents coordinate with each other to optimize a global cost function taking into account their local preferences. They represent a powerful approach to the description and resolution of many practical problems. However, typical MAS applications are characterized by complex dynamics and interactions among a large number of entities, which translate into hard combinatorial problems, posing significant challenges from a computational and coordination standpoints. This paper reviews two methods to promote a hierarchical parallel model for solving DCOPs, with the aim of improving the performance of the DCOP algorithm. The first is a Multi-Variable Agent (MVA) DCOP decomposition, which exploits co-locality of an agent’s variables allowing the adoption of efficient centralized techniques to solve the subproblem of an agent. The second is the use of Graphics Processing Units (GPUs) to speed up a class of DCOP algorithms. Finally, exploiting these hierarchical parallel model, the paper presents two critical applications of DCOPs for demand response (DR) program in smart grids. The Multi-agent Economic Dispatch with Demand Response (EDDR), which provides an integrated approach to the economic dispatch and the DR model for power systems, and the Smart Home Device Scheduling (SHDS) problem, that formalizes the device scheduling and coordination problem across multiple smart homes to reduce energy peaks.

Conferences

CP

"Differential Privacy of Hierarchical Census Data: An Optimization Approach". Ferdinando Fioretto, Pascal Van Hentenryck. In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), 2019.
*Invited to Constraint journal - selected paper*
Downloads: [pdf] [slides] [BibTex] | Links: [online] [request code] Show more

Abstract: This paper is motivated by applications of a Census Bureau interested in releasing aggregate socio-economic data about a large population without revealing sensitive information. The released information can be the number of individuals living alone, the number of cars they own, or their salary brackets. Recent events have identified some of the privacy challenges faced by these organizations. To address them, this paper presents a novel differential-privacy mechanism for releasing hierarchical counts of individuals satisfying a given property. The counts are reported at multiple granularities (e.g., the national, state, and county levels) and must be consistent across levels. The core of the mechanism is an optimization model that redistributes the noise introduced to attain privacy in order to meet the consistency constraints between the hierarchical levels. The key technical contribution of the paper shows that this optimization problem can be solved in polynomial time by exploiting the structure of its cost functions. Experimental results on very large, real datasets show that the proposed mechanism provides improvements up to two orders of magnitude in terms of computational efficiency and accuracy with respect to other state-of-the-art techniques.

IJCAI

"Privacy-Preserving Obfuscation of Critical Infrastructure Networks". Ferdinando Fioretto, Terrence W.K. Mak, Pascal Van Hentenryck. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2019.
Downloads: [pdf] [slides] [BibTex] | Links: [online] [request code] Show more

Abstract: The paper studies how to release data about a critical infrastructure network (e.g., the power network or a transportation network) without disclosing sensitive information that can be exploited by malevolent agents, while preserving the realism of the network. It proposes a novel obfuscation mechanism that combines several privacy-preserving building blocks with a bi-level optimization model to significantly improve accuracy. The obfuscation is evaluated for both realism and privacy properties on real energy and transportation networks. Experimental results show the obfuscation mechanism substantially reduces the potential damage of an attack exploiting the released data to harm the real network.

AAMAS

""Privacy-Preserving Federated Data Sharing". Ferdinando Fioretto, Pascal Van Hentenryck. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2019.
Downloads: [pdf] [slides] [BibTex] | Links: [online] Show more

Abstract: Consider a set of agents with sensitive datasets who are interested in the same prediction task and would like to share their datasets without revealing private information. For instance, the agents may be hospitals with their own historical databases and the task may be the diagnosis of a rare form of disease. This paper investigates whether sharing privacy-preserving versions of these datasets may improve the agent predictions. It proposes a Multi-agent Privacy-preserving Data Sharing (MPDS) protocol that each agent can run locally and produce a privacy-preserving version of its original dataset. The MPDS protocol is evaluated on several standard prediction tasks and the experimental results demonstrate the potential of sharing privacy-preserving datasets to produce accurate predictors.

Workshops

OptMAS

"A large neighboring search schema for multi-agent optimization". Khoi Hoang, Ferdinando Fioretto, William Yeoh, Enrico Pontelli, Roie Zivan. In the International Workshop on Optimisation in Multi-Agent Systems (OPTMAS), 2019.
Downloads: [pdf] [BibTex] | Links: [online] [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.

Pre-prints

"Privacy-Preserving Obfuscation for Distributed Power Systems". CoRR abs/1910.04250 [math.OC], 2019. Terrence W.K. Mak, Ferdinando Fioretto, Pascal Van Hentenryck.
Downloads: [pdf] [BibTex] | Links: [online] [request code] Show more

Abstract: This paper considers the problem of releasing privacy-preserving load data of a decentralized operated power system. The paper focuses on data used to solve Optimal Power Flow (OPF) problems and proposes a distributed algorithm that complies with the notion of Differential Privacy, a strong privacy framework used to bound the risk of re-identification. The problem is challenging since the application of traditional differential privacy mechanisms to the load data fundamentally changes the nature of the underlying optimization problem and often leads to severe feasibility issues. The proposed differentially private distributed algorithm is based on the Alternating Direction Method of Multipliers (ADMM) and guarantees that the released privacy-preserving data retains high fidelity and satisfies the AC power flow constraints. Experimental results on a variety of OPF benchmarks demonstrate the effectiveness of the approach.

"Predicting AC Optimal Power Flows: Combining Deep Learning and Lagrangian Dual Methods". CoRR abs/1909.10461 [eess.SP], 2019. Ferdinando Fioretto, Terrence W.K. Mak, Pascal Van Hentenryck.
Downloads: [pdf] [BibTex] | Links: [online] [request code] Show more

Abstract: The Optimal Power Flow (OPF) problem is a fundamental building block for the optimization of electrical power systems. It is nonlinear and nonconvex and computes the generator setpoints for power and voltage, given a set of load demands. It is often needed to be solved repeatedly under various conditions, either in real-time or in large-scale studies. This need is further exacerbated by the increasing stochasticity of power systems due to renewable energy sources in front and behind the meter. To address these challenges, this paper presents a deep learning approach to the OPF. The learning model exploits the information available in the prior states of the system (which is commonly available in practical applications), as well as a dual Lagrangian method to satisfy the physical and engineering constraints present in the OPF. The proposed model is evaluated on a large collection of realistic power systems. The experimental results show that its predictions are highly accurate with average errors as low as 0.2%. Additionally, the proposed approach is shown to improve the accuracy of widely adopted OPF linear DC approximation by at least two orders of magnitude.

"Privacy-Preserving Obfuscation of Critical Infrastructure Networks". CoRR abs/1905.09778 [cs.CR], 2019. Ferdinando Fioretto, Terrence W.K. Mak, Pascal Van Hentenryck.
Downloads: [pdf] [BibTex] | Links: [online] [request code] Show more

Abstract: The paper studies how to release data about a critical infrastructure network (e.g., the power network or a transportation network) without disclosing sensitive information that can be exploited by malevolent agents, while preserving the realism of the network. It proposes a novel obfuscation mechanism that combines several privacy-preserving building blocks with a bi-level optimization model to significantly improve accuracy. The obfuscation is evaluated for both realism and privacy properties on real energy and transportation networks. Experimental results show the obfuscation mechanism substantially reduces the potential damage of an attack exploiting the released data to harm the real network.

"Differential Privacy for Power Grid Obfuscation". CoRR abs/1901.06949 [cs.AI], 2019. Ferdinando Fioretto, Terrence W.K. Mak, Pascal Van Hentenryck.
Downloads: [pdf] [BibTex] | Links: [online] [request code] Show more

Abstract: The availability of high-fidelity energy networks brings significant value to academic and commercial research. However, such releases also raise fundamental concerns related to privacy and security as they can reveal sensitive commercial information and expose system vulnerabilities. This paper investigates how to release power networks where the parameters of transmission lines and transformers are obfuscated. It does so by using the framework of Differential Privacy (DP), that provides strong privacy guarantees and has attracted significant attention in recent years. Unfortunately, simple DP mechanisms often result in AC-infeasible networks. To address these concerns, this paper presents a novel differential privacy mechanism that guarantees AC-feasibility and largely preserves the fidelity of the obfuscated network. Experimental results also show that the obfuscation significantly reduces the potential damage of an attacker exploiting the release of the dataset.

2018

Journals

JAIR

"Distributed Constraint Optimization Problems and Applications: A Survey". Ferdinando Fioretto, William Yeoh, Enrico Pontelli. In Journal of Artificial Intelligence Research (JAIR), 2018.
Downloads: [pdf] [BibTex] | Links: [online] 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.

AI-MATTER

"AI buzzwords explained: distributed constraint optimization problems". Ferdinando Fioretto, William Yeoh. In AI Matters, 2018.
Downloads: [pdf] [BibTex] | Links: [online] 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.

Constraints

"Accelerating Exact and Approximate Inference for (Distributed) Discrete Optimization with GPUs". Ferdinando Fioretto, Enrico Pontelli, William Yeoh, Rina Dechter. In Constraints, 2018.
Downloads: [pdf] [BibTex] | Links: [online] [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

PRIMA

" Solving Multiagent Constraint Optimization Problems on the Constraint Composite Graph". Ferdinando Fioretto, Hong Xu, Sven Koenig, TK Satish Kumar. In International Conference on Principles and Practice of Multi-Agent Systems (PRIMA), 2018.
Downloads: [pdf] [BibTex] | Links: [online] [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.

CP

"A large neighboring search schema for multi-agent optimization". Khoi Hoang, Ferdinando Fioretto, William Yeoh, Enrico Pontelli, Roie Zivan. In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), 2018.
Downloads: [pdf] [BibTex] | Links: [online] [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.

AAMAS

"Constrained-based Differential Privacy for Private Mobility". Ferdinando Fioretto, Chansoo Lee, Pascal Van Hentenryck. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2018.
Downloads: [pdf] [slides] [BibTex] | Links: [online] [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.

CPAIOR

"Constrained-based Differential Privacy: Releasing Optimal Power Flow Benchmarks Privately". Ferdinando Fioretto, Pascal Van Hentenryck. In Proceedings of the International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR), 2018.
Downloads: [pdf] [slides] [BibTex] | Links: [online] [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.

ISIAM

"Constraint Composite Graph-Based Lifted Message Passing for Distributed Constraint Optimization Problems". Ferdinando Fioretto, Hong Xu, Sven Koenig, TK Satish Kumar. In International Symposium on Artificial Intelligence and Mathematics (ISAIM), 2018.
Downloads: [pdf] [slides] [BibTex] | Links: [online] [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

OptMAS

" Solving Multiagent Constraint Optimization Problems on the Constraint Composite Graph". Ferdinando Fioretto, Hong Xu, Sven Koenig, TK Satish Kumar. In Proceedings of the International Workshop on Optimisation in Multi-Agent Systems (OPTMAS), 2018.
Downloads: [pdf] [slides] [BibTex] | Links: [online] [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

"Differential Private Stream Processing of Energy Consumption". Ferdinando Fioretto, Pascal Van Hentenryck. CoRR abs/1808.01949, 2018.
Downloads: [pdf] [BibTex] | Links: [online] 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

CP

"Preference Elicitation for DCOPs". Atena M. Tabakhi, Tiep Le, Ferdinando Fioretto, William Yeoh. In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), 2017.
Downloads: [pdf] [BibTex] | Links: [online] [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.

AAMAS

"Infinite-Horizon Proactive Dynamic DCOPs". Khoi D. Hoang, Ping Hou, Ferdinando Fioretto, William Yeoh, Roie Zivan, Makoto Yokoo. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2017.
Downloads: [pdf] [slides] [BibTex] | Links: [online] [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.

AAMAS

"A Multiagent System Approach to Scheduling Devices in Smart Homes". Ferdinando Fioretto, William Yeoh, Enrico Pontelli. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2017.
Downloads: [pdf] [slides] [BibTex] | Links: [online] [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.

AAMAS

"A Distributed Constraint Optimization (DCOP) Approach to the Economic Dispatch with Demand Response". Ferdinando Fioretto, William Yeoh, Enrico Pontelli, Ye Ma, Satishkumar Ranade. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2017.
Downloads: [pdf] [slides] [BibTex] | Links: [online] [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

AAMAS

"A Realistic Dataset for the Smart Home Device Scheduling Problem for DCOPs". William Kluegel, Muhammad Aamir Iqbal, Ferdinando Fioretto, William Yeoh, Enrico Pontelli. In Proceedings of the International Workshop on Optimisation in Multi-Agent Systems (OPTMAS), 2017.
*Most visionary paper award*
Downloads: [pdf] [BibTex] | Links: [online] [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.

AMEC

"Investigation of Learning Strategies for the SPOT Broker in Power TAC". Porag Chowdhury, Russell Y. Folk, Ferdinando Fioretto, Christopher Kiekintveld, William Yeoh. In Agent-Mediated Electronic Commerce. Designing Trading Strategies and Mechanisms for Electronic Markets, 2017.
Downloads: [pdf] [BibTex] | Links: [online] [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

OptMAS

"A Realistic Dataset for the Smart Home Device Scheduling Problem for DCOPs". William Kluegel, Muhammad Aamir Iqbal, Ferdinando Fioretto, William Yeoh, Enrico Pontelli. In Proceedings of the International Workshop on Optimisation in Multi-Agent Systems (OPTMAS), 2017.
Downloads: [pdf] [slides] [BibTex] | Links: [online] [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.

AISGSB

"A Multiagent System Approach to Scheduling Devices in Smart Homes". Ferdinando Fioretto, William Yeoh, Enrico Pontelli. In Proceedings of the International Workshop on Artificial Intelligence for Smart Grids and Smart Buildings (AISGSB), 2017.
Downloads: [pdf] [slides] [BibTex] | Links: [online] [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

"A Realistic Dataset for the Smart Home Device Scheduling Problem for DCOPs". William Kluegel, Muhammad Aamir Iqbal, Ferdinando Fioretto, William Yeoh, Enrico Pontelli. CoRR abs/1702.06970, 2017.
Downloads: [pdf] [BibTex] | Links: [online] [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.

"Solving DCOPs with Distributed Large Neighborhood Search". Ferdinando Fioretto, Agostino Dovier, Enrico Pontelli, William Yeoh, Roie Zivan. CoRR abs/1702.06915, 2017.
Downloads: [pdf] [BibTex] | Links: [online] [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

AAMAS

"Proactive Dynamic Distributed Constraint Optimization". Khoi Hoang, Ferdinando Fioretto, Ping Hou, Makoto Yokoo, William Yeoh, Roie Zivan. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2016.
Downloads: [pdf] [slides] [BibTex] | Links: [online] [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.

AAMAS

"ER-DCOPs: A Framework for DCOPs with Uncertainty in Constraint Utilities". Tiep Le, Ferdinando Fioretto, William Yeoh, Tran Cao Son, and Enrico Pontelli. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2016.
Downloads: [pdf] [slides] [BibTex] | Links: [online] [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.

AAAI

"Multi-Variable Agent Decomposition for DCOPs". Ferdinando Fioretto, William Yeoh, Enrico Pontelli. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2016.
Downloads: [pdf] [slides] [BibTex] | Links: [online] [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.

CP

"A Dynamic Programming-based MCMC Framework for Solving DCOPs with GPUs". Ferdinando Fioretto, William Yeoh, Enrico Pontelli. In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), 2016.
Downloads: [pdf] [slides] [BibTex] | Links: [online] [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

MPREF

"A Preliminary Study on Preference Elicitation in DCOPs for Scheduling Devices in Smart Buildings". Atena M. Tabakhi, Ferdinando Fioretto, William Yeoh. In the 10th Workshop on Advances in Preference Handling (MPREF), 2016.
Downloads: [pdf] [slides] [BibTex] | Links: [online] [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.

TADA

"Investigation of Learning Strategies for the SPOT Broker in Power TAC". Porag Chowdhury, Russell Y. Folk, Ferdinando Fioretto, Christopher Kiekintveld, William Yeoh. In the International Workshop on Agent Mediated Electronic Commerce and Trading Agents Design and Analysis (AMEC/TADA), 2016.
Downloads: [pdf] [BibTex] | Links: [online] [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.

AISGSB

"Proactive Dynamic DCOPs". Khoi Hoang, Ferdinando Fioretto, Ping Hou, Makoto Yokoo, William Yeoh, Roie Zivan. In AAAI Workshop on AI for Smart Grids and Smart Buildings (AISGSB), 2016.
Downloads: [pdf] [slides] [BibTex] | Links: [online] [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

"Distributed Constraint Optimization Problems and Applications: A Survey". Ferdinando Fioretto, William Yeoh, Enrico Pontelli. In arXiv:1602.06347v1[cs.AI], 2016.
Downloads: [pdf] [BibTex] | Links: [online] 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.

"Accelerating Exact and Approximate Inference for (Distributed) Discrete Optimization with GPUs". Ferdinando Fioretto, William Yeoh, Enrico Pontelli, Rina Dechter. In arXiv:1608.05288[cs.AI], 2016.
Downloads: [pdf] [BibTex] | Links: [online] [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

TOMACS

"Constrained Community-based Gene Regulatory Network Inference". Ferdinando Fioretto, Agostino Dovier and Enrico Pontelli. In ACM Transactions on Modeling and Computer Simulation (TOMACS), 2015.
Downloads: [pdf] [appendix] [BibTex] | Links: [online] [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

CP

"Exploiting GPUs in Solving (Distributed) Constraint Optimization Problems with Dynamic Programming". Ferdinando Fioretto, Tiep Le, William Yeoh, Enrico Pontelli and Tran Cao Son. In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), 2015.
Downloads: [pdf] [slides] [BibTex] | Links: [online] [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.

AAMAS

"Multi-Variable Agents Decomposition for DCOPs to Exploit Multi-Level Parallelism". Ferdinando Fioretto, William Yeoh and Enrico Pontelli. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2015.
Downloads: [pdf] [BibTex] | Links: [online] [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.

AAMAS

"Large Neighborhood Search with Quality Guarantees for Distributed Constraint Optimization Problems". Ferdinando Fioretto, Federico Campeotto, Agostino Dovier, William Yeoh and Enrico Pontelli. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2015.
Downloads: [pdf] [BibTex] | Links: [online] 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.

AAAI

"Exploiting the Structure of Distributed Constraint Optimization Problems". Ferdinando Fioretto. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), AAAI/SIGAI Doctoral Consortium, 2015.
Downloads: [pdf] [BibTex] | Links: [online] 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.

AAMAS

"Exploiting the Structure of Distributed Constraint Optimization Problems". Ferdinando Fioretto. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Doctoral Mentoring Program, 2015.
Downloads: [pdf] [BibTex] | Links: [online] 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

OptMAS

"Improving DPOP with Branch Consistency for Solving Distributed Constraint Optimization Problems". Ferdinando Fioretto, Tiep Le, William Yeoh, Enrico Pontelli and Tran Cao Son. In Workshop on Optimisation in Multi-Agent Systems (OPTMAS), 2015.
Downloads: [pdf] [BibTex] | Links: [online] 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.

OptMAS

"Large Neighborhood Search with Quality Guarantees for Distributed Constraint Optimization Problems". Ferdinando Fioretto, Federico Campeotto, Agostino Dovier, William Yeoh and Enrico Pontelli. In Workshop on Optimisation in Multi-Agent Systems (OPTMAS), 2015.
Downloads: [pdf] [BibTex] | Links: [online] 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

CP

"Improving DPOP with Branch Consistency for Solving Distributed Constraint Optimization Problems". Ferdinando Fioretto, Tiep Le, William Yeoh, Enrico Pontelli and Tran Cao Son. In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), 2014.
Downloads: [pdf] [slides] [BibTex] | Links: [online] [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.

ECAI

"A GPU Implementation of Large Neighborhood Search for Solving Constraint Optimization Problems". Federico Campeotto, Agostino Dovier, Ferdinando Fioretto and Enrico Pontelli. In Proceedings of the European Conference of Artificial Intelligence (ECAI), 2014.
Downloads: [pdf] [slides] [BibTex] | Links: [online] [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.

AAMAS

"GD-Gibbs: A GPU-based Sampling Algorithm for Solving Distributed Constraint Optimization Problems". Ferdinando Fioretto, Federico Campeotto, Luca Da Rin Fioretto, William Yeoh, Enrico Pontelli. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2014.
Downloads: [pdf] [BibTex] | Links: [online] [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.

PADL

"Exploring the Use of GPUs in Constraint Solving". Federico Campeotto, Alessandro Dal Palu', Agostino Dovier, Ferdinando Fioretto, Enrico Pontelli. In Proceedings of the Practical Aspects of Declarative Languages (PADL), 2014.
Downloads: [pdf] [slides] [BibTex] | Links: [online] [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

WCB

"Experimenting with FIASCO for protein structure prediction". Federico Campeotto, Alessandro Dal Palu', Agostino Dovier, Ferdinando Fioretto, Enrico Pontelli. In Workshop on Constraint-Based Methods for Bioinformatics (WCB), 2014
Downloads: [pdf] [BibTex] | Links: [online] [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.

Par-Search-Opt

"Towards a complete constraint solver on GPU". Federico Campeotto, Alessandro Dal Palu', Agostino Dovier, Ferdinando Fioretto, Enrico Pontelli. In Workshop on Parallel Methods for Search & Optimization (ParSearchOpt), 2014.
Downloads: [pdf] [BibTex] | Links: [online] [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

JAIR

"A Constraint Solver for Flexible Protein Models". Federico Campeotto, Alessandro Dal Palu', Agostino Dovier, Ferdinando Fioretto, Enrico Pontelli. In Journal of Artificial Intelligence Research (JAIR), 2013.
Downloads: [pdf] [BibTex] | Links: [online] 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

CMSB


"Constraint Programming in Community-based Gene Regulatory Network Inference". Ferdinando Fioretto, Enrico Pontelli. In Proceedings of the Computational Methods in System Biology (CMSB), 2013.
*Best student paper award*
Downloads: [pdf] [slides] [BibTex] | Links: [online] [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.

Workshops

WCB

"Constraint Programming in Community-based Gene Regulatory Network Inference". Ferdinando Fioretto, Enrico Pontelli. In Workshop on Constraint-Based-Methods for Bioinformatics (WCB), 2013.
Downloads: [pdf] [BibTex] | Links: [online] [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

CP

"A Filtering Technique for Fragment Assembly-based Proteins Loop Modeling with Constraints". Federico Campeotto, Alessandro Dal Palu', Agostino Dovier, Ferdinando Fioretto and Enrico Pontelli. In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), 2012.
Downloads: [pdf] [BibTex] | Links: [online] [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

WCB

"Protein Loop Modelling via Constraints and Fragment Assembly". Federico Campeotto, Alessandro Dal Palu', Agostino Dovier, Ferdinando Fioretto and Enrico Pontelli. In Workshop on Constraint-Based-Methods for Bioinformatics (WCB), 2012.
Downloads: [pdf] [BibTex] | Links: [online] [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.