A branch-and-price algorith, for a compressor scheduling problem

Visualizar/abrir
Data
2016Autor
Orientador
Co-orientador
Nível acadêmico
Mestrado
Tipo
Assunto
Abstract
This work presents the study and application of a branch-and-price algorithm for solving a compressor scheduling problem. The problem is related to oil production and consists of defining a set of compressors to be activated, supplying the gas-lift demand of a set of wells and minimizing the associated costs. The problem has a non-convex objective function, to which a piecewise-linear formulation has been proposed. This dissertation proposes a column generation approach based on the Dantzig-Wol ...
This work presents the study and application of a branch-and-price algorithm for solving a compressor scheduling problem. The problem is related to oil production and consists of defining a set of compressors to be activated, supplying the gas-lift demand of a set of wells and minimizing the associated costs. The problem has a non-convex objective function, to which a piecewise-linear formulation has been proposed. This dissertation proposes a column generation approach based on the Dantzig-Wolfe decomposition, which achieves tighter lower bounds than the straightforward linear relaxation of the piecewise-linear formulation. The column generation was embedded in a branch-and-price algorithm and further compared with CPLEX, obtaining optimal solutions in lesser time for a set of instances. Further, the branch-and-price algorithm can find better feasible solutions for large instances under a limited processing time. ...
Resumo
O presente trabalho realiza o estudo e aplicação de um algoritmo de branch-and-price para a resolução de um problema de escalonamento de compressores. O problema é ligado à produção petrolífera, o qual consiste em definir um conjunto de compressores a serem ativados para fornecer gas de elevação a um conjunto de poços, atendendo toda demanda e minimizando os custos envolvidos. O problema é caracterizado por uma função objetivo não-convexa que é linearizada por partes de forma a ser formulada co ...
O presente trabalho realiza o estudo e aplicação de um algoritmo de branch-and-price para a resolução de um problema de escalonamento de compressores. O problema é ligado à produção petrolífera, o qual consiste em definir um conjunto de compressores a serem ativados para fornecer gas de elevação a um conjunto de poços, atendendo toda demanda e minimizando os custos envolvidos. O problema é caracterizado por uma função objetivo não-convexa que é linearizada por partes de forma a ser formulada como um problema de programação inteira mista. A abordagem de geração de colunas é baseada na decomposição de Dantzig-Wolfe e apresenta melhores limitantes inferiores em relação à relaxação linear da formulação compacta. O branch-and-price é comparado ao solver CPLEX, sendo capaz de encontrar a solução ótima em menor tempo para um conjunto de instâncias, bem como melhores soluções factíveis para instâncias maiores em um período de tempo limitado. ...
Instituição
Universidade Federal do Rio Grande do Sul. Instituto de Informática. Programa de Pós-Graduação em Computação.
Coleções
-
Ciências Exatas e da Terra (5183)Computação (1779)
Este item está licenciado na Creative Commons License
