Research

Abordagens Integradas para Problemas de Floresta e Roteamento: Métodos Híbridos, Decomposições e Aprendizado de Máquina

Este projeto de pesquisa insere-se na área de Otimização Combinatória e Pesquisa Operacional, com foco em duas classes de problemas NP-difíceis de grande relevância teórica e aplicada.

A primeira classe é o Problema da Floresta Geradora Restrita de Custo Mínimo (PFR), que consiste em: dado um grafo não direcionado com pesos nas arestas e um inteiro \(k >= 2\), encontrar uma floresta geradora (conjunto de árvores que cobre todos os vértices) tal que cada componente conexa tenha pelo menos \(k\) vértices, minimizando o custo total. O PFR modela problemas reais como: alocação de centros de comunicação em redes, microagregação de dados estatísticos (preservação de privacidade), distritalização política, conexão de sensores em redes inteligentes e particionamento de grandes áreas em sub-regiões autossuficientes. Embora existam formulações exatas e heurísticas, há uma lacuna na integração sistemática entre métodos exatos e decomposições, especialmente para instâncias reais com centenas ou milhares de vértices.

A segunda classe é o Problema do Caixeiro Alugador (PCA), uma generalização do clássico Problema do Caixeiro Viajante (TSP). No PCA, múltiplos veículos (cada um com sua própria matriz de custos operacionais entre cidades) podem ser alugados e devolvidos em diferentes vértices, com taxas de retorno específicas. O objetivo é encontrar um ciclo Hamiltoniano que inicia e termina no vértice de origem, podendo trocar de veículo durante o percurso, minimizando a soma dos custos operacionais e das taxas de retorno. Aplicações diretas incluem: logística de transporte com frota heterogênea (locação de caminhões, carros, trens), turismo, manufatura flexível e planejamento de rotas em plataformas de compartilhamento de veículos. A literatura recente concentra-se predominantemente em heurísticas, negligenciando a sinergia entre métodos exatos (branch-and-cut), decomposições (geração de colunas, lagrangiana) e aprendizado de máquina.

Keywords: Otimização Combinatória, Pesquisa Operacional, Métodos Híbridos, Floresta Geradora Restrita, Caixeiro Viajante

Key Objectives:

• Desenvolver métodos híbridos (exatos, heurísticos, decomposições e ML) para resolver instâncias reais do PFR e PCA, superando o estado da arte em qualidade de solução e escalabilidade.
• Estender as formulações inteiras existentes para novas variantes do PFR (k-floresta com restrições adicionais de capacidade) e PCA (múltiplos depósitos, janelas de tempo).
• Provar novas desigualdades válidas e relações de dominância poliédrica.
• Implementar e comparar métodos de decomposição: relaxação lagrangiana com relax-and-cut, geração de colunas (branch-and-price) e decomposição de Benders.
• Desenvolver metaheurísticas (GRASP reativo, algoritmo genético híbrido, ILS) com uso de limites duais para guiar a busca.
• Investigar o uso de aprendizado de máquina (redes neurais gráficas ou reinforcement learning) para escolha de variáveis de branching em branch-and-cut.
• Integrar todos os componentes em um framework modular (redução, metaheurística, decomposição, branch-and-cut com ML, pós-processamento).
• Realizar experimentos computacionais extensivos com instâncias clássicas e reais, comparando com o estado da arte.

Combinatorial Optimisation

My work in combinatorial optimisation focuses on solving discrete decision-making problems that are central to logistics, telecommunications, and manufacturing. I develop both exact and heuristic methods to tackle NP-hard challenges, with a strong emphasis on scalability and real-world applicability. This includes:

• Graph & Network Algorithms: Efficient solutions for routing, flows, and network design problems
• Scheduling & Sequencing: Optimising job-shop, project, and workforce scheduling under constraints
• Decomposition Techniques: Exploiting problem structure via branch-and-bound, dynamic programming, and Lagrangian relaxation
• Hybrid Heuristics: Combining metaheuristics (e.g., genetic algorithms, simulated annealing) with exact methods for large-scale instances

Operations Research

My research in operations research takes a holistic, systems-level view of complex organisational challenges. I build decision-support models that balance competing objectives, manage trade-offs, and improve overall system performance across sectors such as transport, healthcare, and energy. This includes:

• Supply Chain Optimisation: Designing resilient, cost-efficient networks for production and distribution
• Logistics & Transportation: Vehicle routing, fleet management, and last-mile delivery optimisation
• Healthcare Operations: Patient flow modelling, theatre scheduling, and resource allocation in hospitals
• Performance Analytics: Using simulation and data-driven methods to benchmark and improve operational processes

Linear and Integer Programming

My work in linear and integer programming centres on the theoretical foundation and algorithmic advancement of exact optimisation methods. I focus on deriving strong formulations, developing cutting-plane algorithms, and implementing high-performance solvers that can handle industrial-scale problems. This includes:

• Polyhedral Theory: Studying the convex hulls of integer programmes to derive stronger valid inequalities
• Frameworks: Integrating cutting planes, branching rules, and primal heuristics within unified solver architectures
• Column Generation & Dantzig-Wolfe: Decomposing large-scale linear programmes with structured constraints
• Presolve & Parallelisation: Improving solver efficiency through problem reduction and distributed computing

Stochastic Optimisation

Recognising that real-world parameters are rarely known with certainty, my research in stochastic optimisation develops models and algorithms that explicitly account for randomness and ambiguity. I aim to produce solutions that are both optimal in expectation and robust against worst-case realisations. This includes:

• Two-Stage & Multistage Programming: Modelling sequential decisions under uncertainty with recourse actions
• Robust Optimisation: Constructing solutions that remain feasible and performant under parameter uncertainty
• Chance-Constrained Programming: Enforcing probabilistic constraints in energy, finance, and environmental planning
• Scenario Generation & Reduction: Developing statistical methods to approximate continuous uncertainties with finite, tractable scenario trees