Linear optimization tools are used to solve many problems that arise in our day-to-day lives. The linear optimization models and methodologies help to find, for example, the best amount of ingredients in our food, the most suitable routes and timetables for the buses and trains we take, and the right way to invest our savings. We would cite many other situations that involves linear optimization, since a large number of companies around the world base their decisions in solutions which are provided by the linear optimization methodologies. In this thesis, we propose theoretical and computational developments to improve the performance of important linear optimization methods. Namely, we address simplex type methods, interior point methods, the column generation technique and the branch-and-price method. In simplex-type methods, we investigate a variant which exploits special features of problems which are formulated in the general form. We present a novel theoretical description of the method and propose how to efficiently implement this method in practice. Furthermore, we propose how to use the primal-dual interior point method to improve the column generation technique. This results in the primal-dual column generation method, which is more stable in practice and has a better overall performance in relation to other column generation strategies. The primal-dual interior point method also oers advantageous features which can be exploited in the context of the branch-and-price method. We show that these features improves the branching operation and the generation of columns and valid inequalities. For all the strategies which are proposed in this thesis, we present the results of computational experiments which involves publicly available, well-known instances from the literature. The results indicate that these strategies help to improve the performance of the linear optimization methodologies. In particular for a class of problems, namely the vehicle routing problem with time windows, the interior point branch-and-price method proposed in this study was up to 33 times faster than a state-of-the-art implementation available in the literature / Ferramentas de otimização linear são usadas para resolver diversos problemas do nosso dia-a- dia. Os modelos e as metodologias de otimização linear ajudam a obter, por exemplo, a melhor quantidade de ingredientes na nossa alimentação, os horários e as rotas de ônibus e trens que tomamos, e a maneira certa para investir nossas economias. Muitas outras situações que envolvem otimização linear poderiam ser aqui citadas, já que um grande número de empresas em todo o mundo baseia suas decisões em soluções obtidas pelos métodos de otimização linear. Nesta tese, são propostos desenvolvimentos teóricos e computacionais para melhorar o desempenho de métodos de otimização linear. Em particular, serão abordados métodos tipo simplex, métodos de pontos interiores, a técnica de geração de colunas e o método branch-and-price. Em métodos tipo simplex, é investigada uma variante que explora as características especiais de problemas formulados na forma geral. Uma nova descrição teórica do método é apresentada e, também, são propostas técnicas computacionais para a implementação eciente do método. Além disso, propõe-se como utilizar o método primal-dual de pontos interiores para melhorar a técnica de geração de colunas. Isto resulta no método primal-dual de geração de colunas, que é mais estável na prática e tem melhor desempenho geral em relação a outras estratégias de geração de colunas. O método primal-dual de pontos interiores também oferece características vantajosas que podem ser exploradas em conjunto com o método branch-and-price. De acordo com a investigação realizada, estas características melhoram a operação de ramificação e a geração de colunas e de desigualdades válidas. Para todas as estratégias propostas neste trabalho, são apresentados os resultados de experimentos computacionais envolvendo problemas de teste bem conhecidos e disponíveis publicamente. Os resultados indicam que as estratégias propostas ajudam a melhorar o desempenho das metodologias de otimização linear. Em particular para uma classe de problemas, o problema de roteamento de veículos com janelas de tempo, o método branch-and-price de pontos interiores proposto neste estudo foi até 33 vezes mais rápido que uma implementação estado-da-arte disponível na literatura

