Distributed Primal Decomposition for Large-Scale MILPs

• 成果类型: Article
• 署名作者: Camisa, Andrea; Notarnicola, Ivano; Notarstefano, Giuseppe
• 署名单位: University of Bologna
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2021.3057061
• 发表日期: 2022
• 页码: 413-420
• 关键词: Couplings; resource management; Distributed algorithms; Heuristic algorithms; linear programming; Approximation algorithms; Task analysis; Constraint-coupled optimization; distributed optimization; mixed-integer linear programming

摘要

This article deals with a distributed Mixed-Integer Linear Programming (MILP) setup 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 setup 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. Monte Carlo simulations highlight the extremely low suboptimality bounds achieved by the algorithm.