[pt] EXPLORANDO A FRONTEIRA DE OTIMIZAÇÃO COMBINATÓRIA E APRENDIZADO DE MÁQUINA: APLICAÇÕES PARA ROTEAMENTO DE VEÍCULOS E MÁQUINAS DE VETORES DE SUPORTE

[en] EXPLORING THE FRONTIER OF COMBINATORIAL OPTIMIZATION AND MACHINE LEARNING: APPLICATIONS TO VEHICLE ROUTING AND SUPPORT VECTOR MACHINES

[pt] ITALO GOMES SANTANA

[pt] APRENDIZADO DE MAQUINA

[pt] CORTES COMBINATORIOS DE BENDERS

[pt] PROBLEMA DE ROTEAMENTO DE VEICULOS

[pt] META-HEURISTICA

[pt] OTIMIZACAO COMBINATORIA

[en] MACHINE LEARNING

[en] COMBINATORIAL BENDERS CUT

[en] VEHICLE ROUTING PROBLEM

[en] META-HEURISTICS

[en] COMBINATORIAL OPTIMIZATION

[pt] A otimização combinatória (OC) está presente em inúmeras aplicações práticas (por exemplo, planejamento de produção, logística, etc.). Ao longo dos anos, OC e aprendizado de máquina (AM) surgiram, juntas, como uma área prospectiva de pesquisa para melhorar processos de tomada de decisão. Nesse contexto, há interesse em utilizar algoritmos de AM para melhorar métodos de OC. Por outro lado, como muitas tarefas de AM podem ser reformuladas como problemas de otimização, há um amplo interesse em utilizar métodos de OC para resolver esses problemas. Nesta tese, três estudos que conectam OC e AM em torno de duas aplicações importantes são conduzidos: o problema de roteamento de veículos capacitado (PRVC) e máquinas de vetores de suporte com perda em margem rígida (SVM-HML – do inglês support vector machines with hard-margin loss). No primeiro estudo, uma estratégia para explorar vizinhanças de busca local de alta ordem por mineração de padrões em duas meta-heurísticas estado da arte para o PRVC é proposta. Em um segundo estudo, também no contexto do PRVC, critérios de relacionamento para nós de clientes baseados em saídas de redes neurais em grafos são explorados. Com base nessas saídas, medidas de relação podem ser exploradas para orientar a busca local e estender operadores de cruzamento em um algoritmo genético estado da arte. Por fim, no terceiro estudo, uma abordagem eficiente de programação inteira mista baseada em cortes combinatórios de Benders e estratégias de amostragem são utilizadas para treinar modelos de SVM-HML de maneira mais eficiente.

[en] Combinatorial optimization (CO) is ubiquitous in myriad practical applications (e.g., production planning, scheduling, logistics, etc.). Over the years, CO and machine learning (ML) have emerged, together, as a prospective area of research for improving decision-making processes. There is interest to harness ML algorithms to improve existing CO methods. Conversely, since many ML tasks can be reformulated as optimization problems, there is broad interest in leveraging state-of-the-art CO methods for them. In this thesis, we conduct three studies that connect CO and ML around two important applications: the capacitated vehicle routing problem (CVRP) and support vector machines with hard-margin loss (SVM-HML). Our first study proposes a strategy to explore high-order local-search neighborhoods by pattern mining into two state-of-the-art metaheuristics for the CVRP. In a second study, also in the context of the CVRP, we exploit relatedness criteria for customer nodes using predictions from graph neural networks. We show that relatedness measures can be exploited to steer local search and extend crossover operators in a stateof- the-art genetic algorithm. Lastly, in a third study, we propose an efficient mixed-integer programming approach based on Combinatorial Benders cuts and sampling strategies for optimally training the SVM-HML.

THIBAUT VICTOR GASTON VIDAL

MARCO SERPA MOLINARO

ARTUR ALVES PESSOA

RAFAEL MARTINELLI PINTO

THIBAUT VICTOR GASTON VIDAL

ANDREA LODI

2022-11-04

2022-09-09

[pt] TEXTO

application/pdf

INGLÊS

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=61096@1

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=61096@2

https://doi.org/10.17771/PUCRio.acad.61096