Orientadores: Aurelio Ribeiro Leite de Oliveira, Fredy Angel Amaya Robayo / 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-23T17:46:00Z (GMT). No. of bitstreams: 1 MamianLopez_EstherSofia_M.pdf: 1176541 bytes, checksum: 8f49901f40e77c9511c30e86c0d1bb0d (MD5) Previous issue date: 2013 / Resumo: Os modelos probabilísticos de uma linguagem (MPL) são modelos matemáticos onde é definida uma função de probabilidade que calcula a probabilidade de ocorrência de uma cadeia em uma linguagem. Os parâmetros de um MPL, que são as probabilidades de uma cadeia, são aprendidos a partir de uma base de dados (amostras de cadeias) pertencentes à linguagem. Uma vez obtidas as probabilidades, ou seja, um modelo da linguagem, existe uma medida para comparar quanto o modelo obtido representa a linguagem em estudo. Esta medida é denominada perplexidade por palavra. O modelo de linguagem probabilístico que propomos estimar, está baseado nas gramáticas probabilísticas livres do contexto. O método clássico para estimar os parâmetros de um MPL (Inside-Outside) demanda uma grande quantidade de tempo, tornando-o inviável para aplicações complexas. A proposta desta dissertação consiste em abordar o problema de estimar os parâmetros de um MPL usando métodos de pontos interiores, obtendo bons resultados em termos de tempo de processamento, número de iterações até obter convergência e perplexidade por palavra / Abstract: In a probabilistic language model (PLM), a probability function is defined to calculate the probability of a particular string ocurring within a language. These probabilities are the PLM parameters and are learned from a corpus (string samples), being part of a language. When the probabilities are calculated, with a language model as a result, a comparison can be realized in order to evaluate the extent to which the model represents the language being studied. This way of evaluation is called perplexity per word. The PLM proposed in this work is based on the probabilistic context-free grammars as an alternative to the classic method inside-outside that can become quite time-consuming, being unviable for complex applications. This proposal is an approach to estimate the PLM parameters using interior point methods with good results being obtained in processing time, iterations number until convergence and perplexity per word / Mestrado / Matematica Aplicada / Mestra em Matemática Aplicada

Orientadores: Sandra Augusta Santos, Roberto Andreani / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-14T11:40:11Z (GMT). No. of bitstreams: 1 Shirabayashi_WesleyVagnerInes_D.pdf: 877226 bytes, checksum: a814cd9947431a0aee17517c4cc953f4 (MD5) Previous issue date: 2009 / Resumo: Neste trabalho reformulamos o problema de complementaridade não linear generalizado (GNCP) em cones poliedrais como um sistema não linear com restrição de não negatividade em algumas variáveis, e trabalhamos na resolução de tal reformulação por meio de estratégias de pontos interiores. Em particular, definimos dois algoritmos e provamos a convergência local de tais algoritmos sob hipóteses usuais. O primeiro algoritmo é baseado no método de Newton, e o segundo, no método tensorial de Chebyshev. O algoritmo baseado no método de Chebyshev pode ser visto como um método do tipo preditor-corretor. Tal algoritmo, quando aplicado a problemas em que as funções envolvidas são afins, e com escolhas adequadas dos parâmetros, torna-se o bem conhecido algoritmo preditor-corretor de Mehrotra. Também apresentamos resultados numéricos que ilustram a competitividade de ambas as propostas. / Abstract: In this work we reformulate the generalized nonlinear complementarity problem (GNCP) in polyhedral cones as a nonlinear system with nonnegativity in some variables and propose the resolution of such reformulation through interior-point methods. In particular we define two algorithms and prove the local convergence of these algorithms under standard assumptions. The first algorithm is based on Newton's method and the second, on the Chebyshev's tensorial method. The algorithm based on Chebyshev's method may be considered a predictor-corrector one. Such algorithm, when applied to problems for which the functions are affine, and the parameters are properly chosen, turns into the well-known Mehrotra's predictor corrector algorithm. We also present numerical results that illustrate the competitiveness of both proposals. / Doutorado / Otimização / Doutor em Matemática Aplicada

