Orientador: Hermes Renato Hildebrand / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Artes / Made available in DSpace on 2018-08-13T04:23:41Z (GMT). No. of bitstreams: 1 Cuperschmid_AnaReginaMizrahy_M.pdf: 3728417 bytes, checksum: 119719713ed847d7e7e4bdd5ed4b5816 (MD5) Previous issue date: 2008 / Resumo: Os jogos de computador suscitam uma série de considerações, por apresentarem problemas diferentes dos outros tipos de softwares. Neles, os fatores chave para o sucesso são o entretenimento, o prazer e a diversão, que dependem de uma boa usabilidade, fatores esses totalmente vinculados e intimamente relacionados. Este trabalho apresenta uma listagem de heurísticas que permitem avaliações de usabilidade e entretenimento, aqui denominadas de jogabilidade. Esta pesquisa teve, como objetivo, investigar, através da literatura e de estudos de casos, os jogos de computador e elaborar uma lista compreensível de heurísticas de jogabilidade. Para isso foi necessária uma vasta exploração da bibliografia sobre jogos, ergonomia e usabilidade, para, em seguida, realizar avaliações heurísticas de jogabilidade. A análise dos resultados obtidos nos leva a crer que as heurísticas de jogabilidade podem servir como um ponto de partida para uma avaliação de jogos e como uma contribuição para a massa de conhecimentos existentes sobre o assunto. Enxergamos a necessidade de continuar validando as heurísticas levantadas por meio de avaliações de mais jogos, alterando-as, se necessário. / Abstract: Computer games have a series of problems and considerations that differ from other kinds of software. Their key factors for success are: entertainment, fun and pleasure, which depend on good usability. These factors are totally linked and intimately related. This work presents a heuristics list that permits an evaluation of usability and entertainment, here called playability. The objective of this research was to investigate computer games through literature and case studies and elaborate a comprehensive heuristics list of playability. It was necessary a vast exploration of the bibliography of game, ergonomic criteria for the evaluation of human-computer interfaces and usability, and then, perform a heuristic evaluation of playability. The analyses of the final results makes us believe that playability heuristics may be used as a starting point for assessing games and as contribution for the amount of knowledge available about the subject study. We see the need to keep validating the heuristics brought up in this study by assessing more games and updating them if necessary. / Mestrado / Mestre em Artes

