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

## .

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

 Título A branch-and-price algorith, for a compressor scheduling problem Autor Friske, Marcelo Wuttig Orientador Buriol, Luciana Salete Co-orientador Camponogara, Eduardo Data 2016 Nível Mestrado Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Programa de Pós-Graduação em Computação. Assunto Algoritmos Geoinformática [en] Branch-and-price [en] Column generation [en] Compressor scheduling problem [en] Piecewiselinear formulation 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. 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 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. Tipo Dissertação URI http://hdl.handle.net/10183/140804
Arquivos Descrição Formato
000991525.pdf (760.3Kb) Texto completo Adobe PDF Visualizar/abrir

## Este item aparece na(s) seguinte(s) coleção(ões)

Mostrar registro completo

# Percorrer

• ## Esta coleção

• O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.