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.
2017
2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017
3847
3852
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].
Testa, Andrea; Rucco, Alessandro; Notarstefano, Giuseppe
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/678766
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 0
social impact