In this paper, we deal with large-scale Mixed Integer Linear Programs (MILPs) with coupling constraints that must be solved by processors over networks. We propose a finite-time distributed algorithm that computes a feasible solution with suboptimality bounds over asynchronous and unreliable networks. As shown in a previous work of ours, a feasible solution of the considered MILP can be computed by resorting to a primal decomposition of a suitable problem convexification. In this paper we reformulate the primal decomposition resource allocation problem as a linear program with an exponential number of unknown constraints. Then we design a distributed protocol that allows agents to compute an optimal allocation by generating and exchanging only few of the unknown constraints. Each allocation is iteratively used to compute a candidate feasible solution of the original MILP. We establish finite-time convergence of the proposed algorithm under very general assumptions on the communication network. A numerical example corroborates the theoretical results.

Primal decomposition and constraint generation for asynchronous distributed mixed-integer linear programming

Camisa A.
;
Notarstefano G.
2019

Abstract

In this paper, we deal with large-scale Mixed Integer Linear Programs (MILPs) with coupling constraints that must be solved by processors over networks. We propose a finite-time distributed algorithm that computes a feasible solution with suboptimality bounds over asynchronous and unreliable networks. As shown in a previous work of ours, a feasible solution of the considered MILP can be computed by resorting to a primal decomposition of a suitable problem convexification. In this paper we reformulate the primal decomposition resource allocation problem as a linear program with an exponential number of unknown constraints. Then we design a distributed protocol that allows agents to compute an optimal allocation by generating and exchanging only few of the unknown constraints. Each allocation is iteratively used to compute a candidate feasible solution of the original MILP. We establish finite-time convergence of the proposed algorithm under very general assumptions on the communication network. A numerical example corroborates the theoretical results.
2019 18TH IEEE European Control Conference (ECC)
77
82
Camisa A.; Notarstefano G.
File in questo prodotto:
File Dimensione Formato  
2019ecc_camisa_Primal Decomposition and Constraint Generation for Asynchronous Distributed Mixed-Integer Linear Programming.pdf

accesso riservato

Tipo: Versione (PDF) editoriale
Licenza: Licenza per accesso riservato
Dimensione 399.25 kB
Formato Adobe PDF
399.25 kB Adobe PDF   Visualizza/Apri   Contatta l'autore
6pages_primal_decomp_milp_ecc.pdf

accesso aperto

Tipo: Postprint
Licenza: Licenza per accesso libero gratuito
Dimensione 820.17 kB
Formato Adobe PDF
820.17 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/701955
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact