Orientador : Akebo Yamakami / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T03:54:02Z (GMT). No. of bitstreams: 1 Cantao_LuizaAmaliaPinto_D.pdf: 1186821 bytes, checksum: eda2d926b3c608ecd9a61ff5c43bb7ec (MD5) Previous issue date: 2003 / Doutorado

Orientador: Arnaldo Vieira Moura / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-03T14:25:03Z (GMT). No. of bitstreams: 1 Nascimento_JulianaMartinsdo_M.pdf: 4967741 bytes, checksum: 20ceacaab689704941f1f9d3ec41695a (MD5) Previous issue date: 2002 / Resumo: Problemas de otimização combinatória são classificados na grande maioria das vezes como NP-difíceis. Para estes problemas, não são conhecidos algoritmos polinomiais capazes de resolvê-los. Logo, é necessário o desenvolvimento de estratégias eficientes para tratá-los. O desenvolvimento de técnicas híbridas para a resolução destes problemas tem por objetivo valorizar os pontos fortes dos métodos que estão sendo empregados, para, desta forma, compensar os pontos mais fracos, criando um procedimento de qualidade superior. Este trabalho propõe um método híbrido que integra técnicas de Programação por Restrições com metaheurísticas de Busca Tabu para atacar o problema de escalonamento de atividades na produção de um campo petrolífero. Como não há resultados anteriores para serem comparados com os resultados obtidos para as instâncias consideradas neste trabalho, modelos de programação matemática foram utilizados para a obtenção de limitantes duais para a solução do problema. Além disso, para determinar quão robusta é a técnica proposta, uma análise de sensibilidade foi realizada sobre as instâncias consideradas / Abstract: Combinatorial optimization problems are generally NP-hard. As it is not known polinomial time algorithms to solve them, it is necessary to develop efficient strategies to treat them. The aim in developing hybrid techniques to solve combinatorial optimization problems is to strength the good features of the methods that are being combined to compensate for their weakness. In this paper, we propose a hybrid method that combines Constraint Programming techniques and Tabu Search metaheuristics to schedule the activities involved in the production process of an oil field. As there are no previous results to estabilish a comparision with the results obtained with the instances considered in this work, bounds were determined using mathematical programming models. Finally, to estabilish the robusteness of proposed method, a sensibility analysis was performed over the considered instances / Mestrado / Mestre em Ciência da Computação

Orientador: Clovis Perin Filho / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-07-25T01:09:27Z (GMT). No. of bitstreams: 1 Podesta_ValeriaAbraode_D.pdf: 3666244 bytes, checksum: 1835bad12b2cd2f4f460f94767c6052b (MD5) Previous issue date: 1999 / Resumo: O problema de Multifluxo (Fluxo de Multiproduto) em uma rede é um modelo de Programação Matemática com muitas aplicações práticas. Neste trabalho, apresentamos um estudo computacional do Método Primal-Dual de Pontos Interiores aplicado ao problema de Multifluxo. Destacamos a resolução do sistema linear das direções, onde é utilizado o método dos Gradientes Conjugados com uma combinação dos precondicionadores Diagonal e Floresta Geradora Máxima. Vários experimentos computacionais foram realizados, incluindo duas regras de atualização do parâmetro de centragem, três pontos iniciais e critérios de parada no Gradiente Conjugado, entre outros. Apresentamos ainda a caracterização da base de Multifluxo, uma heurística para a obtenção de uma base ótima a partir de uma solução interior "quase-ótima" fornecida pelo Método Primal-Dual e um estudo sobre a degenerescência / Abstract: The Multicommodity Flow Problem is a model of Mathematical Programming defined on a network that has many important applications. In this work, we perform a computational study of a Primal-Dual Interior Point Method applied to this problem. We solve the linear system of iterate displacements using the Conjugate Gradient Method with a combination of the preconditioned Diagonal and Maximum Spanning Forest. Several computational experiments were performed, considering different starting points, different rules of the centering parameter update and different stopping criterion for the Conjugate Gradient. We present a characterization of the Multiflow basis, a heuristic for constructing an optimal basis from an interior "quasi-optimal" solution given by the Primal-Dual Method as well as a study about degeneracy / Doutorado / Doutor em Matemática Aplicada

