论文标题
大型米尔普斯的分布式原始分解
Distributed Primal Decomposition for Large-Scale MILPs
论文作者
论文摘要
本文介绍了在多个控制应用中产生的分布式混合构成线性编程（MILP）设置。网络的代理旨在最大程度地减少受单个约束和涉及所有决策变量的线性耦合约束的局部线性成本函数的总和。考虑的设置的一个关键，具有挑战性的功能是，决策变量的某些组件必须假设整数值。索问题的MILP是NP-HARD，NONCOVEX和大规模的。此外，由于耦合约束，在分布式框架中出现了一些其他挑战，因此具有保证次优界的可行解决方案引起了人们的关注。我们提出了一种基于原始分解方法和耦合约束的适当拧紧的完全分布算法。保证该算法在有限的时间内提供可行的解决方案。此外，为计算的解决方案建立了渐近和有限的次优界。 Montecarlo模拟强调了该算法实现的极低次级次数界限。
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.