Orientadores: Christiano Lyra Filho, Aurelio Ribeiro Leite de Oliveira / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-27T01:38:37Z (GMT). No. of bitstreams: 1 Casacio_Luciana_D.pdf: 3240577 bytes, checksum: f49bb4444bbbfacf0559d3b88d8feee5 (MD5) Previous issue date: 2015 / Resumo: A solução de problemas de otimização linear através de métodos de pontos interiores envolve a solução de sistemas lineares. Esses sistemas quase sempre possuem dimensões elevadas e alto grau de esparsidade em aplicações reais. Para solução, tipicamente são realizadas operações algébricas que os reduzem a duas formulações mais simples: uma delas, conhecida por "sistema aumentado", envolve matrizes simétricas indefinidas e geralmente esparsas; a outra, denominada "sistema de equações normais", usa matrizes de menor dimensão, simétricas e definidas positivas. A solução dos sistemas lineares é a fase que requer a maior parte do tempo de processamento dos métodos de pontos interiores. Consequentemente, a escolha dos métodos de solução é de extrema importância para que se tenha uma implementação eficiente. Normalmente, aplicam-se métodos diretos para a solução como, por exemplo, a fatoração de Bunch-Parllett ou a fatoração de Cholesky. No entanto, em problemas de grande porte, o uso de métodos diretos torna-se desaconselhável, por limitações de tempo e memória. Nesses casos, abordagens iterativas se tornam mais atraentes. O sucesso da implementação de métodos iterativos depende do uso de bons precondicionadores, pois a matriz de coeficientes torna-se muito mal condicionada, principalmente próximo da solução ótima. Uma alternativa para tratar o problema de mal condicionamento é o uso de abordagens híbridas com duas fases: a fase I utiliza um precondicionador para o sistema de equações normais construído com informações de fatorações incompletas, denominado fatoração controlada de Cholesky; a fase II, utilizada nas últimas iterações, adota o precondicionador separador desenvolvido especificamente para sistemas mal condicionados. O trabalho propõe um novo critério de ordenamento das colunas para construção do precondicionador separador, que preserva a estrutura esparsa da matriz de coeficientes original. Os resultados teóricos desenvolvidos mostram que a matriz precondicionada tem o número de condição limitado quando o ordenamento proposto é adotado. Experimentos computacionais realizados com todos os problemas da biblioteca NETLIB mostram que a abordagem é competitiva com métodos diretos e que o número de condição da matriz precondicionada é muito menor do que o da matriz original. Foram também realizadas comparações com a abordagem híbrida anterior, baseada em precondicionadores que reduzem a esparsidade do sistema de equações. Esses experimentos confirmaram o bom desempenho da metodologia em relação ao número de iterações dos métodos de pontos interiores, aos tempos computacionais e à qualidade das soluções. Esses benefícios foram obtidos com a preservação da esparsidade dos sistemas de equações, o que destaca a adequação da abordagem proposta para a solução de problemas de grande porte / Abstract: The solution of linear optimization problems through interior point methods involves the solution of linear systems. These systems often have high dimensions and high sparsity degree, specially in real applications. Typically algebraic operations are performed to reduce the systems in two simpler formulations: one of them is known as the augmented system, and the other one, referred as normal equation systems, has a smaller dimension matrix which is symmetric positive definite. The solution of linear systems is the interior point methods step that requires most of the processing time. Consequently, the choice of the solution methods are extremely important in order to have an efficient implementation. Usually, direct methods are applied for solving these systems as, for example, Bunch-Parllett factorization or Cholesky factorization. However, in large scale problems, the use of direct methods becomes discouraging by limitations of time and memory. In such cases, iterative approaches are more attractive. The success of iterative method approaches depends on good preconditioners once the coefficient matrix becomes very ill-conditioned, especially close to an optimal solution. An alternative to treat the problem of ill conditioning is to use hybrid approaches with two phases: phase I uses a preconditioner for the normal equation systems built with incomplete factorizations information, called controlled Cholesky factorization; phase II, used in the final iterations, adopts the splitting preconditioner, which was developed specifically for such ill conditioned systems. This work proposes a new ordering criterion for the columns of the splitting preconditioner that preserves the sparse structure of the original coefficient matrix. Theoretical results show that the preconditioned matrix has a limited condition number when the proposed idea is adopted. Computational experiments performed with all NETLIB problems show that the approach is competitive with direct methods and the condition number of the preconditioned matrix is much smaller than the original matrix. Comparisons are also performed with the previous hybrid approach. These experiments confirm the good performance of the methodology. The final number of iterations, processing time and quality of solutions of interior point methods are suitable. These benefits are obtained preserving the sparse structure of the systems, which highlights the suitability of the proposed approach for large scale problems / Doutorado / Automação / Doutora em Engenharia Elétrica

