Made available in DSpace on 2015-09-17T15:24:15Z (GMT). No. of bitstreams: 0 Previous issue date: 2014-02-20. Added 1 bitstream(s) on 2015-09-17T15:48:08Z : No. of bitstreams: 1 000843899.pdf: 517994 bytes, checksum: a54791f8368518a4a957793e48d72808 (MD5) / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / Neste trabalho estudamos condicões necessárias e suficientes de otimalidade para problemas de controle ótimo com tempos finais livres, compreendendo o estudo do Princípio do Máximo e convexidade generalizada. Apresentamos as condições necessárias do princípio do máximo com tempos finais fixos e do princípio do máximo com tempos finais livres. Logo apresentamos as condições suficientes para problemas de controle ótimo com tempos finais fixos; introduzimos duas definições de convexidade generalizada, a primeira denominada PML-pseudoinvexidade, que envolve os multiplicadores de Lagrange e, a segunda denominada PM-pseudoinvexidade, que não envolve os multiplicadores de Lagrange. Mostramos que para um problema PML-pseudoinvexo todos os PM-processos (processos de controle que satisfazem as condições necessárias do princípio do máximo) são processos ótimos e reciprocamente os problemas tais que todos os PM-processos são ótimos, são problemas PML-pseudoinvexos; também mostramos que sob algumas condições, PML-pseudoinvexidade e equivalente a PM-pseudoinvexidade. Finalmente apresentamos as condições suficientes para problemas de controle ótimo com tempos finais livres; introduzimos uma de de nição de convexidade generalizada denominada PM-pseudoinvexidade livre, que não envolve os multiplicadores de Lagrange. Mostramos que sob algumas condições, se o problema e PM-pseudoinvexo livre, então todo PM-processo normal e um processo ótimo; também mostramos que sob algumas condições, se o problema e tal que todo PM-processo e um processo ótimo, então o problema e PM-pseudoinvexo livre / In this work we study necessary and sufficient optimality conditions for free end-time optimal control problems, comprising the study of the Maximum Principle and generalized convexity. We introduce the necessary conditions of the xed end-time maximum principle and of the free end-time maximum principle. Next, we present sufficient conditions for xed end-time optimal control problems; we introduce two de nitions of generalized con- vexity, the rst called LMP-pseudoinvexity, which involves the Lagrange multipliers and the second called MP-pseudoinvexity, which does not involve the Lagrange multipliers. We show that for a LMP-pseudoinvex problem all the MP-processes (control processes that satisfy the necessary conditions of the maximum principle) are optimal processes and con- versely the problems such that all the MP-processes are optimal, are LMP-pseudoinvex problems; also we show that under some conditions, LMP-pseudoinvexity is equivalent to MP-pseudoinvexity. Finally, we present sufficient conditions for free end-time optimal control problem; we introduce a de nition of generalized convexity called MP-free pseudoinvexity, which does not involve the Lagrange multipliers. We show that under some conditions, if the problem is MP-free pseudoinvex, then all normal MP-processes are optimal; also we show that under some conditions, if the problem is such that every MP-process is an optimal process, then the problem is MP-free pseudoinvex

