Made available in DSpace on 2014-06-11T19:22:34Z (GMT). No. of bitstreams: 0 Previous issue date: 2012-08-22Bitstream added on 2014-06-13T19:08:11Z : No. of bitstreams: 1 pinheiro_rbn_me_bauru.pdf: 19855827 bytes, checksum: 0c72e37d2b42539464b7fafb4a4e52a2 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho apresentamos o método previsor-corretor primal-dual de pontos interiores, com barreira logarítmica modificada e estratégia de ajuste cúbico (MPIBLM-EX) e o método previsor-corretor primal-dual de pontos interiores, com barreira logarítmica modificada, com estratégias de ajuste cúbico e de convergência global (MPIBLMCG-EX). Na definição do algoritmo proposto, a função barreira logarítmica modificada auxilia o método em sua inicialização com pontos inviáveis. Porém, a inviabilidade pode ocorrer em pontos tais que o logaritmo não está definido, consequentemente, isso implica na não existência de função barreira logarítmica modificada. Para suprir essa dificuldade um polinômio cúbico ajustado ao logaritmo, que preserva as derivadas de primeira e segunda do mestre definido a partir de um ponto da região ampliada ao método previsor-corretor primal-dual de pontos interiores com barreira logarítmica modificada (MPIBML); no processo previsor são realizadas atualizações do parâmetro de barreira nos resíduos das restrições de complementaridade, considerando aproximações de primeira ordem do sistema de direções de busca, enquanto que no procedimento corretor, incluímos os termos quadráticos não-lineares dos resíduos citados, que foram desprezados no procedimento previsor. Considerando também a estratégia de convergência global para o MPIBLM-EX, a qual utiliza uma variante do método de Levenberg-Marquardt para ajustar a matriz dual normal da função lagrangiana, caso esta não seja definida positiva. A matriz dual normal é redefinida para as restrições primais de igualdade, de desigualdade e para as variáveis canalizadas, incorporando variáveis duais e matrizes diagonais relativas às restrições de complementariade. Desse estudo, o MPIBLM-EX é transformado no MPIBLMCG-EX e mostramos... / This work presents a predictor primal-dual interior point method with modified log-barrier and third order extrapolation strategy (IPMLBM-EX) and also and extension of this method with the inclusion of the global convergence strategy (IPMLBGCM-EX). In the definition of the proposed algorithm, the modified log-barrier function helps the method initialize with infeasible points. However, infeasibility may occur for some point where the logarithm is not defined. The implicates in non-existence of the modified log-barrier function. To cope with such as problem, a cubic polynomial function is adjusted to the logarithmic function. Sucha polynomial function preserves first and second order derivatives in certain point defined in the extended region. This function is applied to the predictor-corretor primal-dual interior point method with modified log-barrier function. In the predictor procedure, the barrier parameter is updated in the complementarity conditions considering first-order approximations of the search direction, while the corrector procedure includes the nonlinear quadratic terms of the mentioned residuals, which were neglected in the predictor procedure. We also consider the global convergence strategy for the method, which uses a variant of the Levenberg-Marquardt method to update the normal dual matrix of the Langrangian function, should it fail to be positively defined. In this case, this matrix is redefined for equality primal constraints, bounded inequality primal constraints and bounded variables, incorporating dual variables and diagonal matrices of the complementarity constraints. From such studies, the IPMLBM-EX method is extended to include the global convergence strategy (IPMLBGCM-EX). We have show that both methods are projected gradient methods. An implementation performed with Matlab 6.1 has shown the... (Complete abstract click electronic access below)

