Orientadores: Aurelio Ribeiro Leite de Oliveira, Carla Taviane Lucke da Silva Ghidini / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-20T05:01:05Z (GMT). No. of bitstreams: 1 Berti_LilianFerreira_M.pdf: 11222489 bytes, checksum: 8a581cf3762be9e96b4f77b7206e3112 (MD5) Previous issue date: 2012 / Resumo: Os métodos de pontos interiores têm sido amplamente utilizados para determinar a solução de problemas de programação linear de grande porte. O método preditor corretor, dentre todas as variações de métodos de pontos interiores, é um dos que mais se destaca, devido à sua eficiência e convergência rápida. Este método, em cada iteração, necessita resolver dois sistemas lineares para determinar a direção preditora corretora. Resolver estes sistemas lineares corresponde ao passo que requer mais tempo de processamento, devendo assim ser realizada de forma eficiente. Para resolver estes sistemas lineares a abordagem mais utilizada é a fatoração de Cholesky. No entanto, realizar a fatoração de Cholesky em cada iteração tem um alto custo computacional. Dessa forma, na busca de redução de esforços, precisamente, na redução do número de iterações foi desenvolvida a iteração continuada. Iteração continuada é uma iteração subsequente, realizada após o cálculo da direção preditora corretora, onde é determinada uma nova direção sem que seja necessário realizar uma nova fatoração de Cholesky. Os resultados computacionais dos testes realizados, principalmente em problemas de médio e grande porte mostraram que esta abordagem obtém bom desempenho em comparação com o método preditor corretor / Abstract: Interior point methods have been widely used in the solution of large linear programming problems. The predictor corrector method, among ali interior point variants, is one of mostly used due to its efficiency and convergence properties. This method needs the solution of two linear systems to determine the predictor corrector direction, in each iteration. Solving such systems corresponds to the step which requires more processing time. Therefore, it should be done efficiently. The most common approach to solve the linear systems is the Cholesky factorization, demanding in each iteration a high computacional effort. Thus, in search of effort reduction, in particular, to reduce the iterations number continued iteration was developed. The continued iteration is a subsequent iteration performed after the predictor corrector direction is computed, where a new direction is calculated without need to of Cholesky refactorization. The numerical tests show that the continued iteration performs better in comparison with the preditor corretor method / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada

Orientador: Edmundo Roberto Mauro Madeira / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-21T15:49:43Z (GMT). No. of bitstreams: 1 Genez_ThiagoAugustoLopes_M.pdf: 2286902 bytes, checksum: 384fd51ae0278ea91a914ba4b047c6cc (MD5) Previous issue date: 2012 / Resumo: Computação em nuvem oferece utilidades computacionais de acordo com a necessidade do usuário através do modelo "pago-pelo-uso". Usuários podem fazer o uso da nuvem através dos provedores de software (Software as a Service - SaaS), de plataforma (Plataform as a Service - PaaS) ou de infraestrutura (Infrastructure as a Service - IaaS). Computação em nuvem esta atualmente sendo muito utilizada. ...Observação: O resumo, na íntegra, poderá ser visualizado no texto completo da tese digital / Abstract: Cloud computing offers utility computing according to the user's needs in a "pay-per-use" basis. Customers can make use of the cloud via Software as a Service (SaaS), Plataform as a Service (PaaS), or Infrastructure as a Service (IaaS) providers. ...Note: The complete abstract is available with the full electronic document / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Nelson Luis Saldanha da Fonseca / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-21T15:43:47Z (GMT). No. of bitstreams: 1 Alkmim_GustavoPrado_M.pdf: 588888 bytes, checksum: 595d027838b31a65d91822b3b1ce04e6 (MD5) Previous issue date: 2012 / Resumo: A virtualização de redes é uma tecnologia promissora para ser utilizada como base na Internet do futuro, pois permite a introdução de novas funcionalidades nos elementos da rede a baixo custo. Uma das questões em virtualização de redes é como realizar o mapeamento eficiente de redes virtuais em substratos de redes, que é um problema de mapeamento é NP-Difícil. As soluções existentes na literatura ignoram várias características essenciais para ambientes reais a fim de que o problema possa ser resolvido em um intervalo de tempo razoável. Na presente dissertação, propõem-se oito algoritmos baseados em programação linear inteira 0-1 para resolver o problema de mapeamento que consideram diversas características realistas que não são incluídas em outras modelagens existentes. Seis dos algoritmos minimizam a largura de banda alocada e dois dos algoritmos minimizam o consumo de energia no substrato. Os algoritmos aproximativos propostos são capazes de determinar o mapeamento de redes virtuais em substratos de grande porte em poucos segundos e de encontrar soluções com qualidade, o que possibilita a adoção dos mesmos em mecanismos de controle de admissão em tempo real / Abstract: Network virtualization is a promising technology to be employed in the future Internet, since it allows the introduction of new functionalities in network elements at low cost. One of the open questions in network virtualization is how to perform an efficient mapping of virtual networks in the substrate, which is NP-Hard problem. Existing solutions in the literature ignore several characteristics of real-world environments in order to solve the problem in a reasonable time frame. This paper introduces eight algorithms to solve the mapping problem that are based on 0-1 integer linear programming. One of the main contribution is the consideration of realistic assumptions to the problem that are not considered by others in the literature. Six algorithms minimize the allocated bandwidth and the two others minimize the power consumption in the substrate. The proposed approximative algorithms can map virtual networks in large substrates in few seconds and they find accurate solutions, which make them adequate to be employed in real-time admission control / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientadores: José Raimundo de Oliveira, Takaaki Ohishi / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia / Made available in DSpace on 2018-08-20T08:30:14Z (GMT). No. of bitstreams: 1 RuestaChangman_CarlosAlberto_M.pdf: 2325265 bytes, checksum: f4a566972553d710e7f8258ee572e828 (MD5) Previous issue date: 2012 / Resumo: Este trabalho apresenta um modelo de planejamento da produção de uma indústria pesqueira. A indústria pesqueira é um segmento importante na economia de vários países. Em particular, as empresas voltadas para a exportação enfrentam um ambiente mais complexo, seja pela competição com outras empresas, seja pelo enfrentamento contra as forças do mercado internacional que ditam os preços e as condições de negociação. O cenário tratado neste trabalho é de uma empresa que processa diferentes tipos de pescado e atende diferentes mercados em nível mundial. A oferta de pescados apresenta sazonalidade anual e, por isso, a empresa precisa planejar a aquisição e o processamento de cada tipo de pescado em função da sua disponibilidade, de seus custos, dos preços no mercado global e da capacidade de processamento. A metodologia proposta considera um horizonte de planejamento de no mínimo doze meses à frente para considerar a sazonalidade de oferta de pescado, e divide o planejamento em duas etapas. A primeira etapa é de planejamento anual com discretização mensal. Aqui é definido o montante mensal a ser adquirido de cada pescado e o montante a ser exportado para cada mercado. Na segunda etapa é realizado o planejamento do processamento diário de pescado, quando são definidas a distribuição de pescado nas linhas de processamento e a distribuição do pescado já embalado nos refrigradores. A abordagem adotada basea-se em modelos de Programação Linear e Programação Linear Mista / Abstract: This work presents a production planning model in fish processing industry. In many countries the fishing industry represents an important economic sector, mainly for firms involved with exportation and complex environments of competition and negotiation. In these industries, an important decision is about the production planning, which must consider the market conditions and raw material offer. The scenario studied in this work is a company that processes different types of fish and sells to different markets worldwide. The fish supply has annual seasonality, and therefore the company needs to plan the acquisition and processing of each type of fish depending on their availability, costs, international prices and processing capacity. The proposed methodology considers a planning horizon of at least twelve months to consider the fish supply seasonality and divides the planning into two steps. The first step is annual planning with monthly discretization where is defined the amount to be monthly purchased and the amount of each fish to be exported to each market. In the second step is done the daily processing fish planning, where are defined the distribution of fish processing lines and the distribution of freezing fish already packed. The approach is based on models of Linear Programming techniques and Mixed Linear Programming / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