Made available in DSpace on 2014-11-10T11:09:53Z (GMT). No. of bitstreams: 0 Previous issue date: 2014-05-30Bitstream added on 2014-11-10T11:57:47Z : No. of bitstreams: 1 000790195.pdf: 918459 bytes, checksum: 01e8141c5483f5a04a86fdd9a1917ef1 (MD5) / O Problema do Caixeiro Viajante (PCV) é um problema clássico de Otimização Combinatória. Dado um conjunto de cidades e os custos de viagem entre cada par delas, o objetivo é encontrar um roteiro que passa em todas as cidades apenas uma vez e retorna à cidade de origem de menor custo total. O enunciado simples e resolução não trivial encantaram muitas pessoas ao longo dos anos. Na literatura são apresentadas diversas formulações matemáticas para o Problema do Caixeiro Viajante, além de comparações entre a qualidade da relaxação linear de tais formulações. A formulação clássica para o PCV é forte, porém possui um número exponencial de restrições, e é equivalente à formulação de multiproduto (multi-commodity), de ordem polinomial. O custo computacional para resolver a relaxação linear da formulação multiproduto é alto, incentivando a busca de novas formas de obter limitantes duais. Na literatura são propostos procedimentos para obtenção de limitantes duais para o PCV utilizando-se do método relax and cut, a partir do problema da designação (PD), dualizando inequações válidas que são violadas pela solução ótima do PD. Neste trabalho, propomos a aplicação do método relax and cut para a formulação do PCV com restrições de multiproduto. Os resultados obtidos no estudo computacional são encorajadores, com a implementação de um algoritmo que gera bons limitantes duais com baixo tempo computacional / The Traveling Salesman Problem (TSP) is a classical Combinatorial Optimization problem. Given a set of cities and travel costs between each pair of them, the objective is to find a tour through all the cities, visiting each city once, and returning to the city of origin with minimum total cost. The simple enunciate and non-trivial resolution enchanted many people through the years. In the literature various formulations for the Traveling Salesman Problem are presented, and the quality of the linear relaxation of such formulations is compared. The classical TSP formulation is strong, but have an exponencial number of constraints, and is equivalent to the multi-commodity formulation, of polinomial order. The computational cost to solve the linear relaxation of the multi-commodity formulation is high, stimulating the search of new ways of obtaining dual bounds. In the literature, procedures to obtain dual bounds to the TSP using the relax and cut technique are proposed, starting from the assignment problem (AP) and dualizing violated valid inequalities by the AP’s optimal solution. In this work, we propose an application of the relax and cut technique to the multi-commodity formulation for the TSP. The results obtained by the computational study are encouraging, with the implementation of an algorithm that generates good dual bounds in low running time

Made available in DSpace on 2014-11-10T11:09:53Z (GMT). No. of bitstreams: 0 Previous issue date: 2014-05-29Bitstream added on 2014-11-10T11:57:47Z : No. of bitstreams: 1 000789915_20151203.pdf: 238260 bytes, checksum: 01c4adf72b2af011fbef2f093bba1467 (MD5) Bitstreams deleted on 2015-12-07T09:44:35Z: 000789915_20151203.pdf,. Added 1 bitstream(s) on 2015-12-07T09:45:16Z : No. of bitstreams: 1 000789915.pdf: 971219 bytes, checksum: 2821d946a089738f0f2d290034310374 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho apresentamos um método para munir o conjunto intervalar generalizado M = I(R) ∪ I(R); sendo I(R) = f[a1; a2] : a1 a2 e a1; a2 2 Rg e I(R) = f[a1; a2] : [a2; a1] 2 I(R)g; com algumas diferentes estruturas, como algébrica, topológica e métrica. Também equipamos M com relações de ordem. Na verdade, fizemos isso em um contexto mais geral, pois trabalhamos em Mn = M M M para n 2 N: Nós formulamos problemas de otimização intervalar e relacionamos esses problemas com clássicos problemas de otimização multiobjetivo. Além disso, apresentamos uma versão do Teorema minmax no contexto intervalar e também desenvolvemos conceitos do cálculo em espaços intervalar generalizado, os quais são usados para encontrar o conjunto dos estados atingíveis de um inclusão diferencial clássica sob algumas condições dadas / This work presents a method to endow the generalized interval set M = I(R) ∪ I(R); where I(R) = f[a1; a2] : a1 a2 and a1; a2 2 Rg and I(R) = f[a1; a2] : [a2; a1] 2 I(R)g; with some different structures, such as algebraic, topological, and metric. We also equip M with order relations. Actually, we did this in a more general context because we worked in Mn = M M M for n 2 N: We formulated interval optimization problems and related them to classic multi-objective optimization problems. We presented a version of the mini-max Theorem in the interval context, and also developed concepts of calculus on the generalized interval space which are used to find the attainable state set of a classic differential inclusion under some given conditions

