11 |
[en] INTEGRATING METAHEURISTICS WITH MIP SOLVERS TO THE CAPACITATED VEHICLE ROUTING PROBLEM / [pt] INTEGRANDO METAEURÍSTICAS COM RESOLVEDORES MIP PARA O CAPACITATED VEHICLE ROUTING PROBLEMPEDRO NUNO DE SOUZA MOURA 02 March 2012 (has links)
[pt] Desde a sua origem, as abordagens a problemas de Otimização Combinatória
polarizam-se entre métodos exatos e heurísticos. Recentemente, porém,
estratégias que combinam ambos os métodos têm sido propostas para
os mais variados problemas, apresentando resultados promissores. Nesse
contexto, destacam-se os conceitos de vizinhaças de bola e elipsoidal,
que realizam buscas em relação a uma ou mais soluções de referência.
Este trabalho estuda a aplicação de tais vizinhanças para o Problema
de Roteamento de Veículos com Restrição de Capacidade (CVRP), sobre
o algoritmo de Branch-and-Cut-and-Price Robusto. Experimentos foram
realizados e seus resultados analisados. / [en] Since its inception, approaches to Combinatorial Optimization were polarized
between exact and heuristic methods. Recently, however, strategies that
combine both methods have been proposed for various problems, showing
promising results. In this context, the concepts of ball and ellipsoidal neighborhood
appear, which perform a search regarding one or more reference
solutions. This work studies the application of such neighborhoods for the
Capacitated Vehicle Routing Problem (CVRP), using the Robust Branchand-
Cut-and-Price algorithm. Experiments were made and its results were
analyzed.
|
12 |
[en] A MIP-BASED APPROACH TO SOLVE A REAL-WORLD SCHOOL TIMETABLING PROBLEM / [pt] UMA ABORDAGEM BASEADA EM PROGRAMAÇÃO INTEIRA MISTA PARA RESOLVER UM PROBLEMA DO MUNDO REAL DE GERAÇÃO DE GRADES HORÁRIAS ESCOLARESNARA TORRES MOREIRA 29 July 2016 (has links)
[pt] Problemas de geração de grades horárias visam agendar eventos a
fim de satisfazer demandas, ao mesmo tempo que satisfazem restrições adicionais.
Uma solução é boa se todas as grades horárias resultantes são
aceitáveis para todas as pessoas e recursos envolvidos. Para a geração de
grades horárias escolares, um número conhecido de aulas, envolvendo estudantes,
professores e salas de aula, deve ser agendado ao longo da semana,
enquanto limitações operacionais, institucionais, pedagógicas e pessoais devem
ser satisfeitas. A alta dificuldade do problema tem levado muitos pesquisadores
a trabalhar em abordagens de resolução para o mesmo desde
o início dos anos 60. Encontrar uma solução aplicável em um cenário do
mundo real implica em satisfazer vários requisitos de qualidade e em não
ignorar questões políticas, o que torna o problema clássico muito mais intrincado.
Este trabalho descreve uma abordagem baseada em programação
inteira mista (MIP) desenvolvida para resolver um problema real de geração
de grades horárias escolares e discute ideias e desafios encarados durante a
fase de implantação da solução em algumas escolas brasileiras. Em contraste
com outros trabalhos na área, o compartilhamento de professores entre diferentes
unidades de uma escola é considerado. Experimentos computacionais
foram realizados para cenários cujo número de unidades varia de 2 a 15, o
número de professores de 35 a 471, e o número de turmas de 16 a 295. Diferentes
estratégias foram combinadas, visando a convergência da procura por
boas soluções. Por fim, os resultados são avaliados e as melhores abordagens
são destacadas. / [en] Timetabling problems look to schedule meetings in order to satisfy
a set of demands, while respecting additional constraints. In a good
solution the resulting timetables are acceptable to all people and resources
involved. In school timetabling, a given number of lectures, involving
students, teachers and classrooms, need to be scheduled over the week,
while having to satisfy operational, institutional, pedagogical and personal
restrictions. The difficulty of the problem has driven many researchers
to work on solving approaches for it since the early 1960 s. Finding an
actual solution to a real world scenario implies satisfying many quality
requirements and not ignoring the political issues, which turns the classical
problem much more intricate. This work describes an approach based on
mixed integer programming (MIP) developed for solving a real-world school
timetabling problem and discusses ideas and issues faced during solution
deployment phase for some Brazilian schools. In contrast to other works on
school timetabling, teaching staff sharing between distinct school units are
considered. Computational experiments were performed for scenarios whose
number of school units varies from 2 to 15, number of teachers varies from
35 to 471 and number of classes varies from 16 to 295. Different strategies
were combined aiming at converging to good solutions. Finally, results are
evaluated and the best approaches are highlighted.
|
13 |
[en] OPTIMIZATION IN SPORTS: SPORT SCHEDULING AND QUALIFICATION PROBLEMS / [pt] OTIMIZAÇÃO EM ESPORTES: PROGRAMAÇÃO DE TABELAS E PROBLEMAS DE CLASSIFICAÇÃOSEBASTIAN ALBERTO URRUTIA 26 April 2006 (has links)
[pt] O planejamento e a gestão de atividades esportivas é uma
área promissora e pouco explorada para aplicações de
Pesquisa Operacional. Os problemas nesta área são em geral
de formulação simples e alcançam grande difusão nos meios
de comunicação. Embora sua formulação seja simples, em
geral estes problemas são difíceis de serem resolvidos em
termos computacionais. Os resultados de muitos trabalhos
acadêmicos nesta área têm sido aceitos como soluções para
problemas reais e várias soluções vem sendo implementadas
na prática. Esta tese tem como objetivo principal estudar
dois tipos de problemas que surgem na área de esportes: a
programação de tabelas e os problemas da classificação. A
programação de tabelas para competições esportivas é uma
tarefa difícil, na qual diversas técnicas de otimização
combinatória têm sido aplicadas. Nesta tese, formula-se o
Problema do Torneio com Viagens Espelhado como um problema
de otimização em grafos. O problema é resolvido utilizando-
se algoritmos aproximados. Apresentam-se duas heurísticas
para este problema. A primeira é muito rápida e serve para
fornecer soluções iniciais para a segunda, que é capaz de
obter soluções de boa qualidade em tempos razoáveis. São
deduzidos limites duais para um tipo particular de
instâncias. Estes limites permitem provar a otimalidade
das soluções obtidas heuristicamente para instâncias muito
maiores do que as maiores instâncias resolvidas na
literatura. Por ultimo, é apresentado um modelo de
programação linear inteira para o problema, ao qual são
acrescentadas desigualdades válidas. Os problemas da
classificação visam obter condições, necessárias e
suficientes, para a classificação de uma determinada
equipe para as finais de um campeonato em relação ao
número de pontos a ser obtido. São apresentados modelos de
programação linear inteira que permitem resolver estes
problemas no contexto do Campeonato Brasileiro de Futebol. / [en] Sports management is a very attractive and not very
explored area for applications of Operations Research.
Problems in this area use to have simple formulations and
reach a big coveragge by the media. Although their
formulations are simple, in general these problems are
difficult to be solved in computational terms. The results
of many academic works in this area have been accepted as
solutions for real problems and some solutions are being
implemented.
This thesis has the main objective of studying two types
of problems that appear in the sports area: the fixture
creation and the qualification problems.
Fixture creation (also known as sport scheduling) for
sport competitions is a difficult task, in which several
combinatorial optimization techniques has been applied. In
this thesis, the Mirrored Traveling Tournament Problem is
formulated as a graph optmization problem. The problem is
solved using approximation algorithms. Two heuristics are
introduced for this problem. The first one is very fast
and is used to supply initial solutions for the second one
which is able to obtain high quality solutions in
reasonable computation times. Dual limits are deduced for
a particular type of instances. These limits allow to
prove the optimality of the heuristically abtained
solutions for instances that are much bigger than those
soved in the literature. Finally, an integer programming
model is introduced in wich valid inequalities are added.
The qualification problems aim to obtain necessary and
sufficient conditions for the playoffs qualification of a
given team in terms of the number of points to be
obtained. Integer programming models are introduced which
allow solving these problems in the context of the
Brazilian Football Championship.
|
14 |
[en] HEURISTICS FOR ROUTING AND WAVELENGTH ASSIGNMENT BY PARTITION COLORING / [pt] HEURÍSTICAS PARA ROTEAMENTO E ATRIBUIÇÃO MÍNIMA DE COMPRIMENTOS DE ONDA POR COLORAÇÃO DE PARTIÇÕESTHIAGO FERREIRA DE NORONHA 22 July 2004 (has links)
[pt] Nas redes de fibras óticas, as informações são transmitidas
na forma de um sinal luminoso através de uma fibra ótica. A
tecnologia de multiplexação WDM permite a transmissão
simultânea de vários sinais em um mesmo enlace. As conexões
entre estações terminais são estabelecidas na forma de
caminhos óticos, que são definidos em função de sua rota e
do comprimento de onda no qual são multiplexados.
Conversores de comprimentos de onda não são considerados
neste trabalho. Conseqüentemente, os caminhos óticos devem
permanecer com o mesmo comprimento de onda em todos os
enlaces do transmissor ao receptor. O Problema de
Roteamento e Atribuição Mínima de Comprimentos de Onda (min-
RWA) consiste em estabelecer um conjunto de conexões entre
pares de estações e atribuir um determinado comprimento de
onda para cada uma delas, de forma que caminhos óticos que
compartilhem algum enlace da rede tenham comprimentos de
onda diferentes e que o número total de comprimentos de
onda utilizados seja mínimo. Neste trabalho, uma nova
heurística é proposta para min-RWA, onde k possíveis rotas
são calculadas para cada conexão e, em seguida, uma rota
(dentre as rotas pré-calculadas) e um comprimento de onda
são atribuídos a cada conexão resolvendo-se um Problema de
Coloração de Partições (PCP). O PCP é um problema de
coloração em grafos particionados, ou seja, grafos onde os
vértices estão particionados em subconjuntos disjuntos. O
PCP consiste em selecionar e colorir um único vértice de
cada subconjunto, de modo que dois vértices adjacentes, no
grafo induzido pelos vértices selecionados tenham cores
diferentes e que o número total de cores utilizadas seja
mínimo. Nesta dissertação, são apresentadas e propostas
novas heurísticas para PCP e min-RWA. Estas heurísticas são
comparadas com as melhores conhecidas na literatura. / [en] In optical networks, the information is transmitted along
the optical fibers as optical signals. Wavelength Division
Multiplexing (WDM) allows more efficient use of the huge
capacity of optical fibers, as far as it permits the
simultaneous transmission of different channels along the
same fiber, each of them using a different wavelength. The
connections are established by lightpaths, in which the
signal is converted to the optical domain and reaches the
receptor without conversion to the electrical domain. A
lightpath is defined by a route and a wavelength. We assume
that wavelength conversion along a lightpath is not
permitted, since this technology is not yet fully
available. Therefore, each lightpath should use the same
wavelength from the transmitter to the receiver. The
Routing and Wavelength Assignment problem consists in
routing a set of lightpaths and assigning a wavelength to
each of them. All connection requirements are known
beforehand and one seeks to minimize the total number of
wavelengths used for routing these connections, so as that
two lightpaths sharing a common link use different
wavelengths. In this work, we propose a new heuristic in
which min-RWA is solved by a combined approach involving
the computation of alternative routes for the lightpaths,
followed by the solution of a Parttion Coloring Problem
(PCP). Given a graph where the vertex set is partitioned in
disjoint susets, PCP consists in selecting and coloring
only one vertex in each subset, so as that every two
adjacent colored nodes have different colors and the total
number of colors used is minimum. We present and propose
new heuristics for PCP and min-RWA. Computational
experiments are reported comparing the new heuristics and
those which already appeared in the literature.
|
15 |
[en] A SIMPLE AND EFFECTIVE HYBRID GENETIC SEARCH FOR THE JOB SEQUENCING AND TOOL SWITCHING PROBLEM / [pt] UMA BUSCA GENÉTICA HÍBRIDA SIMPLES E EFETIVA PARA O PROBLEMA DE SEQUENCIAMENTO DE TAREFAS E TROCA DE FERRAMENTASJORDANA ZERPINI MECLER 19 August 2020 (has links)
[pt] O problema de sequenciamento de tarefas e troca de ferramentas (job sequencing and tool switching problem - SSP) tem sido extensivamente estudado na área de pesquisa operacional, devido à sua relevância prática e interesse metodológico. Dada uma máquina que pode carregar uma quantidade limitada de ferramentas simultaneamente e um número de tarefas que requerem um subconjunto das ferramentas disponíveis, o SSP procura uma sequência de tarefas que minimize o número total de trocas de ferramentas na máquina. Para resolver este problema, é proposta uma busca genética híbrida simples e efetiva baseada em uma representação de solução genérica, um operador de decodificação sob medida, buscas locais eficientes e técnicas de gerenciamento de diversidade. Para orientar a busca, um objetivo secundário desenvolvido para tratar empates é introduzido. Essas técnicas permitem explorar soluções estruturalmente distintas e escapar de ótimos locais. Conforme apresentado nos experimentos computacionais em instâncias clássicas, o algoritmo proposto supera significativamente todas as abordagens anteriores, mesmo sendo de fácil entendimento e implementação. Por fim, resultados obtidos em um novo conjunto de instâncias maiores são reportados para estimular futuras pesquisas e análises comparativas. / [en] The job sequencing and tool switching problem (SSP) has been extensively studied in the field of operations research, due to its practical relevance and methodological interest. Given a machine that can load a limited amount of tools simultaneously and a number of jobs that require a subset of the available tools, the SSP seeks a job sequence that minimizes the number of tool switches in the machine. To solve this problem, we propose a simple and efficient hybrid genetic search based on a generic solution representation, a tailored decoding operator, efficient local searches and diversity management techniques. To guide the search, we introduce a secondary objective designed to break ties. These techniques allow to explore structurally different solutions and escape local optima. As shown in our computational experiments on classical benchmark instances, our algorithm significantly outperforms all previous approaches while remaining simple to apprehend and easy to implement. We finally report results on a new set of larger instances to stimulate future research and comparative analyses.
|
16 |
[pt] ESTRATÉGIAS PARA O CONTROLE DE PARÂMETROS NO ALGORITMO GENÉTICO COM CHAVES ALEATÓRIAS ENVIESADAS / [en] STRATEGIES FOR PARAMETER CONTROL IN THE BIASED RANDOM-KEY GENETIC ALGORITHMLUISA ZAMBELLI ARTMANN R VILELA 08 November 2022 (has links)
[pt] O Algoritmo Genético de Chaves Aleatórias Enviesadas (BRKGA) é
uma metaheurística populacional utilizada na obtenção de soluções ótimas ou
quase ótimas para problemas de otimização combinatória. A parametrização
do algoritmo é crucial para garantir seu bom desempenho. Os valores dos
parâmetros têm uma grande influência em determinar se uma boa solução
será encontrada pelo algoritmo e se o processo de busca será eficiente. Uma
maneira de resolver esse problema de configuração de parâmetros é por
meio da abordagem de parametrização online (ou controle de parâmetros).
A parametrização online permite que o algoritmo adapte os valores dos
parâmetros de acordo com os diferentes estágios do processo de busca e
acumule informações sobre o espaço de soluções nesse processo para usar as
informações obtidas em estágios posteriores. Ele também libera o usuário da
tarefa de definir as configurações dos parâmetros, resolvendo implicitamente
o problema de configuração. Neste trabalho, avaliamos duas estratégias para
implementar o controle de parâmetros no BRKGA. Nossa primeira abordagem
foi adotar valores de parâmetros aleatórios para cada geração do BRKGA.
A segunda abordagem foi incorporar os princípios adotados pelo irace, um
método de parametrização do estado da arte, ao BRKGA. Ambas as estratégias
foram avaliadas em três problemas clássicos de otimização (Problema de
Permutação Flowshop, Problema de Cobertura de Conjuntos e Problema do
Caixeiro Viajante) e levaram a resultados competitivos quando comparados ao
algoritmo tunado. / [en] The Biased Random-Key Genetic Algorithm (BRKGA) is a populationbased metaheuristic applied to obtain optimal or near-optimal solutions to
combinatorial problems. To ensure the good performance of this algorithm
(and other metaheuristics in general), defining parameter settings is a crucial
step. Parameter values have a great influence on determining whether a good
solution will be found by the algorithm and whether the search process will
be efficient. One way of tackling the parameter setting problem is through
the parameter control (or online tuning) approach. Parameter control allows
the algorithm to adapt parameter values according to different stages of the
search process and to accumulate information on the fitness landscape during
the search to use this information in later stages. It also releases the user
from the task of defining parameter settings, implicitly solving the tuning
problem. In this work, we evaluate two strategies to implement parameter
control in BRKGA. Our first approach was adopting random parameter values
for each of BRKGA s generations. The second approach was to introduce
the principles adopted by Iterated Race, a state-of-the-art tuning method,
to BRKGA. Both strategies were evaluated in three classical optimization
problems (Flowshop Permutation Problem, Set Covering Problem, and the
Traveling Salesman Problem) and led to competitive results when compared
to the tuned algorithm.
|
17 |
[en] NEW HEURISTICS AND AN INTEGER PROGRAMMING APPROACH TO AN INEXACT GRAPH MATCHING PROBLEM / [pt] NOVAS HEURÍSTICAS E UMA ABORDAGEM POR PROGRAMAÇÃO INTEIRA PARA UM PROBLEMA DE CORRESPONDÊNCIA INEXATA DE GRAFOSALEXANDRE ROCHA DUARTE 26 March 2004 (has links)
[pt] Esta dissertação apresenta novos algoritmos aproximados e
uma abordagem exata para a resolução de um problema de
correspondência inexata de grafos. O problema considerado é
o de correspondência entre um grafo representando um modelo
genérico e outro representando dados a serem reconhecidos.
Assumi-se que o grafo dos dados possui mais vértices que o
do modelo. A motivação para o estudo desse problema vem de
problemas de reconhecimento de cenas, que consistem na
caracterização dos objetos envolvidos em uma determinada
cena, assim como das relações existentes entre eles. Uma
aplicação para este problema na área de reconhecimento de
imagens médicas é a de efetuar-se o reconhecimento de
estruturas 3D do cérebro humano, a partir de imagens
obtidas por ressonância magnética. Tais imagens são
previamente processadas por algum método de segmentação
automática e o processo de reconhecimento consiste na busca
da correspondência estrutural entre a imagem e um modelo
genérico, tipicamente definido como um atlas de imagens
médicas. Foram propostos novos algoritmos aproximados, tais
como um algoritmo construtivo guloso aleatorizado, um
procedimento de reconexão de caminhos e um GRASP que
combina estes com uma técnica de busca local. Além disso,
foi proposta uma formulação original do problema como um
problema de programação linear inteira, que permitiu a
resolução de algumas instâncias de forma exata. / [en] This dissertation presents new approximation algorithms and
an exact approach to the solution of an inexact graph
matching problem. The problem consists in finding the best
match between a generic model graph and a graph
representing an image, the latter with more nodes than the
former. The motivation for studying this problem comes from
a scene recognition problem, which consists in
characterizing objects involved in a given scene and the
relationships between them. An application of this problem
appears in the analysis of medical images and consists in
recognizing 3-dimensional structures in the human brain
using images obtained by magnetic resonance. Such images
must be previously processed by an automatic segmentation
method and the recognition process consists in the search
of an structural matching between the image and a generic
model, typically defined as an atlas of medical images.
New heuristics are proposed, such as a greedy randomized
construction algorithm, a path relinking procedure and a
GRASP heuristic that combines them with a local search
technique. Furthermore, an original integer formulation
of the problem based on integer multicommodity flows is
proposed, which makes possible the exact solution of medium-
sized instances.
|
18 |
[en] HEURISTICS FOR THE PROBLEM OF DNA SEQUENCING BY HYBRIDIZATION / [pt] HEURÍSTICAS PARA O PROBLEMA DE SEQÜÊNCIAMENTO DE DNA POR HIBRIDAÇÃOERALDO LUIS REZENDE FERNANDES 04 May 2005 (has links)
[pt] O seqüenciamento por hibridação é uma alternativa
interessante para a tarefa
de seqüenciamento de DNA. Este método ainda está sendo
aperfeiçoado
e pode superar as técnicas utilizadas em termos de tempo e
custo. Uma
etapa crucial do método consiste em resolver um problema
combinatório
que pode ser formulado como um caso especial do problema do
caixeiro viajante
com coleta de prêmios. Neste trabalho, propõe-se uma nova
heurística
construtiva multi-partida para resolver este problema. Uma
estratégia de
aprendizado baseada em uma memória adaptativa e um
procedimento de
construção de vocabulário são utilizados para melhorar o
desempenho da
heurística multi-partida. A memória adaptativa é utilizada
para intensificar as construções de novas soluções com os
elementos que aparecem com
uma freqüência maior nas melhores soluções encontradas
anteriormente pela
heurística multi-partida. O procedimento de construção de
vocabulário consiste
em construir novas soluções através da combinação de partes
comuns a
boas soluções. Testes computacionais mostraram que estas
duas estratégias
aumentam significativamente o desempenho da heurística
multi-partida e
são particularmente indicadas para problemas de
escalonamento nos quais
as melhores soluções são na maioria dos casos formadas por
blocos de elementos
que aparecem juntos com muita freqüência. A heurística
proposta
supera os resultados dos melhores algoritmos encontrados na
literatura,
tanto em termos da qualidade das soluções encontradas, como
do tempo
de computação. / [en] Sequencing by hybridization is an attractive alternative
for DNA sequencing.
This novel method can be less time and cost consuming than
the techniques
applied nowadays. A very important step of this method is
to solve
a combinatorial problem formulated as a special case of the
prize-collecting
traveling salesman problem. In this work, we propose a new
multistart construtive
heuristic to solve this problem. A learning strategy based
on adaptive
memory and a vocabulary building procedure are used to
improve the
performance of the multistart heuristic. The adaptive
memory is used to
intensify the construction of new solutions with the
elements that appear
frequently in the best solutions previously found by the
multistart heuristic.
The objective of the vocabulary building procedure is to
construct new
solutions combining parts of good solutions. Computational
experiments
have shown that these two methods significantly improves
the performance
of the multistart heuristic and are particularly suitable
for scheduling problems
whose best solutions are in most cases built by blocks of
elements that
appear together very often. The proposed heuristic obtains
systematically
better solutions and is less time consuming than the best
algorithms found
in the literature.
|
19 |
[en] AUTOMATED SYNTHESIS OF OPTIMAL DECISION TREES FOR SMALL COMBINATORIAL OPTIMIZATION PROBLEMS / [pt] SÍNTESE AUTOMATIZADA DE ÁRVORES DE DECISÃO ÓTIMAS PARA PEQUENOS PROBLEMAS DE OTIMIZAÇÃO COMBINATÓRIACLEBER OLIVEIRA DAMASCENO 24 August 2021 (has links)
[pt] A análise de complexidade clássica para problemas NP-difíceis é geralmente
orientada para cenários de pior caso, considerando apenas o comportamento
assintótico. No entanto, existem algoritmos práticos com execução em um tempo razoável para muitos problemas clássicos. Além disso, há evidências que apontam para algoritmos polinomiais no modelo de árvore de decisão linear para resolver esses problemas, embora não muito explorados. Neste trabalho, exploramos esses resultados teóricos anteriores. Mostramos que a solução ótima para problemas combinatórios 0-1 pode ser encontrada reduzindo esses problemas para uma Busca por Vizinho Mais Próximo sobre o conjunto de vértices de Voronoi correspondentes. Utilizamos os hiperplanos que delimitam essas regiões para gerar sistematicamente uma árvore de decisão que repetidamente divide o espaço até que possa separar todas as soluções, garantindo uma resposta ótima. Fazemos experimentos para testar os limites de tamanho para os quais podemos construir essas árvores para os casos do 0-1 knapsack, weighted minimum cut e symmetric traveling salesman. Conseguimos encontrar as árvores desses problemas com tamanhos até 10, 5 e 6, respectivamente. Obtemos também as relações de adjacência completas para os esqueletos dos politopos do knapsack
e do traveling salesman até os tamanhos 10 e 7. Nossa abordagem supera
consistentemente o método de enumeração e os métodos baseline para o weighted
minimum cut e symmetric traveling salesman, fornecendo soluções ótimas em
microssegundos. / [en] Classical complexity analysis for NP-hard problems is usually oriented to
worst-case scenarios, considering only the asymptotic behavior. However, there
are practical algorithms running in a reasonable time for many classic problems. Furthermore, there is evidence pointing towards polynomial algorithms in
the linear decision tree model to solve these problems, although not explored
much. In this work, we explore previous theoretical results. We show that the
optimal solution for 0-1 combinatorial problems can be found by reducing these
problems into a Nearest Neighbor Search over the set of corresponding Voronoi
vertices. We use the hyperplanes delimiting these regions to systematically generate a decision tree that repeatedly splits the space until it can separate all solutions, guaranteeing an optimal answer. We run experiments to test the size limits for which we can build these trees for the cases of the 0-1 knapsack, weighted minimum cut, and symmetric traveling salesman. We manage to find the trees of these problems with sizes up to 10, 5, and 6, respectively. We also obtain the complete adjacency relations for the skeletons of the knapsack and traveling salesman polytopes up to size 10 and 7. Our approach consistently outperforms the enumeration method and the baseline methods for the weighted minimum cut and symmetric traveling salesman, providing optimal solutions within microseconds.
|
20 |
[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 MACHINESITALO GOMES SANTANA 04 November 2022 (has links)
[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.
|
Page generated in 0.4291 seconds