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 algorithm to solve this class of optimization problems in a peer-To-peer network with no coordinator and with limited computation and communication capabilities. In the proposed algorithm, at each communication round, agents solve locally a small LP, generate suitable cutting planes, namely intersection cuts and cost-based cuts, and communicate a fixed number of active constraints, i.e., a candidate optimal basis. We prove that, if the cost is integer, the algorithm converges to the lexicographically minimal optimal solution in a finite number of communication rounds. Finally, through numerical computations, we analyze the algorithm convergence as a function of the network size.
Testa, A., Rucco, A., Notarstefano, G. (2017). A finite-Time cutting plane algorithm for distributed mixed integer linear programming. Institute of Electrical and Electronics Engineers Inc. [10.1109/CDC.2017.8264225].
A finite-Time cutting plane algorithm for distributed mixed integer linear programming
Testa, Andrea;Notarstefano, Giuseppe
2017
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 algorithm to solve this class of optimization problems in a peer-To-peer network with no coordinator and with limited computation and communication capabilities. In the proposed algorithm, at each communication round, agents solve locally a small LP, generate suitable cutting planes, namely intersection cuts and cost-based cuts, and communicate a fixed number of active constraints, i.e., a candidate optimal basis. We prove that, if the cost is integer, the algorithm converges to the lexicographically minimal optimal solution in a finite number of communication rounds. Finally, through numerical computations, we analyze the algorithm convergence as a function of the network size.File | Dimensione | Formato | |
---|---|---|---|
678766_disclaimer.pdf
accesso aperto
Tipo:
Postprint
Licenza:
Licenza per accesso libero gratuito
Dimensione
868.56 kB
Formato
Adobe PDF
|
868.56 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.