Orientador : Prof. Dr. Fabiano Silva / Tese (doutorado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 21/02/2017 / Inclui referências : f. 67-71 / Área de concentração : Ciência da computação / Resumo: Várias codificações de problemas relevantes para SAT ou suas variações são conhecidas e estudadas pela comunidade. Uma possível maneira de mensurar a eficiência destas codificações consiste em avaliar a manutenção da Arco Consistência Generalizada (ACG) da fórmula resultante pelo resolvedor SAT. Ao melhor de nosso conhecimento, não há estudos sobre a manutenção de tal consistência para codificações relativas, que descrevem relações binárias sobre um dado conjunto de elementos do problema. Neste trabalho, é apresentado um estudo sobre a Arco Consistência Generalizada em codificações SAT relativas. É mostrado que, dependendo das propriedades da relação codificada, as fórmulas obtidas por estas codificações são mantidas ACG pelo procedimento da Propagação Unitária. Conjectura-se também que estas codificações não podem ser polinomialmente restritas para mantê-las ACG. Neste trabalho, é também apresentado um método para manter uma consistência parcial nas fórmulas obtidas pelas codificações relativas. O método é baseado na manutenção da árvore de dominantes do grafo induzido pela relação codificada, durante o processo de busca do resolvedor SAT. Resultados experimentais indicam que o método pode reduzir o número de decisões realizadas pelo resolvedor e, logo, o espaço de busca explorado. Outras contribuições deste trabalho incluem codificações relativas para conectividade em grafos e para o problema da Árvore de Steiner, um framework genérico para unificar as codificações relativas conhecidas, um algoritmo polinomial para SAT para fórmulas mantidas ACG, e a implementação de algoritmos que mantêm árvores de dominantes para grafos dinâmicos dentro do código-fonte de um resolvedor SAT no estado-da-arte. / Abstract: Many encodings from relevant problems to SAT or its variants are known and studied by the community. One possible way to measure the efficiency of these encodings consists on evaluating the maintenance of the Generalized Arc Consistency (GAC) of the resulting formula by the SAT solver. To the best of our knowledge, there is no study about such consistency for relative encodings, that describe binary relations over a given set of elements from the problem. In this work, it is presented a study about the Generalized Arc Consistency for relative SAT encodings. It is shown that, depending on the properties of the encoded relation, the formulae obtained by such encodings are maintened GAC by the Unit Propagation procedure. It is also conjectured that these encodings cannot be polynomially restricted in order to maintain them GAC. In this work, it is also presented a method to maintain a partial consistency on the formulae obtained by relative encoding. The method is based on the maintenance of the dominator tree of the underlying graph, during the search procedure of the SAT solver. Experimental evaluations indicate that the method may reduce the number of decisions made by the solver, and, thus, the search space it explores. Other contributions of this work include relative encodings for graph connectivity and for the Steiner Tree problem, a generic framework unifying known relative encodings, a polynomial-time algorithm for SAT for formulae maintened GAC, and the implementation of algorithms that maintain dominator trees for dynamic graphs inside the source code of a state-of-the-art SAT solver.

Made available in DSpace on 2014-06-11T19:22:34Z (GMT). No. of bitstreams: 0 Previous issue date: 2010-08-27Bitstream added on 2014-06-13T19:26:23Z : No. of bitstreams: 1 luciano_ejr_me_bauru.pdf: 912610 bytes, checksum: 8374c6e06cc40c16b0d99dbb004d73c7 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / Este projeto tem como objetivo descrever, implementar e avaliar um modelo de Unit Commitment (UC) hidrotérmico para o ambiente de mercados de energia. O modelo deve considerar aspectos que têm sido negligenciados na abordagem atualmente vigente no Brasil, ou seja, o modelo deve apresentar as seguintes contribuições: i) a discretização do problema deve ser feita em base horária e não semanal, de modo a permitir o estabelecimento de um mercado de curtíssimo prazo efetivo; ii) o modelo deve levar em conta os custos de partida/parada de máquinas, comparando a solução do modelo proposta com o modelo em que essses custos não são considerados; iii) as inter-relações entre os mercados pool e bilateral são descritas de forma explícita em um único problema de otimização de UC; iv) a inserção dos custos de oportunidade hidráulica propostos no âmbito desse trabalho na função de custos / This project aims to describe, implement and evaluate a model of Unit Commitment (UC) for the hydrothermal environment of energy markets. The model takes into account aspects that have been neglected in the approach currently used in Brazil, and present the following contributions: i) discretization of the problem is performed in an hourly basis, instead of the weekly-based approach currently used, to allow the establishment of an effective market for short term generation planning; ii) the model takes into account unit start-up and shut down costs; the outcomes of the proposed model are compared with those of a model in which these costs are not considered; iii) the interrelationships between pool and bilateral markets are described explicity within a single optimization problem in the proposed UC model; iv) the inclusion of opportunity costs associated with hydraulic utility, proposed in the context of this research

