A branch-and-price algorith, for a compressor scheduling problem
dc.contributor.advisor | Buriol, Luciana Salete | pt_BR |
dc.contributor.author | Friske, Marcelo Wuttig | pt_BR |
dc.date.accessioned | 2016-05-12T02:14:30Z | pt_BR |
dc.date.issued | 2016 | pt_BR |
dc.identifier.uri | http://hdl.handle.net/10183/140804 | pt_BR |
dc.description.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-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. | en |
dc.description.abstract | 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. | pt_BR |
dc.format.mimetype | application/pdf | pt_BR |
dc.language.iso | eng | pt_BR |
dc.rights | Open Access | en |
dc.subject | Geoinformática | pt_BR |
dc.subject | Compressor scheduling problem | en |
dc.subject | Algoritmos | pt_BR |
dc.subject | Branch-and-price | en |
dc.subject | Column generation | en |
dc.subject | Piecewiselinear formulation | en |
dc.title | A branch-and-price algorith, for a compressor scheduling problem | pt_BR |
dc.type | Dissertação | pt_BR |
dc.contributor.advisor-co | Camponogara, Eduardo | pt_BR |
dc.identifier.nrb | 000991525 | pt_BR |
dc.degree.grantor | Universidade Federal do Rio Grande do Sul | pt_BR |
dc.degree.department | Instituto de Informática | pt_BR |
dc.degree.program | Programa de Pós-Graduação em Computação | pt_BR |
dc.degree.local | Porto Alegre, BR-RS | pt_BR |
dc.degree.date | 2016 | pt_BR |
dc.degree.level | mestrado | pt_BR |
Files in this item
This item is licensed under a Creative Commons License
-
Exact and Earth Sciences (5098)Computation (1754)