标题： 大规模MILPs的分布式原始分解 显示英文标题

标题： Distributed Primal Decomposition for Large-Scale MILPs

摘要： 本文讨论了一种在多个控制应用中出现的分布式混合整数线性规划（MILP）设置。网络中的代理旨在最小化局部线性成本函数的总和，同时满足个体约束和一个涉及所有决策变量的线性耦合约束。所考虑设置的一个关键且具有挑战性的特征是，某些决策变量的组成部分必须取整数值。所研究的MILPs是NP难的、非凸的且大规模的。此外，在分布式框架中由于耦合约束的存在，会出现多个额外的挑战，因此具有保证次优界限的可行解是值得关注的。我们提出了一种完全分布式的算法，该算法基于一种原始分解方法和对耦合约束的适当收紧。该算法保证在有限时间内提供可行解。此外，建立了计算解的渐近和有限时间次优界限。蒙特卡洛仿真表明，该算法实现了极低的次优界限。 显示英文摘要

摘要： This paper deals with a distributed Mixed-Integer Linear Programming (MILP) set-up arising in several control applications. Agents of a network aim to minimize the sum of local linear cost functions subject to both individual constraints and a linear coupling constraint involving all the decision variables. A key, challenging feature of the considered set-up is that some components of the decision variables must assume integer values. The addressed MILPs are NP-hard, nonconvex and large-scale. Moreover, several additional challenges arise in a distributed framework due to the coupling constraint, so that feasible solutions with guaranteed suboptimality bounds are of interest. We propose a fully distributed algorithm based on a primal decomposition approach and an appropriate tightening of the coupling constraint. The algorithm is guaranteed to provide feasible solutions in finite time. Moreover, asymptotic and finite-time suboptimality bounds are established for the computed solution. Montecarlo simulations highlight the extremely low suboptimality bounds achieved by the algorithm.