Made available in DSpace on 2014-06-11T19:22:34Z (GMT). No. of bitstreams: 0 Previous issue date: 2013-08-13Bitstream added on 2014-06-13T20:49:16Z : No. of bitstreams: 1 breda_jc_me_bauru.pdf: 2251769 bytes, checksum: 17ce532752d5bbdff8225f1f7dea91f1 (MD5) / Este trabalho tem como objetivo a concepção, implementação, solução e teste de um modelo de leilão multiperíodo para sistemas hidrotérmicos com representação da transmissão (LMSHRT) para o ambiente de mercados de energia. Com essa nova abordagem de modelagem, o modelo de leilão proposto é capaz de calcular tanto o despacho de geração hidrotérmico quanto os preços de equilíbrio de mercado em base horária para cada barra/região do sistema. Assim, a abordagem proposta além de herdar as principais características anteriormente propostas em (da Silva, 2010) e (Vergílio, 2011), tais como, a capacidade de introduzir a representação de contratos bilaterais, a obtenção dos preços em base horária, de forma a viabilizar um mercado de curto prazo e a capacidade intrínseca de reduzir riscos futuros de déficit de energia, incorpora ainda no modelo, a possibilidade da respresentação da transmissão com seus fluxos e perdas associadas. Para solução e validação do modelo é utilizado o método de pontos interiores primal dual barreira logarítima. Testes complementares são realizados com o objetivo de verificar como a variação dos principais parâmetros do modelo influenciou no despacho das unidades geradoras e na formação dos preços de equilíbrio do sistema / This research aims at the conception, implementation, solution and testing of the proposed network-constrained multiperiod auction model for hydrotermal generation systems, to be used in a day-ahead energy market clearing procedure. With this new modeling approach, the proposed auction model is able to calculate both the hydrothermal generation dispatch as well as the market clearing prices on an hourly basis for each bus/region of the system. Thus, in addition to inheriting the main features of the previously work proposed in (da Silva, 2010) and (Vergílio, 2011) such as the ability to introduce the representation of bilateral contracts, the ability to obtain prices on an hourly bais in order to facilitate a short-term market, and the intrinsic ability to reduce future energy deficit risks, the approach proposed also incorporates the possibility of representing transmission network flows and losses. To validate the model and solution an interior point method is implemented specifically, the primal-dual logarithmic barrier. Additional tests are performed in order to verify now he variation of the main parameters of the model influence the dispatch of generating units and the formation of energy market clearing prices

