[pt] Este trabalho emprega conceitos e ferramentas de Teoria das Categorias e Teoria de Topoi para construir um modelo matemático de problemas, reduções entre problemas, espaços e estratégias de busca heurística. Mais precisamente, uma estratégia de construção de espaços de busca é representada por um funtor de uma certa categoria de problemas para uma certa categoria de florestas. A coleção de todos estes funtores forma um topos, um modelo específico equipado com uma lógica interna própria. Esta lógica interna é usada, então, para definir estratégias de busca e heurísticas em Teoria Local dos Conjuntos. Possíveis aplicações do trabalho incluem (1) a especificação lógica e a classificação de heurísticas e meta-heurísticas usadas na prática e (2) uma versão mais abstrata e geral de resultados específicos relacionando a estrutura de problemas com métodos de resolução adequados. / [en] This work employs concepts and tools from Category Theory and Topos Theory to construct a mathematical model for problems, reductions between problems, heuristic search spaces and strategies. More precisely, a search space construction strategy is represented by a functor from a certain category of problems to a certain category of forests. The collection of all such functors forms a topos, a specific model equipped with its own internal logic. This internal logic is then used to define search satrategies and heuristics in Local Set Theory. Possible applications of this work include (1) the logical specification and classification of heuristics and metaheuristics used in pratice and (2) a more abstract and general rendering of specific results relating the structure of problems to adequate problem-solving methods.

