Integrating Artificial Intelligence and Mixed Integer Linear Programming: Explainable Graph-Based Instance Space Analysis in Air Transportation

• URL: http://arxiv.org/abs/2512.01698v1
• Date: Mon, 01 Dec 2025 14:03:29 GMT
• Title: Integrating Artificial Intelligence and Mixed Integer Linear Programming: Explainable Graph-Based Instance Space Analysis in Air Transportation
• Authors: Artur Guerra Rosa, Felipe Tavares Loureiro, Marcus Vinicius Santos da Silva, Andréia Elizabeth Silva Barros, Silvia Araújo dos Reis, Victor Rafael Rezende Celestino,
• Abstract summary: 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.<n>The study aims to validate the use of Graph Neural Networks (GNNs) for extracting structural feature embeddings from MILP instances.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Beyond Pixels: Vector-to-Graph Transformation for Reliable Schematic Auditing [34.54168175788343]
  We propose a Vector-to-Graph (V2G) pipeline that converts CAD diagrams into property graphs where nodes represent components and edges encode connectivity.<n>On a diagnostic benchmark of electrical compliance checks, V2G yields large accuracy gains across all error categories, while leading MLLMs remain near chance level.
  arXiv  Detail & Related papers  (2026-02-12T07:50:49Z)
• GADPN: Graph Adaptive Denoising and Perturbation Networks via Singular Value Decomposition [6.24191713518868]
  GADPN is a graph structure learning framework that adaptively refines graph topology via low-rank denoising and generalized structural perturbation.<n>It achieves state-of-the-art performance while significantly improving efficiency.<n>It shows particularly strong gains on challenging disassortative graphs, validating its ability to robustly learn enhanced graph structures.
  arXiv  Detail & Related papers  (2026-01-13T05:25:32Z)
• Dual-Kernel Graph Community Contrastive Learning [14.92920991249099]
  Graph Contrastive Learning (GCL) has emerged as a powerful paradigm for training Graph Neural Networks (GNNs)<n>We propose an efficient GCL framework that transforms the input graph into a compact network of interconnected node sets.<n>Our method outperforms state-of-the-art GCL baselines in both effectiveness and scalability.
  arXiv  Detail & Related papers  (2025-11-11T14:20:39Z)
• Efficient Environmental Claim Detection with Hyperbolic Graph Neural Networks [1.7259898169307608]
  We explore Graph Neural Networks (GNNs) and Hyperbolic Graph Neural Networks (HGNNs) as lightweight yet effective alternatives to transformer-based models.<n>Our results show that our graph-based models, particularly HGNNs in the poincar'e space (P-HGNNs), achieve performance superior to the state-of-the-art on environmental claim detection.
  arXiv  Detail & Related papers  (2025-02-19T11:04:59Z)
• LASE: Learned Adjacency Spectral Embeddings [9.227991604045416]
  We learn nodal Adjacency Spectral Embeddings (ASE) from graph inputs.<n>LASE is interpretable, parameter efficient, robust to inputs with unobserved edges.<n>LASE layers combine Graph Convolutional Network (GCN) and fully-connected Graph Attention Network (GAT) modules.
  arXiv  Detail & Related papers  (2024-12-23T17:35:19Z)
• Graph Structure Refinement with Energy-based Contrastive Learning [56.957793274727514]
  We introduce an unsupervised method based on a joint of generative training and discriminative training to learn graph structure and representation.<n>We propose an Energy-based Contrastive Learning (ECL) guided Graph Structure Refinement (GSR) framework, denoted as ECL-GSR.<n>ECL-GSR achieves faster training with fewer samples and memories against the leading baseline, highlighting its simplicity and efficiency in downstream tasks.
  arXiv  Detail & Related papers  (2024-12-20T04:05:09Z)
• Learning to Model Graph Structural Information on MLPs via Graph Structure Self-Contrasting [50.181824673039436]
  We propose a Graph Structure Self-Contrasting (GSSC) framework that learns graph structural information without message passing. The proposed framework is based purely on Multi-Layer Perceptrons (MLPs), where the structural information is only implicitly incorporated as prior knowledge. It first applies structural sparsification to remove potentially uninformative or noisy edges in the neighborhood, and then performs structural self-contrasting in the sparsified neighborhood to learn robust node representations.
  arXiv  Detail & Related papers  (2024-09-09T12:56:02Z)
• Counterfactual Intervention Feature Transfer for Visible-Infrared Person Re-identification [69.45543438974963]
  We find graph-based methods in the visible-infrared person re-identification task (VI-ReID) suffer from bad generalization because of two issues. The well-trained input features weaken the learning of graph topology, making it not generalized enough during the inference process. We propose a Counterfactual Intervention Feature Transfer (CIFT) method to tackle these problems.
  arXiv  Detail & Related papers  (2022-08-01T16:15:31Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  We propose a graph gradual pruning framework termed CGP to dynamically prune GNNs. Unlike LTH-based methods, the proposed CGP approach requires no re-training, which significantly reduces the computation costs. Our proposed strategy greatly improves both training and inference efficiency while matching or even exceeding the accuracy of existing methods.
  arXiv  Detail & Related papers  (2022-07-18T14:23:31Z)
• Towards Unsupervised Deep Graph Structure Learning [67.58720734177325]
  We propose an unsupervised graph structure learning paradigm, where the learned graph topology is optimized by data itself without any external guidance. Specifically, we generate a learning target from the original data as an "anchor graph", and use a contrastive loss to maximize the agreement between the anchor graph and the learned graph.
  arXiv  Detail & Related papers  (2022-01-17T11:57:29Z)
• Neural combinatorial optimization beyond the TSP: Existing architectures under-represent graph structure [9.673093148930876]
  We analyze how and whether recent neural architectures can be applied to graph problems of practical importance. We show that augmenting the structural representation of problems with Distance is a promising step towards the still-ambitious goal of learning multi-purpose autonomous solvers.
  arXiv  Detail & Related papers  (2022-01-03T14:14:28Z)
• Structural Landmarking and Interaction Modelling: on Resolution Dilemmas in Graph Classification [50.83222170524406]
  We study the intrinsic difficulty in graph classification under the unified concept of resolution dilemmas'' We propose SLIM'', an inductive neural network model for Structural Landmarking and Interaction Modelling.
  arXiv  Detail & Related papers  (2020-06-29T01:01:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.