Orientadores: Christiano Lyra Filho, Celso Cavellucci / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-13T17:12:20Z (GMT). No. of bitstreams: 1 Bacalhau_EduardoTadeu_M.pdf: 2312425 bytes, checksum: c300ba31a847eef9ba5343cfd6548c0f (MD5) Previous issue date: 2009 / Resumo: O trabalho aborda a alocação ótima de recursos para manutenção de redes de distribuição de energia elétrica. O modelo matemático do problema procura representar os componentes das redes, suas inter-relações para operação das redes, suas contabilidades e mudanças de condições por ações de manutenções. O objetivo do processo de otimização é reduzir os custos de manutenção sob restrições de operação com determinados níveis de contabilidade, ao longo de um horizonte de planejamento. As melhores estratégias de manutenção podem ser obtidas através da solução de um problema de otimização combinatória inteiro misto, com variáveis discretas e contínuas. A principal contribuição do trabalho é o desenvolvimento de meta-heurísticas híbridas que possam encontrar estratégias de manutenções de melhor qualidade, considerando-se abordagens anteriores para o problema. São desenvolvidas três meta-heurísticas híbridas, que utilizam diferentes formas de articulações de Busca em Profundidade, Busca em Largura e Simulated Annealing. Estudos de casos realizam comparações entre as três abordagens e um algoritmo genético híbrido. A análise dos resultados permite destacar as qualidades de cada uma das abordagens. / Abstract: This work is concerned with the optimal allocation of maintenance resources on electric power distribution networks. The mathematical model represents the main components of the network, their interrelationships for the operation of the network, their reliabilities and the changes in condition due to maintenance procedures. The objective of the optimization process is the reduction of maintenance costs under constraints of reliability, during a given planning period. The best maintenance strategies can be obtained from the solution of a mixed integer combinatorial optimization problem, with continuous and discrete variables. The main contribution of the present work is the development hybrid heuristics that are able to obtain better solutions for the problem, with respect to previous approaches. Three hybrid heuristics are developed, based on the depth first, breath first and simulated annealing state space searches. Case studies compare the three approaches with a hybrid genetic algorithm previously proposed to address the problem. The analysis of results highlights the benefits of each approach. / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientador: Fernando Jose Von Zuben / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-14T03:50:32Z (GMT). No. of bitstreams: 1 Castro_PabloAlbertoDalbemde_D.pdf: 3372739 bytes, checksum: 137d410adffc7c418667750c4e3326de (MD5) Previous issue date: 2009 / Resumo: Sistemas imunológicos artificiais (SIAs) e modelos gráficos probabilísticos são duas importantes técnicas para a construção de sistemas inteligentes e tem sido amplamente exploradas por pesquisadores das mais diversas áreas, tanto no aspecto teórico quanto pratico. Entretanto, geralmente o potencial de cada técnica é explorado isoladamente, sem levar em consideração a possível cooperação entre elas. Como uma primeira contribuição deste trabalho, é proposta uma metodologia que explora as principais vantagens dos SIAs como ferramentas de otimização voltadas para aprendizado de redes bayesianas a partir de conjuntos de dados. Por outro lado, os SIAs já propostos para otimização em espaços discretos e contínuos correspondem a meta-heurísticas populacionais sem mecanismos para lidarem eficientemente com blocos construtivos, e também com poucos recursos para se beneficiarem do conhecimento já adquirido acerca do espaço de busca. A segunda contribuição desta tese é a proposição de quatro algoritmos que procuram superar estas limitações, em contextos mono-objetivo e multiobjetivo. São substituídos os operadores de clonagem e mutação por um modelo probabilístico representando a distribuição de probabilidades das melhores soluções. Em seguida, este modelo é empregado para gerar novas soluções. Os modelos probabilísticos utilizados são a rede bayesiana, para espaços discretos, e a rede gaussiana, para espaços contínuos. A escolha de ambas se deve às suas capacidades de capturar adequadamente as interações mais relevantes das variáveis do problema. Resultados promissores foram obtidos nos experimentos de otimização realizados, os quais trataram, em espaços discretos, de seleção de atributos e de ensembles para classificação de padrões, e em espaços contínuos, de funções multimodais de elevada dimensão. Palavras-chave: sistemas imunológicos artificiais, redes bayesianas, redes gaussianas, otimização em espaços discretos e contínuos, otimização mono-objetivo e multiobjetivo / Abstract: Artificial immune systems (AISs) and probabilistic graphical models are two important techniques for the design of intelligent systems, and they have been widely explored by researchers from diverse areas, in both theoretical and practical aspects. However, the potential of each technique is usually explored in isolation, without considering the possible cooperation between them. As a first contribution of this work, it is proposed an approach that explores the main advantages of AISs as optimization tools applied to the learning of Bayesian networks from data sets. On the other hand, the AISs already proposed to perform optimization in discrete and continuous spaces correspond to population-based meta-heuristics without mechanisms to deal effectively with building blocks, and also having few resources to benefit from the knowledge already acquired from the search space. The second contribution of this thesis is the proposition of four algorithms devoted to overcoming these limitations, both in single-objective and multi-objective contexts. The cloning and mutation operators are replaced by a probabilistic model representing the probability distribution of the best solutions. After that, this model is employed to generate new solutions. The probabilistic models adopted are the Bayesian network, for discrete spaces, and the Gaussian network, for continuous spaces. These choices are supported by their ability to properly capture the most relevant interactions among the variables of the problem. Promising results were obtained in the optimization experiments carried out, which have treated, in discrete spaces, feature selection and ensembles for pattern classification, and, in continuous spaces, multimodal functions of high dimension. Keywords: artificial immune systems, Bayesian networks, Gaussian networks, optimization in discrete and continuous domains, single-objective and multi-objective optimization / Doutorado / Engenharia de Computação / Doutor em Engenharia Elétrica

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-08T14:02:44Z (GMT). No. of bitstreams: 1 Santos_RafaelFranciscodos_M.pdf: 909075 bytes, checksum: b4d466696cb4f640a50eca288dfccd5c (MD5) Previous issue date: 2006 / Resumo: Nesta dissertação propomos um uso mais geral dos Cortes Canônicos (CCs) introduzidos por Balas e Jeroslow ([2]) no método de Ramificação Local (RamLoc) de Fischetti e Lodi ([6]). A ramificação local é uma heurística de propósito geral para Programação Inteira Mista (MIP) que explora vizinhanças definidas através da adição de inequações lineares ao modelo original. Estas inequações determinam subproblemas que são computados mais rapidamente pelos resolvedores de MIP. Uma análise da execução da RamLoc indicou que, em algumas situações, ela acrescenta cortes de ramificação local muito superficiais (i.e.,que descartam poucas soluções) e que estes cortes ocorrem com grande freqüência. Como os cortes de ramificações locais de Fischetti e Lodi são casos especiais dos CCs para programação inteira 0?1, n'os propomos a incorporação de CCs mais profundos (i.e.,que descartam mais soluções) à RamLoc. Executamos o algoritmo resultante sobre 25 das 29 instâncias testadas em [6] e obtivemos melhores resultados do aqueles alcançado pela RamLoc original e pelo resolvedor comercial de MIP XPRESS com seus parâmetros default. Uma outra investigação que empreendemos foi a inclusão dos CCs na heurística para modelos gerais de programação inteira mista RINS ([3]). Esta heurística surgiu durante o desenvolvimento desta dissertação e apresentou um bom desempenho. Realizamos alguns testes com as mesmas instâncias sobre as quais a RamLoc foi executada e obtivemos resultados promissores. Por fim, além da utilização dos CCs em heurísticas, criamos uma estratégia de ramificação que pode ser embutida nos algoritmos de branch-and-cut dos resolvedores de MIP. Denominamos esta estratégia de dive branching e a implementamos no resolvedor XPRESS. Em experimentos conduzidos com o mesmo conjunto de instâncias anteriores, obtivemos resultados de melhor qualidade do que aqueles produzidos pelo XPRESS com seus parâmetros default / Abstract: In this dissertation we propose a broader usage of the Canonical Cuts (CC) introduced by Balas and Jeroslow ([2]) in the Local Branching method (LB) of Fischetti and Lodi ([6]). The LB is a general purpose heuristic for Mixed Integer Programming (MIP) that explores neighborhoods defined by the addition of linear inequalities to the original model. These inequalities determine subproblems that are computed more quickly by MIP solvers. An analysis of the execution of LB indicated that, in some situations, it adds local branching cuts that are too superficial (i.e., chopping off few solutions) and that these cuts happen very often. Since the local branching cuts of Fischetti and Lodi are special cases of CCs for 0?1 integer programming, we propose to incorporate deeper CCs (i.e, chopping of more solutions) to LB. We executed the resulting algorithm on 25 out of the 29 instances tested in [6] and we obtained better results than those attained by the original LB and by the XPRESS commercial MIP solver under default settings. Another research that we carried out was the inclusion of CC to the RINS heuristics for general mixed integer programs ([3]). This heuristic appeared during the development of this dissertation and showed a good performance. We carried out some tests with the same instances on which LB was tested and the results are promising. Finally, besides using the CCs in heuristics, we created a branching strategy that can be embedded to the branch-and-cut algorithms of the MIP solvers. We called it dive branching and implemented it in the XPRESS solver. In experiments with the same set of instances as before, we obtained results of better quality than those produced by XPRESS with default settings / Mestrado / Mestre em Ciência da Computação