[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.

Orientador: José Carlos Miguel / Banca: Cyntia Graziella Guizelim Simões Girotto / Banca: Paulo César de almeida Raboni / Resumo: Este trabalho teve como objetivos a análise das heurísticas envolvidas numa experiência de ensino por meio da perspectiva metodológica da resolução de problemas e a análise da relação dos alunos do Ensino Médio com a disciplina Matemática. À luz da Teoria Histórico-Cultural, este trabalho pode contribuir para análise da subjetividade dos processos de formação de conceitos, dos modos de pensar dos educandos face à aprendizagem Matemática, de sua criatividade e raciocínio lógico ao resolver problemas. A metodologia utilizada foi a pesquisa qualitativa. Os alunos, sujeitos da pesquisa, foram considerados ora como resolvedores, ora como propositores de problemas; os dados foram coletados, em aulas de Matemática, de Maio a Novembro de 2.007. Ao conhecer como a experiência e os conhecimentos específicos afetam a solução de um problema, analisei os resultados e conclui que a eficiência na sua resolução depende não somente da memória, das idéias prévias e estratégias, mas de todos esses processos enunciados que participam efetivamente da formação do conceito matemático. Também conclui que prevalece, ainda, entre os educandos, uma visão ingênua e marcada por mitos resistentes a respeito da Matemática, porém se mostraram criativos ao resolverem problemas e modificaram aspectos importantes na sua relação com esta disciplina após serem submetidos a aulas na perspectiva metodológica de resolução de problemas. Pode-se afirmar que a perspectiva mencionada anteriormente propicia o conhecimento da Matemática, conduz à formação dos conceitos e ao desenvolvimento da criatividade dos educandos. Em suma, faz-se necessária uma ampla revisão na prática pedagógica desenvolvida em Matemática, a fim de que esta contribua para que os educandos tornem-se sujeitos de transformações sociais. / Abstract: This paper had as the goal the analysis of heuristics involved in a teaching experience through the methodological perspective of the problems solving and the analysis of the relations from the high school students with the subject Mathematics. In the light the view of the Historical-Cultural Theory, this paper can contribute for the analysis of the subjectivity of the concept-formation processes, the learners’ ways of thinking when talking about the Math’s learning, their creativity and logical thinking while solving problems. The methodology applied was the qualitative research. The students, individuals of the research, were considered sometimes problem-solvers and other times problem-proposers; the data were collected, in Math classes, from May to November, 2.007. When we know how the experience and the specific knowledge affect the solving of a problem, I analyzed the results and concluded that the efficiency in this resolution depends not only memory, previous ideas and strategies, but through all these mentioned processes that effectively take part in the formation of the Math concept. I concluded that it prevails, yet, among the learners a naïve view and marked by resistant myths concerning to Math, but they showed themselves creative when solving problems and changed important aspects of their relation with this subject after being given classes in the methodological perspective of the problem solving. We can state that the perspective mentioned above provides the Math knowledge; it conducts to the formation of concepts and the development of the learners ׳ creativity. In short, it is necessary a large review on the pedagogical practice developed in Mathematics, so that this subject can contribute for the learners to become individuals from social transformations. / Mestre

Artificial Intelligence Planning is about acting in order to achieve a desired goal. Under incomplete information, the task of finding the actions needed to achieve the goal can be modelled as a search problem in the belief space. This task is costly, as belief space is exponential in the number of states, which is exponential in the number of variables. Good belief representations and heuristics are thus critical for scaling up in this setting. The translation-based approach to automated planning with incomplete information deals with both issues by casting the problem of search in belief space to a search problem in state space, where each node of the search space represents a belief state. We develop plan synthesis tools that use translated versions of planning problems under uncertainty, with partial or null sensing available. We show formally under which conditions the introduced translations are polynomial, and capture all and only the plans of the original problems. We study empirically the value of these translations. / La Planificación es la disciplina de Inteligencia Artificial que estudia los procesos de razonamiento necesarios para conseguir las acciones que logren un objetivo dado. En presencia de información incompleta, el problema de planificación puede ser modelado como una búsqueda en el espacio de estados de creencia, cada uno de ellos representando un conjunto de estados posibles. Este problema es costoso ya que el numero de estados de creencia puede ser exponencial en el número de estados, lo cual es exponencial en el número de variables del problema. El uso de buenas representaciónes de los estados y de heurísticas informadas resultan cruciales para escalar en este espacio de búsqueda. En esta tesis se presentan traducciones para planificación con información incompleta, que transforman el problema de búsqueda en el espacio de estados de creencia, en búsqueda en espacio de estados, donde cada nodo representa un estado de creencia. Hemos desarrollado herramientas para la generación de planes para el problema traducido, ya sea con percepción parcial o nula. A su vez, demostramos formalmente bajo qué circunstancias las traducciones son polinómicas, completas y correctas. La evaluación empírica remarca el valor de dichas traducciones

Orientador: Silvio Alexandre de Araujo / Banca: Reinaldo Morabito / Banca: Geraldo Nunes Silva / Resumo: O objetivo deste trabalho é estudar um caso particular dos problemas de corte e empacotamento, denominado Problema de Carregamento de Paletes do Produtor. Inicialmente, uma formulação proposta na literatura é avaliada com um pacote computacional. Posteriormente, as heurísticas lagrangiana e surrogate são estudadas e um método de atualização dos multiplicadores surrogate é adaptado para este problema. A importância em se estudar o Problema de Carregamento de Paletes do Produtor é que, devido à escala e extensão de certos sistemas logísticos, um pequeno aumento do número de produtos a serem carregados sobre cada palete pode resultar em economias substanciais. A motivação em se estudar o método de atualização surrogate proposto é que, além da adaptação do presente trabalho não ter sido realizada na literatura, uma posterior aplicação desta heurística em conjunto com um procedimento branch and bound poderá render melhores resultados que outras heurísticas. / Abstract: The aim of this work is studying a particular case of cutting and packing problem, so-called the Manufacturer's Pallet Loading Problem. Initially, a formulation proposed in the literature is evaluated with a computer package. Subsequently, the lagrangian and surrogate heuristics are studied and a method to update the surrogate multiplier is adapted for this problem. The importance of studying the manufacturer's pallet loading problem is that, due to the scale and scope of some logistics systems, a small increase in the number of products to be loaded on each pallet can result in substantial savings. The motivation of studying the proposed method of updating the surrogate multipliers is that, besides the adaptation of this work has not been carried out in the literature, further application of heuristics within a procedure branch and bound can yield better results than other heuristics. / Mestre

Using concepts of the socio-technical systems theory, this dissertation defines mathematically the problems of cooperative teams formation considering social and technical constraints separately, and then presents their computational complexity. Mainly, it is defined and studied the central problem in this work, which jointly considers social and technical requirements for creating teams of cooperative work, to be called FEST (Socio-Technical Teams Formation Problem). Two mathematical formulations and a meta-heuristic are proposed for FEST. One formulation uses a cubic number of variables and constraints, whereas the second one has a quadratic number of variables but an exponential number of constraints. The proposed heuristic is based on the Non-monotonic Simulated Annealing meta-heuristic with local search using swap-like operators. The correctness of both formulations is proved. A polynomial algorithm to separate the constraints of the second formulation is presented. It is proved that the two formulations provide the same linear programming bound, and valid inequalities to strengthen it are proposed. For the compact formulation, some classes of valid inequalities are shown to be facet-inducing under suitable hypotheses. Finally, it is statistically analyzed the performance of the presented formulations and meta-heuristic. Real and random generated instances are used in the computational experiments. / Utilizando conceitos da Teoria dos Sistemas SociotÃcnicos, este trabalho define matematicamente os problemas de formaÃÃo de equipes cooperativas considerando separadamente restriÃÃes sociais e tÃcnicas e apresenta a complexidade computacional dos mesmos. Sobretudo, à definido e estudado o problema central deste trabalho, que considera conjuntamente requisitos sociais e tÃcnicos para criaÃÃo de equipes de trabalho cooperativo, denominado FEST (Problema de FormaÃÃo de Equipes SociotÃcnicas). Duas formulaÃÃes matemÃticas e uma meta-heurÃstica para o FEST sÃo propostas. Uma formulaÃÃo utiliza um nÃmero cÃbico de variÃveis e restriÃÃes, enquanto a segunda formulaÃÃo possui um nÃmero quadrÃtico de variÃveis, mas um nÃmero exponencial de restriÃÃes. A meta-heurÃstica proposta à baseada no Simulated Annealing NÃo-MonotÃnico com busca local que usa operadores tipo swap. A corretude de ambas as formulaÃÃes à provada. Um algoritmo polinomial para separar as restriÃÃes da segunda formulaÃÃo à apresentado. Mostra-se que as duas formulaÃÃes fornecem o mesmo limite de programaÃÃo linear, e desigualdades vÃlidas para fortalecÃ-lo sÃo propostas. Para a formulaÃÃo compacta, algumas classes de desigualdades vÃlidas sÃo demonstradas indutoras de facetas sob hipÃteses apropriadas. Por fim, foi analisado estatisticamente o desempenho das formulaÃÃes e da meta-heurÃstica apresentadas. InstÃncias reais e geradas aleatoriamente sÃo usadas nos experimentos computacionais.

[pt] Na atualidade, as organizações públicas e privadas buscam otimizar seus processos de modo que, estes garantam a qualidade dos serviços e o retorno sobre o capital investido nas diversas operações que estão envolvidas. Com isso, as organizações que não se preocupam em desenhar seus processos com eficácia e eficiência, estarão sujeitas a falhas, onerando assim os custos de operação. O estudo em questão propõe uma política de atendimento às demandas de manutenção e a utilização de uma ferramenta de roteirização diária no desempenho das operações do setor de manutenção de uma universidade pública do estado de Minas Gerais. O Problema de Roteirização de Veículos (PRV), do inglês Vehicle Routing Problem (VRP), como é conhecido na literatura, é definido como o atendimento a pontos de demanda geograficamente dispersos, por intermédio de uma frota de veículos disponíveis que, em geral, partem e retornam a um depósito central. O PRV tem como objetivo encontrar rotas viáveis com um menor custo que respeite as restrições operacionais, como duração da jornada de trabalho, capacidade dos veículos, duração das rotas, entre diversas outras. No trabalho será proposta uma metodologia que sugere uma nova política de distribuição de profissionais e materiais necessários para realização dos atendimentos às demandas de manutenção das unidades internas e externas da universidade e faz uso de um software de solução do PRV para verificar o desempenho das políticas propostas. Os resultados do estudo para as estratégias propostas apresentaram reduções significativas, variando de 17,86 porcento a 66,27 porcento do custo mensal, além de oportunidades de ganhos operacionais frente ao cenário atual. Espera-se que o software de PRV seja utilizado na programação diária dos roteiros dos veículos do setor. / [en] Currently, public and private organizations seek to optimize their process-es in order to guarantee the quality of services and the return on capital invested in the various operations that are involved. As a result, organizations that are not concerned with designing their processes effectively and efficiently, will be sub-ject to failures, thus increasing operating costs. The study in question proposes a policy to meet maintenance demands and the use of a daily routing tool in the performance of operations in the maintenance sector of a public university in the state of Minas Gerais. The Problema de Roteamento de Veículos (PRV), from the English Vehicle Routing Problem (VRP), as it is known in the literature, is defined as the service to meet geographically dispersed demand points, through a fleet of available vehicles that, in general, depart and return to a central depot. The VRP aims to find viable routes at a lower cost that respects operational re-strictions, such as working hours, vehicle capacity, duration of routes, among others. In the work, a methodology will be proposed that suggests a new policy for the distribution of professionals and materials needed to fulfill the demands of maintenance of the university s internal and external units and makes use of a VRP solution software to verify the performance of the proposed policies. The results of the study for the proposed strategies showed significant reductions, varying from 17.86 percent to 66.27 percent of the monthly cost, in addition to opportunities for operational gains compared to the current scenario. It is expected that the VRP software will be used in the daily programming of the routes for vehicles in the sector.

[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.

Esta pesquisa trata da aplicação de meta-heurísticas baseadas em busca em vizinhança variável em problemas de operação de transportes. Desta forma, buscou-se encontrar problemas complexos durante a operação de sistemas de transportes, nas grandes cidades, que possam ser resolvidos com a aplicação de meta-heurística baseada em busca em vizinhança variável. Este trabalho aborda dois diferentes problemas de planejamento e operação de transportes. O primeiro problema abordado neste trabalho é o Problema de Programação da Tabela de Horários, de Veículos e de Tripulantes de Ônibus, no qual as viagens que comporão a tabela de horários, os veículos que executarão as viagens e as tripulações que operarão os veículos são alocadas simultaneamente e de maneira integrada. O segundo problema a ser abordado é o problema de distribuição física, o qual envolve o agrupamento e a alocação de entregas a uma frota de veículos visando minimizar o frete total. Uma abordagem para a modelagem matemática deste problema é modelar como um problema de bin-packing, com bins de tamanho variável unidimensional (do inglês Variable Sized Bin-Packing Problem - VSBPP), ou seja, uma generalização do tradicional problema de bin-packing no qual bins (veículos) de diferentes capacidades e custos estão disponíveis para a alocação de um conjunto de objetos (cargas), de modo que o custo total dos bins (veículos) utilizados seja mínimo. A outra abordagem proposta para o problema de distribuição física é modelar o problema como um problema de bin-packing, com bins de tamanho variável bidimensional (do inglês Bidimensional Variable Sized Bin-Packing Problem BiD-VSBPP). Assim sendo, trata-se de uma expansão do problema de bin-packing com bins de tamanho variável unidimensional (VSBPP), no qual bins (veículos) de diferentes capacidades (capacidade volumétrica e capacidade de carga) e custos estão disponíveis para a alocação de um conjunto de objetos (cargas), os quais possuem as dimensões peso e volume, de modo que o custo total dos bins (veículos) utilizados seja mínimo. Durante a realização deste trabalho, foi desenvolvido um programa computacional em C++, o qual implementa a meta-heurística Busca em Vizinhança Variável (VNS) e duas meta-heurísticas baseadas em VNS. São apresentados resultados de experimentos computacionais com dados reais e dados benchmarking. Os resultados obtidos comprovam a eficácia das meta-heurísticas propostas. / This work approaches variable neighborhood search meta-heuristic applicate on transport operation problems. This way, we sought find complex transport operation problems in large cities that can be solved with the variable neighborhood search meta-heuristic application. This work approaches two different transport planning and operation problems. The first problem approached in this paper is the Bus Timetable Vehicle Crew Scheduling Problem, in which timetabling, bus and crew schedules are simultaneously determined in an integrated approach. The second problem to be approached is the physical distribution problem which comprises grouping and assigning deliveries to a heterogeneous fleet of vehicles aiming to minimize the total freight cost. The problem can be mathematical modeled as one-dimensional Variable Sized Bin-Packing Problem (VSBPP), a generalization of the traditional bin-packing problem, in which bins (vehicles) with different sizes and costs are available for the assignment of the objects (deliveries) such that the total cost of the used bins (vehicles) is minimized. Another proposed approach to the problem of physical distribution is model as two dimensional Variable Sized Bin-Packing Problem (BiD-VSBPP). Therefore, it is an expansion of the bin-packing problem with bins variable-length-dimensional (VSBPP), in which bins (vehicle) of different capacity (capacity and load carrying capacity) and costs are available for allocation a set of objects (loads), which have the dimensions weight and volume, so that minimized the total cost of bins (vehicle). In this work, was developed a C++ software implemented, which was implemented a meta-heuristic Variable Neighborhood Search (VNS) and two others meta-heuristics based on VNS. Computational results for real-world problems and benchmarking problems are presented, showing the effectiveness of these proposed meta-heuristics.

Esta tese apresenta um estudo sobre modelagem computacional onde são aplicadas meta-heurísticas de otimização na solução de problemas inversos de transferência radiativa em meios unidimensionais com albedo dependente da variável óptica, e meios unidimensionais de duas camadas onde o problema inverso é tratado como um problema de otimização. O trabalho aplica uma meta-heurística baseada em comportamentos da natureza conhecida como algoritmo dos vagalumes. Inicialmente, foram feitos estudos comparativos de desempenho com dois outros algoritmos estocásticos clássicos. Os resultados encontrados indicaram que a escolha do algoritmo dos vagalumes era apropriada. Em seguida, foram propostas outras estratégias que foram inseridas no algoritmo dos vagalumes canônico. Foi proposto um caso onde se testou e investigou todas as potenciais estratégias. As que apresentaram os melhores resultados foram, então, testadas em mais dois casos distintos. Todos os três casos testados foram em um ambiente de uma camada, com albedo de espalhamento dependente da posição espacial. As estratégias que apresentaram os resultados mais competitivos foram testadas em um meio de duas camadas. Para este novo cenário foram propostos cinco novos casos de testes. Os resultados obtidos, pelas novas variantes do algoritmo dos vagalumes, foram criticamente analisados. / This thesis presents a study on computational modeling where optimization metaheuristics are applied to the solution of inverse radiative transfer problems in heterogeneous media: in one-layer media with space-dependent single scattering albedo, and two-layer media, where the inverse problem is formulated as an optimization problem. It is applied a metaheuristic based on the natural behavior of fireflies, known as the firefly algorithm. Initially, comparative studies of performance were made with two other classic stochastic algorithms. The results indicated that the choice of the firefly algorithm was appropriate. Then, it was proposed other strategies that have been inserted into the original firefly algorithm. A first case was proposed where all the strategies were investigated and tested. The strategies with the best results were investigated in other two different cases. All the three proposed cases involved one-layer media with space-dependent scattering albedo. The strategies have been tested and evaluated, and those which presented the best competitive results were then implemented for radiative problems in two-layer media. For this new scenario five test cases were investigated, and the results obtained with the new strategies developed in this work were critically analyzed.