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.

A finite-Time cutting plane algorithm for distributed mixed integer linear programming / Testa, Andrea; Rucco, Alessandro; Notarstefano, Giuseppe. - ELETTRONICO. - 2018-:(2017), pp. 3847-3852. (Intervento presentato al convegno 56th IEEE Annual Conference on Decision and Control, CDC 2017 tenutosi a Melbourne, VIC, Australia nel 12-15 Dec. 2017) [10.1109/CDC.2017.8264225].

### A finite-Time cutting plane algorithm for distributed mixed integer linear programming

#### 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.
##### Scheda breve Scheda completa Scheda completa (DC)
2017
2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017
3847
3852
A finite-Time cutting plane algorithm for distributed mixed integer linear programming / Testa, Andrea; Rucco, Alessandro; Notarstefano, Giuseppe. - ELETTRONICO. - 2018-:(2017), pp. 3847-3852. (Intervento presentato al convegno 56th IEEE Annual Conference on Decision and Control, CDC 2017 tenutosi a Melbourne, VIC, Australia nel 12-15 Dec. 2017) [10.1109/CDC.2017.8264225].
Testa, Andrea; Rucco, Alessandro; Notarstefano, Giuseppe
File in questo prodotto:
File
678766_disclaimer.pdf

accesso aperto

Tipo: Postprint
Licenza: Licenza per accesso libero gratuito
Dimensione 868.56 kB

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11585/678766`
• ND
• 12
• 0