Uncertain multi-agent MILPs: A data-driven decentralized solution with probabilistic feasibility guarantees

Alessandro Falsone, Federico Molinari, Maria Prandini
Proceedings of the 2nd Conference on Learning for Dynamics and Control, PMLR 120:1000-1009, 2020.

Abstract

We consider uncertain multi-agent optimization problems that are formulated as Mixed Integer Linear Programs (MILPs) with an almost separable structure. Specifically, agents have their own cost function and constraints, and need to set their local decision vector subject to coupling constraints due to shared resources. The problem is affected by uncertainty that is only known from data. A scalable decentralized approach to tackle the combinatorial complexity of constraint-coupled multi-agent MILPs has been recently introduced in the literature. However, the presence of uncertainty has been addressed only in a distributed convex optimization framework, i.e., without integer decision variables. This work fills in this gap by proposing a data-driven decentralized scheme to determine a solution with probabilistic feasibility guarantees that depend on the size of the data-set.

Cite this Paper

BibTeX
@InProceedings{pmlr-v120-falsone20a, title = {Uncertain multi-agent MILPs: A data-driven decentralized solution with probabilistic feasibility guarantees}, author = {Falsone, Alessandro and Molinari, Federico and Prandini, Maria}, booktitle = {Proceedings of the 2nd Conference on Learning for Dynamics and Control}, pages = {1000--1009}, year = {2020}, editor = {Bayen, Alexandre M. and Jadbabaie, Ali and Pappas, George and Parrilo, Pablo A. and Recht, Benjamin and Tomlin, Claire and Zeilinger, Melanie}, volume = {120}, series = {Proceedings of Machine Learning Research}, month = {10--11 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v120/falsone20a/falsone20a.pdf}, url = {https://proceedings.mlr.press/v120/falsone20a.html}, abstract = {We consider uncertain multi-agent optimization problems that are formulated as Mixed Integer Linear Programs (MILPs) with an almost separable structure. Specifically, agents have their own cost function and constraints, and need to set their local decision vector subject to coupling constraints due to shared resources. The problem is affected by uncertainty that is only known from data. A scalable decentralized approach to tackle the combinatorial complexity of constraint-coupled multi-agent MILPs has been recently introduced in the literature. However, the presence of uncertainty has been addressed only in a distributed convex optimization framework, i.e., without integer decision variables. This work fills in this gap by proposing a data-driven decentralized scheme to determine a solution with probabilistic feasibility guarantees that depend on the size of the data-set.} }
Endnote
%0 Conference Paper %T Uncertain multi-agent MILPs: A data-driven decentralized solution with probabilistic feasibility guarantees %A Alessandro Falsone %A Federico Molinari %A Maria Prandini %B Proceedings of the 2nd Conference on Learning for Dynamics and Control %C Proceedings of Machine Learning Research %D 2020 %E Alexandre M. Bayen %E Ali Jadbabaie %E George Pappas %E Pablo A. Parrilo %E Benjamin Recht %E Claire Tomlin %E Melanie Zeilinger %F pmlr-v120-falsone20a %I PMLR %P 1000--1009 %U https://proceedings.mlr.press/v120/falsone20a.html %V 120 %X We consider uncertain multi-agent optimization problems that are formulated as Mixed Integer Linear Programs (MILPs) with an almost separable structure. Specifically, agents have their own cost function and constraints, and need to set their local decision vector subject to coupling constraints due to shared resources. The problem is affected by uncertainty that is only known from data. A scalable decentralized approach to tackle the combinatorial complexity of constraint-coupled multi-agent MILPs has been recently introduced in the literature. However, the presence of uncertainty has been addressed only in a distributed convex optimization framework, i.e., without integer decision variables. This work fills in this gap by proposing a data-driven decentralized scheme to determine a solution with probabilistic feasibility guarantees that depend on the size of the data-set.
APA
Falsone, A., Molinari, F. & Prandini, M.. (2020). Uncertain multi-agent MILPs: A data-driven decentralized solution with probabilistic feasibility guarantees. Proceedings of the 2nd Conference on Learning for Dynamics and Control, in Proceedings of Machine Learning Research 120:1000-1009 Available from https://proceedings.mlr.press/v120/falsone20a.html.

Related Material