Computational Grids are large infrastructures composed of several components such as clusters, or massively parallel machines, generally spread across a country or the world, linked together through some network such as Internet, and allowing a transparent access to any resource. Grids have become unavoidable for a large part of the scientific community requiring computational power such as high-energy physics, bioinformatics or earth observation. Large projects are emerging, often at an international level, but even if Grids are on the way of being efficient and user-friendly systems, computer scientists and engineers still have a huge amount of work to do in order to improve their efficiency. Amongst a large number of problems to solve or to improve upon, the problem of scheduling the work and balancing the load is of first importance.<p><p><p>This work concentrates on the way the work is dispatched on such systems, and mainly on how the first level of scheduling – generally name brokering, or meta-sheduling – is performed. We deeply analyze the behavior of popular strategies, compare their efficiency, and propose a new very efficient brokering policy providing notable performances, attested by the large number of simulations we performed and provided in the document.<p><p><p>The work is mainly split in two parts. After introducing the mathematical framework on which the following of the manuscript is based, we study systems where the grid brokering is done without any feed-back information, i.e. without knowing the current state of the clusters when the resource broker – the grid component receiving jobs from clients and performing the brokering – makes its decision. We show here how a computational grid behaves if the brokering is done is such a way that each cluster receives a quantity of work proportional to its computational capacity.<p><p><p>The second part of this work is rather independent from the first one, and consists in the presentation of a brokering strategy, based on Whittle's indices, trying to minimize as much as possible the average sojourn time of jobs. We show how efficient the proposed strategy is for computational grids, compared to the ones popular in production systems. We also show its robustness to several parameter changes, and provide several very efficient algorithms allowing to make the required computations for this index policy. We finally extend our model in several directions.<p> / Doctorat en sciences, Spécialisation Informatique / info:eu-repo/semantics/nonPublished

Dans la collaboration entre transporteurs, plusieurs transporteurs forment une alliance pour échanger leurs demandes de transport dans le but d'améliorer la rentabilité. Dans cette thèse, nous avons étudié la planification collaborative de transport entre transporteurs de charges partielles. Plus concrètement, nous avons étudié trois sous-problèmes soulevés dans cette planification collaborative: le problème de ramassage et de livraison avec fenêtres de temps, profits et demandes réservées, le problème de détermination de gagnants dans l'échange combinatoire, et le problème de génération d'enchère.Ces trois sous-problèmes sont les problèmes clés pour la planification collaborative de transport parmi des transporteurs, et ils sont peu étudiés dans la littérature. Nous avons établi les nouveaux modèles de programmation mathématique pour ces problèmes et développé des heuristiques efficaces pour trouver des solutions très proches de leurs optimums dans un temps de calcul raisonnable. Les heuristiques proposées sont plus performantes que les solveurs commerciaux (GUROBI, CPLEX) non seulement en termes de la qualité de solution, mais aussi en termes du temps de calcul. / In carrier collaboration, multiple carriers form an alliance to exchange their delivery requests for the purpose of improving profitability. In this thesis, we have studied the collaborative transportation planning (CTP) among less-than-truckload (LTL) carriers. More concretely, we have studied three sub-problems raised in this collaborative planning: the pickup and delivery problem with time windows, profits, and reserved requests (PDPTWPR), the winner determination problem (WDP) in carrier collaboration via combinatorial exchange (CE), and the bid generation problem (BGP).These sub-problems are the key issues for collaborative transportation planning among carriers, and they are rarely studied in the literature. We have established new mathematical programming models for these problems and developed efficient heuristics to find solutions close to their optimums in a reasonable computational time. The heuristics proposed are more efficient than commercial solvers (GUROBI, CPLEX) not only in terms of solution quality, but also in terms of computation time.

