Distributed and Asynchronous Coordination of a Mixed-Integer Linear System via Surrogate Lagrangian Relaxation
Distributed and Asynchronous Coordination of a Mixed-Integer Linear System via Surrogate Lagrangian Relaxation
复制标题
DOI：
10.1109/tase.2020.2998048
复制
发表时间：
2021-07-01
影响因子：
5.6
通讯作者：
Luh, Peter B.
中科院分区：
文献类型：
--
作者：
Bragin, Mikhail A.;Yan, Bing;Luh, Peter B.
随着允许通信和本地计算的物联网的出现以及工业 4.0 的愿景，可预见的转变是从集中式系统规划和操作向具有交互组件和子系统的分散式转变，例如自我优化工厂。在本文中，开发了一种新的“基于价格”的分解和协调方法，以异步方式有效地协调由分布式子系统（例如机器和零件）组成的系统，这些子系统由混合整数线性规划（MILP）公式描述。该新颖方法是一种双重方法，通过根据“供给和需求”的经济原理更新拉格朗日乘数来执行协调。为了确保该方法内的低通信要求，“协调器”和子系统之间的交换仅限于由协调器广播的“价格”（拉格朗日乘数）以及在协调器处发送的子系统解决方案。然而，异步协调可能会导致收敛困难，因为由于通信和求解时间的不确定性，子系统解到达协调器的顺序并未预先定义。在有限通信和求解时间的现实假设下，我们的方法的收敛性通过创新性扩展李亚普诺夫稳定性理论得到证明。通过模拟对广义分配问题进行数值测试表明，该方法收敛速度快，并提供接近最优的结果，为未来工厂的自优化铺平了道路。包含随附的 CPLEX 代码和数据。从业者注意事项 - 鉴于可预见的向自我优化工厂的转变，其中机器和零件具有通信和计算能力，开发了一种新颖的“基于价格”的分布式异步方法来协调由分布式子系统组成的系统。在有限通信和求解时间的现实假设下，方法的收敛性得到了证明。通过模拟对广义分配问题进行数值测试表明，该方法收敛速度快，并提供接近最优的结果，为未来工厂的自优化铺平了道路。包含随附的 CPLEX 代码和数据。
With the emergence of the Internet of Things that allows communications and local computations and with the vision of Industry 4.0, a foreseeable transition is from centralized system planning and operation toward decentralization with interacting components and subsystems, e.g., self-optimizing factories. In this article, a new "price-based" decomposition and coordination methodology is developed to efficiently coordinate a system consisting of distributed subsystems such as machines and parts, which are described by mixed-integer linear programming (MILP) formulations, in an asynchronous way. The novel method is a dual approach, whereby the coordination is performed by updating Lagrangian multipliers based on economic principles of "supply and demand." To ensure low communication requirements within the method, exchanges between the "coordinator" and subsystems are limited to "prices" (Lagrangian multipliers) broadcast by the coordinator and to subsystem solutions sent at the coordinator. Asynchronous coordination, however, may lead to convergence difficulties since the order in which subsystem solutions arrive at the coordinator is not predefined as a result of uncertainties in communication and solving times. Under realistic assumptions of finite communication and solve times, the convergence of our method is proven by innovatively extending the Lyapunov stability theory. Numerical testing of generalized assignment problems through simulation demonstrates that the method converges fast and provides near-optimal results, paving the way for self-optimizing factories in the future. Accompanying CPLEX codes and data are included. Note to Practitioners-In view of a foreseeable transition toward self-optimizing factories whereby machines and parts have communication and computational capabilities, a novel "price-based" distributed and asynchronous method to coordinate a system consisting of distributed subsystems is developed. Under realistic assumptions of finite communication and solve times, method convergence is proven. Numerical testing of generalized assignment problems through simulation demonstrates that the method converges fast and provides near-optimal results, paving the way for self-optimizing factories in the future. Accompanying CPLEX codes and data are included.