Orientador : Neida Maria Patias Volpi / Tese (doutorado) - Universidade Federal do Paraná, Setor de Tecnologia, Programa de Pós-Graduação em Métodos Numéricos em Engenharia. Defesa: Curitiba, 08/07/2016 / Inclui referências : f. 71-75 / Área de concentração / Resumo: O processo de planejamento de radioterapia é um fator essencial para garantir o nível máximo de eficiência do tratamento subsequente. Neste planejamento, há pelo menos dois problemas de decisão que podem ser modelados e resolvidos utilizando técnicas de Pesquisa Operacional. Estes incluem a melhor posição para emissão do feixe (problema do posicionamento dos feixes) e a quantidade ótima da dose que deve ser entregue através de cada feixe (problema da distribuição de dose). Esta tese apresenta um modelo matemático para otimizar concomitantemente os problemas do posicionamento dos feixes e da distribuição de dose, na presença de múltiplos objetivos. Três matheurísticas são propostas para resolver casos realistas que são de grande escala. As matheurísticas usam, respectivamente, Algoritmos Genéticos, Busca Tabu e Busca em Vizinhança Variável e são, portanto, denominadas GArad, TSrad e VNSrad. O desempenho das metodologias propostas é avaliado em dois tipos de instâncias de câncer na região da próstata, que envolvem um único corte de tomografia computadorizada (CT) e um conjunto de cortes de CT (problema 3D). Para o problema em um único corte de CT, os resultados das matheurísticas propostas são comparados com a solução ótima obtida por método exato. Em ambas instâncias, avaliaram-se os resultados em relação à cobertura de dose no tumor, e aos limites percentuais de dose nos órgãos de risco, além de avaliar a performance das metodologias em diferentes tempos computacionais. No geral, as metodologias fornecem uma solução para os problemas do posicionamento dos feixes e distribuição de dose, e, além disso, são metodologias flexíveis para considerar as necessidades específicas do paciente. Palavras-chaves: Saúde; Radioterapia; Otimização; Matheurística; Algoritmo Genético; Busca Tabu; Busca em Vizinhança Variável. / Abstract: Radiotherapy planning is a vital component in ensuring the maximum level of effectiveness of the subsequent treatment. In the planning task, there are at least two connected decision problems that can be modelled and solved using Operational Research techniques. These include the best position of the radiotherapy machine (beam angle problem) and the optimal quantity of the dose that has to be delivered through each beam (dose distribution problem). This thesis presents a mathematical optimisation model for solving the combined beam angle and dose distribution problem in the presence of multiple objectives. Three matheuristics are developed to solve realistic large-scale instances. The matheuristics use Genetic Algorithms, Tabu Search and Variable Neighbourhood Search and are hence termed GArad, TSrad and VNSrad, respectively. The performance of the proposed methods is assessed on two prostate cancer instances, namely a single computed tomography (CT) slice and a set of CT slices (3D problem). For the single-slice problem, the results of the proposed matheuristics are compared to the optimal solutions obtained by an exact method where the experiments show that the proposed methods are able to achieve optimality or to produce a relatively small deviation. For the multi-slice problem, the computational experiments show that the proposed methods produce viable solutions which can be attained in a reasonable computational time. Overall, the methodologies can provide a solution for beam angle and dose distribution problems, and besides that they are flexible to consider the patient needs. Key-words: Healthcare; Radiotherapy; Optimisation; Matheuristic; Genetic Algorithm; Tabu Search; Variable Neighbourhood Search.

Made available in DSpace on 2014-06-11T19:22:18Z (GMT). No. of bitstreams: 0 Previous issue date: 2013-03-15Bitstream added on 2014-06-13T20:09:18Z : No. of bitstreams: 1 longhi_al_me_sjrp.pdf: 570095 bytes, checksum: 5a30b272ec5bfcb3379a569e16f72a50 (MD5) / Os problemas de dimensionamento de lotes e corte de estoque unidimensional têm importante papel em diversos setores industriais, tais como, fábricas de móveis tubulares e de papel, metalurgicas, entre outros e geralmente são tratados de maneira indepen-dente. Neste trabalho, abordamos os dois problemas de maneira integrada. Estudamos um modelo clássico do problema de dimensionamento de lotes, bem como, sua reformu-lação baseada no problema de caminho mínimo. Para o problema de corte de estoque unidimensional, foram estudados três diferentes modelos matemáticos propostos na lite-ratura. Apresentamos os modelos estudados de maneira integrada e fizemos um estudo computacional, utilizando dados gerados aleatoriamente, comparando os diferentes mo-delos para o problema integrado / The lot-sizing and the one-dimensional cutting-stock problems have an important role in the production sector, such as, tubular furniture and paper factories, metallurgi-cal, among others and generally are dealt independently. In this work, we approach both problems in an integrated way. We studied a classical model for lot sizing problem and its reformulation based on the shortest path problem. For the one-dimensional cutting stock problem, three different models proposed in the literature were studied. We present the studied models in an integrated way and we made a computacional study using randomly generated data, comparing the different models for the integrated problem