Neste trabalho, os métodos de pontos interiores primal-dual e preditor corretor são estudados e desenvolvidos para o problema de minimização de custos na geração e perdas na transmissão do pré-despacho DC (fluxo de carga em corrente contínua) de um sistema de potência hidroelétrico, com base no modelo de fluxo em redes e no princípio do mínimo esforço. A estrutura matricial, resultante da simplificação do problema proposto pela inclusão do princípio do mínimo esforço, é estudada visando implementações eficientes. / In this work, the primal-dual and predictor corrector interior points methods are studied and developed for the predispatch DC problem that minimizes generation and transmission losses on hydroelectric power systems, on the basis of the network flow model and the minimum effort principle. The matrix structure, resulting of the simplification of the problem considered by inclusion of the minimum effort principle, is studied aiming efficient implementations. A disturbed primal-dual method is considered on the basis of a heuristic definition that determine the choice of the disturbance parameter. This method showed to be efficient in practice and converged in fewer iterations when compare with an existing implementation of the network flow model.

Neste trabalho é apresentada uma ferramenta de otimização para análise de problemas de alocação de água em bacias hidrográficas utilizando técnicas de programação linear e linear por partes, integradas a um modelo de amortecimentos de ondas em canais. A otimização é feita de forma global, com uso de softwares de programação linear baseados nos métodos de pontos interiores. A metodologia de uso do sistema consiste em se obter uma solução ?ótima? para situações de disponibilidade de água insuficiente a todos os usos conflitantes na bacia. A ferramenta está sendo acoplada e incorporada ao AcquaNet, um Sistema de Suporte a Decisões (SSD) para análise de sistemas de recursos hídricos, que utiliza um algoritmo de rede de fluxo afim de otimizar a alocação de água. A formulação utilizando programação linear permite a análise global do sistema e por isso, espera-se melhor aproveitamento da água disponível, seja no menor déficit de atendimento às demandas ou maior armazenamento nos reservatórios. A programação linear com utilização de métodos de pontos interiores é atualmente uma técnica bastante conhecida e bem desenvolvida. Existem vários pacotes computacionais gratuitos com implementações eficientes dos métodos de pontos interiores que motivaram sua utilização neste trabalho. / This work presents an optimization tool for analyzing the problems of water allocation in watersheds by utilizing techniques of linear and piecewise linear programming integrated to a pattern of stream flow routing. The optimization is done in a global way with the usage of linear programming packages based upon the Internal Point Methods. The methodology of the usage consists in the acquirement of an optimal solution for situation of insufficient water availability for all conflicting consumptions from the watershed. The tool is being attached and incorporated to AcquaNet, which is a decision support system (DSS) for analysis of water resources systems that utilizes a network flow algorithm, with the purpose of optimizing the water allocation. The formulation that uses the linear programming leads to the analysis of the system as a whole and for this reason it is expected a better usage of the available water with a lower deficit in the supply or a greater storage in the reservoirs. Linear Programming with Internal Point Methods is nowadays a well known and very well developed technique. There are several computational packages with efficient implementations of the Internal Points Methods freely available, and that, has brought great motivation in its usage in the present work.