Orientador: Antonio Carlos Bannwart / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecanica / Made available in DSpace on 2018-07-25T04:21:28Z (GMT). No. of bitstreams: 1 Higa_Marcio_M.pdf: 7914219 bytes, checksum: c0df34dbad62f75065ad547646e7c5c8 (MD5) Previous issue date: 1999 / Resumo: Através dos métodos do "pinch-point" e da programação linear, foram realizadas diversas simulações e análises térmicas de uma planta típica de produção de açúcar e álcool, visando a máxima recuperação de calor e a redução do consumo de vapor. As simulações foram divididas em três grupos. No primeiro, usou-se o método do "pinch-point" para investigar basicamente a planta de produção de açúcar, analisando também a influência de diversas alternativas (eliminação de sangrias de vapor entre estágios de evaporação, número de efeitos de evaporação, compressão mecânica do vapor do último estágio de evaporação, área e número de trocadores de calor). No segundo grupo, na mesma planta, empregou-se o método de programação linear, a fIm de determinar a distribuição otimizada das sangrias de vapor para pré-aquecimento do caldo. No terceiro grupo de análises, considerando também o consumo na produção de álcool, retomou-se ao método do "pinch-point", onde as sangrias foram primeiramente maxirnizadas nos últimos estágios de evaporação e em seguida ajustadas para satisfazer as áreas dos evaporadores existentes na planta básica. Para tanto, foi desenvolvido um programa de computador específico que permite a simulação do efeito das diversas variáveis, inclusive a razão de produção açúcar/álcool. Diversas alternativas de grande impacto no consumo de vapor são apresentadas / Abstract: Using pinch technology and linear prograrnrning, several simulations of thermal analysis of a typical sugar cane plant and alcohol production were performed. The objective was the maximum heat recovery and the reduction of steam consumption. The simulations were divided into three groups. In the fIrst, pinch technology was applied to analyze only the sugar cane basic plant production and the influence of several alte~natives (elimination of vapor bleed between evaporator effects, number of evaporator effects, mechanical compression of vapor in the last effect of evaporation, area and number of heat exchangers). In the second group, use was made of linear prograrnrningin the same plant to determine the optimized confIguration of vapor bleeds for juice preheating. In the third group, pinch technology was again applied, including the consumption from alcohol production. First of ali, the maximum vapor bleed was assumed at the last effects of evaporation, then adjusted to adapt to the evaporator areas of basic plant. Therefore, a specifIc computer programming was developed to simulate the several variable, including the ratio of production sugar/alcohoL Several alternatives of deep impact in steam consumption were investigated. / Mestrado / Termica e Fluidos / Mestre em Engenharia Mecânica

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

Le présent travail propose d’étudier les problèmes de coordination en se plaçant dans un contexte de planification decentralisée, partant du postulat qu’une gestion centralisée n’est pas pertinente au regard des enjeux de confidentialité qu’affichent chaque partenaire d’une même chaîne logistique. Plus précisément, l’objectif du travail réside dans l’élaboration d’un protocole de négociation tendant à rechercher une solution de planification « gagnant-gagnant », i.e. l’élaboration de plans satisfaisant le producteur (clients du service transport) tout en augmentant le profit des prestataires de transport. La méthodologie suivie pour le développement de ce travail s’articule autour de deux étapes. Le contexte de planification decentralisée des activités d’un producteur avec celles d’un opérateur de transport est dans un premier temps étudié. L’objectif est de caractériser les modèles de programmation linéaire et les raisonnement nécessaires au développement du protocole de coordination et à la mise en œuvre de la simulation du comportement des deux partenaires, de manière à mettre en exergue les facteurs influant la performance globale. L’expérimentation conduite dans ce cadre s’appuie sur la notion de plans d’expériences. Le problème est dans un second temps étendu à la coordination des activités de plusieurs opérateurs de transport avec un producteur. Dans ce nouveau contexte, la résolution du problème de répartition de charges de transport entre les différents acteurs est intégrée dans le processus de négociation. Les modèles et protocole ainsi enrichis sont validés sur la base de plusieurs cas de tests. / The present work aims to study the coordination problems in the context of decentralized planning, based on the postulate that centralized management is not suitable regarding the confidentiality objectives of each partner of the same supply chain. More specifically, the aim of this work is to develop a negotiation protocol seeking to reach a “win-win” planning solution, i.e. the development of plans satisfying the producer (the customer of transportation service) while increasing profit of transport operators. The development methodology of this work contains two phases. The context of decentralized planning of activities of one producer and one transport operator is firstly studied. The main objective is to characterize the linear programming models and the key determinants to develop the coordination protocol and also to implement the simulation of both partners in order to identify the factors affecting the overall performance. The conducted experimentation in this context is based on the concept of the design of experiments. The problem is extended in a second phase to the coordination of several transport operators with one producer. In this new context, the problem of allocating transport load to different transport operators is integrated into the negotiation process. The complemented models and protocol are validated based on test cases.