Orientadores: Antonio E. Costa Pereira, Tomasz Kowaltowski / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-13T23:56:33Z (GMT). No. of bitstreams: 1 Cohn_PauloGomide_M.pdf: 11566794 bytes, checksum: f91095d37be2b90e3632446d7c42da36 (MD5) Previous issue date: 1991 / Resumo: Apresenta-se inicialmente uma introdução à programação em lógica através de uma abordagem evolutiva. Começando de um sistema formal de primeira ordem bastante complexo, descreve-se o conceito de prova de teoremas e sua automação. A partir daí apresenta-se a idéia de eficiência da prova. Os principais avanços obtidos durante o século XX nesta área são apontados, dando-se ênfase ao princípio de resolução de Robinson. Ao restringir a linguagem do sistema formal às sentenças de Horn, obtem-se uma grande melhora da eficiência do mecanismo de prova, preservando razoável poder de expressão. Alguns problemas relativos à expressividade da linguagem são apontados assim como formas em que têm sido abordados na atualidade. Uma delas é a programação por restrições. Na segunda parte do trabalho é apresentada a implementação de um interpretador/sistema de execução para a linguagem Prolog. A partir de uma especificação breve, de alto nivel, são introduzidos, incrementalmente, os detalhes de implementação de nivel mais baixo (estruturas de dados, controle de execução) até se obter um programa puramente procedimental escrito numa linguagem convencional (C). Finalmente, os conceitos de programação por restrições mencionados no inicio do trabalho são apresentados de forma mais detalhada para que se possa ter uma visão mais clara do seu funcionamento na prática. Assim, adotando uma abordagem semelhante à utilizada para descrever o compilador Prolog, é apresentado um interpretador de alto nivel para programas de restrições e, após alguns refinamentos, é obtido um conjunto de instruções que pode ser implementado numa linguagem de programação convencional. / Abstract: An introduction to logic programming is initially presented by means of an evolutionary approach. Starting with a fairly complex first order formal system, the concepts of theorem proving and its automatization are described. From there the idea of proof efficiency is presented. The most significant advances obtained during the 20th century in this area are pointed out emphasizing Robinson's resolution principle. Restraining the formal system's language to Horn sentences, a major improvement of the proof mechanism is obtained, preserving reasonable expressive power. Some problems related to language expressiveness and the ways in which they have been recently approached are shown. One of these approaches is constraint programming. In the second part of the work, the implementation of an interpreter/runtime system for the Prolog language is shown. From a brief, high-level specification, lower-level implementation details (data structures, execution control) are introduced until a purely procedural program written in a conventional language (C) is obtained. Finally, the contraint programming concepts mentioned in the first part are presented in a more detailed form in order to allow for a clearer vision of how it works in practice. Thus, by means of an approach similar to that used to describe the Prolog compiler, a high-level interpreter for constraint programs is presented and, after some refinements, an instruction set that may be implemented in a conventional programming language is obtained. / Mestrado / Mestre em Ciência da Computação

Orientador: Rogerio Drummond B.P. de Mello Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-14T00:51:57Z (GMT). No. of bitstreams: 1 Furuti_CarlosAlberto_M.pdf: 3275024 bytes, checksum: c9e79cba4eee955be84f82738f61261b (MD5) Previous issue date: 1991 / Resumo: Não informado. / Abstract: Not informed. / Mestrado / Mestre em Ciência da Computação

Orientadores: Celso Pascoli Bottura, Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-14T03:31:11Z (GMT). No. of bitstreams: 1 Armentano_ViniciusAmaral_M.pdf: 6248423 bytes, checksum: 3fbfa1b6616c2229cb675d79d44fbf3e (MD5) Previous issue date: 1979 / Resumo: Sistemas físicos e econômicos modelados como sistemas lineares dinâmicos a tempo discreto com critério ou função objetivo linear são considerados problemas lineares dinâmicos. A Programação Linear Dinâmica é um corpo de teoria e métodos destinados ao estudo desses problemas. Um problema 'linear dinâmico pode ser considerado um caso especial de um problema mais geral de controle ótimo ou otimização dinâmica. No Capítulo I e feita a apresentação do problema, bem como dos métodos de resolução, aqui divididos em duas categorias: a-) Métodos indiretos que buscam a decomposição do problema original ou que somente se utilizam da separabilidade da função objetivo. b-) Métodos diretos que exploram a estrutura da matriz de restrições global. No Capítulo II são expostos três métodos pertencentes a categoria dos indiretos. Todos eles dependem de teoria e técnicas provenientes da programação matemática, aqui apresentadas de maneira sucinta antes de serem aplicadas aos problemas lineares dinâmicos. As seções desse capítulo pode ser lidas independentemente. No capítulo III são descritos dois algoritmos baseados no método Simplex e classificados como diretos. A principal característica desses algoritmos esta na manipulação da base global que é substituída por um conjunto de bases locais. O número dessas bases e igual ao numero de períodos que constituem o horizonte de planejamento. O capítulo se encerra com uma análise comparativa entre os dois algoritmos / Mestrado / Mestre em Engenharia Elétrica

