Integrating Artificial Intelligence and Mixed Integer Linear Programming: Explainable Graph-Based Instance Space Analysis in Air Transportation
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909938149752832 |
|---|---|
| author | Rosa, Artur Guerra Loureiro, Felipe Tavares da Silva, Marcus Vinicius Santos Barros, Andréia Elizabeth Silva Reis, Silvia Araújo dos Celestino, Victor Rafael Rezende |
| author_facet | Rosa, Artur Guerra Loureiro, Felipe Tavares da Silva, Marcus Vinicius Santos Barros, Andréia Elizabeth Silva Reis, Silvia Araújo dos Celestino, Victor Rafael Rezende |
| contents | This paper analyzes the integration of artificial intelligence (AI) with mixed integer linear programming (MILP) to address complex optimization challenges in air transportation with explainability. The study aims to validate the use of Graph Neural Networks (GNNs) for extracting structural feature embeddings from MILP instances, using the air05 crew scheduling problem. The MILP instance was transformed into a heterogeneous bipartite graph to model relationships between variables and constraints. Two neural architectures, Graph Convolutional Networks (GCN) and Graph Attention Networks (GAT) were trained to generate node embeddings. These representations were evaluated using Instance Space Analysis (ISA) through linear (PCA) and non-linear (UMAP, t-SNE) dimensionality reduction techniques. Analysis revealed that PCA failed to distinguish cluster structures, necessitating non-linear reductions to visualize the embedding topology. The GCN architecture demonstrated superior performance, capturing global topology with well-defined clusters for both variables and constraints. In contrast, the GAT model failed to organize the constraint space. The findings confirm that simpler graph architectures can effectively map the sparse topology of aviation logistics problems without manual feature engineering, contributing to explainability of instance complexity. This structural awareness provides a validated foundation for developing future Learning to Optimize (L2O) agents capable of improving solver performance in safety-critical environments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_01698 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Integrating Artificial Intelligence and Mixed Integer Linear Programming: Explainable Graph-Based Instance Space Analysis in Air Transportation Rosa, Artur Guerra Loureiro, Felipe Tavares da Silva, Marcus Vinicius Santos Barros, Andréia Elizabeth Silva Reis, Silvia Araújo dos Celestino, Victor Rafael Rezende Computational Engineering, Finance, and Science Neural and Evolutionary Computing Optimization and Control 90C35 G.1.6; I.2.6; J.2 This paper analyzes the integration of artificial intelligence (AI) with mixed integer linear programming (MILP) to address complex optimization challenges in air transportation with explainability. The study aims to validate the use of Graph Neural Networks (GNNs) for extracting structural feature embeddings from MILP instances, using the air05 crew scheduling problem. The MILP instance was transformed into a heterogeneous bipartite graph to model relationships between variables and constraints. Two neural architectures, Graph Convolutional Networks (GCN) and Graph Attention Networks (GAT) were trained to generate node embeddings. These representations were evaluated using Instance Space Analysis (ISA) through linear (PCA) and non-linear (UMAP, t-SNE) dimensionality reduction techniques. Analysis revealed that PCA failed to distinguish cluster structures, necessitating non-linear reductions to visualize the embedding topology. The GCN architecture demonstrated superior performance, capturing global topology with well-defined clusters for both variables and constraints. In contrast, the GAT model failed to organize the constraint space. The findings confirm that simpler graph architectures can effectively map the sparse topology of aviation logistics problems without manual feature engineering, contributing to explainability of instance complexity. This structural awareness provides a validated foundation for developing future Learning to Optimize (L2O) agents capable of improving solver performance in safety-critical environments. |
| title | Integrating Artificial Intelligence and Mixed Integer Linear Programming: Explainable Graph-Based Instance Space Analysis in Air Transportation |
| topic | Computational Engineering, Finance, and Science Neural and Evolutionary Computing Optimization and Control 90C35 G.1.6; I.2.6; J.2 |
| url | https://arxiv.org/abs/2512.01698 |