[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.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:61096 |
| Date | 04 November 2022 |
| Creators | ITALO GOMES SANTANA |
| Contributors | THIBAUT VICTOR GASTON VIDAL |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | English |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0028 seconds