Orientadores: Carlos Alberto de Castro Junior, Ruben Augusto Romero Lazaro / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-14T21:34:08Z (GMT). No. of bitstreams: 1 Guimaraes_MarcosAntoniodoNascimento_D.pdf: 1387088 bytes, checksum: 36029ed51311645d24da08d56bb91409 (MD5) Previous issue date: 2009 / Resumo: O objetivo desse trabalho de pesquisa é desenvolver ferramentas computacionais eficientes para a otimização da operação de sistemas de distribuição de energia elétrica. A principal contribuição apresentada é fornecer uma metodologia para redução de perdas de potência ativa, baseada em reconfiguração e alocação de bancos de capacitores fixos e automáticos. É possível encontrar na literatura várias propostas baseadas nos mais diversos tipos de algoritmos, entretanto, na maioria dos casos as propostas apresentadas propõem o atendimento a um único objetivo. A proposta apresentada neste trabalho contempla a otimização dos objetivos de forma conjunta, usando um único algoritmo, de forma a tirar o máximo proveito dos recursos já instalados no sistema. Mostra-se que é possível obter uma economia significativa no custo de instalação de bancos de capacitores, utilizando a reconfiguração como ferramenta adicional. Um dos maiores desafios a ser enfrentado, no entanto, refere-se ao tamanho do espaço de busca, que nesse caso cresce consideravelmente. Para a resolução do problema optou-se pelo algoritmo genético, que é uma metaheurística já consagrada na resolução de problemas de grande complexidade. No decorrer do trabalho foram desenvolvidas diversas ferramentas e operadores genéticos especiais que tornaram possível a obtenção de excelentes resultados com baixo custo computacional. Adicionalmente, foi desenvolvido um algoritmo de Simulated Annealing que, a partir da melhor configuração obtida pelo algoritmo genético desenvolvido, otimiza as manobras dos taps do transformador da subestação de forma coordenada com taps dos capacitores automáticos. O comutador de tap do transformador tem uma vida útil limitada em aproximadamente 100.000 operações, o que corresponde a aproximadamente 30 operações diárias, e o algoritmo desenvolvido tem por finalidade, minimizar o número de operações diárias do dispositivo, prolongando sua vida útil. / Abstract: The goal of this research work is to develop efficient computational tools for optimizing the operation of distribution systems. The main contribution presented here is providing a methodology for reducing the real power losses based on reconfiguration and placement of both fixed and automatic capacitor banks. Many different methodologies, using several different algorithms can be found in the literature. However, most of them focus on one objective only. The method presented here comprises the simultaneous optimization of multiple objectives, in one algorithm only, to fully use the resources already installed in the system. It is shown that significant savings with the purchase of capacitor banks can be achieved by using reconfiguration as an additional tool. One of the hardest challenges to be tackled is related to the search space, that may grow significantly. The problem is solved by a genetic algorithms, which is an already widely accepted metaheuristic for solving very complex problems. Many different tools and special genetic operators have been developed along the research work. Those provided excellent results, at a low computational cost. Additionally, a simulated annealing algorithm was developed to optimize the substation transformer tap maneuvers in a coordinated way with the automatic capacitor bank tap maneuvers, from the best configuration obtained with genetic algorithms. The transformer tap commuter has a useful life limited to 100,000 operations, or approximately 30 daily operations. The proposed algorithm also minimizes the number of daily operations to stretch transformers' service life. / Doutorado / Energia Eletrica / Doutor em Engenharia Elétrica