Many electric utilities have been tapping such energy sources as wind energy or conservation for years. However, the literature shows few attempts to incorporate such non-dispatchable energy sources as decision variables into the long-range planning methodology. In this dissertation, efficient algorithms for electric utility capacity expansion planning with renewable energy are developed. The algorithms include a deterministic phase which quickly finds a near-optimal expansion plan using derating and a linearized approximation to the time-dependent availability of non-dispatchable energy sources. A probabilistic second phase needs comparatively few computer-time consuming probabilistic simulation iterations to modify this solution towards the optimal expansion plan. For the deterministic first phase, two algorithms, based on a Lagrangian Dual decomposition and a Generalized Benders Decomposition, are developed. The Lagrangian Dual formulation results in a subproblem which can be separated into single-year plantmix problems that are easily solved using a breakeven analysis. The probabilistic second phase uses a Generalized Benders Decomposition approach. A depth-first Branch and Bound algorithm is superimposed on the two-phase algorithm if conventional equipment types are only available in discrete sizes. In this context, computer time savings accrued through the application of the two-phase method are crucial. Extensive computational tests of the algorithms are reported. Among the deterministic algorithms, the one based on Lagrangian Duality proves fastest. The two-phase approach is shown to save up to 80 percent in computing time as compared to a purely probabilistic algorithm. The algorithms are applied to determine the optimal expansion plan for the Tijuana-Mexicali subsystem of the Mexican electric utility system. A strong recommendation to push conservation programs in the desert city of Mexicali I results from this implementation. / Ph. D.

The tree-width and branch-width of a graph are two well-studied examples of parameters that measure how well a given graph can be decomposed into a tree structure. In this thesis we give several results and applications concerning these concepts, in particular if the graph is embedded on a surface. In the first part of this thesis we develop a geometric description of tangles in graphs embedded on a fixed surface (tangles are the obstructions for low branch-width), generalizing a result of Robertson and Seymour. We use this result to establish a relationship between the branch-width of an embedded graph and the carving-width of an associated graph, generalizing a result for the plane of Seymour and Thomas. We also discuss how these results relate to the polynomial-time algorithm to determine the branch-width of planar graphs of Seymour and Thomas, and explain why their method does not generalize to surfaces other than the sphere. We also prove a result concerning the class C_2k of minor-minimal graphs of branch-width 2k in the plane, for an integer k at least 2. We show that applying a certain construction to a class of graphs in the projective plane yields a subclass of C_2k, but also show that not all members of C_2k arise in this way if k is at least 3. The last part of the thesis is concerned with applications of graphs of bounded tree-width to the Traveling Salesman Problem (TSP). We first show how one can solve the separation problem for comb inequalities (with an arbitrary number of teeth) in linear time if the tree-width is bounded. In the second part, we modify an algorithm of Letchford et al. using tree-decompositions to obtain a practical method for separating a different class of TSP inequalities, called simple DP constraints, and study their effectiveness for solving TSP instances.

O presente trabalho desenvolve um modelo de apoio à tomada de decisão de atividades de scheduling em um sistema de dutos sequenciais, com uma origem e vários destinos. Esse modelo foi inserido em uma ferramenta computacional que possibilita a realização de estudos de caso em um duto real denominado OSBRA, que a partir da maior refinaria brasileira, a REPLAN, abastece cinco órgãos localizados em quatro unidades da federação diferentes. O sistema proposto baseia seu método na execução iterativa de um modelo de programação linear inteira mista, com o horizonte de tempo sendo deslocado com o intuito de se atingir uma programação para um período de no mínimo um mês. São consideradas no modelo as principais características operacionais do OSBRA, como variação da vazão em função da entrada ou saída de sangrias de recebimento, sempre respeitando os limites de vazão tanto dos trechos de dutos quanto das sangrias. Outras características do sistema real contempladas no modelo são o recebimento por parte das bases intermediárias exclusivamente por sangria, ou seja, apenas uma parte da batelada é recebida evitando, desta forma, a parada dos trechos de duto a jusante; variação diária de demanda e utilização de bateladas selo para evitar a contaminação entre produtos adjacentes. Dezoito cenários do sistema OSBRA, com diferentes características sazonais, foram submetidos ao modelo, que obteve soluções de grande qualidade, atingindo-se um nível de serviço satisfatório na grande maioria dos cenários. / This thesis presents a model to support decision making of scheduling activities in a sequential pipeline system, composed by one refinery source and multiple destinations. This model is inserted into a system and used to develop a case study in the real world pipeline system called OSBRA that links the largest refinery in Brazil, REPLAN, to five terminals located in four different states. The proposed system relies its method in the iterative execution of a model of mixed integer linear programming, with the time horizon being moved in order to achieve a schedule for a period of at least one month. The main operational features and restrictions of OSBRA are considered in this model, as the flow variation due to the entry or exit of bleeding receiving, always within the limits of both the flow sections of pipelines as of bleeding. Others features of the real system contemplated in the model are the receiving by the intermediate bases exclusively by bleeding, meaning that only part of the batch is received thus, avoiding downstream stretches from the pipeline to stop, daily variance in the demand and the use of stamp batches to prevent contamination between adjacent derivatives. Eighteen scenarios of OSBRA’s system were submitted to the model and high quality solutions were obtained, reaching a satisfactory level of service in most scenarios.

