Deep-learning-based primal heuristics for MILP: supervised solution-prediction models

Abstract

A programação linear inteira mista (\emph{Mixed-Integer Linear Programming}, MILP) é crucial no auxílio à tomada de decisão em cenários complexos devido à sua capacidade de modelar problemas de otimização combinatória e aproximar dinâmicas não-lineares. Heurísticas baseadas em modelos de aprendizagem profunda (\emph{deep learning}) oferecem uma solução promissora para resolver problemas MILP eficientemente. Tendo foco em modelos supervisionados para predição de soluções, esta dissertação investiga o projeto, o treinamento e a integração de modelos de aprendizagem profunda em heurísticas primais, usando o agendamento \emph{offline} de tarefas em nanossatélites (\emph{Offline Nanosatellite Task Scheduling}, ONTS) como um caso de teste. As principais conclusões deste trabalho se referem à arquitetura dos modelos, às funções de perda, à aquisição de dados e à meta-heurísticas. Além disso, as heurísticas baseadas em aprendizagem propostas para o ONTS foram capazes de reduzir, em média, 35\% do tempo necessário para encontrar uma solução factível, e um ganho médio de 43\% na qualidade das soluções encontradas. Esses resultados destacam o potencial da aprendizagem profunda em gerar heurísticas adaptáveis e eficientes para problemas de otimização, direcionando pesquisas futuras para a investigação da capacidade de generalização de redes neurais baseadas em grafos e de técnicas para geração de dados sintéticos.

Abstract: Mixed-Integer Linear Programming (MILP) is a crucial tool for solving complex decision-making problems due to its ability to model combinatorial optimization tasks and arbitrarily approximate nonlinear features. Deep-learning-based primal heuristics offer a promising solution for efficiently addressing MILP problems. Focusing on supervised solution prediction models, this dissertation investigates the design, training, and integration of deep learning models into primal heuristics using the Offline Nanosatellite Task Scheduling (ONTS) problem as a test case. Key findings are drawn on model architecture, loss functions, data acquisition, and meta-heuristic. On top of that, the proposed learning-based heuristic approaches were able to provide, on one hand, a 35\% reduction in the expected time to find a feasible solution to the ONTS problem, and on another, a 43\% expected gain in the normalized quality of the heuristic solutions. These results highlight the potential of deep learning approaches to enhance the adaptability and efficiency of optimization solutions, with future research needed to further explore Graph Neural Network (GNN) generalization and improve data generation techniques.