Made available in DSpace on 2014-06-11T19:22:18Z (GMT). No. of bitstreams: 0 Previous issue date: 2011-02-28Bitstream added on 2014-06-13T20:48:40Z : No. of bitstreams: 1 costa_tm_me_sjrp.pdf: 1425800 bytes, checksum: f5b08954e14201ee5211145299b1e813 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho, estamos interessados em apresentar uma abordagem relacionando a análise não suave com a otimização. Primeiramente, é realizado um estudo sobre conceitos da análise não suave, como cones normais, cone tangente de Bouligand, subdiferenciais proximal, estrita, limite e de clarke. Com esses conceitos exibimos uma série de resultados, por exemplo, uma caracterização par funções de Lipschitz, subdiferencais da soma, produto e máximo de funções semi-contínuas inferior, uma versão não suave dos multiplicadores de Lagrange, i.e., condições de primeira ordem para otimalidade de problemas de otimização não suaves. Também é feito um estudo sobre as condições de segunda ordem para otimalidade em problemas de otimização não suaves e para isso, foi necessário a apresentação de outros conceitos e propriedades como os de Hessiana generalizada, Jacobiana aproximada a Hessiana proximada. Após a apresentação desses resultados, é feita uma análise sobre dois Teoremas que fornecem, com abordagens distintas, condições suficiente de segunda ordem para problemas de otimização não suaves e este trabalho é finalizado com a aprsentação de um resultado que é considerado uma unificação desses dois Teoremas / In this work we are interested in the presentation of an approach relating Nonsmooth Analysis to Optimization. First we make a study about concepts of nonsmooth analysis such as, normal cone, Bouligand's tangent cone, proximal, strict and limiting Subdiferential, as well as Clarke's Suddifferential. After these, we exhibit a series of results, for example, a characterization of Lipschitz functions, Subdifferential sum, product and maxium rules of lower semicontinuous functions and a nonsmooth version of Lagrange's multiplier rule, that is, a first order necessary condition of optimality for nonsmooth optimization problems. We also made a study about second order optimality conditions for nonsmooth optimization problems. In order to do that, it was necessary to present other concepts and properties about generalized Hessian, approximate Jacobian and approximate Hessian. After presenting these concepts and results, an analysis of two theorems that provide, with different approches, second order conditions for optimality for nonsmooth problems is made. Finally, this dissertation is completed with the exposition of a result that is considered a unification of these two theorems

Made available in DSpace on 2014-06-11T19:22:18Z (GMT). No. of bitstreams: 0 Previous issue date: 2001-02-17Bitstream added on 2014-06-13T19:07:26Z : No. of bitstreams: 1 fiorotto_dj_me_sjrp.pdf: 485977 bytes, checksum: 8cd2b3ba49a25a9c6a863795f27811c3 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / O problema de dimensionamento de lotes é um problema de otimização da produção, em que o objetivo é planejar a quantidade de itens a ser produzida em várias, ou única, máquinas em cada período ao longo do horizonte de tempo, de modo a tender uma demanda e otimizar uma função objetivo. Este trabalho aborda o problema de dimensionamento de lotes em um único estágio em um ambiente com máquinas paralelas distintas. Cada item pode ser produzido em qualquer máquina, acarretando um tempo de preparação que é gasto antes de começar a produção. O objetivo do trabalho consiste em obter limitantes inferiores de boa qualidade para este problema. Para tanto, é desenvolvido um método de solução baseado numa reformulação do problema a e na relaxação lagrangiana de um conjunto de restrições. Alguns resultados computacionais são apresentados algumas propostas futuras para a continuidade do trabalho. / The lot-sizing problem is a production optimization problem, where the objective is to plan the quantity of items to be produced in multiple, or single, machines in each period over a time horizon, in order to satisfy a demand and optimize an objective function. This work addresses the single stage parallel machine lot-sizing problem. Each item can be produced on any machine, and incur a setup time before to start the production. The objective of this work is to lower bounds of good quality for this problem. A solution method is developed based on a reformulation of the problem and the Lagrangian relaxation of a set of constrainsts. Some computational results are presented comparing the proposed method with a method from the literature, and, some future researches are proposed.