A otimização de uma rede de transporte de derivados de petróleo é um problema complexo e abordado na literatura atual. A modelagem matemática deste problema proposta neste trabalho cria um problema de otimização combinatorial. Métodos de resolução deste problema através da programação linear inteira mista e de algoritmos heurísticos de evolução diferencial (Evolução Diferencial Binária e Evolução Diferencial Discretizada) são propostos utilizando variáveis binárias. Os resultados encontrados com a programação linear apresentam valores ótimos para os benchmarks com pequenos espaços de busca e valores sub-ótimos para grandes. Resultados utilizando a evolução diferencial também são apresentados como uma alternativa de baixo esforço computacional. A aplicação destes métodos proporciona alternativas para o transporte de diferentes produtos em um horizonte de tempo definido e compara os métodos heurísticos com codificações binárias e contínuas. Tais resultados incentivam a utilização de algoritmos heurísticos com codificação contínua e apontam os métodos de discretização como alternativas eficazes para a resolução de problemas discretos. / The optimization of an pipeline network is a complex problem and addressed in the current literature. The mathematical modeling of this problem proposed in this paper creates a problem of combinatorial optimization. Methods for solving this problem using linear mixed integer programming and heuristic algorithms of differential evolution (Binary Differential Evolution and Discretized Differential Evolution) are proposed using binary variables. The results obtained with the linear programming have optimal values for the benchmarks with small search spaces and sub-optimal for large values. Results using the differential evolution are also presented as an alternative low computational effort. The application of these methods provides alternatives for transporting different products in a defined time horizon and compare heuristic methods with continuous and binary encodings. Such results encourage the use of heuristic algorithms with continuous coding and the point discretization methods as effective for solving problems discrete alternatives.

O presente trabalho desenvolve um modelo de apoio à tomada de decisão de atividades de scheduling em um sistema de dutos sequenciais, com uma origem e vários destinos. Esse modelo foi inserido em uma ferramenta computacional que possibilita a realização de estudos de caso em um duto real denominado OSBRA, que a partir da maior refinaria brasileira, a REPLAN, abastece cinco órgãos localizados em quatro unidades da federação diferentes. O sistema proposto baseia seu método na execução iterativa de um modelo de programação linear inteira mista, com o horizonte de tempo sendo deslocado com o intuito de se atingir uma programação para um período de no mínimo um mês. São consideradas no modelo as principais características operacionais do OSBRA, como variação da vazão em função da entrada ou saída de sangrias de recebimento, sempre respeitando os limites de vazão tanto dos trechos de dutos quanto das sangrias. Outras características do sistema real contempladas no modelo são o recebimento por parte das bases intermediárias exclusivamente por sangria, ou seja, apenas uma parte da batelada é recebida evitando, desta forma, a parada dos trechos de duto a jusante; variação diária de demanda e utilização de bateladas selo para evitar a contaminação entre produtos adjacentes. Dezoito cenários do sistema OSBRA, com diferentes características sazonais, foram submetidos ao modelo, que obteve soluções de grande qualidade, atingindo-se um nível de serviço satisfatório na grande maioria dos cenários. / This thesis presents a model to support decision making of scheduling activities in a sequential pipeline system, composed by one refinery source and multiple destinations. This model is inserted into a system and used to develop a case study in the real world pipeline system called OSBRA that links the largest refinery in Brazil, REPLAN, to five terminals located in four different states. The proposed system relies its method in the iterative execution of a model of mixed integer linear programming, with the time horizon being moved in order to achieve a schedule for a period of at least one month. The main operational features and restrictions of OSBRA are considered in this model, as the flow variation due to the entry or exit of bleeding receiving, always within the limits of both the flow sections of pipelines as of bleeding. Others features of the real system contemplated in the model are the receiving by the intermediate bases exclusively by bleeding, meaning that only part of the batch is received thus, avoiding downstream stretches from the pipeline to stop, daily variance in the demand and the use of stamp batches to prevent contamination between adjacent derivatives. Eighteen scenarios of OSBRA’s system were submitted to the model and high quality solutions were obtained, reaching a satisfactory level of service in most scenarios.

