Approximate solution to decomposable MILPs with coupling constraints : a numerical study

Motivated by the need of an efficient use of limited resources in social systems, we address the problem of solving a mixed integer linear resource sharing in a large scale multi-agent system. We perform a numerical study of an algorithm that has been recently proposed in the literature for computing a feasible solution by decomposing the MILP in smaller ones while tightening the coupling constraints due to resource sharing. The algorithm rests on dual decomposition and can be implemented in a decentralized scheme. It guarantees the feasibility in finite-time and provides better performance guarantees than an alternative method in the literature.

Considerando la necessità di un uso efficace di risorse limitate nei social systems, affrontiamo il problema della soluzione di una mixed integer linear resource sharing in un sistema multi-agente su larga scala. Eseguiamo uno studio numerico di un algoritmo che è stato recentemente proposto nella letteratura per calcolare una soluzione fattibile scomponendo il MILP in parti più piccole, stringendo i vincoli di accoppiamento a causa della resource sharing. L'algoritmo si basa sulla dual decomposition e può essere implementato in uno schema decentralizzato. Garantisce la fattibilità in finite-time e fornisce migliori garanzie sulle prestazioni rispetto ad un metodo alternativo in letteratura.