Made available in DSpace on 2014-06-11T19:22:34Z (GMT). No. of bitstreams: 0 Previous issue date: 2010-08-23Bitstream added on 2014-06-13T20:48:01Z : No. of bitstreams: 1 souza_mas_me_bauru.pdf: 1718716 bytes, checksum: 06558a2073d16192fb7eaf1e9f95ca28 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Este trabalho visa a investigação e implementação de métodos Primal - Dual Previsor-Corretor de Pontos Interiores com a estratégia de busca unidimensional, e a aplicação destes em problemas de Despacho Econômico e Ambiental. Objetiva-se utilizar estes métodos para determinar soluções aproximadas e consistentes dos problemas causados citados, que forneçam a solução de minimização dos custos dos combustíveis empregados na geração termoelétrica de energia, otimizando um processo de alocação da demanda de energia elétrica entre as unidades geradoras disponíveis, de tal forma que as restrições operacionais sejam atendidas e que o custo de geração é minimizado. Pretende-se também, analisar o problema de Despacho Ambiental com um objetivo único quando se acopla a este o Problema de Despacho Econômico e busca-se, simultaneamente, a minimização dos custos de geração e a redução da emissão de poluentes na natureza. Os métodos foram implementados, testados em Problemas de Despacho Econômico e Ambiental, e o seu desempenho foi comparado com outros métodos já utilizados, cujos resultados são encontrados na literatura / This work aims the investigation and implementation of Primal-Dual Predictor-Corrector interior points methods, with the strategy of one-dimensional search, and its application in Economic and Environmental Dispatch Problems. It pretends to use these methods to determine approximate and consistent solutions of the mentioned problems, that provide the solution to minimize the fuel costs used in thermoelectric power generation, optimizing an allocations process of eletric power demand among available generation units, such that the operational constraints are attended and that generation cost is minimized. It too pretends to analyze the Environmental Dispatch Problem with the one objective when it is joined with the Dispatch Problems and it searchs, simultaneously, the minimization of the generation costs and the reduction of emission of the polluants in the nature. The methods were implemented, tested on the Economic and Environemental Dispatch Problems and its performance was compared with others method currently used, whose results are found in the literature

Neste trabalho é apresentada uma ferramenta de otimização para análise de problemas de alocação de água em bacias hidrográficas utilizando técnicas de programação linear e linear por partes, integradas a um modelo de amortecimentos de ondas em canais. A otimização é feita de forma global, com uso de softwares de programação linear baseados nos métodos de pontos interiores. A metodologia de uso do sistema consiste em se obter uma solução ?ótima? para situações de disponibilidade de água insuficiente a todos os usos conflitantes na bacia. A ferramenta está sendo acoplada e incorporada ao AcquaNet, um Sistema de Suporte a Decisões (SSD) para análise de sistemas de recursos hídricos, que utiliza um algoritmo de rede de fluxo afim de otimizar a alocação de água. A formulação utilizando programação linear permite a análise global do sistema e por isso, espera-se melhor aproveitamento da água disponível, seja no menor déficit de atendimento às demandas ou maior armazenamento nos reservatórios. A programação linear com utilização de métodos de pontos interiores é atualmente uma técnica bastante conhecida e bem desenvolvida. Existem vários pacotes computacionais gratuitos com implementações eficientes dos métodos de pontos interiores que motivaram sua utilização neste trabalho. / This work presents an optimization tool for analyzing the problems of water allocation in watersheds by utilizing techniques of linear and piecewise linear programming integrated to a pattern of stream flow routing. The optimization is done in a global way with the usage of linear programming packages based upon the Internal Point Methods. The methodology of the usage consists in the acquirement of an optimal solution for situation of insufficient water availability for all conflicting consumptions from the watershed. The tool is being attached and incorporated to AcquaNet, which is a decision support system (DSS) for analysis of water resources systems that utilizes a network flow algorithm, with the purpose of optimizing the water allocation. The formulation that uses the linear programming leads to the analysis of the system as a whole and for this reason it is expected a better usage of the available water with a lower deficit in the supply or a greater storage in the reservoirs. Linear Programming with Internal Point Methods is nowadays a well known and very well developed technique. There are several computational packages with efficient implementations of the Internal Points Methods freely available, and that, has brought great motivation in its usage in the present work.