1. Distributed Mixed-Integer Linear Programming via Cut Generation and Constraint Exchange.
- Author
-
Testa, Andrea, Rucco, Alessandro, and Notarstefano, Giuseppe
- Subjects
ALGORITHMS ,ASSIGNMENT problems (Programming) ,PEER-to-peer architecture (Computer networks) ,DISTRIBUTED algorithms ,EXCHANGE ,APPROXIMATION algorithms ,CYBER physical systems - Abstract
Many problems of interest for cyber-physical network systems can be formulated as mixed-integer linear programs in which the constraints are distributed among the agents. In this paper, we propose a distributed algorithmic framework to solve this class of optimization problems in a peer-to-peer network with no coordinator and with limited computation and communication capabilities. At each communication round, agents locally solve a small linear program, generate suitable cutting planes, and communicate a fixed number of active constraints. Within the distributed framework, we first propose an algorithm that, under the assumption of integer-valued optimal cost, guarantees finite-time convergence to an optimal solution. Second, we propose an algorithm for general problems that provides a suboptimal solution up to a given tolerance in a finite number of communication rounds. Both algorithms work under asynchronous, directed, unreliable networks. Finally, through numerical computations, we analyze the algorithm scalability in terms of the network size. Moreover, for a multi-agent multi-task assignment problem, we show, consistently with the theory, its robustness to packet loss. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF