1 |
[en] HEURISTICS FOR THE CONNECTED P-MEDIAN PROBLEM / [pt] HEURÍSTICAS PARA O PROBLEMA DAS P-MEDIANAS CONECTADASCARLOS EDUARDO COSTA VIEIRA 28 March 2007 (has links)
[pt] Esta tese define os problemas das p-medianas conectadas e o
de localização de facilidades não-capacitadas conectadas.
Possíveis aplicações incluem problemas de planejamento
regional e o projeto de redes de telecomunicações ou de
transporte. Para o primeiro problema, duas formulações de
programação linear inteira são apresentadas e comparadas.
Um destes modelos é adaptado para o segundo problema. Para
o problema das p-medianas conectadas, algoritmos
aproximados são desenvolvidos. Uma estratégia de
busca local híbrida é proposta. Para acelerar as iterações
do algoritmo de busca local, idéias como circularidade,
melhoria iterativa e o descarte de vizinhos são
incorporadas. Heurísticas GRASP e VNS são desenvolvidas
incluindo a utilização de um filtro com o objetivo de
diminuir os tempos de processamento e do procedimento de
reconexão por caminhos com o objetivo de melhorar a
qualidade das soluções encontradas. Diversos testes são
realizados comparando-se esses algoritmos. Os resultados
mostraram a necessidade de se executar um passo adicional
de pós-otimização às heurísticas GRASP e VNS propostas. / [en] In this work, the connected p-median and the connected
facility location problems are defined. Applications arise
in regional planning, design of telecommunications and
transportation networks. For the first problem,
two integer linear programming formulations are proposed.
Adaptations are made in one of these formulations and are
used to model the second problem. Approximation algorithms
to solve the connected p-median problem are developed. A
hybrid local search strategy is proposed. In order to speed
up the local search iterations, ideas as circularity, first-
improving strategy and discard neighbors are incorporated.
A GRASP algorithm and a VNS heuristic are also proposed. A
filter is used to reduce the computational time required
and a path-relinking is applied to improve the results
found. Computational experiments to compare the algorithms
are reported. To improve these results, it is applied a
post-optimization step to the GRASP and VNS heuristics.
|
2 |
[en] A HYBRID IMPROVEMENT HEURISTICS FOR THE BIN PACKING PROBLEM AND ITS APPLICATION TO THE PROBLEM OF TASK SCHEDULING / [pt] UMA HEURÍSTICA HÍBRIDA DE MELHORIA PARA O PROBLEMA DE BIN PACKING E SUA APLICAÇÃO AO PROBLEMA DE ESCALONAMENTO DE TAREFASADRIANA CESARIO DE FARIA ALVIM 09 January 2004 (has links)
[pt] A principal contribuição desta tese consiste no
desenvolvimento de uma heurística híbrida, robusta e
eficiente, para o problema de empacotamento unidimensional.
A heurística proposta utiliza os seguintes componentes:
limites inferiores e superiores do número de caixas;
reduções; abordagem dual para a obtenção de soluções
iniciais; heurísticas para redistribuição dos pesos; e
busca tabu. O outro objetivo desta tese é a aplicação desta
heurística para a solução do problema de escalonamento em
processadores paralelos idênticos. São apresentados
resultados computacionais obtidos sobre centenas de
problemas testes da literatura. / [en] We propose in this work a hybrid improvement procedure for
the bin packing problem. This heuristic has several
components: lower and upper bounds; reductions,
construction of initial solutions by reference to the dual
problem;heuristics for load redistribution based on
dominance, differencing, and unbalancing; and tabu search.
We also investigate the application of this hybrid
heuristic to the problem of task scheduling on identical
parallel processors. Computational results on hundreds of
benchmark test problem are presented.
|
3 |
[en] ALGORITHM RELAX-AND-CUT FOR THE 0-1 QUADRATIC KNAPSACK PROBLEM / [pt] UM ALGORITMO RELAX-AND-CUT PARA O PROBLEMA QUADRÁTICO DA MOCHILA 0-1MARCIO DE MORAES PALMEIRA 01 November 2005 (has links)
[pt] Consideramos o Problema Quadrático da Mochila 0-1 (QKP),
que consiste em maximizar uma função booleana quadrática
sujeito a uma restrição de capacidade linear. O problema
possui aplicações em várias áreas, como por exemplo,
telecomunicações. engenharia financeira, problemas de
localização e teoria dos grafos (clique máximo). Propomos
um algoritmo de Branch-and-Bound para resolver exatamente
QKP, baseado em Relaxação Lagrangeana. Inicialmente,
linearizamos a formulação do problema acima, e em seguida,
aplicamos a técnica de relax-and-cut dinamicamente à
relaxação contínua do problema, utilizando algumas classes
de desigualdades válidas. O método do subgradiente é usado
neste processo. Propomos também uma nova heurística primal
para QKP, que obtém soluções melhores do que heurísticas
propostas anteriormente, encontrando a solução ótima em
todas as instâncias que consideramos. A boa qualidade dos
limites superior e inferior é traduzida em gap`s pequenos
no nó raiz da árvore de enumeração (em geral, menor do que
1%, inclusive para instâncias difíceis). Isto, aliado a
testes de fixação de variáveis, permite resolver
exatamente QKP em poucos nós da árvore de enumeração.
Introduzimos uma maneira de gerar instâncias aleatórias
mais difíceis do que as instâncias na literatura.
Apresentamos resultados computacionais para instâncias
geradas aleatoriamente (instâncias da literatura, e as
novas instâncias mais difíceis) para QKP de tamanhos e
densidades diferentes; e também para instâncias conhecidas
do problema de clique máxima. / [en] We consider the 0-1 Quadratic Knapsack Problem (QKP),
which consists of maximizing a quadratic Boolean function
subject to a linear capacity constraint. The problem has
applications in several areas such as telecommunications,
financial engineering, location problems, graph theory
(Max Clique).
We propose a Branch-and-Bound algorithm to solve
the QKP to optimality based on lagrangian Relaxation.
Initially, we linearize the formulation of the problem
given above and then we relax-and-cut dinamicaly its
continous relaxation using a few classes of valid
inequalities. In the process the Subgradient Method is
applied.
We also propose a new primal heuristic for the QKP
that has improved upon previous approaches, and finds an
optimal solution for all of the instances we considered.
The good quality of our upper and lower bounds is
translated into small gaps at the root node of the
enumeration tree (usually below 1%, even for difficult
instances). That, coupled with tests for fixing variables,
allowed optimality to be proven within only a few nodes of
the enumeration tree.
We provide a way to randomly generate instances
of the QKP harder than those in the literature. We report
computational results for randomly generated instances
(the ones in the literature and the new harder ones) of
QKP with different densities and sizes; and also for Known
instances of Max Clique problems.
|
4 |
[en] ALGORITHMS FOR POST ENROLLMENT-BASED COURSE TIMETABLING / [pt] ALGORITMOS PARA PROBLEMAS DE PROGRAMAÇÃO DE HORÁRIOS DE CURSOS PÓS-MATRÍCULAVITOR CAVALCANTI DANTAS 24 June 2009 (has links)
[pt] Problemas de Programação de Horários (PPHs) tem sido amplamente
estudados, dada a sua importância prática e teórica. A maioria das variações
do problema pertence µa classe NP-Difícil. Em geral, trata-se da alocação de
recursos materiais e humanos no espaço e no tempo, visando a otimização
de um conjunto de objetivos definidos. Na Programação de Horários de
Cursos Universitários, por exemplo, o objetivo pode ser a satisfação do
corpo docente e o desempenho acadêmico dos alunos. Nos últimos anos, as
formulações de PPHs propostas pela International Timetabling Competition
(ITC) tem sido bastante utilizadas, sendo notável a predominância de
métodos baseados em busca local e metaeurísticas entre as abordagens
propostas recentemente. Este trabalho tem como objetivo propor algoritmos
para o Problema de Programação de Horários Pós-Matrícula da ITC,
focando principalmente em métodos heurísticos baseados em Programação
Matemática. Entre os modelos de Programação Linear Inteira Mista que
propomos para este problema, destaca-se o modelo baseado na Formulação
de Representantes Assimétricos para o Problema de Coloração de Grafos.
Abordamos a aplicação da heurística de Local Branching e propomos um
esquema de resolução por Geração de Colunas, como forma de viabilizar
o tratamento dos modelos propostos, uma vez que a complexidade de tais
modelos representa um desafio para os resolvedores de Programação Linear
Inteira Mista atualmente disponíveis. / [en] Timetabling Problems have been widely studied, given its practical and
theorical relevance. Most of its variations belong to the NP-Hard class of
problems. In general, it is about allocation of material and human resources
in time and space, aiming to optimize some set of defined objetives. In
University Course Timetabling, for example, the objective might be the
satisfaction of professors and the academic performance of students. In the
last years, the formulations for timetabling problems proposed by the In-
ternational Timetabling Competition (ITC) have been widely adopted. The
predominance of meta-heuristics and local search-based methods is remark-
able among the recently proposed approaches. The objetive of this thesis
is to propose algorithms for the Post Enrolment-based Course Timetabling
Problem of the ITC, focusing on Mathematical Programming-based heuris-
tic methods. Among the Mixed Integer Linear Programming models that
we propose for this problem, we highlight the one based on the Asymetric
Representatives Formulation for the Graph Coloring Problem. We explore
the application of the Local Branching heuristic and we propose a Column
Generation solution procedure, as an attempt to handle the proposed models,
given that the complexity of such models poses a challenge for currently
available Mixed Integer Linear Programming solvers.
|
5 |
[en] COMBINING METAHEURISTICS WITH MP SOLVERS, WITH APPLICATIONS TO THE GENERALIZED ASSIGNMENT PROBLEM (GAP) / [pt] COMBINANDO METAURÍSTICAS COM RESOLVEDORES MIP, COM APLICAÇÕES AO GENERALIZED ASSIGNMENT PROBLEM (GAP)DANIEL AMARAL DE MEDEIROS ROCHA 08 March 2010 (has links)
[pt] Métodos que combinam estratégias normalmente encontradas em algoritmos metaeurísticos com técnicas para resolver problemas de programação inteira mista (MIP) têm apresentado ótimos resultados nos últimos anos. Este trabalho propõe dois novos algoritmos nessa linha: um algoritmo que faz pós-processamento nas soluções encontradas pelo resolvedor MIP. Os dois algoritmos utilizam um novo tipo de vizinhança, chamada de vizinhança elipsoidal, que possui fortes semelhanças com as técnicas de relinking de algoritmos PR e que neste trabalho é generalizada e extendida para múltiplas soluções. O problema generalizado de alocação (GAP) é usado para os experimentos. São testados também um resolvedor MIP puro (ILOG CPLEX versão 11) e um algoritmo branch and price que utiliza as heurísticas RINS e guided dives. Os algoritmos testados são comparados entre e com heurísticas específicas para o GAP. Os resultados são satisfatórios e indicam que as vizinhanças elipsoidais conseguem frequentemente melhorar as soluções encontradas pelo resolvedor MIP, encontrando a melhor solução para algumas instâncias. / [en] Methods that mix strategies usually found in metaheristic algorithms with techniques to solve mixed integer programming problems (MIPs) have had great results over the past few years. This wprk proposes two new algorithms in this philosophy: one is based on the Path Relink (PR) metaheuristc, while the other one is a simple algorithm that does post-processing in the solutions found by the MIP solver. Both algorithms use a new neighborhood structure, called ellipsoidal neighborhood, that has strong resemblances with the relinking step from PR algorithms and that, in this work, is generalized and extended for multiple solutions. The generalized assignment problem (GAP) is used for the computational experiments. Also tested are MIP solver (ILOG CPLEX version 11) and a branch and price algorithm that uses the RINS and guides dives heuristics. The tested algorithms are compared among themselves and with GAP-specific heuristics. The results are satisfactory and show that the ellipsoidal neighborhood can frequently improve the solutions found by the MIP solver, even finding the best result for some instances.
|
6 |
[en] ON THE SIMULTANEOUS MINIMIZATION OF WORST TESTING COST AND EXPECTED TESTING COST WITH DECISION TREES / [pt] MINIMIZAÇÃO SIMULTÂNEA DO PIOR CUSTO E DO CUSTO MÉDIO EM ÁRVORES DE DECISÃOALINE MEDEIROS SAETTLER 25 January 2017 (has links)
[pt] O problema de minimizar o custo de avaliar uma função discreta lendo sequencialmente as suas variáveis é um problema que surge em diversas aplicações, entre elas sistemas de diagnóstico automático e aprendizado ativo. Neste problema, cada variável da função está associada a um custo, que se deve pagar para checar o seu valor. Além disso, pode existir uma distribuição de probabilidades associadas aos pontos onde a função está definida. A maioria dos trabalhos nesta área se concentra ou na minimização do custo máximo ou na minimização do custo esperado gasto para avaliar a função. Nesta dissertação, mostramos como obter uma Ômicron logaritmo de N aproximação em relação à minimização do pior custo (a melhor aproximação possível assumindo que P é diferente de NP). Nós também mostramos um procedimento polinomial para avaliar uma função otimizando simultaneamente o pior custo e o custo esperado. / [en] The problem of minimizing the cost of evaluating a discrete function by sequentially reading its variables is a problem that arises in several applications, among them automatic diagnosis design and active learning. In this problem, each variable of the function is associated with a cost, that we have to pay in order to check its value. In addition, there may exist a probability distribution associated with the points where the function is defined. Most of the work in the area has focussed either on the minimization of the maximum cost or on the minimization of the expected cost spent to evaluate the function. In this dissertation, we show how to obtain an Ômicron logarithm of N approximation with respect to the worst case minimization (the best possible approximation under the assumption that P is different from NP). We also show a polynomial time procedure for evaluate a function that simultaneously optimizes both the worst and the expected costs.
|
7 |
[en] COVERING CODES: BOUNDS AND HEURISTICS / [pt] CÓDIGOS DE COBERTURA: LIMITES E HEURÍSTICASCARLOS RAONI DE ALENCAR MENDES 08 March 2010 (has links)
[pt] Compreensão de dados, codificação digital da fala, telecomunicações via celular, correção de erros de transmissão, são algumas das aplicações práticas do estudo dos códigos de cobertura, um importante ramo da área da matemática denominada teoria dos códigos. Neste trabalho são abordados dois problemas de códigos de cobertura: o problema clássico de códigos de cobertura e o recente problema denominado de códigos curtos de cobertura. Apresenta-se uma aplicação da metaeurística Busca Tabu Reativa, uma importante variação da Busca Tabu clássica, para os problemas citados. Além disto, apresenta-se uma nova técnica heurística para resolução de problemas de otimização combinatória denominada Heurística de Melhoria via Geração de Colunas (HMGC), juntamente com uma aplicação da mesma aos problemas em questão. A HMGC combina a geração atrasada de colunas, técnica usada na resolução de problemas com um grande número de variáveis de decisão (colunas), e heurísticas de busca local. É feita uma comparação dos resultados obtidos pela Busca Tabu Reativa, a Busca Tabu sem o mecanismo de reação e a HMGC, de forma a avaliar a qualidade das heurísticas apresentadas. / [en] Data compression, speech coding, móbile telecommunications and error-corretion are some of the practical apllications of the covering codes study, an important field of coding theory. This work addresses two problems of covering codes: the classic code covering problem and the recent short code covering problem. It presents an application of Reactive Tabu Search (RTS) metaheuristic for the problems cited, the RTS is an important variation of the classic Tabu Search. Moreover, it presents a new heuristic technique for solving combinatorial optimization problems named Column Generation Improbement Heuristic (CGIH). It also presents an application of CGIH for the covering codes problems. The CGIH combines the delayed column generation, technique used to solve problems with a large number of decision variables (columns), and local search heuristics. A comparison of results obtained by the Reactive Tabu Search, the Tabu Search without the reaction mechanism and the CGIH is also presented in order to assess the effectivenss of the presented heuristics.
|
8 |
[en] A FRAMEWORK FOR VOCABULARY BUILDING HEURISTIC AND YOURS APPLICATION TO THE CAR SEQUENCING PROBLEM / [pt] UM FRAMEWORK PARA CONSTRUÇÃO DE VOCABULÁRIO E SUA APLICAÇÃO AO PROBLEMA DE SEQÜENCIAMENTO DE CARROSDARLINTON BARBOSA FERES CARVALHO 18 September 2007 (has links)
[pt] Construção de vocabulário é uma heurística para problemas
de otimização
combinatória que propõe identificar porções de boas
soluções e recombiná-las de modo a intensificar a busca em
regiões do espaço de soluções identificadas como
promissoras. A técnica de construção de vocabulário pode
ser
aplicada de diversas maneiras na resolução de problemas.
Para facilitar a
implementação e comparação de algoritmos de um mesmo
domínio, a tecnologia de frameworks é uma solução que já
demonstrou ser muito eficaz. O
objetivo deste trabalho é desenvolver um framework para a
implementação
de heurísticas baseadas em construçao de vocabulário. O
desenvolvimento
foi fundamentado em extensa revisão bibliográfica sobre a
técnica e em boas
práticas de engenharia de software, como frameworks
orientados a objetos
e padrões de projeto. Como um estudo de caso, foram
geradas aplicações
a partir do framework para a resolução do problema de
seqüenciamento da
produção de carros, que é um problema combinatório
proposto a partir de
necessidades reais da indústria / [en] Vocabulary building is a heuristic for solving
combinatorial optimization
problems, based on the identification of solution
fragments which are
common to good solutions and on their combination to
intensify the search
on promising regions of the solution space. This technique
can be vastly
applied on problem solving. The technology of frameworks
is an efficient
strategy to facilitate the implementation and comparison
of same domain
algorithms. The objective of this work is to develop a
framework for the
implementation of heuristics based on vocabulary building.
Its development
was based on a wide bibliographic revision about the
technique and good
software engineering practices, like oriented objects
frameworks and design
patters. We generated applications of the framework to
solve the car
sequencing problem, which is a combinatorial problem
proposed by real
requirements of the industry
|
9 |
[en] PRIMAL AND DUAL ALGORITHMS FOR THE UNCAPACITED P-MEDIAN PROBLEM / [pt] ALGORITMOS PRIMAIS E DUAIS PARA O PROBLEMA DAS P-MEDIANASGLEIDSON FONSECA SOARES 04 November 2009 (has links)
[pt] Uma facilidade é qualquer centro que presta serviços a um conjunto
de clientes. Pode ser, dentre outros, uma escola, uma fabrica ou um armazém. Problemas de localização de facilidades são problemas de otimização
combinatória que tratam da tomada de decisão relativa ao posicionamento
destes serviços, que devem otimizar algum critério pré-definido. As medidas
que usualmente são utilizadas para quantificar a qualidade de uma solução
para esta classe de problemas tem seus cálculos baseados em que clientes
são servidos por que facilidade. Uma conseqüência imediata é a forte relação entre os problemas de localização e os problemas de classificação de
dados (clusterização). Dentre os problemas de localização de facilidades amplamente
estudados esta o problema das p-Medianas (PMNC), objeto de
pesquisa desta dissertação. O PMNC tem como objetivo determinar quais
p facilidades devem ser abertas com o intuito de minimizar a soma das
distancias de cada cliente a facilidade aberta mais próxima do mesmo. O
PMNC é classificado como um problema NP - Difícil e é um dos problemas
centrais na classificação automática de dados (clusterização). Esta dissertação apresenta algoritmos primais, duais e exatos para tratamento do
PMNC, focando no desenvolvimento de algoritmos duais e exatos. Foram
implementadas cinco heurísticas construtivas e um método de busca local.
Além disto, foram propostos três novos métodos duais e um método exato.
Como resultado, analisamos um conjunto de técnicas para o tratamento do
problema. A escolha da melhor técnica é fortemente dependente da configuração da instancia tratada. Foi obtido o ótimo para algumas instancias e
para as demais a diferença entre o valor dos limites inferior e superior nos
melhores casos não ultrapassam 3%. / [en] A facility is any center that offers services to a set of clients. It
may be, among others, a school, a factory or a depot. Facility location
problems are combinatorial optimization problems that handle decisionmaking
in respect to the positioning of those services, optimizing some
defined criteria. The measures often used to assess the quality of a solution
for this class of problems relate to which clients are served by which facility.
An immediate consequence is the strong relationship between location
problems and data clustering. One of the widely studied facility location
problems is the uncapacited p-median problem (UPM), the main subject of
this thesis. Given a set of possible facility locations, the UPM consists in
determining a subset of locations at which the facilities shall be established,
minimizing the sum of distances from each client to its closest open facility.
The UPM belongs to the class of NP-hard problems and is a central problem
of data clustering. This thesis presents primal, dual and exact algorithms
for approaching the UPM, focusing on the development of dual and exact
algorithms. Five constructive heuristics and one local search method were
implemented. Furthermore, three new dual methods and one exact method
were proposed. The result is the analysis of a set of techniques to solve
the problem. The choice of best technique is strongly dependent of the
configuration of the treated instance. We obtained the optimum for some
instances and for others the difference between the value of the lower and
upper bounds in the best cases do not exceed 3%.
|
10 |
[en] HEURISTICS FOR THE NETWORK DESIGN PROBLEM WITH DISCRETE COST FUNCTIONS / [pt] HEURÍSTICAS PARA O PROJETO DE REDES COM FUNÇÕES DE CUSTO DISCRETASDANIEL ALOISE 28 June 2005 (has links)
[pt] Problemas de multifluxos surgem como modelos básicos no
contexto de várias aplicações de fluxos em redes, tais
como redes de telecomunicações, redes de transporte e
logística. Em tais aplicações, os fluxos que atravessam a
rede compartilham simultaneamente os mesmos recursos
disponíveis e são definidos por suas próprias restrições.
A cada uma das arestas ligando os pontos da rede está
associado um custo, fixo ou proporcional à sua utilização.
Este trabalho trata problemas de projeto de redes
multifluxos, em que os custos estão associados às
capacidades instaladas nas arestas. Particularmente, será
estudado o caso em que a função de custo nas arestas
possui o comportamento de uma função escada crescente e
descontínua, para o qual métodos exatos de resolução são
ineficientes. Métodos heurísticos são propostos para a
resolução aproximada do problema e sintetizados em um
algoritmo de multi-partida com memória adaptativa. Um
mecanismo de intensificação, conhecido na literatura como
construção de vocabulário, é também explorado e aplicado.
Finalmente, experimentos computacionais são realizados e o
método de resolução proposto é analisado quanto aos seus
resultados e os resultados obtidos pelo método de
resolução proposto são analisados. O método obtém as
melhores soluções conhecidas para algumas instâncias da
literatura. / [en] Multicommodity flow problems arise widely as basic models
in the context of network flows applications such as
telecommunication networks, transportation problems, and
logistic. In these applicatons, the flows that cross the
networks share the same avaiable resources simultaneously
and are defined by their own constraints. Each edge
connecting two nodes in the network has an associated cost
that is either fixed or proportional to its use. This work
focuses on a network design problem in which the cost are
associated with the capacities installed in the edges.
Particularly, the network design problem studied has
discrete and step increasing cost functions on the edges,
for which exact methods are inefficient. Heuristics are
proposed for the approximate memory algorithm. An
intensification mechanism, known in the literature as
vocabulary building, is also explored and applied.
Finally, computational experiments are performed and the
results obtained with the proposed solution method are
evaluated. The method obtains the best known solutions for
some instances in the literature.
|
Page generated in 0.0507 seconds