Orientadores: Fernando Jose Von Zuben, Leandro Nunes de Castro / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-15T01:42:44Z (GMT). No. of bitstreams: 1 Gomes_LalinkadeCamposTeixeira_D.pdf: 3303378 bytes, checksum: 65adc8d5ec20cd1f431eaca2fe3765cc (MD5) Previous issue date: 2006 / Resumo: Problemas de otimização combinatória apresentam grande relevância prática e surgem em uma ampla gama de aplicações. Em geral, a otimização combinatória está associada a uma explosão de candidatos à solução, inviabilizando a aplicação de métodos exatos. Frente à intratabilidade desta classe de problemas via métodos exatos, nos últimos anos tem havido um crescente interesse por métodos heurísticos capazes de encontrar soluções de alta qualidade, não necessariamente ótimas. Considerando o notório sucesso empírico de meta-heurísticas concebidas através da inspiração biológica e na natureza, essas abordagens vêm ganhando cada vez mais atenção por parte de pesquisadores. É fato conhecido que não existe uma única metodologia capaz de sempre produzir os melhores resultados para todas as classes de problemas, ou mesmo para todas as instâncias de uma mesma classe. Assim, a busca de solução para problemas de natureza combinatória constitui uma linha de pesquisa desafiadora. Nesta tese são considerados problemas de otimização combinatória multicritério e multimodal. Como principal contribuição, destaca-se a concepção de novas meta-heurísticas para a solução de problemas combinatórios de elevada complexidade, tendo sido propostas duas classes de ferramentas computacionais. A primeira envolve um método híbrido fundamentado em mapas auto-organizáveis de Kohonen e inferência nebulosa, em que um conjunto de regras guia o processo de treinamento do mapa de modo a permitir o tratamento de problemas com restrições e múltiplos objetivos. A segunda abordagem baseia-se em sistemas imunológicos artificiais. Em particular, a abordagem imunológica levou à proposição de meta-heurísticas capazes de encontrar e manter diversas soluções de alta qualidade, viabilizando o tratamento de problemas multimodais. Como casos de estudo, foram consideradas duas classes de problemas de otimização combinatória multimodal: o problema de roteamento de veículos capacitados e o problema do caixeiro viajante simétrico. As técnicas propostas foram também adaptadas para a solução de problemas de bioinformática, em particular ao problema de análise de dados de expressão gênica, produzindo resultados diferenciados e indicando um elevado potencial para aplicações práticas. / Abstract: Combinatorial optimization problems possess a high practical relevance and emerge on a wide range of applications. Usually, combinatorial optimization is associated with an explosion of candidates to the solution, making exact methods unfeasible. Before the unfeasibility of exact methods when dealing with this class of problems, lately there has been an increasing interest in heuristic methods capable of finding high-quality solutions, not necessarily the optimal one. Considering the widely known empirical success of metaheuristics conceived with inspiration on biological systems and on the nature itself, such approaches are receiving more and more attention from the scientific community. Evidently, there is no single methodology able to always produce the best results for all classes of problems, or even for all instances of one specific class. That is why the search for solutions to combinatorial problems remains a challenging task. This thesis considers multicriteria and multimodal combinatorial optimization problems. As the main contribution, one can emphasize the conception of new metaheuristics designed to the solution of high-complexity combinatorial optimization problems, and two classes of computational tools have been proposed. The first one involves hybrid method based on Kohonen self-organizing maps and fuzzy inference, in which a set of rules guides the training of the self-organizing maps in order to allow the handling of problems with constraints and multiple objectives. The second approach is based on artificial immune systems. Particularly, the immune-inspired approach leads to the proposal of metaheuristics capable of finding out and maintaining multiple high-quality solutions, making it possible to deal with multimodal problems. As case studies, the capacitated vehicle routing problem and the symmetric traveling salesman problem are considered, giving rise to combinatorial and multimodal problems. The proposed techniques were also adapted to the solution of problems in the field of bioinformatics, specifically the analysis of gene expression data, leading to distinguished results and indicating a high potential for practical applications. / Doutorado / Engenharia de Computação / Doutor em Engenharia Elétrica