A otimização de uma rede de transporte de derivados de petróleo é um problema complexo e abordado na literatura atual. A modelagem matemática deste problema proposta neste trabalho cria um problema de otimização combinatorial. Métodos de resolução deste problema através da programação linear inteira mista e de algoritmos heurísticos de evolução diferencial (Evolução Diferencial Binária e Evolução Diferencial Discretizada) são propostos utilizando variáveis binárias. Os resultados encontrados com a programação linear apresentam valores ótimos para os benchmarks com pequenos espaços de busca e valores sub-ótimos para grandes. Resultados utilizando a evolução diferencial também são apresentados como uma alternativa de baixo esforço computacional. A aplicação destes métodos proporciona alternativas para o transporte de diferentes produtos em um horizonte de tempo definido e compara os métodos heurísticos com codificações binárias e contínuas. Tais resultados incentivam a utilização de algoritmos heurísticos com codificação contínua e apontam os métodos de discretização como alternativas eficazes para a resolução de problemas discretos. / The optimization of an pipeline network is a complex problem and addressed in the current literature. The mathematical modeling of this problem proposed in this paper creates a problem of combinatorial optimization. Methods for solving this problem using linear mixed integer programming and heuristic algorithms of differential evolution (Binary Differential Evolution and Discretized Differential Evolution) are proposed using binary variables. The results obtained with the linear programming have optimal values for the benchmarks with small search spaces and sub-optimal for large values. Results using the differential evolution are also presented as an alternative low computational effort. The application of these methods provides alternatives for transporting different products in a defined time horizon and compare heuristic methods with continuous and binary encodings. Such results encourage the use of heuristic algorithms with continuous coding and the point discretization methods as effective for solving problems discrete alternatives.

Orientadores: Pedro Luis Dias Peres, Ricardo Coração de Leão Fontoura de Oliveira / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-14T06:55:42Z (GMT). No. of bitstreams: 1 Moreira_HeberRocha_M.pdf: 2003528 bytes, checksum: 9b091e7706d78e1298bd1d0603504e7f (MD5) Previous issue date: 2009 / Resumo: Esta dissertação trata de um dos mais importantes problemas em aberto na teoria de controle, o projeto de controladores por realimentação estática de saída. A principal contribuição é propor um método para computar controladores robustos estáticos por realimentação de saída para sistemas lineares incertos discretos no tempo, usando um controlador por realimentação de estados como parâmetro de entrada do método. Além disso, os resultados são estendidos para tratar do projeto de controle H2 robusto por realimentação de saída. As condições de síntese são formuladas em termos de um procedimento convexo de otimização, baseado em um conjunto finito de desigualdades matriciais lineares. Exemplos numéricos são apresentados para ilustrar a eficiência dos metodos propostos quando comparados com outros métodos existentes na literatura. / Abstract: This thesis deals with one of the most important open problems in control theory, the design of static output feedback controllers. The main contribution is to propose a method to compute robust static output feedback controllers for uncertain linear discrete-time systems, using a state feedback controller as an input parameter for the method. Additionally, the results are extended to cope with H2 static output feedback control design. The synthesis conditions are formulated in terms of a convex optimization procedure, based on a finite set of linear matrix inequalities. Numerical examples are presented to illustrate the effectiveness of the proposed approach compared to other methods available in the literature. / Mestrado / Automação / Mestre em Engenharia Elétrica