Back to Search
Start Over
Distributed Primal Decomposition for Large-Scale MILPs.
- Source :
-
IEEE Transactions on Automatic Control . Jan2022, Vol. 67 Issue 1, p413-420. 8p. - Publication Year :
- 2022
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *LINEAR programming
*MONTE Carlo method
*DISTRIBUTED algorithms
*COST functions
Subjects
Details
- Language :
- English
- ISSN :
- 00189286
- Volume :
- 67
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Automatic Control
- Publication Type :
- Periodical
- Accession number :
- 154764234
- Full Text :
- https://doi.org/10.1109/TAC.2021.3057061