Orientador: Heloisa Vieira da Rocha / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-15T11:49:36Z (GMT). No. of bitstreams: 1 Tanaka_EduardoHideki_D.pdf: 5276780 bytes, checksum: 5d96841bbaebe2f4b4e18694a8a7c807 (MD5) Previous issue date: 2009 / Resumo: Para ser mais inclusivo e menos exclusivo, o design de sistemas de informação deve considerar questões de acessibilidade. Atualmente, existem padrões para orientar o design acessível e, também, alguns métodos para avaliação de acessibilidade, voltados principalmente para conteúdo na Web. Dos métodos de avaliação de acessibilidade existentes, os mais adotados hoje em dia são aqueles baseados na verificação de conformidade com guias de design acessível e os testes com usuários com deficiências. Tanto um quanto o outro podem ser considerados métodos caros e que demandam um tempo considerável para aplicação e análise, sendo esta uma das razões para que muitos desenvolvedores simplesmente ignorem a avaliação da acessibilidade durante o ciclo de desenvolvimento de software. Sabendo disto, esta tese de doutorado propõe exatamente um método alternativo para avaliar a acessibilidade em sistemas de informação, baseado em heurísticas. Os resultados obtidos através de dois experimentos mostraram que as heurísticas de acessibilidade propostas são fáceis de aprender, rápidas de aplicar e de baixo custo, o que possibilita sua aplicação a qualquer momento do processo de desenvolvimento de um software / Abstract: To be more inclusive and less exclusive, the design of information systems must take into account accessibility issues. Nowadays, there are standards to guide the accessible design and, also, some accessibility evaluation methods, focused on the assessment of Web content, mainly. From all accessibility evaluation methods available, the most adopted nowadays are guidelines review and tests with users with disabilities. Both of them can be considered expensive methods and require a reasonable time to apply and to analyze so that several developers simply ignore accessibility evaluation during the software development cycle. Knowing these issues, this PhD thesis proposes an alternative method to evaluate accessibility, based on heuristics. The results of two experiments showed that the proposed accessibility heuristics are easy to learn, fast to apply and not expensive, therefore, it could be applied anytime during the software development cycle / Doutorado / Sistemas de Informação / Doutor em Ciência da Computação

