Hyper-Graph Partitioning for a Multi-Agent Reformulation of Large-Scale MILPs
| Autor: | Maria Prandini, Lucrezia Manieri, Alessandro Falsone |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
Scheme (programming language)
Structure (mathematical logic) Mathematical optimization Control and Optimization Computer science Graph partition Resolution (logic) Matrix (mathematics) computational methods Control and Systems Engineering Large-scale systems Focus (optics) computer optimization Sparse matrix computer.programming_language Integer (computer science) |
| Popis: | This letter addresses the challenge of solving large-scale Mixed Integer Linear Programs (MILPs). A resolution scheme is proposed for the class of MILPs with a hidden constraint-coupled multi-agent structure. In particular, we focus on the problem of disclosing such a structure to then apply a computationally efficient decentralized optimization algorithm recently proposed in the literature. The multi-agent reformulation problem consists in manipulating the matrix defining the linear constraints of the MILP so as to put it in a singly-bordered block-angular form, where the blocks define local constraints and decision variables of the agents, whereas the border defines the coupling constraints. We translate the matrix reformulation problem into a hyper-graph partitioning problem and introduce a novel algorithm which accounts for the specific requirements on the singly-bordered block-angular form to best take advantage of the decentralized optimization approach. Numerical results show the effectiveness of the proposed hyper-graph partitioning algorithm. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|