Orientador: Waldemar W. Setzer / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-14T11:42:46Z (GMT). No. of bitstreams: 1 Badelucci_AntonioCarlos_M.pdf: 7319789 bytes, checksum: cffff5414360e0cb106bba181db8d264 (MD5) Previous issue date: 1974 / Resumo: Este trabalho visa ser um subsídio aqueles que se interessam, na ciência da computação, pela resolução de problemas referentes à manipulação simbólica estruturada. O sistema apresentado não pretente ser completo ou final, sua concepção prevê e espera complementos. Espero com ele abrir perspectivas de desenvolvimento na área das linguagens e na resolução de alguns problemas de lingüística computacional. O sistema apresentado vem precedido de uma crítica de outros sistemas em aspecto em que estes nos pareceram ineficientes ou mal concebidos, preocupamo-nos em fornecer ao usuário a máxima flexibilidade na utilização dos recursos do sistema, com um mínimo desgaste na introdução de novos conceitos e tendo sempre em conta uma facilitação do processo de aprendizagem. Essa preocupação vem acompanhada de outra: no desenvolvimento do sistema tivemos sempre presente uma ótima utilização de memória e a minimização dos tempos de execução. A concepção geral e acompanhada de listagens e explicações sobre cada peça particular do sistema. / Abstract: Not informed. / Mestrado / Mestre em Ciência da Computação

Orientador : Clovis Perin Filho / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-14T20:12:42Z (GMT). No. of bitstreams: 1 Marins_FernandoAugustoSilva_D.pdf: 8217799 bytes, checksum: 742307af34df06fe0a33afc37f0dd706 (MD5) Previous issue date: 1987 / Resumo: Este trabalho propõe um refinamentodo metodo simplex especializado para Programas em Redes Lineares por Partes, denomi nado MSFV. Este refinamento e uma extensão do conceito de bases fortemente viáveis para Programas em Redes, desenvolvido por W.H. Cunningham. A viabilidade forte e mantida por meio de uma regra de saida especifica, para escolha da variável básica que deve deixar a base em cada iteração do simplex. Prova-se que, o uso de viabilidade forte em conjunto com regras de entrada adequadas, evita os fenômenos de ciclagem ("cycling") e de empacamento ("stalling"). Alem disto são apresentados resultados computacionais testando o MSFV combinado com várias regras de entrada. Adicionalmente, é realizada uma investigação do desempenho do MSFV incorporando a Tecnica de Mudança de Escala, proposta por Edmonds e Kar / Abstract: This work proposes a refinementof the simplex method especialized for solving Piecewise-Linear Network Programs, named MSFV. Such a refinement is an extension of the strongly feasible bases concept for Network Programs, developed by W.H. Cunningham. Strongly feasibility is preserved by a specific leaving variable selection rule at each simplex ite~ation. It is proved that the use of strong feasibility together with adequate entering variable selection rules prevents two phenomena cycling (ciclic sequence of degenerate iterations) and stall ing (exponentially long sequence of degenerated iterations). Moreover it is reported a computational testing of MSFV linked with several entering variable selection rules. In addition, it is investigated the performance of MSFV with theScaling Technique, proposed by Edmonds and Kar / Doutorado