Orientador: Vinicius Amaral Armentano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-10T19:15:18Z (GMT). No. of bitstreams: 1 FrancaFilho_MoacirFelizardode_D.pdf: 1342634 bytes, checksum: 4855202b36314e8c55f20746c709054e (MD5) Previous issue date: 2007 / Resumo: Este trabalho é dedicado à programação de tarefas em máquinas paralelas. Dois ambientes são considerados. No primeiro, as máquinas são idênticas e o objetivo é a minimização da soma ponderada de custos de atraso. Todas as tarefas estão disponíveis para processamento no início do horizonte de programação e a cada uma são associadas uma data de entrega e uma penalização por atraso específicas. No segundo, as máquinas são não relacionadas e o objetivo é a minimização da soma ponderada de custos de avanço e de atraso. Instantes de liberação, datas de entrega, penalizações por avanço e por atraso são específicos para cada tarefa. Em ambos, as transições entre tarefas requerem tempos de preparação dependentes da seqüência de processamento. Os problemas são resolvidos por meio de GRASP e Busca Tabu. Memória de longo prazo é empregada para melhorar o desempenho das duas metaheurísticas. No GRASP, soluções de elite influenciam a fase construtiva. Na Busca Tabu, estratégias de diversificação e de intensificação fazem uso direto das soluções de elite e também de freqüências de residência. Como pós-otimização, nas duas metaheurísticas, realizam-se religações de caminhos entre as soluções de elite / Abstract: This work is dedicated to the scheduling of a set of jobs in parallel machines. Two scenarios are considered. In the first one, the machines are identical and the objective is the minimization of the weighted sum of tardiness costs. All jobs are ready for processing at the beginning of the scheduling horizon and to each one is associated a due date and a tardiness penalty. In the second scenario, the machines are non-related and the objective is the minimization of the weighted sum of earliness and tardiness costs. Ready times, due dates, earliness and tardiness penalties are specifics to each job. In both problems, the transitions between jobs require sequence dependent setup times. The problems are solved using GRASP and Tabu Search. Long term memory is applied to improve the performance of the metaheuristics. A set of elite solutions are used to influence the constructive phase in GRASP. In Tabu Search, diversification and intensification strategies make direct use of the elite solutions, as well of residence frequences. Path relinking between the elite solutions is used as a post-optimization approach / Doutorado / Automação / Doutor em Engenharia Elétrica

Orientador: Antonio Carlos Moretti / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-10T22:48:39Z (GMT). No. of bitstreams: 1 DalGallo_RodrigoMarchiori_M.pdf: 685835 bytes, checksum: 9e0e8765da2a5926a7a5952b31283ca5 (MD5) Previous issue date: 2008 / Resumo: O trabalho tem como objetivo a implementação de um método heurístico para a resolução de problemas de programação inteira com dimensão completa. Nos atemos aos problemas de corte e empacotamento, mas a aplicação pode ser estendida a qualquer outro problema dessa classe. No problema de programação linear relaxado aplicamos o Método de Gilmore & Gomory e a partir da solução contínua obtida através do método simplex, aplicamos o método heurístico e comparamos os resultados com as soluções exatas obtidas a partir de Branch & Bound / Abstract: The objective of this dissertation is the implementation of a heuristic method to solve integer linear programming problems with complete dimension. We worked specifically with cutting and stock problems, but it can be aplied to any other class of integer problems. We used the Gilmore & Gomory method of column generation and starting by the continuous solution obtained with simplex method, we aplied the heuristic method and made a comparation of results with the exact solutions obtained by the Branch&Bound method / Mestrado / Pesquisa Operacional / Mestre em Matemática Aplicada

Orientadores: Marcia Aparecida Gomes Ruggiero, Antonio Carlos Moretti / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-11T07:33:43Z (GMT). No. of bitstreams: 1 Sakamori_Momoe_M.pdf: 494316 bytes, checksum: ffa8a12071e05ab6083c917588e53797 (MD5) Previous issue date: 2008 / Resumo: Neste trabalho resolvemos um problema de corte unidimensional não-linear para minimizar o número de objetos processados, setup e desperdício. O termo não-linear representa o setup da máquina de corte. Resolvemos o problema utilizando o pacote MINOS e obtemos a solução inteira através de um procedimento heurístico. Como o número de padrões de corte pode ser muito grande, propomos uma geração de colunas modificada, que usa os multiplicadores de Lagrange do problema não-linear ao invés das variáveis duais do problema de programação linear padrão. Além disso, propomos um novo processo de geração de colunas utilizando um problema da mochila não-linear como subproblema para gerar colunas promissoras / Abstract: In this work we solve a nonlinear unidimensional cutting-stock problem to minimize the number of objects processed, setup and trim loss. The nonlinear term represents the setup of the cutting machine. We solve the problem using the MINOS package and obtain the integer solution through a heuristic procedure. Since the number of cutting patterns can be very high, we propose a modified column generation that uses the Lagrange multipliers of the nonlinear problem instead the dual variables of the standard linear programming problem. Also, we propose a new column generation process using a nonlinear knapsack problem as the subproblem to generate pro_table columns / Mestrado / Pesquisa Operacional / Mestre em Matemática Aplicada