.png){kind=icon}
.png){kind=icon}
Return
Distributed Primal Decomposition for Large-Scale MILPs
.png){kind=icon}
OA
AI
DOI：10.1109/TAC.2021.3057061.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Couplings
Resource management
Distributed algorithms
Heuristic algorithms
Linear programming
Approximation algorithms
Task analysis
Constraint-coupled optimization
distributed optimization
mixed-integer linear programming
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
7
Papers:
1.3W
Citations:
6.7W