Orientador: Flavio Keidi Miyazawa / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-04T12:11:50Z (GMT). No. of bitstreams: 1 Santos_GedsonOliveira_M.pdf: 357922 bytes, checksum: 0e5b89d41d77b575e7c1eaf58856ae09 (MD5) Previous issue date: 2005 / Resumo: administração do risco de crédito requer modelos e técnicas sofisticadas para auxílio nas tomadas de decisões. Área com pouquíssimos trabalhos acadêmicos e vasto campo para estudo tem na Otimização Contínua uma excelente alternativa para o seu desenvolvimento. Baseado nos conceitos de Basiléia II, este trabalho propõe o desenvolvimento de instrumentos de otimização da carteira de crédito, os quais podem efetivamente reestruturá-la na minimização de riscos e concentrações e na maximização de retornos. Para atingirmos nosso objetivo, utilizamos técnicas de Programação Matemática que trabalham com variáveis contínuas, tais como, Programação Linear, Programação Linear Paramétrica e Programação Quadrática Convexo / Abstract: Credit risk management requires sophisticated models and techniques in the decision making process. It is an area with few academic works, and that makes it a vast field for research. The Continuous Optimization technique offers an excellent opportunity for the development of new approaches. Based on that technique, and using the concepts of Basel II, this work develops instruments for the optimization of credit portfolios, which can effectively reorganize them, with minimization of risks and concentrations and maximization of returns. To reach our objective, we use Mathematical Programming techniques that work with continuous variables such as Linear Programming, Parametric Linear Programming and Convex Quadratic Programming / Mestrado / Engenharia de Software / Mestre em Computação

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-24T03:31:34Z (GMT). No. of bitstreams: 1 Cavalcante_CristinaCeliaBarros_M.pdf: 2965474 bytes, checksum: 985e21c3520bb2270df4c0dda2caeaf9 (MD5) Previous issue date: 1998 / Resumo: Esta dissertação estuda o problema de escalonamento com restrição de mão-de-obra (SPLC) e apresenta algumas estratégias para obtenção de limitantes inferiores e de limitantes superiores para este problema NP-difícil. No que diz respeito à obtenção de limitantes inferiores para o SPLC, são apresentadas duas formulações de programação inteira e discutidos os limitantes inferiores obtidos com a relaxação linear de cada uma delas. Um algoritmo de branch-and-bound específico para o SPLC é também implementado na tentativa de se obter soluções exatas para este problema. Finalmente, é introduzida uma extensão, baseada em uma formulação de programação inteira, para um método existente na literatura para o cálculo de limitantes inferiores para problemas de escalonamento com restrição de recursos. Com relação à obtenção de limitantes superiores para o SPLC, são propostas e implementadas quatro estratégias heurísticas seqüenciais (heurística baseada em regras de prioridade, heurística baseada em classes de escalonamento, heurística baseada em programação linear e um algoritmo seqüencial de busca tabu) e duas estratégias paralelas e assíncronas (A-Team e um algoritmo paralelo de busca tabu). Um conjunto de instâncias de teste para o SPLC é gerado e disponibilizado como benchmark para ser usado na avaliação da qualidade dos limitantes inferiores e superiores obtidos neste trabalho e em outros disponíveis na literatura. Embora pouco sucesso tenha sido obtido com as estratégias propostas para obtenção de limitantes inferiores, no caso dos limitantes superiores, as estratégias paralelas e assíncronas propostas e implementadas neste trabalho mostraram-se altamente adequadas à obtenção de soluções de boa qualidade para o SPLC e são, atualmente, responsáveis pelas melhores soluções conhecidas para este problema. / Abstract: This dissertation studies the scheduling problem under labour constraints (SPLC) and presents some strategies to obtain lower and upper bounds for this NP-hard problem. Concerning the lower bounds, two integer programming formulations are presented and the lower bounds associated with their linear relaxations are discussed. A branch-and-bound algorithm is also implemented as an essay to provide exact solutions for this problem. Finally, integer programming is used as a basis to extend a procedure reported in the literature to compute lower bounds for the resourte constrained project scheduling problem. In order to get upper bounds for SPLC, four heuristic approaches (priority rule based heuristic, schedule set based heuristic, linear programming based heuristic and sequential tabu search algorithm) and two parallel strategies (A - Team and parallel tabu search algorithm) are proposed and implemented. A benchmark instance data set for SPLC is generated to be used in the evaluation of the lower and upper bounds obtained in this dissertation and in other works available in the SPLC literature. Although little success has been achieved with respect to the lower bounds, in the case of upper bounds, the parallel strategies proposed in this work have shown the applicability of such techniques in providing high quality solutions for SPLC, and are, presently, responsible for the best known solutions for this problem. / Mestrado / Mestre em Ciência da Computação