This report gives the reader a detailed description of a computer engineering master thesis work done at the company Netlight Consulting AB. Netlight Consulting AB is a growing IT consulting company based in Stockholm with offices in major cities across Europe. One of their key success factors is their focus on personal and professional development amongst all employees. An essential part of this development program consist of reoccurring evaluation periods, where every employee receives written constructive feedback from some of their co-workers. This thesis’ focus lies in improving the algorithm that organizes which employee should evaluate who. The original algorithm turned out to harbor a number of flaws, e.g. it was not always able to deliver a satisfactory matching where every participant received the minimum number of evaluations.   In this thesis a new matching algorithm has been implemented that is platform independent and that facilitates future modifications with accessible source code written in Java. The input data for the matching algorithm, i.e. the set of all potential evaluation pairs, is of importance to obtain satisfactory matching results. The number of potential evaluation pairs determines the number of possible matching combinations, which in turn increases the probability to find a satisfactory matching. In this thesis the input data has been extended by utilizing a data mining technique known as SONAR. Two different data mining sources were evaluated, and one of them is shown to extend the number of potential evaluation pairs in the matching input by 20%. Finally, a new feature to support assignment of different evaluation sizes was added to the matching algorithm.

The interdisciplinary field of systems biology has evolved rapidly over the last few years. Different disciplines have contributed to the development of both its experimental and theoretical branches.Although computational biology has been an increasing activity in computer science for more than a two decades, it has been only in the past few years that optimization models have been increasingly developed and analyzed by researchers whose primary background is Operations Research(OR). This dissertation aims at contributing to the field of computational biology by applying mathematical programming to certain problems in molecular biology.Specifically, we address three problems in the domain of Genome Wide Association Studies}:(i) the Pure Parsimony Haplotyping Under uncertatind Data Problem that consists in finding the minimum number of haplotypes necessary to explain a given set of genotypes containing possible reading errors; (ii) the Parsimonious Loss Of Heterozygosity Problem that consists of partitioning suspected polymorphisms from a set of individuals into a minimum number of deletion areas; (iii) and the Multiple Individuals Polymorphic Alu Insertion Recognition Problem that consists of finding the set of locations in the genome where ALU sequences are inserted in some individual(s).All three problems are NP-hard combinatorial optimization problems. Therefore, we analyse their combinatorial structure and we propose an exact approach to solution for each of them. The proposed models are efficient, accurate, compact, polynomial-sized and usable in all those cases for which the parsimony criterion is well suited for estimation. / Option Informatique du Doctorat en Sciences / info:eu-repo/semantics/nonPublished

In recent years, the popularity of graph databases has grown rapidly. This paper focuses on single-graph as an effective model to represent information and its related graph mining techniques. In frequent pattern mining in a single-graph setting, there are two main problems: support measure and search scheme. In this paper, we propose a novel framework for constructing support measures that brings together existing minimum-image-based and overlap-graph-based support measures. Our framework is built on the concept of occurrence / instance hypergraphs. Based on that, we present two new support measures: minimum instance (MI) measure and minimum vertex cover (MVC) measure, that combine the advantages of existing measures. In particular, we show that the existing minimum-image-based support measure is an upper bound of the MI measure, which is also linear-time computable and results in counts that are close to number of instances of a pattern. Although the MVC measure is NP-hard, it can be approximated to a constant factor in polynomial time. We also provide polynomial-time relaxations for both measures and bounding theorems for all presented support measures in the hypergraph setting. We further show that the hypergraph-based framework can unify all support measures studied in this paper. This framework is also flexible in that more variants of support measures can be defined and profiled in it.