( PDF ) Alocação de gás de injeção em poços de petróleo sob restrições d precedência:linearização por partes e programação inteira

Download PDF

ads:

AUGUSTO MARASCA DE CONTO

ALOCAÇÃO DE GÁS DE INJEÇÃO EM POÇOS

DE PETRÓLEO SOB RESTRIÇÕES DE

PRECEDÊNCIA: LINEARIZAÇÃO POR PARTES E

PROGRAMAÇÃO INTEIRA

FLORIANÓPOLIS

2006

ads:

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

UNIVERSIDADE FEDERAL DE SANTA CATARINA

PROGRAMA DE PÓS-GRADUAÇÃO

EM ENGENHARIA ELÉTRICA

ALOCAÇÃO DE GÁS DE INJEÇÃO EM POÇOS

DE PETRÓLEO SOB RESTRIÇÕES DE

PRECEDÊNCIA: LINEARIZAÇÃO POR PARTES E

PROGRAMAÇÃO INTEIRA

Dissertação submetida à Universidade Federal de Santa Catarina

como requisito parcial à obtensão do grau de

MESTRE EM ENGENHARIA ELÉTRICA

por

AUGUSTO MARASCA DE CONTO

Florianópolis, setembro de 2006.

ads:

ALOCAÇÃO DE GÁS DE INJEÇÃO EM POÇOS

DE PETRÓLEO SOB RESTRIÇÕES DE

PRECEDÊNCIA: LINEARIZAÇÃO POR PARTES E

PROGRAMAÇÃO INTEIRA

Augusto Marasca de Conto

Esta Dissertação foi julgada adequada para a obtenção do título de Mestre em Engenharia

na especialidade Engenharia Elétrica, área de concentração Automação e Sistemas, e

aprovada em sua forma ﬁnal pelo Programa de Pós-Graduação.

Florianópolis, Setembro de 2006.

Prof. Eduardo Camponogara, Ph.D. (Orientador)

Prof. Nelson Sadowski, Dr.

Coordenador do Programa de Pós-Graduação em Engenharia Elétrica

da Universidade Federal de Santa Catarina

Banca Examinadora:

Prof. Eduardo Camponogara, Ph.D. (Orientador)

Prof. Mário César Zambaldi, Dr.

Prof. José Eduardo Ribeiro Cury, Dr.

Prof. Rômulo Silva de Oliveira, Dr.

Dedico aos meus pais, Augusto e Ivone,

e à minha irmã Cláudia.

iii

Resumo da dissertação apresentada à UFSC como parte dos requisitos necessários para obtenção do

grau de Mestre em Engenharia Elétrica.

ALOCAÇÃO DE GÁS DE INJEÇÃO EM POÇOS

DE PETRÓLEO SOB RESTRIÇÕES DE

PRECEDÊNCIA: LINEARIZAÇÃO POR PARTES E

PROGRAMAÇÃO INTEIRA

Augusto Marasca de Conto

Setembro/2006

Orientador: Eduardo Camponogara

Área de Concentração: Automação e Sistemas

Palavras-chave: Campos de petróleo, alocação de gás de injeção, formulação linear por partes, pro-

gramação inteira mista, teoria poliedral, restrições de precedência

Número de Páginas: xi + 94

A alocação ótima de gás de injeção busca taxas de injeção para poços de petróleo ope-

rados por gas-lift que otimize uma função objetivo, normalmente que maximize o lucro, em

um campo de petróleo. Apesar do grande interesse nesta classe de problemas, a maioria

dos trabalhos nesta área não os trata adequadamente, produzindo soluções sub-ótimas e não

considerando explicitamente decisões discretas de ativação e desativação dos poços. Neste

trabalho buscamos obter taxas ótimas de injeção de gás considerando restrições de capaci-

dade máxima de gás disponível e restrições de precedência de ativação dos poços. Como a

curva de performance do poço, que caracteriza sua resposta, é não-linear, aplicamos a ela

um procedimento de linearização por partes. Então utilizamos programação linear inteira

mista, que possui um grande ferramental teórico e algorítmico. Este problema pertence a

classe NP-Difícil, então apresentamos um procedimento para obtenção de cortes que ace-

lera a busca da resposta ótima. Experimentos computacionais mostraram que estes cortes

podem reduzir o número de iterações do algoritmo de otimização. A programação inteira

mista também nos garante que a solução ótima global seja obtida, e permite uma medida

da qualidade da solução pelos limites primal-dual, caso a execução do algoritmo seja inter-

rompida. Desenvolvemos também uma interface de otimização para o usuário, que permite

que ele especiﬁque uma instância de um problema de alocação de gás de injeção e obtenha a

solução ótima, sem que para isto ele necessite conhecer detalhes do modelo e do algoritmo

de resolução do problema.

Abstract of dissertation presented to UFSC as a partial fulﬁllment of the requirements for the degree

of Master in Electrical Engineering.

LIFT-GAS ALLOCATION TO OIL WELLS UNDER

PRECEDENCE CONSTRAINTS: PIECEWISE

LINEARIZATION AND INTEGER PROGRAMMING

Augusto Marasca de Conto

September/2006

Advisor: Eduardo Camponogara

Area of Concentration: Automation and Systems Engineering

Key words: Oil ﬁelds, lift-gas allocation, piecewise linear formulation, mixed-integer programming,

polyhedral theory, precedence constraints

Number of Pages: xi + 94

Optimum lift-gas allocation searches gas injection rates for wells in gas-lifted oil ﬁelds that

optimizes an objective, generally proﬁt. Despite the long interest, most of the literature lack

rigor, producing sub-optimal solutions and not treating explicitly discrete decisions and well

activation and deactivation. In this work, we present a formulation for optimum lift-gas al-

location with maximum available gas and activation precedence constraints. We use mixed

integer linear programming with piecewise linearization of the well performance curves, be-

cause of its great theoretical and algorithmic possibilities. This problem belongs to the NP-

Hard class, thus we propose a procedure to obtain cutting planes that accelerates the search

for the optimum allocation. Computational experiments showed that these cuts can reduce

the number of algorithmic iterations. Mixed integer programming also produces globally

optimum solutions and gives a measure of the solution quality by the primal-dual bounds,

in case of the algorithmic execution is interrupted. We also have developed an optimiza-

tion interface that allows the user to specify an instance of the lift-gas allocation problem

and obtain its solution, without necessarily knowing details of the model and the resolution

algorithm.

Sumário

1 Introdução 1

1.1 Problemática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3 Visão geral da dissertação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 O problema de alocação de gás de injeção 3

2.1 Ciclo de vida de campos de petróleo . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.2 Elevação artiﬁcial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.3 Alocação de gás de injeção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.4 Revisão da literatura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.5 Sumário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3 Fundamentos de otimização inteira 14

3.1 Introdução à otimização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.2 Programação inteira . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.2.1 Formulações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.2.2 Introdução a algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.3 Métodos de planos de corte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.3.1 Desigualdades válidas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.3.2 Coberturas para mochila . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.3.3 Lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.3.4 Down-lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.4 O problema da mochila com restrições de precedência . . . . . . . . . . . . . . . . . 32

3.4.1 Deﬁnição do problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.4.2 K-coberturas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.4.3 Lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.5 Linearização por partes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.5.1 Modelo com pesos por ponto (Modelo I) . . . . . . . . . . . . . . . . . . . 36

3.5.2 Modelo seqüencial de pesos (Modelo II) . . . . . . . . . . . . . . . . . . . . 38

3.5.3 Modelo de Sherali (Modelo III) . . . . . . . . . . . . . . . . . . . . . . . . 40

3.6 Sumário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4 Modelo linear por partes 44

4.1 Formulação do problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4.2 Desigualdades válidas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.2.1 Coberturas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.2.2 K-Coberturas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4.3 Fatores de lifting para K-coberturas . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.4 Fatores de pseudo-lifting para K-coberturas . . . . . . . . . . . . . . . . . . . . . . 56

4.5 Resultados computacionais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

4.6 Sumário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

5 Interface de otimização 67

5.1 Ambiente de especiﬁcação do problema . . . . . . . . . . . . . . . . . . . . . . . . 68

5.1.1 Estrutura de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

5.1.2 Ajuste de curvas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

5.1.3 Padrão dos arquivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

5.2 Servidor de otimização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

5.2.1 Gerenciador de instâncias . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

5.2.2 Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

5.3 Estudo de caso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

5.4 Sumário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

vii

6 Conclusões e trabalhos futuros 83

A Fatores de lifting exatos para uma ﬂoresta 85

B Modelo linear por partes considerando concavidade 88

B.1 Exemplo ilustrativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

viii

Lista de Figuras

2.1 Etapas de produção de um campo de petróleo . . . . . . . . . . . . . . . . . . . . . 4

2.2 Poço operado por gas-lift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.3 Curvas típicas de gas-lift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.4 Linearização por partes da curva de performance do poço . . . . . . . . . . . . . . . 8

2.5 Conjunto de poços de petróleo produzindo por gas-lift . . . . . . . . . . . . . . . . 8

2.6 Exemplo de grafo de precedência de ativação . . . . . . . . . . . . . . . . . . . . . 11

3.1 Formulações para X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.2 Exemplo ilustrativo do algoritmo de Branch and Bound . . . . . . . . . . . . . . . . 23

3.3 Ilustração do corte no problema da mochila com x

= x

= 0 e x

= x

= 1 . . . 25

3.4 Exemplo de restrição de precedência . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.5 Linearização por partes para o modelo por pesos . . . . . . . . . . . . . . . . . . . . 37

3.6 Linearização por partes para o modelo seqüencial . . . . . . . . . . . . . . . . . . . 39

3.7 Linearização por partes para o modelo de Sherali . . . . . . . . . . . . . . . . . . . 41

4.1 Linearização por partes da CPP de um poço n. . . . . . . . . . . . . . . . . . . . . . 45

4.2 Grafo de restrição de precedência G = (V,E) . . . . . . . . . . . . . . . . . . . . . 48

5.1 Ambiente de especiﬁcação do problema . . . . . . . . . . . . . . . . . . . . . . . . 68

5.2 Editor gráﬁco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

5.3 Diagrama de classes da estrutura de dados da interface . . . . . . . . . . . . . . . . 70

5.4 Guia de caracterização de poço com exemplo de ajuste de curva . . . . . . . . . . . 74

5.5 Exemplo do formato de gravação dos dados . . . . . . . . . . . . . . . . . . . . . . 75

5.6 Exemplo de conexão com o gerenciador de instâncias . . . . . . . . . . . . . . . . . 79

5.7 Interface para o usuário do servidor de otimização . . . . . . . . . . . . . . . . . . . 80

5.8 Apresentação da solução de um problema . . . . . . . . . . . . . . . . . . . . . . . 81

B.1 Exemplo de CPP considerando concavidade nas variáveis de decisão. . . . . . . . . 90

Lista de Tabelas

2.1 Comparativo entre alguns métodos de elevação artiﬁcial . . . . . . . . . . . . . . . . 5

3.1 Exemplo de instância para o problema da mochila . . . . . . . . . . . . . . . . . . . 16

3.2 Solução para uma instância do problema da mochila sem restrição de precedência . . 33

4.1 Taxa de injeção para os poços de petróleo . . . . . . . . . . . . . . . . . . . . . . . 48

4.2 Fatores de lifting para o exemplo da mochila . . . . . . . . . . . . . . . . . . . . . . 55

4.3 Recursos mínimos de ativação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

4.4 Subconjuntos para ativação de H(C) . . . . . . . . . . . . . . . . . . . . . . . . . . 60

4.5 Coeﬁcientes de pseudo-lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

4.6 Impacto dos planos de corte por taxa de injeção de gás . . . . . . . . . . . . . . . . 63

4.7 Impacto dos planos de corte por densidade do grafo . . . . . . . . . . . . . . . . . . 64

5.1 Descrição dos campos de petróleo para o estudo de caso . . . . . . . . . . . . . . . 80

Capítulo 1

Introdução

1.1 Problemática

Nos diasatuais o petróleo ainda é a principal fonte de energia em nosso planeta. Apesar deestarem

surgindo novas tecnologias, ainda somos bastante dependentes da queima destes hidrocarbonetos.

Este recurso ainda existe em grande quantidade em nosso planeta, mas é uma fonte de energia não-

renovável e, em um horizonte de tempo não muito longo, este recurso se esgotará. Uma conseqüência

natural é que conforme o extraímos, sua obtenção se torna mais difícil e cara, pois cada vez temos

que buscá-lo em regiões mais profundas (poços mais longos) e menos acessíveis (como o fundo do

oceano). A necessidade de novas fontes faz com que seja considerada a produção de óleos de difícil

extração devido à sua densidade e viscosidade.

É cada vez mais necessário técnicas eﬁcientes para a extração e processamento do petróleo. A oti-

mização entra neste contexto com o objetivo de auxiliar a atingir o desempenho ótimo dos processos

existentes.

Várias técnicas de elevação artiﬁcial podem ser empregadas para trazer o petróleo de um reserva-

tório à superfície. Uma técnica bastante utilizada no Brasil e no mundo é chamada de gas-lift, em que

gás é injetado na base do poço, diminuindo a pressão da coluna de ﬂuido que auxilia sua produção

natural. O gás utilizado geralmente é o gás produzido pelo poço junto com o petróleo, que é compri-

mido e reinjetado. O poço possui uma taxa de produção de acordo com a quantidade de gás injetado.

A relação entre a quantia de gás injetada em um poço e sua produção é conhecida como Curva de

Performance do Poço. Cada poço possui uma taxa de injeção de gás que o levará a uma produção

mais lucrativa, assim como existem taxas de injeção para cada um dos poços que levarão o campo de

petróleo a obter seu maior lucro. Não necessariamente as taxas que levam o campo a sua condição de

maior lucro são as mesmas de cada poço separadamente.

Um dos custos que envolvem a operação de um campo de gas-lift é o da compressão do gás. O

equipamento de compressão representa o maior custo na operação do campo, portanto é importante

que o gás de injeção seja utilizado da maneira mais eﬁciente possível [1]. Outra situação ocorre em

reservatórios maduros, em que o petróleo está terminando e o número de poços é grande. Nestes

1. Introdução 2

campos, não apenas é necessário determinar em que ponto de produção os poços irão operar, mas

também deve ser decidido quais poços irão operar. O operador pode desejar priorizar alguns poços,

fazendo com que outros só sejam ativados (entrem em operação) se os de maior prioridade já estive-

rem produzindo. A esta ordem de ativação dos poços, damos o nome de Restrição de Precedência.

1.2 Objetivos

Nesta dissertação apresentamos uma maneira de obter as taxas de injeção de gás que levem um

campo de petróleo com poços operados por gas-lift ao ótimo econômico. Consideramos que a capa-

cidade de gás é limitada, não necessariamente existe gás disponível para que todos os poços operem

em suas regiões de maior lucratividade. Consideramos também as restrições de precedência, limites

mínimos e máximos de operação dos poços e que eles possam ser desativados.

Para o desenvolvimento deste trabalho foi utilizada uma modelagem de otimização baseada em

programação linear inteira. Existem algoritmos para modelos desta categoria que em princípio são

capazes de gerar uma solução ótima global. Como a curva de performance do poço possui caracte-

rística não linear, foi feita uma linearização por partes, aproximando a curva por vários segmentos de

reta.

Também desenvolvemos uma interface que permite que o usuário caracterize seu campo de petró-

leo, e invoque automaticamente algoritmos de otimização; não apenas o apresentado neste trabalho

como outros. A interface tem como objetivo abstrair do usuário a compreensão do funcionamento

dos algoritmos, fazendo com que ele se preocupe apenas com a operação de seu campo de petróleo.

1.3 Visão geral da dissertação

Esta dissertação está dividida em seis capítulos. No próximo capítulo apresentamos mais deta-

lhadamente o cenário que pretendemos abordar, com um detalhamento da operação por gas-lift, uma

formulação geral para o problema e um resumo dos trabalhos existentes nesta área. No Capítulo

3 fazemos uma breve revisão dos fundamentos de otimização inteira, ferramenta que foi utilizada

para o desenvolvimento do trabalho. O emprego da teoria de otimização apresentada no problema

de alocação ótima de gás de injeção é mostrado no Capítulo 4. No Capítulo 5 apresentamos a ferra-

menta desenvolvida para auxiliar o operador a resolver problemas desta classe. Por ﬁm, no Capítulo

6 apresentamos as conclusões deste trabalho e perspectivas para trabalhos futuro.

Capítulo 2

O problema de alocação de gás de injeção

2.1 Ciclo de vida de campos de petróleo

Há vários séculos o petróleo é conhecido e utilizado. Povos antigos, como os Babilônios, Egíp-

cios, Gregos e Romanos o utilizavam para desde a pavimentação de estradas até ﬁns bélicos. Na

América, também era conhecido pelos povos Incas e Maias. Naquela época, o petróleo era retirado

de exsudações naturais, não sendo necessário a escavação para sua obtenção.

O início da era moderna do petróleo se dá em 1859, quando o primeiro poço foi perfurado.

Descobriu-se que este era um negócio bastante lucrativo, pois seus derivados substituíam o óleo de

baleia, utilizados na época para iluminação, com custos de produção bastante inferiores. Em seguida

a gasolina e o diesel, que eram derivados até então desprezados, passaram a alimentar motores à

combustão, adicionando expressivos lucros à atividade.

Em 1900 o método de percussão para perfuração de poços foi substituído pelo rotativo. Neste

método uma broca rotativa é utilizada para escavar e perfurar as rochas até o reservatório. Ele permitiu

a escavação de poços mais profundos e longos, e é empregado até hoje com algumas variações,

podendo chegar a mais de 10.000 metros.

O petróleo tem origem a partir de matéria orgânica depositada junto com sedimentos. A interação

destes elementos em condições apropriadas de temperatura e pressão são essenciais para a formação

de hidrocarbonetos. O tipo do hidrocarboneto gerado, óleo ou gás, depende da constituição da matéria

orgânica original e das condições termoquímicas presentes no processo.

Após serem gerados, os hidrocarbonetos migram de sua rocha geradora por falhas geológicas,

até encontrar uma armadilha geológica, uma rocha selante impermeável. A rocha reservatório deve

possuir espaços vazios (porosidade) e que eles estejam conectados (permeabilidade).

A descoberta de uma jazida de petróleo envolve um longo período de estudo de dados geofísicos

e geológicos. Apenas após estes estudos é proposta a perfuração de um poço pioneiro, que é a etapa

que exige mais investimentos do processo de prospecção. Não se pode prever a existência de petróleo,

apenas locais mais favoráveis para sua ocorrência.

2. O problema de alocação de gás de injeção 4

Produção

Pré-produção Construção Platô Declínio Decomposição

Tempo

Figura 2.1: Etapas de produção de um campo de petróleo

Os estudos geológicos são realizados por técnicas como a geologia de superfície, que mapeia as

rochas da superfície da área em estudo; a aerofotometria e fotogeologia, que constrói mapas geoló-

gicos a partir de imagens do terreno; e a geologia de sub-superfície, que consiste no estudo de dados

geológicos obtidos em um poço exploratório. Também são empregados métodos sísmicos, que con-

sistem em gerar ondas sísmicas e mapear sua reﬂexão no tempo e espaço, para o levantamento da

estrutura geológica do interior da área em estudo. Mais de 90% dos investimentos em prospecção são

aplicados à sísmica de reﬂexão [2].

Uma vez encontrado o petróleo, ainda é necessário estudos para se levantar o tamanho, forma e

produtividade do acúmulo. Conhecendo-se o campo, é feito um estudo de viabilidade de exploração

do reservatório. Neste estudo consideram-se a viabilidade econômica, opções de desenvolvimento do

campo, equipamentos de produção e logística de evacuação da produção. Em seguida, é realizado um

plano de desenvolvimento que serve de base para as ações tomadas sobre o campo. Seu propósito é

um projeto conceitual do equipamento a ser empregado e da política de operação para que os objetivos

de produção sejam atingidos.

A fase de produção é iniciada quando as primeiras quantidades comerciais de hidrocarbonetos são

extraídas. É o momento em que os investimentos começam a ser recuperados. A Figura 2.1 mostra a

produção em cada uma das etapas desta fase:

1. Construção: neste período os poços recém perfurados são progressivamente colocados em seus

pontos de operação;

2. Platô: novos poços são trazidos aos seus pontos de operação e os antigos começam a declinar,

mantendo a produção total constante. Este período é tipicamente de 2 a 5 anos para um campo

de óleo e maior para campos de gás [3];

3. Declínio: todos os produtores declinam sua produção.

A vida de um campo normalmente termina quando ele permanentemente gera prejuízos. Ainda é

tecnicamente possível continuar a produção, mas economicamente inviável. Neste ponto, a redução

do custo de operação pode ser utilizada para aumentar o tempo de vida do campo.

2. O problema de alocação de gás de injeção 5

Haste Bomba Elétrica Gas-Lift

Flexível Submersível

Instalação $ $$ $$$

Operação

$ $$ $$

Produção (BPD

)

1 - 5.000 100 - 60.000 80 - 10.000

Flexibilidade

++ - ++

Viscosidade

+ -

Sólidos

- - +

Gás

- - ++

Alta temperatura

+ - +

Profundidade

Curvas

- +

offshore

- - + ++

Tabela 2.1: Comparativo entre alguns métodos de elevação artiﬁcial

2.2 Elevação artiﬁcial

Quando um novo poço de petróleo é perfurado inicialmente a pressão interna do reservatório é

suﬁciente para vencer a coluna de ﬂuido e o óleo ﬂui naturalmente para a superfície, chamamos estes

poços de surgentes. Em decorrência desta extração natural, com o tempo, a pressão interna diminui e

se torna necessário algum método de elevação artiﬁcial para extrair o óleo para a superfície.

A elevação artiﬁcial não é empregada apenas quando o poço deixa de ﬂuir naturalmente. Ela

também pode ser usada para aumentar a produção de um poço de baixa vazão natural para um ponto

determinado pelo plano de produção. Podem ainda existir casos em que é necessário apenas injetar

energia em uma fase inicial, para ativar o poço, que em seguida passa a produzir naturalmente.

Existem vários métodos de elevação artiﬁcial. A escolha do método a ser empregado depende de

fatores como: viscosidade, presença de sólidos e composição do ﬂuido; temperatura, profundidade e

forma do poço (se possui curvas); se o poço está localizado em terra (onshore) ou no mar (offshore);

produtividade, custo de instalação, equipamento auxiliar necessário e presença de infra-estrutura.

Pode-se ainda iniciar a extração com um método para poços de maior produtividade e conforme a

produtividade do reservatório diminui, fazer a substituição por outro método. Alguns dos métodos

disponíveis hoje são mostrados a seguir. A Tabela 2.1 extraída de [3] mostra um comparativo entre

eles. O símbolo “$$$” indica que o método possui um custo maior que “$$”, que por sua vez é

maior que “$”. Os símbolos “- -” à “++” indicam de maneira crescente a adequação do método às

características apresentadas.

Haste Flexível: uma bomba na forma de um cilindro hidráulico é posicionada no fundo do poço.

Seu êmbolo é movido para cima e para baixo por uma haste, que é acoplada a um motor elétrico

localizado na superfície. Válvulas no cilindro controlam a entrada e saída do ﬂuido, o bombeando

para a superfície.

Bomba Elétrica Submersível: é utilizada uma bomba centrífuga de vários estágios, alimentada

BPD - Barrels Per Day, Barris por dia.

2. O problema de alocação de gás de injeção 6

Tubo

Anular

Óleo e Gás

Produzidos

Reservatório

Gás

Válvula

Figura 2.2: Poço operado por gas-lift

por um motor elétrico. A produção por este método é também determinada pelo número de estágios

que a compõem. Pode-se ainda instalar um variador da velocidade do motor que permite um ajuste

na produção do poço, mas isto representa um custo adicional e nem sempre é empregado.

Gas-Lift: um dos métodos de elevação artiﬁcial mais empregados é o gas-lift contínuo [4]. Neste

método gás em alta pressão é injetado continuamente no tubo de produção, resultando na redução da

densidade da coluna de ﬂuido, e assim reduzindo a diferença de pressão entre o topo e o fundo do

poço, estimulando a produção natural.

A Figura 2.2 (retirada de [5]) mostra um poço operando por gas-lift. As válvulas localizadas ao

longo do tubo de produção são necessárias apenas para o início da operação do poço. A descarga

do poço consiste em retirar o ﬂuido presente na coluna de produção e/ou anular para colocar o poço

em produção. Inicialmente todas as válvulas estão abertas. Conforme o gás é injetado no anular há

uma transferência de ﬂuido dele para dentro do tubo de produção. Quando o nível do ﬂuido no anular

baixar da altura da válvula, esta deve ser fechada para que o processo se mantenha nas outras válvulas

e o gás não entre diretamente no tubo de produção. O fechamento das válvulas ocorre em seqüência.

Quando todo o ﬂuido for expulso da região anular apenas a última válvula se mantém aberta, iniciando

a produção do poço. Este procedimento deve ser realizado lentamente para não daniﬁcar as válvulas.

Um poço em operação por gas-lift tem sua produção controlada pela taxa de injeção de gás apli-

cada em sua base. A relação entre a vazão de gás injetado e a vazão de saída de ﬂuido q

× q

out

dada pela curva de performance do poço (CPP).

A forma da curva depende da resposta do poço ao gás injetado. Na Figura 2.3(a), a curva A

representa um poço surgente. A injeção de gás em um poço desta categoria aumenta sua produção. A

curva B representa um poço que não ﬂui naturalmente, entretanto qualquer que seja a quantidade de

gás injetado já coloca o poço em operação. No caso da curva C, é necessário um mínimo de injeção

2. O problema de alocação de gás de injeção 7

Taxa de injeção de gás q

Taxa de produção de óleo q

out

(a)

Taxa de injeção de gás q

Taxa de produção de óleo q

out

max

out

Região

econômica

(b)

Figura 2.3: Curvas típicas de gas-lift

de gás para iniciar a produção. Por ﬁm, a curva D é semelhante a C, mas há um salto na produção

inicial para um valor maior que zero.

Destacamos nas curvas C e D a presença de uma quantidade mínima de gás injetado, que ocorre

devido a necessidade de vencer a coluna hidrostática que se forma no poço, caracterizando um limite

inferior na taxa de injeção. Também observamos que todas as curvas possuem um limite superior de

gás que pode ser injetado. Ele não deve ser ultrapassado pois a altas vazões o ﬂuido produzido passa

a carregar sólidos junto, que são prejudiciais aos equipamentos.

As CPPs possuem uma forma característica que pode ser observada na Figura 2.3(b). A partir do

ponto em que existe produção de ﬂuido há um crescimento rápido até uma vazão máxima. Após, a

curva cai lentamente até o limite superior de injeção. A região econômica do gráﬁco é onde o poço

produz com maior lucro. Considerando que não existe restrição de produção, o ponto ótimo é quando

o lucro gerado por um incremento de produção seja igual ao incremento no custo de operação [6].

A curva de performance do poço pode ser obtida numericamente por simulações a partir de méto-

dos apropriados de cálculo, como por exemplo a análise nodal [7]. Quando apenas pontos destas cur-

vas são conhecidos ou podem ser obtidos a partir de experimentos de campo, são empregados métodos

de ajuste de curvas para o levantamento delas. Para problemas de otimização clássica modelam-se as

CPPs como polinômios de terceira ordem. Entretanto, apesar de serem mais facilmente tratáveis, o

ajuste em curvas deste tipo não apresenta uma boa correlação. Alarcón et al. [8] propõem, em seu tra-

balho de alocação ótima de lift-gas utilizando programação não-linear, que a curva seja representada

por um polinômio de segunda ordem, acrescido de um termo logarítmico:

out

= c

+ c

ln(q

+ 1)

onde c

, c

e c

são as constantes que caracterizam o poço. Outra representação desta curva foi

proposta por Nakashima e Camponogara [9], utilizando a composição de duas exponenciais:

out

= α

(2− e

−β

) − α

Estas curvas apresentam melhor correlação que a polinomial pura, sendo que a baseada em exponen-

ciais se mantém ﬁel também na extrapolação. Uma propriedade interessante da curva exponencial é

2. O problema de alocação de gás de injeção 8

Taxa de injeção de gás q

Taxa de produção de óleo q

Figura 2.4: Linearização por partes da curva de performance do poço

Poços

Separador

Compressores

Reservatório

Válvulas

gás

óleo

água

Figura 2.5: Conjunto de poços de petróleo produzindo por gas-lift

que

out

= −α

−β

− α

−β

. Para que a CPP seja côncava, basta garantir que α

 0 e

 0.

Neste trabalho utilizamos uma abordagem linear por partes. Cada par de pontos consecutivos da

curva é interpolado por uma reta como pode ser visto na Figura 2.4. Esta técnica permite que sejam

empregados métodos de programação linear. Em contrapartida, faz-se necessário o uso de variáveis

de decisão para selecionar a região da curva que está sendo trabalhada. Um aspecto relevante das

curvas lineares por partes é que elas permitem utilizar os pontos de teste diretamente, sem a neces-

sidade de ajustar uma curva, o que pode ser tedioso e envolver problemas de otimização não-linear

sob restrições. Os testes para obtenção destes pontos são realizados na fase inicial de produção do

poço, antes da extração das quantidades comerciais, quando está sendo levantado o perﬁl de produ-

ção do poço e do reservatório. São medidas as quantidades de óleo, gás e água produzidas para um

conjunto adequado de taxas de injeção. Uma formulação mais detalhada da linearização por partes

para descrever as CPPs será apresentada no Capítulo 4.

Na Figura 2.5 apresentamos um esquema de um campo de petróleo com poços operados por gas-

lift. Um banco de compressores produz gás a alta pressão, que é armazenado em um reservatório.

Válvulas controlam a quantidade de gás injetado em cada poço. O petróleo produzido é levado a um

separador que divide o ﬂuido em água, óleo e gás. A água extraída sofre um processo de tratamento

para atender determinadas especiﬁcações, regulamentadas por órgãos de controle do meio ambiente,

limitando a quantidade de poluentes como o teor de óleo e sulfato de hidrogênio antes de ser descar-

tada [2]. O óleo produzido é armazenado e vendido. Uma parcela do gás é comprimida novamente

para ser reinjetada nos poços. O excedente pode ser armazenado ou escoado, ou se não existir maneira

2. O problema de alocação de gás de injeção 9

de fazê-lo, é queimado.

Uma restrição tipicamente tratada nos problemas de alocação ótima de gas-lift é a capacidade total

de injeção de gás dos compressores. Nem sempre a planta possui gás a alta pressão suﬁciente para

que todos os poços operem em seus pontos de maior lucratividade. Isto pode ocorrer, por exemplo,

porque um compressor do conjunto está desligado para reparos ou manutenção. Outra possibilidade

é de um campo com muitos poços, em que o petróleo no reservatório está terminando, devendo-se

escolher quais os poços serão ativados.

Na realidade, o cálculo das taxas de injeção ótimas não é a única ferramenta utilizada na deter-

minação dos pontos de operação dos poços. São considerados outros aspectos como, por exemplo, o

plano de recuperação do reservatório. O comportamento do acúmulo em longo prazo, sua dinâmica,

deve ser considerado para que uma extração inapropriada de alguns poços não deixem regiões do

reservatório com óleo acumulado que não possa ser extraído. Assim, restrições de precedência de

ativação podem ser utilizadas para representar estes aspectos subjetivos. Elas signiﬁcam que um dado

poço só pode ser ativado se um outro, seu predecessor na restrição, já esteja produzindo pelo menos

seu mínimo. É claro que estas restrições só fazem sentido em poços não surgentes.

2.3 Alocação de gás de injeção

A alocação ótima de gas-lift busca taxas de injeção de gás para cada um dos poços de um campo

que maximize ou minimize algum objetivo. Duas abordagens são mais comumente utilizadas: a

primeira é baseada na performance hidrodinâmica, onde se buscam pontos de operação para os poços

que maximizem a produção total do campo; outra abordagem é baseada em um critério econômico,

a qual busca o maior lucro que um conjunto de poços pode fornecer. Ainda são possíveis outras

abordagens como, por exemplo, a minimização do custo de operação sujeita a uma quota mínima

produção.

Embora neste trabalho utilizamos a abordagem baseada no critério econômico, ela pode ser adap-

tada facilmente para minimizar os custos de produção da quota mínima. Assim, nossa formulação

necessita de informações como custos de produção e lucros obtidos. É importante salientar que esta-

mos interessados na operação do campo de petróleo, por isso questões externas a ele, como situação

do mercado, não são consideradas.

Como foi visto na seção anterior, dois tipos de restrição podem ser considerados quando estamos

tratando este problema: capacidade máxima de injeção de gás, que é uma restrição decorrente das

capacidades dos compressores; e restrições de precedência, que restringe a ativação de um dado poço

em decorrência de outros. Considerando nosso objetivo econômico e estas restrições do sistema,

2. O problema de alocação de gás de injeção 10

chegamos à seguinte formulação:

P(G) : Maximize f =

∑

n=1

+ p

− p

out

−

∑

n=1

Sujeito a: q

out

= ˜q

out

) n = 1,... ,N

∑

n=1

 q

max

 y

∀(m,n) ∈ E(G)

 q

 u

n = 1,... ,N

∈ {0,1} n = 1,... ,N

onde:

• N é o número de poços que produzem via gas-lift;

• q

é a taxa de injeção de gás alocada para o poço n;

• q

out

é a taxa de produção de ﬂuidos do poço n, dada pela função ˜q

out

);

• p

e p

representam o lucro (preço de venda menos os custos de processamento) obtido por

barril de óleo e gás vendido, respectivamente;

• p

é o custo de tratamento do barril de água a ser descartada;

• p

representa o custo de compressão de gás;

• γ

, γ

e γ

são respectivamente as frações de óleo, gás e água produzidas pelo poço n, sendo

que γ

+ γ

= 1;

• ˜q

out

) é curva de performance do poço n, que relaciona a quantidade de gás injetado com a

quantidade de ﬂuido produzido no poço;

• q

max

é a capacidade total de injeção de gás, sendo que a soma das taxas de injeção de gás dos

N poços não deve ultrapassar esta taxa;

• y

assume valor 1 se o poço n está ativo, e 0 caso contrário;

• G é um grafo direcionado acíclico que representa as restrições de precedência. Seus vértices

são o conjunto dos N poços do campo e suas arestas são dadas por E(G). A Figura 2.6 apresenta

um exemplo de um grafo de precedência. Nela, os poços 1 e 3 podem ser ativados livremente,

o poço 2 requer que o de número 1 já esteja ativado pelo menos em seu mínimo, e assim

sucessivamente;

• l

e u

são respectivamente as taxas de injeção mínima e máxima para o poço n.

Proposição 2.1 P(G) é NP-Difícil no sentido forte [9].

2. O problema de alocação de gás de injeção 11

2 3

4 5 6

Figura 2.6: Exemplo de grafo de precedência de ativação

A Proposição 2.1 evidencia o grau de diﬁculdade do problema em consideração. Ou seja, existe

um algoritmo de tempo pseudo-polinomial se e somente se a classe P equivale a classe NP [10];

2.4 Revisão da literatura

Mayhill [11] analisou em seu trabalho a relação entre a taxa de injeção de gás e a produção do

poço, chamando a curva resultante de curva de performance do poço (CPP).

Desde a década de 70, problemas de injeção ótima de gás vêem sendo abordados. Redden et al.

[12] reconheceu a importância de uma operação de um campo de gas-lift de acordo com critérios

econômicos, em que leva em consideração o custo de compressão, capacidade limitada de gás e

a possibilidade de compressores estarem inoperantes. Também propuseram um procedimento para

encontrar a distribuição de gás de injeção que resulta em um maior lucro baseado na perturbação

iterativa da distribuição corrente. Apesar da qualidade da proposta iterativa, o procedimento pode

produzir soluções sub-ótimas e não pode ser estendido para tratar outras restrições, como limites

inferior e superior de gás de injeção.

Mach et al. [7] redeﬁniram o método de [12] com uma abordagem nodal que considera perdas de

pressão em toda a coluna de gas-lift. Seu procedimento nodal leva a uma curva de performance do

poço mais precisa.

Kanu et al. [6] compilou os métodos e princípios anteriores de alocação de gas-lift de acordo

com critérios econômicos em um método chamado equal slope. O método pode obter a alocação de

gás que produz maior lucro para um conjunto de poços modelados por CPPs com capacidade de gás

limitada. Este método pode ser visto como a aplicação da dualidade Lagrangeana para eliminar a

restrição de capacidade de gás. O método possui limitações, incluindo a incapacidade de tratar poços

que não respondam instantaneamente à injeção de gás (limite inferior) e a diﬁculdade de incorporar

restrições adicionais.

Mais tarde, Nishikiori et al. [13, 14] apresentaram uma formulação não-linear sob restrições

para alocação de gás de injeção, com um método quasi-Newton combinado com um descenso pela

projeção do gradiente para buscar a solução ótima. O método de Nishikiori et al. provou ser melhor

que o equal slope, obtendo alocação de maior lucro em tempo menor. Apesar da proposta ter imposto

2. O problema de alocação de gás de injeção 12

limites não-lineares às taxas de injeção, ométodo pode divergir enão trata de poços que não produzem

espontaneamente.

Buitrago et al. [4] estão entre os pioneiros em tratar de cenários com poços que não respondem

instantaneamente à injeção de gás. A abordagem, chamada de Ex-In, combina uma busca estocástica

e uma heurística de cálculo de direção de descenso. Por um lado, o método Ex-In utiliza um algoritmo

genético, no sentido que uma população de soluções evolui no tempo, mas por outro lado, utiliza uma

direção obtida de forma heurística para produzir uma solução candidata. A busca termina quando

a população de soluções não produz melhorias na solução objetivo ou após um número máximo de

iterações. Apesar da busca Ex-In ocorrer sobre o espaço de soluções factíveis, ela não garante que o

ótimo global seja alcançado, e não possui um procedimento de obtenção de um limite superior, que

poderia ser utilizado para estimar a qualidade de sua solução. Em um sistema com 56 poços, uma

comparação computacional com o método equal slope mostrou que o Ex-In obteve soluções melhores.

Alarcón et al. [8] introduziram curvas de performance de poço com termos logarítmicos e po-

linomias de segunda ordem como um ajuste melhor que os polinomiais puros para representar os

dados. Eles melhoraram o método de Nishikiori et al. [14] substituindo o método quasi-Newton

pelo algoritmo SQP (Sequential Quadratic Programming - Programação Seqüencial Quadrática) para

garantir convergência para uma solução ótima local. O algoritmo SQP é mais robusto e pode operar

com restrições adicionais, entretanto, a abordagem requer intervenção dos engenheiros para tratar de

poços que não respondem imediatamente à injeção de gás. Assim, os autores propuseram regras ad

hoc para guiar o engenheiro na decisão de quais poços devem ser ativados e desativados.

Fang e Lo [15] abandonaram os procedimentos baseados em programação não linear e sugeriram

a linearização por partes das CPPs, reformulando o problema utilizando programação linear. Esta

visão trouxe uma série de vantagens e abriu várias possibilidades. Primeiro, podemos obter soluções

ótimas globais com algoritmos poderosos de programação linear, facilmente introduzir restrições adi-

cionais e tratar de problemas muito grandes. Segundo, nos permite utilizar a teoria e algoritmos de

programação linear inteira mista (MILP) para tratar de decisões discretas. O método de Fang e Lo

superou os métodos anteriores, mas eles não ﬁzeram uso de toda a teoria para tratar problemas de

programação inteira mista de maneira sistemática, sugerindo regras heurísticas, baseadas em arre-

dondamento para tratar o problema de ativação de poços.

Wang et al. [16] sugeriram um modelo em programação não linear inteira mista (MINLP) para

generalizar a abordagem anterior. O modelo proposto incorpora as decisões de alocação de gás de in-

jeção, decisões sobre as taxas de produção e restrições da planta de produção. Como os problemas de

programação não linear inteira mista são inerentemente difíceis de serem resolvidos, eles propuseram

uma combinação de programação linear, programação separável e algoritmos genéticos. Apesar dos

resultados experimentais terem sido satisfatórios, o método pode produzir soluções sub-ótimas e não

produz limites superiores/inferiores que permitem avaliar a qualidade das soluções.

Nakashima e Camponogara [9, 17] desenvolveram algoritmos utilizando programação dinâmica

(DP) para o problema de alocação de gás de injeção. Seus métodos tratam as decisões discretas de

ativação dos poços de maneira sistemática, e consideram incertezas nas CPPs, aceitando múltiplas

curvas e resolvendo problemas max-min, resultando em soluções próximas à ótima com garantias de

2. O problema de alocação de gás de injeção 13

performance. Junto com o método de MINLP proposto em [16], foi o primeiro a tratar rigorosamente

as descontinuidades nas CPPs. O algoritmo de programação dinâmica pode tratar de restrições de

precedência de ativação, com uma execução em tempo pseudo-polinomial se as restrições possuírem a

forma de uma ﬂoresta. Além da inexistência de um algoritmo pseudo-polinomial para tratar de grafos

de precedência gerais, a limitação principal da abordagem em programação dinâmica é a diﬁculdade

de adicionar restrições.

2.5 Sumário

Neste capítulo apresentamos uma visão geral sobre a formação e operação de um campo de pe-

tróleo. Apresentamos alguns dos métodos utilizados para extrair o petróleo para a superfície e, em

seguida, nos aprofundamos no método de extração por gas-lift, em que gás é injetado na base do poço

para diminuir a pressão da coluna e possibilitar que o petróleo seja retirado. Em seguida apresentamos

o problema geral de alocação ótima de gás de injeção segundo critérios econômicos, sob restrição de

limite de capacidade de injeção e precedência na ativação dos poços. Por ﬁm, apresentamos uma

revisão bibliográﬁca, que contextualiza esta dissertação frente a outros trabalhos já publicados sobre

o assunto.

Capítulo 3

Fundamentos de otimização inteira

3.1 Introdução à otimização

Otimização é a área da matemática aplicada que busca obter valores para variáveis de decisão

com o objetivo de obter um comportamento ótimo, sujeito a um conjunto de restrições do modelo

matemático. As variáveis de decisão são avaliadas a partir de algum critério, que pode ser a maximi-

zação ou minimização de uma função. Os pontos que atendem as restrições do problema são pontos

factíveis, e seu conjunto é denominado de região factível do problema.

Modelos são estruturas que buscam representar alguma característica de uma realidade. As razões

que levam ao uso de modelos são as mais variadas. Dentre elas podemos citar: ajudam a compreender

melhor a natureza do objeto que está sendo estudado; experimentos realizados sobre o objeto em

estudo possuem custos proibitivos ou até são impossíveis; podem-se realizar testes antes que o objeto

em estudo seja construído. Modelos podem ser concretos, como uma miniatura de avião utilizada

em testes em um túnel de vento. Modelos abstratos usualmente são representações matemáticas da

realidade em estudo. A modelagem de um problema não é uma tarefa trivial, dependendo de fatores

subjetivos como intuição, experiência, criatividade e poder de síntese [18, 19].

Para modelar problemas de otimização é utilizada uma linguagem conhecida como programação

matemática. É importante ressaltar que programação matemática é bastante diferente de programação

de computadores. Programação matemática é utilizada no sentido de “planejamento” [18]. Inevitavel-

mente programação matemática envolve computação, pois problemas práticos normalmente possuem

grandes quantidades de dados e cálculos que tornam necessário o emprego dos computadores. Os

elementos que a compõem são:

Variáveis de decisão: Variáveis cujos valores deﬁnem uma solução para o problema;

Função objetivo: Expressão que relaciona as variáveis de decisão com o comportamento do modelo.

É a função que se deseja maximizar ou minimizar;

Restrições: Conjunto de funções das variáveis de decisão que deﬁnem o espaço de soluções que

pode ser aplicado ao problema.

3. Fundamentos de otimização inteira 15

Um problema geral de otimização pode ser escrito em programação matemática como:

P : Maximize f(x)

Sujeito a: g(x)  0

x ∈ R

onde x é o vetor de variáveis de decisão, f : R

→ R é a função objetivo e g : R

→ R

são as restrições

do problema que limitam o espaço de soluções factíveis.

Ainda é possível problemas sem função objetivo, onde se deseja apenas encontrar uma solução

que atenda as restrições. Por exemplo, montar a tabela de um campeonato de futebol obedecendo a

restrições como o limite de partidas consecutivas em um campo. E problemas com múltiplas funções

objetivo. Por exemplo, em um problema de manufatura que se deseja maximizar o lucro e minimizar

o tempo de produção.

Exemplo: O problema da mochila

Um alpinista deseja escolher entre diversos itens quais levar para sua expedição. Os objetos

devem ser escolhidos de forma que atenda ao máximo suas necessidades na escalada, sendo que eles

não devem exceder a capacidade de sua mochila. Os dados do problema são:

• N é o número de itens disponíveis;

• c

é um valor que representa a utilidade associada ao item n para a escalada;

• b é a capacidade total da mochila;

• a

é o espaço ocupado pelo item n;

Na especiﬁcação do problema, devemos deﬁnir as variáveis de decisão, a função objetivo e as

restrições:

Variáveis de decisão: x

assume valor 1 se o item n será carregado na mochila, e 0 caso contrário;

Função objetivo: O valor total dos itens selecionados f(x) =

∑

n=1

deve ser maximizado.

Restrições: O espaço ocupado pelos itens selecionados não deve exceder a capacidade da mochila e

as variáveis de decisão devem assumir valores binários do conjunto B = {0,1}.

Em programação matemática, o problema ﬁca:

: Maximize

∑

n=1

Sujeito a:

∑

n=1

 b

∈ B n = 1,...,N

3. Fundamentos de otimização inteira 16

n item utilidade tamanho

1 Fogareiro 2 5

2 Corda

7 5

3 Colchonete

2 4

4 Ração

4 3

5 Primeiros Socorros

3 2

6 Grampos

7 2

7 Aparelho de GPS

6 1

Tabela 3.1: Exemplo de instância para o problema da mochila

Dado o modelo, chamamos de instância o conjunto de dados que caracterizam um problema. Para

o exemplo da mochila uma instância é dada na Tabela 3.1. Considerando a capacidade da mochila

b = 6, obtemos a seguinte formulação em programação matemática:

Maximize 2x

+ 7x

+ 2x

+ 4x

+ 3x

+ 7x

+ 6x

(3.1)

Sujeito a: 5x

+ 5x

+ 4x

+ 3x

+ 2x

+ x

 6

x ∈ B

Dependendo da natureza da função objetivo e das restrições, os problemas de otimização são

classiﬁcados em subdomínios.

Programação Linear: é uma classe de problemas de otimização onde tanto a função objetivo quanto

as restrições são lineares. Matematicamente, esta classe de problemas é representada por:

: Maximize c

Sujeito a: Ax  b

x ∈ R

onde b e c são vetores

e A é uma matriz. Problemas desta natureza são bastante empregados e

bem resolvidos algoritmicamente, por meio do algoritmo Simplex e métodos de ponto interior

[20].

Programação Linear Inteira: possui formulação semelhante à Programação Linear pois a função

objetivo e as restrições devem ser lineares. Entretanto, neste sub-domínio da otimização as

variáveis de decisão pertencem a um domínio discreto.

: Maximize c

x (3.2)

Sujeito a: Ax  b

x ∈ Z

Global Positioning System, Sistema de Posicionamento Global.

Nesta dissertação utilizamos a notação de matrizes coluna para os vetores.

3. Fundamentos de otimização inteira 17

Quando as variáveis de decisão pertencem ao conjunto binário B

, pode-se dizer que o pro-

blema é de Programação Binária. É empregada quando se deseja modelar problemas em que se

deve escolher entre uma ou outra alternativa, como no problema da mochila apresentado, tendo

que decidir em carregar ou não o objeto; ou em problemas em que as variáveis de decisão de-

vem ser necessariamente inteiras, não tendo sentido assumirem valores fracionários como, por

exemplo, em uma montadora de veículos que se deseja determinar a quantidade ótima a ser

produzida.

Programação Linear é NP-Difícil, pois qualquer problema da classe NP-Completa pode ser

reduzido a P

em tempo e espaço polinomial, por exemplo, o problema de satisfatibilidade.

Programação Linear Inteira Mista: esta sub-classe dos problemas é uma união das duas apresen-

tadas anteriormente. Nela existem variáveis de decisão contínuas e inteiras.

: Maximize c

x+ h

Sujeito a: Ax+ Gy  b

x ∈ R

y ∈ Z

Emprega-se a programação linear inteira mista, ou apenas programação inteira mista, normal-

mente quando são utilizadas variáveis de decisão sobre variáveis contínuas. Problemas desta

subclasse são tão complexos quanto os apresentados anteriormente.

Programação Não-linear com Restrições: é o caso mais geral de problemas de otimização.

: Maximize f(x)

Sujeito a: g(x)  0

x ∈ R

onde f(x) e g(x) são não lineares e não precisam ser necessariamente contínuas. Não existe

uma forma geral para resolver problemas desta natureza, devendo-se analisar cada caso em

busca de um algoritmo eﬁciente, quando existir.

Existem ainda dois casos particulares: na programação quadrática a função objetivo é uma

função quadrática das variáveis de decisão f(x) =

Qx+ c

x, sendo Q uma matriz simétrica,

e as restrições são lineares Ax  b. Se a matriz Q for positiva deﬁnida ou positiva semi-deﬁnida

encontrar a solução global é relativamente fácil. Mas se Q for indeﬁnida, negativa deﬁnida ou

negativa semi-deﬁnida o problema já se torna difícil.

Na programação não-linear irrestrita, todas as variáveis de decisão podem assumir qualquer va-

lor. Caso f(x) seja contínua, pode-se empregar o método de descenso ou o método de Newton.

A diﬁculdade desta subclasse é garantir que o problema convirja para um ponto ótimo global,

não apenas sendo ótimo para uma região próxima (ótimo local).

3. Fundamentos de otimização inteira 18

3.2 Programação inteira

Nesta seção apresentamos os conceitos básicos para resolução de problemas modelados com Pro-

gramação Inteira baseados no livro de Wolsey [21]. Tendo em vista que o modelo a ser desenvolvido

para P(G) é tipo inteiro misto, faz-se necessário um maior aprofundamento desta teoria. A teoria apli-

cada à programação inteira pura também pode ser utilizada na programação inteira mista, tomando

alguns cuidados. Podem-se ignorar as variáveis de decisão reais ao aplicar métodos que levam em

conta que os números são inteiros, e tratar o problema completo quando são consideradas as relaxa-

ções.

3.2.1 Formulações

Consideramos agora o problema geral de programação inteira dado por P

. Suponha que X ⊆ Z

o conjunto das soluções factíveis. Tipicamente, existem muitas (possivelmente inﬁnitas) formulações

para X dadas por meio de poliedros. Esta equivalência entre elementos de X e os elementos da sua for-

mulação como um poliedro P são fundamentais, tanto ao processo de formulação quanto aos procedi-

mentos algorítmicos de solução. Abaixo, formalizamos estas noções e apresentamos conceitos-chave

para o desenvolvimento desta dissertação.

Deﬁnição 3.1 Um subconjunto do R

descrito por um conjunto de restrições lineares P = {x ∈ R

Ax  b} é um poliedro.

Deﬁnição 3.2 O poliedro P ⊆ R

é uma formulação para o conjunto X ⊆ Z

se, e somente se,

X = P∩ Z

Seja X o conjunto das soluções factíveis de um problema inteiro dado pelos pontos do conjunto

X = {(2,2), (3,1), (3,2), (3,3), (4,1), (4,2), (4,3), (5,1), (5,2), (5,3)}. Então é fácil veriﬁcar que os

poliedros:

= {x ∈ R

: −2x

+ x

 −

, x



+ x



, 2x

− x



−

− x

 −

= {x ∈ R

: −

+ x



+ x

 21,

− x



, −

− x

 −7 },

= {x ∈ R

: −x

+ x

 0, x

 3,

 5, −x

 −1,

−x

− x

 −4 },

3. Fundamentos de otimização inteira 19

4 5

Figura 3.1: Formulações para X

assim como P

∩ P

, são formulações para X, como pode ser visto na Figura 3.1.

No exemplo apresentamos três formulações para o mesmo conjunto de pontos X. Observamos

que pode existir um número inﬁnito de formulações para X. Então, como escolher entre duas formu-

lações? Pode-se dizer que uma formulação é melhor que outra? Chegamos então a seguinte deﬁnição:

Deﬁnição 3.3 Dado um conjunto de pontos X ⊂ R

, e duas formulações P

e P

para X, dizemos que

é melhor que P

se P

⊂ P

Podemos dizer ainda que uma formulação melhor é mais forte ou apertada que outra. Evidente-

mente, nem todas as formulações podem ser comparadas. Como vemos as formulações P

e P

são

não comparáveis, pois P

 P

nem P

 P

A formulação P

é dita ideal porque não existe uma formulação P

para o conjunto X tal que P

⊂

. Também porque se resolvermos a relaxação linear de P

a solução do problema está localizada

sobre um dos vértices de P

. A seguir, formalizamos estes conceitos.

Deﬁnição 3.4 Dado um conjunto de pontos X, x é combinação convexa de X se existe um conjunto

ﬁnito de pontos x

∈ X e λ

∈ R

, j = 1,.. . ,n, com

∑

j=1

= 1 tal que x =

∑

j=1

Deﬁnição 3.5 Dado um conjunto de pontos X, conv(X) = {x : x é combinação convexa de X} é o

fecho convexo do conjunto X.

Proposição 3.1 conv(X) é um poliedro [22, página 106, Teorema 6.2].

Proposição 3.2 Os vértices de conv(X) são pontos de X [21, página 15, Proposição 1.2].

Como conseqüência temos que conv(X) pode ser descrito por um conjunto ﬁnito de desigualda-

des lineares, e P

: {maxc

x : x ∈ X} pode ser reescrito como {maxc

x : x ∈ conv(X)}. Entretanto,

encontrar todas as desigualdades que descrevem conv(X) nem sempre é fácil, pois pode existir um nú-

mero muito grande (exponencial) de desigualdades. No exemplo apresentado na Figura 3.1 podemos

veriﬁcar que para o conjunto de pontos X, a formulação P

= conv(X).

3. Fundamentos de otimização inteira 20

3.2.2 Introdução a algoritmos

Formulado o problema, o passo seguinte é encontrar uma maneira eﬁciente de encontrar a solução

ótima. Como já foi citado, problemas de programação linear não inteira possuem algoritmos eﬁcientes

para obtenção da solução ótima, como os métodos Simplex [20] e ponto interior [23]. Porém no caso

da programação inteira, por pertencerem à classe NP-difícil, não existem algoritmos gerais capazes

de encontrar a solução ótima global de maneira eﬁciente (a não ser que NP=P).

Algoritmos exatos são métodos capazes de encontrar a solução ótima global para um problema

de otimização. Nem sempre o seu uso é possível, geralmente devido ao elevado tempo e/ou grande

quantidade de recursos computacionais demandados pelo algoritmo. Em casos onde uma solução

relativamente boa é admissível, podem-se empregar heurísticas e meta-heurísticas. Estes métodos

não garantem uma solução ótima para o problema, mas são capazes de encontrar uma solução de

qualidade em um tempo adequado para aplicação.

3.2.2.1 Otimalidade e relaxação

Dado um problema em programação linear inteira z = max{c

x : x ∈ X}, como provar que um

ponto x

∗

é ótimo? Uma maneira é encontrar um limite inferior à solução z

 z e um limite superior

z  z de tal forma que z = z = z. Esta abordagem propõe um algoritmo para a solução desta classe de

problemas. Deve-se buscar uma seqüência decrescente de limites superiores:

> z

> ... > z

 z

e uma sequência crescente de limites inferiores:

< z

< ... < z

 z

até que seja atingido:

− z

 ε

onde ε é um valor positivo muito pequeno. Então temos que encontrar maneiras de obter estes limites.

Limite Primal: Toda solução factível x

∗

∈ X induz um limite inferior z

= c

x  z. Geralmente

encontrar uma solução factível para um problema não é muito difícil. O desaﬁo é encontrar

uma boa solução, isto é, que seja próxima da solução ótima.

Limite Dual: O limite dual procura um limite superior para os problemas de maximização. A abor-

dagem mais importante é a relaxação, que busca tornar o problema mais fácil de ser resolvido

em que a solução ótima seja no mínimo tão grande quanto z. Na relaxação deve-se balancear

a diﬁculdade de obtê-la com os benefícios que ela trará. Uma relaxação muito apertada pode

requerer um esforço computacional grande, enquanto uma relaxação mais facilmente computá-

vel pode resultar em valores muito distantes. Uma relaxação bastante empregada é a relaxação

linear.

3. Fundamentos de otimização inteira 21

Deﬁnição 3.6 Para o problema em programação linear inteira P

= max{c

x : x ∈ P∩ Z

}

com formulação P = {x ∈ R

: Ax  b}, sua relaxação linear é P

= max{c

x : x ∈ P}.

Ou seja, a relaxação linear de um problema em programação linear inteira consiste em transfor-

mar suas variáveis de decisão inteiras em reais, transformando o problema para programação

linear apenas, que pode ser facilmente resolvido.

Nos problemas de minimização o limite primal representa um limite superior na função objetivo,

e o limite dual um limite inferior. A seguir, vamos apresentar alguns algoritmos exatos para resolução

de problemas de otimização.

3.2.2.2 Branch and Bound

O algoritmo de Branch and Bound baseia-se em dividir o problema em problemas menores e mais

fáceis de serem resolvidos, e depois unir as soluções para formar a solução do problema original.

Uma maneira de se representar esta divisão seria ﬁxar os valores de todas as variáveis inteiras,

enumerando todas as possíveis soluções para o problema. Em seguida obter o valor da função objetivo

para cada uma das soluções e escolher a ótima. Esta abordagem é chamada de enumeração explícita

e não é uma boa maneira de se resolver o problema, pois o número de soluções possíveis cresce

exponencialmente com o número de variáveis de decisão, a tornando impraticável já para problemas

de tamanho médio.

No algoritmo de Branch and Bound, para cada decomposição do problema é avaliado se a árvore

de soluções factíveis pode ser reduzida. Esta abordagem é chamada de enumeração implícita, pois

descarta maus ramos da árvore de soluções. A seguir é apresentado o algoritmo em pseudocódigo

para um problema de maximização:

Branch-And-Bound(

)

1 L ← {P} ⊲ lista de nós ativos

2 T ← ({P},

0) ⊲ árvore inicial de Branch and Bound

3 z

← −∞ ⊲ limite inferior

4 x

∗

← NIL ⊲ a solução do problema

5 enquanto L =

6 faça escolha um P

de L

7 resolver relaxação RL

← {maxc

x : x ∈ P

}

8 z

← valorObjetivo[RL

]

9 x

← solução[RL

]

10 se

= −∞ ⊲ P

11 então descarte P

por infactibilidade

12 senão se

 z

13 então descarte P

por limite

3. Fundamentos de otimização inteira 22

14 senão

15 se x

∈ Z

> z

16 então z ← z

⊲ novo limite inferior

17 x

∗

← x

⊲ nova solução

18 senão ⊲ x

/∈ Z

19 escolha uma variável fracionária x

da solução

20 P

← P

∩ {x

 ⌊x

⌋}

21 P

← P

∩ {x

 ⌈x

⌉}

22 adicione P

e P

a T como folhas de P

23 insira P

e P

em L

24 descarte P

Nas primeiras quatro linhas do algoritmo é criada uma lista de nós ativos, uma árvore de soluções,

um vetor para armazenar o valor das variáveis de decisão da melhor solução encontrada e uma variável

para armazenar o valor da função objetivo correspondente. Na prática, não é necessário armazenar a

árvore de soluções, apenas a lista dos nós ativos, mas para compreensão do algoritmo esta informação

é mantida. Em seguida, o algoritmo entra em um laço que é executado para cada um dos elementos

da lista de nós ativos. Na primeira iteração existe apenas o nó que representa o problema completo.

A escolha do nó ativo para ser processado pode ser feita de várias maneiras. Heurísticas buscam

o nó que seja o melhor candidato a levar à solução do problema o mais rápido possível. Deseja-se o

nó que leve a um alto limite inferior, que reduza ao máximo a árvore de soluções e por conseqüência

o tempo de processamento. Outra abordagem pode ser uma busca em profundidade. Esta heurística é

menos elaborada que as adotadas como padrão em implementações comerciais, implicando em uma

execução mais lenta (maior número de iterações), mas ela mantém o número de nós ativos pequeno,

sendo indicada quando há pouca memória para executar o algoritmo. Uma abordagem comercial

consiste em inicialmente utilizar uma busca em profundidade, que leva rapidamente a uma solução

inteira (não necessariamente boa), e em seguida partir para uma heurística mais elaborada. A presença

de uma solução inteira permite que nós sejam descartados rapidamente por limite.

Escolhido um nó é resolvida sua relaxação, que como vimos geralmente é utilizada a relaxação

linear. O nó pode ser descartado por infactibilidade se seu conjunto de soluções é vazio, ou por

limite se seu limite superior apresentar valor na relaxação menor que o melhor limite inferior já

obtido. Então são veriﬁcados os valores obtidos nas variáveis de decisão. Se elas obtiveram valores

inteiros, o limite superior do nó também é seu limite inferior, e uma nova melhor solução pode ter

sido encontrada. Caso contrário é escolhida uma das variáveis de decisão e o problema é dividido

em dois sub-problemas (ou até em mais, em implementações mais avançadas), que são adicionados à

lista de nós ativos e à árvore de soluções.

Da mesma forma, não existe uma melhor forma de escolher a variável de decisão que será usada

para dividir o problema. Geralmente é empregada a mais fracionária das variáveis, ou seja, a variável

que possui valor mais distante do seu inteiro mais próximo. Por exemplo, considere duas variáveis

de decisão y

= 1,4 e y

= 2,8, então é escolhida a variável y

, pois 1,4 está mais distante de 1 (seu

inteiro mais próximo) que 2,8 está de 3.

3. Fundamentos de otimização inteira 23

17, 4

 1

 0

z = −∞

∗

= NIL

(a)

17, 4

 1

 0

z = 13

∗

= (0, 1, 0, 0, 0, 0, 1)

(b)

17, 4

17, 33...

 1

 0

 1x

 0

= 13

∗

= (0, 1, 0, 0, 0, 0, 1)

(c)

17, 4

17, 33...

 1

 0

 1x

 0

= 17

∗

= (0, 0, 0, 1, 0, 1, 1)

(d)

17, 4

17, 33...

1716, 5

 1

 0

 1x

 0

= 17

∗

= (0, 0, 0, 1, 0, 1, 1)

(e)

Figura 3.2: Exemplo ilustrativo do algoritmo de Branch and Bound

Dado o exemplo do problema da mochila apresentado na Equação 3.1, a Figura 3.2 apresenta a

aplicação do algoritmo. Na ﬁgura, os nós escuros já foram processados e os nós claros compõem a

lista dos nós ativos.

1. Em (a) foi resolvida a relaxação linear do problema original, chegando a solução x = (0,

, 0,

0, 1, 1, 1) com limite superior igual a 17,4. Como x

apresentou valor fracionário, o problema

foi dividido em dois conjuntos de soluções sobre x

2. Em (b) foi escolhido o nó do conjunto de soluções P

, resolvida sua relaxação obtendo asolução

inteira x

= (0, 1, 0, 0, 0, 0, 1) com limite superior 13. Note que o limite inferior passa a ser 13,

e o nó é fechado por otimalidade.

3. A parte (c) da ﬁgura mostra a resolução do nó P

, que obteve solução x

= (0, 0, 0,

, 1, 1, 1) e

valor da relaxação

= 17

. A variável x

apresentou valor fracionário neste subproblema.

Então este foi dividido em torno de x

, gerando novos subconjuntos de solução P

e P

4. (d) mostra a resolução da relaxação de P

, com x

= (0, 0, 0, 1, 0, 1, 1) e

= 17. Observe

que novamente a solução foi inteira. Como sua solução é maior que a até então obtida, esta

passa ser a solução do problema.

5. Em (e) resolvemos RL

, com solução x

= (0, 0,

, 0, 1, 1, 1) e

= 16,5. Como o limite

superior é menor que z

, isto é, a solução deste ramo da árvore não pode ser melhor que a já

obtida, o nó é cortado por limite.

3. Fundamentos de otimização inteira 24

6. Como não existem mais nós ativos, a solução z

∗

= 17 e x

∗

= (0, 0, 0, 1, 0, 1, 1) é o ótimo global

do problema.

3.2.2.3 Planos de corte

Considere a restrição do problema da mochila em (3.1),

+ 5x

+ 4x

+ 3x

+ 2x

+ x

 6 (3.3)

x ∈ B

. Podemos observar que x

, x

e x

não podem assumir valor 1 simultaneamente, pois se

= x

= 1, temos que 3x

+ 2x

= 7 > 6, que excede a capacidade da mochila. Mas se

eles forem agrupados dois a dois, a restrição continua válida. Isto sugere a restrição x

+ x

 2.

Na mesma linha de raciocínio, observamos ainda que se x

= 1, x

, x

e x

devem ser 0. Assim,

podemos complementar a restrição obtendo

+ x

 2. (3.4)

Esta desigualdade é válida para a instância apresentada, pois ela é verdadeira para todos os pontos

que compõem o conjunto de soluções X da instância.

Deﬁnição 3.7 Uma desigualdade π

x  π

é uma desigualdade válida para um conjunto X ⊆ R

x  π

para todo x ∈ X.

Em um problema em programação inteira de espaço de soluções X, a inserção de desigualda-

des válidas pode gerar uma redução no poliedro da formulação, ou seja, P∩ {x : π

x  π

} ⊂ P. O

algoritmo de planos de corte consiste em inserir cortes válidos ao poliedro até que a resolução da re-

laxação linear do problema seja inteira, que implica na obtenção do ótimo global. Este procedimento

não requer a obtenção das expressões que produzem o fecho convexo de todo o poliedro, apenas a sua

redução de maneira apropriada. A seguir, apresentamos o algoritmo de planos de corte.

Planos-De-Corte(

)

1 t ← 0 ⊲ contador

2 P

← P ⊲ poliedro inicial

3 faça sempre

4 resolver relaxação RL

← {maxc

x : x ∈ P

}

5 x

← solução[RL

]

6 se x

∈ Z

7 então retorne x

⊲ x

é solução ótima

8 busque um corte (π

,π

) para x

9 se (π

,π

) corta x

10 então P

t+1

← P

∩ {x : (π

)

x  π

}

11 t ← t + 1

3. Fundamentos de otimização inteira 25

+ 2x

 3

+ x

 1

Figura 3.3: Ilustração do corte no problema da mochila com x

= x

= 0 e x

= x

= 1

12 senão retorne NIL ⊲ não encontrou solução

Podemos observar que este algoritmo busca cortes para o poliedro até que seja encontrada uma

solução inteira, que é o ótimo global. A obtenção dos cortes (linha 8) é a base do algoritmo. Como

é uma tarefa difícil, nem sempre são encontrados cortes até resolver o problema, assim o algoritmo

pode retornar uma falha (linha 12).

Existem procedimentos gerais para a obtenção de desigualdades válidas para problemas inteiros,

como o de Chavátal-Gomory [21, 22]. Para a programação inteira pura os cortes de Chavátal-Gomory

fazem que o algoritmo de planos de cortes convirja em um número ﬁnito de iterações. Para problemas

binários com formulação P = {x ∈ R

: Ax  b,x  1} e S = P∩ Z

, o procedimento de cortes

disjuntivos pode ser utilizado para obter conv(S) após n iterações.

A obtenção dos cortes geralmente faz uso da estrutura da formulação. No exemplo acima apli-

camos parcialmente um procedimento chamado de coberturas que busca cortes para o problema da

mochila, e será visto mais detalhadamente na próxima seção. Com a adição desta nova restrição con-

venientemente escolhida ao problema, sua relaxação linear passa a apresentar x

= (0,0,0,1,0,1,1)

em suas variáveis de decisão, contra x

= (0,

,0,0,1,1,1) que é o valor obtido na formulação origi-

nal. Uma vez que x∈ Z

na nova formulação, esta solução é ótima global. Note que ao introduzirmos

a restrição (3.4) a P = {x ∈ B

: sujeito a (3.3) }, não obtemos o fecho convexo conv(S), S = P∩ Z

mas uma conﬁguração exata em torno da solução ótima.

A Figura 3.3 ilustra a inserção do corte no subespaço x

× x

, ﬁxando x

= x

= 0 e x

= 1. Neste subespaço (3.3) ﬁca 5x

+ 2x

 3 e o corte (3.4) ﬁca 2x

+ x

 1. Podemos observar

que a inserção do corte reduz o poliedro, mas que não gera o poliedro mínimo (x

 0 e x

 1 para

este sub-espaço). Mesmo assim, este corte leva à solução problema.

3. Fundamentos de otimização inteira 26

3.2.2.4 Branch and Cut

A inserção pura de cortes não é a melhor maneira de se resolver um problema de otimização. A

obtenção eﬁciente de cortes é uma tarefa difícil. Uma maneira alternativa de resolver os problemas

de otimização é combinar algoritmos conhecidos. O algoritmo de Branch and Cut é a combinação

dos dois algoritmos vistos anteriormente. Para cada nó da árvore de soluções do Branch and Bound

são inseridos cortes. Em cada nó busca-se o máximo de cortes que podem ser inseridos em um tempo

razoável, reduzindo assim o limite superior do nó e promovendo uma redução no tamanho da árvore

Branch and Bound.

É necessário, entretanto limitar o tempo de busca por cortes em cada nó. Um excesso de empenho

do algoritmo na busca de cortes pode representar uma redução pequena na relaxação, de maneira que

este tempo não seja compensado na redução do número de nós.

3.3 Métodos de planos de corte

Nesta seção formalizaremos os conceitos de aplicação de cortes a uma formulação e como gerar

cortes para o problema da mochila.

3.3.1 Desigualdades válidas

Vimosna Deﬁnição3.7 o que é uma desigualdade válida. Um poliedro possui inﬁnitas desigualda-

des válidas, surgindo a questão de quais desigualdades são relevantes e quais podem ser descartadas.

Deﬁnição 3.8 Dadas duas desigualdades válidas π

x  π

e µ

x  µ

para um poliedro P ⊆ R

também notadas por (π,π

) e (µ,µ

), dizemos que π

x  π

domina µ

x  µ

se existe u > 0 tal que

π  uµ e π

 uµ

, e (π,π

) = (µ,µ

Note que se (π,π

) domina (µ,µ

), denotado por (π,π

) ≺ (µ,µ

), então (µ,µ

) é redundante e

pode ser descartada da formulação.

Deﬁnição 3.9 Considerando um poliedro P ⊆ R

, uma desigualdade válida π

x  π

é redundante

para P se existirem desigualdades (µ

)

x µ

, i = 1,... ,k, de P e pesos u

> 0 tal que (

∑

i=1

)

x

∑

i=1

domine a desigualdade π

x  π

Desejamos trabalhar com as desigualdades necessárias e suﬁcientes para deﬁnição do poliedro,

chamadas de desigualdades válidas fortes, ou apenas desigualdades fortes. São fortes no sentido que

levam a uma formulação mais apertada. Para o entendimento mais preciso de desigualdades fortes,

alguns conceitos serão apresentados.

Deﬁnição 3.10 Os pontos x

,. ..,x

∈ R

são ditos aﬁm independentes se a única solução u

, i =

1,...,k, para

∑

i=1

= 0 e

∑

i=1

= 0 for nula.

3. Fundamentos de otimização inteira 27

Dizer que pontos x

,. ..,x

∈ R

são aﬁm independentes é equivalente a dizer que os pontos

−x

),...,(x

−x

) são linearmente independentes. É fácil observar que o maior número de pontos

aﬁm independentes em R

é n+ 1, por exemplo, n pontos linearmente independentes e o vetor zero.

Deﬁnição 3.11 Se para um poliedro P o número máximo de pontos aﬁm independentes é k, então a

dimensão do poliedro P, denotada por dim(P), é k− 1.

Deﬁnição 3.12 Um poliedro P ⊆ R

é de dimensão cheia se, e somente se, dim(P) = n.

Dizer que um poliedro P ⊆ R

tem dimensão cheia signiﬁca dizer que não existem variáveis de

decisão que podem ser expressas como função de outras variáveis. Não existem igualdades que são

satisfeitas por todo x ∈ P.

Deﬁnição 3.13 Uma face de um poliedro P induzida por uma desigualdade válida π

x  π

é F =

{x ∈ P : π

x = π

}. A desigualdade π

x  π

deﬁne ou representa a face.

Deﬁnição 3.14 Uma face F é uma faceta de P se dim(F) = dim(P) − 1.

Considerando o poliedro do problema da mochila em (3.1)

P = {x ∈ R

: 5x

+ 5x

+ 4x

+ 3x

+ 2x

+ x

 6,

 1, j = 1,... ,7}.

(3.5)

Seja e

∈ R

o vetor com todas as entradas nulas a exceção da j-ésima entrada, cujo valor é unitá-

rio. Note que e

∈ P para j = 1,... ,7. Logo {e

}

j=1

∪ {0} constitui um conjunto de pontos aﬁm

independentes de P e, portanto, dim(P) = 7.

Considere agora a face representada pela desigualdade da mochila F = {x ∈ P : 5x

+ 5x

+ 3x

+ 2x

+ x

= 6}. Tomando os pontos x

= (1,0,0,0,0,0,1), x

= (0,1,0,0,0,0,1),

= (0,0,1,0,1,0,0), x

= (0,0,1,0,0,1,0), x

= (0,0,0,1,1,0,1), x

= (

,0,0,0,0,0) e x

(0,0,

,1,0,0,0), podemos veriﬁcar que x

∈ F, j = 1,... ,7, são linearmente independentes e que

estes pontos formam um conjunto de pontos aﬁm independentes (independência linear implica em

independência aﬁm, mas o contrário não é verdade). Concluímos que dim(F) = 7− 1 = 6 e como

dim(F) = dim(P) − 1 veriﬁcamos que F é uma faceta de P, ou seja, face de dimensão máxima.

3.3.2 Coberturas para mochila

Na Seção 3.2.2.3 vimos informalmente a aplicação de coberturas para a geração de cortes no

problema da mochila. Nesta seção e nas próximas estes conceitos serão generalizados. Iniciamos

apresentando algumas deﬁnições.

Considere os conjuntos X = {x ∈ B

∑

j=1

 b} e N = {1,.. . , n}.

Deﬁnição 3.15 Um conjunto C ⊆ N é uma cobertura se

∑

j∈C

> b. Uma cobertura é mínima se

para todo j ∈ C, C\{ j} não é uma cobertura.

3. Fundamentos de otimização inteira 28

Uma cobertura assinala um conjunto de elementos que excede a capacidade da mochila. Se o

conjunto obtido pela remoção de qualquer elemento da cobertura pode ser armazenado na mochila,

dizemos que a cobertura é mínima. Para (3.3), C = {4,5,6} é uma cobertura, pois a

+ a

3+ 2+2 = 7 > 6. Esta cobertura também é mínima, pois a

= 5  6, a

= 5  6 e a

4  6.

Proposição 3.3 Dado uma cobertura C ⊆ N, a desigualdade

∑

j∈C

 |C| − 1 (3.6)

é válida para X.

Temos então para a cobertura C = {4,5,6} a desigualdade válida x

+ x

 2. Deﬁnimos

= conv(X

), de X

= {x ∈ B

|C|

∑

j∈C

 b}, como o poliedro obtido a partir da projeção de

conv(X) sobre o espaço das variáveis da cobertura. Podemos facilmente veriﬁcar que dim(P

) = |C|,

ou seja, P

tem dimensão cheia. Deﬁnimos F

= {x ∈ P

∑

j∈C

= |C| − 1} como a face de P

induzida por (3.6), podemos veriﬁcar que F

é uma faceta, ou seja, dim(F

) = dim(P

) − 1. Para

o exemplo dado acima, dim(P

) = 3 e {(1,1,0),(1,0,1),(0,1,1)} ⊆ F

formam um conjunto aﬁm

independente que nos leva a concluir que dim(F

) = 2.

Podemos ainda estender a cobertura para outras variáveis de decisão, para torná-la mais forte.

Deﬁnição 3.16 A cobertura estendida de uma cobertura C é E(C) = C∪ { j : a

 a

,∀i ∈ C}.

Da mesma maneira, a extensão da cobertura implica na desigualdade também válida para um

conjunto X ⊆ N:

∑

j∈E(C)

 |C| − 1

Em nosso exemplo E(C) = {1,2,3,4,5,6}, pois a

 max{a

: j ∈ C} = 3, mas 7 /∈ E(C)

porque a

< a

. A desigualdade para a extensão da cobertura é então

+ x

 2 (3.7)

Considerando simultaneamente as desigualdades (3.3) e (3.7), observamos que se x

= 1, não

existe em (3.7) nenhuma outra variável de decisão que possa assumir valor 1, pois para (3.3) apenas x

poderia ser selecionado sem que a capacidade da mochila seja excedida, e x

não pertence à (3.7). Mas

se considerarmos apenas a desigualdade da cobertura estendida, ainda é possível que outra variável

de decisão seja diferente de zero. Isto sujere que a desigualdade (3.7) ainda possui folga, e que

esta folga está nas variáveis de decisão adicionadas na extensão da cobertura, pois para a cobertura

apenas, a desigualdade é mínima. Em síntese, poderíamos buscar valores α

, α

e α

que tornam a

desigualdade

+ α

+ x

 2

o mais apertada possível.

3. Fundamentos de otimização inteira 29

3.3.3 Lifting

Dado uma cobertura C ⊆ N = {1,...,n}, desejamos encontrar valores para α

, j ∈ N\C, de ma-

neira que a desigualdade

∑

j∈C

∑

j∈N\C

 |C| − 1

seja válida para X = {x ∈ B

∑

j=1

 b}. A extensão E(C) de uma cobertura C, conforme visto

acima, nos dá uma forma de obter valores α

, onde α

= 1 para j ∈ E(C)\C enquanto α

= 0 para

j ∈ N\E(C). Abaixo apresentamos um procedimento alternativo para o cômputo dos fatores α

. Este

procedimento é conhecido por lifting e os parâmetros α

por fatores de lifting.

Seja  j

,. .., j

 uma ordenação de N\C. Faça para t = 1 até r.

Para calcular o maior valor possível de α

no qual α

∑

t−1

i=1

∑

j∈C

 |C| − 1 seja

válida, devemos resolver o problema

= Maximize

t−1

∑

i=1

∑

j∈C

Sujeito a:

t−1

∑

i=1

∑

j∈C

 b− a

x ∈ B

|C|+t−1

assim chegamos a α

= |C| − 1− ζ

Se a cobertura C for mínima, a desigualdade gerada utilizando este procedimento deﬁne uma

faceta de conv(X) [24, Teorema 1]. De fato, a desigualdade (3.6) deﬁne uma faceta, portanto uma

face máxima, para o subconjunto das variáveis de decisão derivadas da cobertura. O procedimento de

lifting busca obter os pesos das variáveis de decisão que não aparecem na cobertura, de maneira que

a restrição obtida no espaço completo das variáveis continue deﬁnindo uma faceta.

Podemos observar, entretanto, que cada iteração deste procedimento requer que seja resolvida

uma instância de um problema da mochila, cuja diﬁculdade de resolução é comparável a do problema.

Assim, são utilizadas heurísticas para a obtenção de cortes que podem não ser ótimos, mas são bons

o suﬁciente para reduzir o poliedro de maneira a auxiliar na resolução do problema original com

algoritmos de planos de corte ou Branch and Cut.

Sabemos queC = {4,5,6} é uma cobertura mínima para a restrição da mochila (3.3). Vamos agora

ilustrar o procedimento para obter os fatores de lifting das variáveis de decisão que não pertencem à

cobertura. Primeiro construímos uma ordenação de N\C =  j

, j

 = 1,2,3,7, r = 4. Para

este procedimento, considere implícita a restrição x ∈ B

|C|+t−1

. Efetuamos então o processo iterativo,

como segue:

3. Fundamentos de otimização inteira 30

t = 1 j

= 1

1) ζ

= max x

+ x

s.a. 3x

+ 2x

 6− a

= 6− 5 = 1

2) ζ

= 0

3) α

= |C| − 1− ζ

= 2

t = 2 j

= 2

4) ζ

= max 2x

+ x

s.a. 5x

+ 3x

+ 2x

 1

5) ζ

= 0

6) α

= |C| − 1− ζ

= 2

t = 3 j

= 3

7) ζ

= max 2x

+ 2x

+ x

s.a. 5x

+ 5x

+ 3x

+ 2x

 2

8) ζ

= 1

9) α

= |C| − 1− ζ

= 1

t = 4 j

= 7

10) ζ

= max 2x

+ 2x

+ x

s.a. 5x

+ 5x

+ 4x

+ 3x

+ 2x

 5

11) ζ

= 2

12) α

= |C| − 1− ζ

= 0

Chegamos então à desigualdade:

+ α

+ x

+ α

 2

+ 2x

+ x

 2

válida para X. Esta restrição nos deﬁne a face F = {x ∈ conv(P∩ Z

) : 2x

+2x

2}. Considere os pontos x

= (1, 0, 0, 0, 0, 0, 0,), x

= (0, 1, 0, 0, 0, 0, 0), x

= (0, 0, 1, 0, 1, 0, 0),

= (0, 0, 0, 1, 1, 0, 0), x

= (0, 0, 0, 1, 0, 1, 0), x

= (0, 0, 0, 0, 1, 1, 0), x

= (0, 0, 1, 0, 0, 1, 1).

Notamos que x

∈ F, j = 1,.. . ,7, e que estes pontos são aﬁm independentes. Então dim(F) = 6, e

como dim(F) = dim(

P) − 1,

P = conv(P∩ Z

), F é uma faceta do poliedro

3.3.4 Down-lifting

Lifting pode ser entendido como o procedimento onde tomamos a face induzida pela desigualdade

da cobertura,

∑

j∈C

 |C| − 1, do poliedro da formulação do problema da mochila acrescido das

equações x

= 0 para j ∈ N\C. Então rotacionamos a desigualdade de cobertura de forma a se obter

uma face de maior dimensão para o poliedro original da mochila.

Um procedimento análogo pode ser realizado com uma face deﬁnida por equações da forma x

= 1

[22, 25]. Para qualquer cobertura C e qualquer subconjunto D ⊂ C, a desigualdade:

∑

j∈C\D

 |C| − |D| − 1

3. Fundamentos de otimização inteira 31

é válida para o poliedro restrito:

conv({x ∈ B

|C|−|D|

∑

j∈N\D

 b−

∑

j∈D

}).

O lifting da seção anterior pode ser utilizado sobre C\D para produzir uma desigualdade:

∑

j∈C\D

∑

j∈N\C

 |C| − |D| − 1.

diminuindo a capacidade da mochila para b−

∑

j∈D

, pois x

= 1, j ∈ D, e considerando os somató-

rios sobre C\D, assim como α

= |C| − |D| − 1− ζ

. O cômputo destes fatores (N\C) algumas vezes

é chamado de up-lifting, para diferenciar dos fatores das variáveis ﬁxadas em 1 (D).

Finalmente, a desigualdade acima pode ser submetida a um processo de down-lifting dos fatores

de D para se obter uma faceta da forma:

∑

j∈C\D

∑

j∈N\C

∑

j∈D

 |C| − |D| − 1+

∑

j∈D

onde β

= ζ

− (|C| − |D|) − 1, e os fatores ζ

, j

∈  j

,. .., j

 é uma ordenação de D, são obtidos

resolvendo o problema:

= Maximize

∑

j∈C\D

∑

j∈N\C

t−1

∑

i=1

Sujeito a:

∑

i∈N\D

 b−

∑

j∈D

∑

i=1

x ∈ B

|N|−|D|+t−1

Temos a desigualdade da cobertura correspondente a C = {4,5,6}, dada por x

+ x

 2.

Fazendo D = {5}, obtemos a desigualdade x

 1 para conv(P∩{x ∈ B

|N|

: x

= 1}). Executando

lifting para x

, calculamos:

= max{x

+ x

: 3x

+ 2x

 0} = 0

e portanto, α

= |C| − |D| − 1− ζ

= 1, obtendo a desigualdade x

+ x

 1.

Realizando lifting para x

, calculamos primeiramente:

= max{x

+ x

: 4x

+ 3x

+ 2x

 3} = 1

que nos leva a deduzir que α

= 0. Daí resulta a desigualdade x

+ x

 1.

Executando down-lifting na variável x

, desejamos calcular β

tal que:

+ x

 1+ β

(3.8)

3. Fundamentos de otimização inteira 32

permaneça válida quando x

= 0. Note que, qualquer que seja o valor de β

, (3.8) é válida quando

= 1. Para isto,

 max{x

+ x

: 4x

+ 3x

+ 2x

+ x

 6} − 1 = ζ

− 1

Calculando ζ

, descobrimos que ζ

= 2 e portanto β

 2−1= 1 que nos permite obter a desigualdade

+ x

 2.

Continuamos agora com o lifting de x

. Devemos calcular ζ

= max{x

+ x

: 4x

+ 2x

+ x

 1} = 0. Concluímos que α

= 2− 0 = 2. Para a última variável, x

, computamos

= max{2x

:5x

+4x

+3x

+2x

 1} = 0, permitindo calcular que α

= 2

e obter a desigualdade válida

+ 2x

+ x

 2.

Coincidentemente chegamos à mesma desigualdade obtida na seção anterior. Já foi demonstrado que

esta desigualdade induz uma faceta para o poliedro

P = conv(P∩ Z

A ordem em que os fatores de lifting são calculados é importante na construção da faceta. É possí-

vel obter desigualdades diferentes para uma mesma cobertura modiﬁcando apenas a ordem de cálculo.

Outro ponto a considerar na ordenação é que os subproblemas gerados sejam sempre factíveis. Por

isto, em nosso exemplo alternamos o cômputo dos fatores de up-lifting com os de down-lifting.

3.4 O problema da mochila com restrições de precedência

Na seção anterior vimos que para a instância apresentada do nosso problema da mochila, as va-

riáveis de decisão assumiram valor x

= (0,0,0,1,0,1,1) para uma solução ótima. Portanto para esta

instância o alpinista deveria levar a ração, os grampos e o aparelho de GPS (Tabela 3.2). Entretanto,

não faz sentido que o alpinista leve os grampos sem que ele também leve a corda, mas a corda pode

ser útil sem os grampos. Assim em nosso problema hipotético temos uma restrição de precedência

de que os grampos só podem ser levados se a corda também for. Na Figura 3.4 apresentamos uma

representação para esta restrição e a estendemos aos outros elementos da mochila. Para representar as

restrições de precedência utilizamos um grafo acíclico direcionado G = (V,E) em que seus vértices

V = {1,... ,7} são os próprios elementos da mochila e suas arestas E = {(2,6),(3,6),(4,1)} indicam

a precedência.

A seguir, apresentamos algumas deﬁnições que serão necessárias para a obtenção de desigualda-

des válidas para o problema da mochila com restrições de precedência.

Deﬁnição 3.17 Dizemos que i precede j, denotado por i  j, se existe um caminho de i até j em G.

Esta deﬁnição signiﬁca que i deve ser carregado na mochila antes que j seja considerado.

Deﬁnição 3.18 Dizemos que i precede propriamente j, denotado por i ≺ j, se i  j e i = j.

3. Fundamentos de otimização inteira 33

n item utilidade tamanho levar

1 Fogareiro 2 5 não

2 Corda

7 5 não

3 Colchonete

2 4 não

4 Ração

4 3 sim

5 Primeiros Socorros

3 2 não

6 Grampos

7 2 sim

7 Aparelho de GPS

6 1 sim

Tabela 3.2: Solução para uma instância do problema da mochila sem restrição de precedência

23 4

5 67

Corda

Grampos

Ração

Fogareiro

Colchonete

GPS

Primeiros

Socorros

Figura 3.4: Exemplo de restrição de precedência

Deﬁnição 3.19 Dado um conjunto S ⊆ V, l(S) = {i : i  j para algum j ∈ S} é o conjunto suporte de

S. Para apenas um elemento, l(i) = l({i}).

O conjunto suporte contém todos os predecessores de S. Note que S ⊆ l(S).

Deﬁnição 3.20 Dado um conjunto S ⊆ V, H(S) = {i ∈ S : ∄ j ∈ S|i ≺ j} é o conjunto das folhas de S,

e R(S) = {i ∈ S : ∄ j ∈ S| j ≺ i} é o conjunto das raízes de S.

Considere o grafo da Figura 3.4 e S = {1,2,6}. Então l(S) = {1,2,3,4,6}, H(l(S)) = {1,6} e

R(l(S)) = {2,3,4}.

3.4.1 Deﬁnição do problema

Formalmente, o problema da mochila com restrições de precedência pode ser deﬁnido como:

dado um grafo de precedência acíclico direcionado G = (V,E) de vértices V = {1,... ,n} e arestas

E ⊆ V ×V, um peso c

e um volume a

, i ∈ V, para cada vértice e uma capacidade b da mochila,

: Maximize

∑

j∈V

Sujeito a: x

 0 j ∈ H(V)

 1 j ∈ R(V)

 x

∀(i, j) ∈ E

∑

j∈V

 b

∈ B j ∈ V

3. Fundamentos de otimização inteira 34

Deﬁnição 3.21 σ

∑

i∈l( j)

é a capacidade mínima da mochila necessária para selecionar o ele-

mento j e seus predecessores.

Proposição 3.4 Se max{σ

: j ∈ H(V)}  b, então dim(

P) = n, onde

P = conv(P∩ Z

) [26].

3.4.2 K-coberturas

Aqui vamos generalizar o conceito de cobertura ao problema da mochila com restrições de pre-

cedência e estendê-lo com a noção de K-cobertura.

Deﬁnição 3.22 b(S) =

∑

i∈S

, S ⊆ V é o volume ocupado pelos elementos de S.

Deﬁnição 3.23 C ⊆ V é uma cobertura se:

i. b(C) > b,

ii. l(C) = C.

Deﬁnição 3.24 C ⊆ V é uma K-cobertura se:

i. C é uma cobertura,

ii. Para todo conjunto S ⊆ H(C) com |S| = K, b(l(S)) > b,

iii. Para todo i ∈ S, b(l(S)\{i})  b.

A partir de agora, tomemos uma nova capacidade b = 11 para a mochila em nossos exemplos.

Considere o conjunto C = {1,3,4} para o exemplo do problema da mochila. C é uma cober-

tura, pois l(C) = {1,3,4} e b(C) = 5+ 4 + 3 = 12 > 11, que atende à Deﬁnição 3.23. Note que

H(C) = {1,3}. Se tomarmos o conjunto S = {1,3}, S ⊆ H(C), temos b(l(S)) = b({1,3,4}) = 12 > b.

S também atende à condição 3 da Deﬁnição 3.24, pois para cada i ∈ S, se i = 1, b(l(S)\{1}) =

b({3,4}) = 7  11; e se i = 3, b({1,4}) = 8  11. Portanto, C é uma 2-cobertura.

Proposição 3.5 Dado uma K-cobertura C ⊆ V, a desigualdade

∑

i∈H(C)

 K − 1 (3.9)

é uma faceta para P

se, e somente se,

{S⊆H(C):|S|=K−1}

l(S) =

Note na 2-cobertura C = {1,3,4} que

{S⊆{1,3}:|S|=1}

l(S) = l({1}) ∩ l({3}) = {1,4} ∩ {3} =

portanto a desigualdade induzida pela cobertura x

+ x

 2 é uma faceta para P

3. Fundamentos de otimização inteira 35

3.4.3 Lifting

Considerando a desigualdade de K-cobertura em (4.6), podemos obter através de um processo de

lifting uma desigualdade mais forte que englobe as variáveis não contempladas na K-cobertura, ou

seja,

∑

i∈H(C)

∑

i∈V\C

 K − 1

sendo α

, i ∈ V\C, os fatores de lifting. Da mesma forma que no problema clássico da mochila, os

fatores de lifting dependem da cobertura e a ordem na qual o procedimento é aplicado. Em virtude

das restrições de precedência, temos ainda que impor uma ordenação topológica na ordem de lifting,

para garantir que o procedimento seja bem deﬁnido. Seja C

′

= i

,. ..,i

 uma ordenação topológica

dos elementos de V\C, ou seja, i

⊀ i

para todo 1  h < k  T. Então o fator de lifting α

pode ser

calculado resolvendo o problema

= Maximize

∑

j∈H(C)

t−1

∑

j=1

Sujeito a: x ∈ X

onde X

= {x ∈ X : x

= 0 para todo i ∈ U, enquanto x

= 1 para todo i ∈ W}, U

= {i

t+1

,. ..,i

= {i

} e α

= K − 1− ζ

, j = 1,.. . ,t − 1, são obtidos recursivamente, e α

= K − 1− ζ

Para aplicarmos programação inteira no cômputo dos fatores de lifting, precisamos encontrar

uma formulação do conjunto X

. O problema dado a seguir corresponde a uma formulação em

programação matemática que pode ser utilizada para obter ζ

= Maximize

∑

j∈H(C)

t−1

∑

j=1

Sujeito a:

∑

j∈V

 b

 x

(i, j) ∈ E

= 1

∈ B i ∈ V

onde G

= (V

) é o grafo induzido de G por V

= C∪ {i

,. ..,i

}, ou seja, G

= G[V

Considere a cobertura C = {1,3,4}, e uma ordenação topológica C

′

= 2,6,5,7 dos elementos

que não pertencem à cobertura. Para obter os fatores de lifting inicialmente temos V

= {1,2,3,4}

e resolvemos ζ

= {maxx

+ x

: 5x

+ 5x

+ 4x

 11,x

 x

= 1} = 1, com solução

,. ..,x

) = (0,1,1,0,0,0,0). Assim obtemos α

= K − 1− ζ

= 0. Para o elemento seguinte de

′

, ζ

= {maxx

+ x

: 5x

+ 5x

+ 4x

+ 2x

 11,x

 x

= 1} = 1, com

,. ..,x

) = (0,1,1,0,0,1,0). Portanto α

= 0.

O cômputo de α

é feito por ζ

= {maxx

+ x

: 5x

+ 5x

+ 4x

+ 2x

 11,x



 x

= 1} = 1, obtendo (x

,. ..,x

) = (0,0,1,1,1,0,0) que implica em α

= 0.

3. Fundamentos de otimização inteira 36

E por ﬁm ζ

= {maxx

+ x

: 5x

+ 5x

+ 4x

+ 2x

+ x

 11,x

 x



= 1} = 1, com (x

,. ..,x

) = (0,0,1,1,0,0,1) que resulta em α

= 0. Todos os fatores de lifting

assumiram valor zero, então a desigualdade

+ x

 2

também é uma faceta para conv(P∩ Z

3.5 Linearização por partes

Consideremos o problema de otimização separável:

sep

: Maximize F =

∑

j=1

)

onde x ∈ X ⊆ R

são as possíveis soluções para o problema e f

é uma função não-linear qualquer. F

é dita separável porque seus elementos f

são funções apenas de uma variável x

Tomaremos agora a função f

) e para simpliﬁcar a notação eliminaremos o índice j. A lineari-

zação por partes consiste em selecionar k+1 pontos P = {p

: p

= (a

, f(a

)),a

= l,a

= u,a

i−1

< a

}

que pertençam a uma região [l,u] do domínio de x e interpolá-los por retas, formando a função linear

por partes

f(x). A Figura 3.5 ilustra a função não-linear f(x) e sua linearização por partes

f(x). Cada

par de pontos r

= (p

i−1

, p

), i = 1,... ,k, forma uma região da função linear

f(x). Apresentaremos a

seguir três modelos de aproximação de f(x) em funções lineares por partes utilizando programação

linear inteira mista.

3.5.1 Modelo com pesos por ponto (Modelo I)

Nesta primeira abordagem utilizamos variáveis de decisão reais λ

associadas ao peso de cada

ponto p

, e variáveis de decisão inteiras y

que selecionam a região de

f(x). Temos então a seguinte

formulação:

x =

∑

i=0

(3.10a)

f(x) =

∑

i=0

f(a

)λ

(3.10b)

3. Fundamentos de otimização inteira 37

= 0 a

= 1 a

= 2 a

= 3 a

= 4

f(x)

Figura 3.5: Linearização por partes para o modelo por pesos

com restrições:

 y

(3.11a)

 y

+ y

i+1

i = 1,. ..,k− 1 (3.11b)

 y

(3.11c)

∑

i=0

= 1 (3.11d)

∑

i=1

= 1 (3.11e)

 0 i = 0,. .. ,k (3.11f)

∈ R i = 0,. .. ,k (3.11g)

∈ B i = 1,. .. ,k (3.11h)

Tomemos como exemplo a Figura 3.5, com os valores dos pontos conforme indicado. Desejamos

representar de acordo com o modelo x = 2,7. Assim, y

= 1 e y

= 0, i = 3, seleciona apenas a

região r

(restrições (3.11e) e (3.11h)). As variáveis (λ

,. ..,λ

) assumem valores (0, 0, 0,3, 0,7, 0)

(restrições (3.11d), (3.11f) e (3.11g)). Para as restrições (3.11a) a (3.11c) temos:

 y

=⇒ λ

 0 (3.11a)

 y

+ y

=⇒ λ

 0+ 0 = 0 (3.11b)

 y

+ y

=⇒ λ

 0+ 1 = 1

 y

+ y

=⇒ λ

 1+ 0 = 1

 y

=⇒ λ

 0 (3.11c)

Os valores de x e

f(x) são calculados por (3.10a) e (3.10a) respectivamente:

3. Fundamentos de otimização inteira 38

x = 0· 0+ 1· 0+ 2· 0,3+ 3· 0,7+ 4· 0

= 0,6+ 2,1 = 2,7

f(x) = 1· 0+ 4· 0+ 2· 0,3+ 6· 0,7+ 4· 0

= 0,6+ 4,2 = 4,8

Observamos que o ponto desejado x = 2,7 está entre a

e a

. Portanto, y

= 1 seleciona apenas

aquela região. Observamos também que λ

assumiu um valor maior que λ

, pois x está mais próximo

de a

, devendo sua variável de peso ser mais expressiva.

3.5.2 Modelo seqüencial de pesos (Modelo II)

Neste modelo, escrevemos x como:

x = a

+ λ

+ .. . + λ

onde 0  λ

 a

− a

i−1

, i = 1,...,k.

Desejamos representar um dado x que pertence a uma região r da função. Então λ

assume:











− a

i−1

se i < r

x− a

se i = r

0 se i > r

Assim chegamos a formulação:

x =a

∑

i=1

(3.12a)

f(x) = f(a

) +

∑

i=1

f(a

) − f(a

i−1

)

− a

i−1

(3.12b)

com restrições:

 a

− a

(3.13a)

 (a

− a

i−1

i = 2,. ..,k (3.13b)

 (a

− a

i−1

i = 1,. ..,k− 1 (3.13c)

 0 (3.13d)

∈ R i = 1,. ..,k (3.13e)

∈ B i = 1,. ..,k− 1 (3.13f)

3. Fundamentos de otimização inteira 39

= 0 a

= 1 a

= 2 a

= 3 a

= 4

f(x)

Figura 3.6: Linearização por partes para o modelo seqüencial

Note que em (3.13c) está implícito λ

 0, pois λ

 (a

−a

i−1

 0, sendo y

∈ {0,1} e a

> a

i−1

As variáveis inteiras y

selecionam as regiões anteriores a x. Assim, se considerarmos que x pertence

a uma região r,



1 se i < r

0 se i  r

Observamos em (3.13f) que y

é deﬁnido apenas até i = k − 1, sendo desnecessário y

, pois se x

pertencer à última região, y

= 1, ∀i ∈ {1,. .. ,k− 1}.

Para o mesmo exemplo do modelo anterior, buscamos x = 2,7. Como a

 x  a

, r = 3 e

) = (1,1,0). As variáveis reais (λ

,. .. ,λ

)= (1, 1, 0,7, 0). A Figura 3.6 ilustra este modelo

e as restrições ﬁcam:

 a

− a

=⇒ λ

 1− 0 = 1 (3.13a)

 (a

− a

=⇒ λ

 (1− 0)1 = 1 (3.13c)

∴ λ

= 1

 (a

− a

=⇒ λ

 (2− 1)1 = 1 (3.13b)

 (a

− a

=⇒ λ

 (2− 1)1 = 1 (3.13c)

∴ λ

= 1

 (a

− a

=⇒ λ

 (3− 2)1 = 1 (3.13b)

 (a

− a

=⇒ λ

 (3− 2)0 = 0 (3.13c)

∴ 0  λ

 1

 (a

− a

=⇒ λ

 (4− 3)0 = 0 (3.13b)

 0 (3.13d)

∴ λ

= 0

Os valores de x e

f(x) são calculados por (3.12a) e (3.12b) respectivamente:

3. Fundamentos de otimização inteira 40

x = a

+ λ

= 0+ 1+ 1+ 0,7+ 0 = 2,7

f(x) = f(a

) +

f(a

) − f(a

)

− a

f(a

) − f(a

)

− a

f(a

) − f(a

)

− a

f(a

) − f(a

)

− a

= 1+ 3· 1+ (−2) · 1+ 4· 0,7+ (−2) · 0

= 4,8

Padberg apresenta em [27] uma comparação entre este modelo (Modelo II) e o anterior (Modelo

I). Ele faz uma transformação do Modelo I para o espaço de variáveis de decisão do Modelo II, e

mostra que o Modelo II está estritamente contido nesta transformação do Modelo I. Mostra ainda

que os vértices do poliedro correspondente à relaxação linear do Modelo II são todos inteiros com

respeito às variáveis y. Isto implica que a solução de um problema de otimizar uma função linear por

partes pode ser obtida por meio de programação linear pura. Neste aspecto, o Modelo II é considerado

localmente muito melhor que o Modelo I. Padberg propõe ainda que o Modelo I não seja utilizado,

pois esta formulação é sempre igual ou melhor que a anterior, mesmo no pior caso e que o Modelo I

deveria ser deﬁnitivamente abandonado, apesar de sua popularidade nos livros texto.

Entretanto sob o aspecto didático, o Modelo I é mais intuitivo que o II, devido ao signiﬁcado de

suas variáveis de decisão e simplicidade das restrições. Em um exercício algébrico, Padberg pro-

põe uma formulação que transforma o Modelo II no espaço de variáveis de decisão de I, mas suas

restrições continuam pouco intuitivas. Então Sherali propõe em [28] uma formulação simples com

variáveis de decisão semelhantes às do Modelo I e com as características poliedrais do Modelo II.

3.5.3 Modelo de Sherali (Modelo III)

Sherali propõe em [28] uma “formulação didática” para a linearização por partes. Nesta formu-

lação, são utilizadas duas variáveis de peso para cada região da linearização: λ

é o peso do ponto à

esquerda da região e λ

é o peso do ponto à direita da região. Também são empregadas variáveis y

inteiras que selecionam a região. Esta formulação é mais geral que as anteriores, pois permite também

linearizar funções descontínuas.

x =

∑

i=1

i−1

+ a

] (3.14a)

f(x) =

∑

i=1

[ f(a

i−1

)λ

+ f(a

)λ

] (3.14b)

3. Fundamentos de otimização inteira 41

= 0 a

= 1 a

= 2 a

= 3 a

= 4

f(x)

Figura 3.7: Linearização por partes para o modelo de Sherali

com restrições

+ λ

= y

i = 1,. .. ,k (3.15a)

∑

i=1

= 1 (3.15b)

 0 i = 1,. .. ,k (3.15c)

∈ R i = 1,. .. ,k (3.15d)

∈ B i = 1,. .. ,k (3.15e)

Na Figura 3.7 vemos uma ilustração deste modelo. Para exempliﬁcar, representamos x = 2,7.

Para selecionar a região r

de x, as variáveis inteiras y

assumem valores (y

,. ..,y

) = (0,0,1,0),

atendendo as restrições (3.15b) e (3.15e). Devido às restrições (3.15a), (3.15c) e (3.15d), λ

e λ

= 0,

i ∈ {1,2,4}; e λ

= 0,3 e λ

= 0,7.

Com (3.14a) e (3.14b) calculamos x e

f(x), como apresentado a seguir. Como λ

e λ

são nulos

para i ∈ {1,2,4}, estes termos serão omitidos.

x = a

+ a

= 2· 0,3+ 3· 0,7 = 2,7

f(x) = f(a

)λ

+ f(a

)λ

= 2· 0,3+ 6· 0,7 = 4,8

3. Fundamentos de otimização inteira 42

Do exemplo apresentado, (3.15a) e (3.15b) são escritas matricialmente como

Ax =







1 1 −1 0 0 0 0 0 0 0 0 0

0 0 0 1 1 −1 0 0 0 0 0 0

0 0 0 0 0 0 1 1 −1 0 0 0

0 0 0 0 0 0 0 0 0 1 1 −1

0 0 1 0 0 1 0 0 1 0 0 1







x =

















Desejamos mostrar que

A é totalmente unimodular. As colunas das variáveis λ possuem apenas

uma linha diferente de zero. De acordo com Newhauser [22], estas colunas podem ser desconsidera-

das. Note que a matriz resultante (colunas de y) corresponde a uma matriz de incidência [21, página

40], que é totalmente unimodular. Assim, a matriz

A também é totalmente unimodular.

As restrições (3.15c) a (3.15e), na forma y

 0 e y

 1 para todo i = 1,.. . , k, implicam em

identidades que são concatenadas à matriz

A, e não afetam sua unimodularidade. Note também que

as restrições de igualdade podem ser transformadas em desigualdades (π

x = π

=⇒ π

x  π

x  π

). Assim, a matriz de restrições para esta formulação é totalmente unimodular.

A conseqüência é que o poliedro desta formulação é mínimo, ou seja, ele corresponde ao poliedro

do fecho convexo das soluções, e todos seus vértices estão sobre pontos inteiros. Assim, apenas

programação linear é suﬁciente para resolver um problema de linearização por partes pura. Em [28]

Sherali mostra que se f(x) for contínua, sua formulação é equivalente à do Modelo II.

Em [29] apresentamos uma comparação entre o modelo com pesos por ponto (Modelo I) com

o modelo de Sherali (Modelo III). Aplicamos os modelos ao problema de alocação ótima de gás de

injeção com restrição de capacidade máxima de injeção, mas sem a restrição de precedência de ati-

vação. Executamos experimentos numéricos em instâncias com 32 e 64 poços de petróleo, aplicando

o algoritmo de Branch and Bound puro, sem o uso de geração automática de cortes. Os experimen-

tos mostraram que as formulações baseadas no modelo de Sherali apresentaram sempre um número

menor de iterações do algoritmo em relação às formulações baseadas no Modelo I, e portanto, que o

modelo apresenta resultados melhores também quando não é aplicado de maneira pura, isto é, com

outras restrições além das do modelo (no caso, restrições de capacidade máxima de injeção de gás).

3.6 Sumário

Neste capítulo vimos que a otimização é a área da matemática aplicada que busca uma solução

ótima (mínima ou máxima) para um problema atendendo a restrições. Vimos que ela é dividida em

vários domínios, e nos aprofundamos no domínio que envolve variáveis inteiras. Estudamos o pro-

blema da mochila e vimos mais detalhadamente o problema com restrições de precedência, que será

aplicado ao problema de otimização de gás de injeção. Mostramos como obter desigualdades fortes

para esta formulação, que são importantes para agilizar o processo de resolução do problema. Por ﬁm,

3. Fundamentos de otimização inteira 43

apresentamos três modelos de linearização por partes de funções separáveis utilizando programação

linear inteira-mista.

Capítulo 4

Modelo linear por partes

Na Seção 2.3 apresentamos uma formulação geral para o problema de alocação ótima de gás de

injeção sob restrições da capacidade máxima de injeção de gás e de precedência de ativação. Neste

capítulo a curva de performance do poço (CPP) será linearizada por partes e aplicaremos programação

linear inteira-mista sobre P(G).

Em seguida apresentaremos desigualdades válidas para o poliedro da formulação, derivadas a par-

tir das desigualdades de cobertura para o problema da mochila sob restrições de precedência, as quais

podem ser empregadas na geração de cortes em um algoritmo de planos de corte. Os conceitos intro-

duzidos serão elucidados por meio de exemplos. As formulações e demonstrações apresentadas neste

capítulo foram desenvolvidas por Nakashima[19]. Camponogara e Conto apresentam sinteticamente

em [30] o desenvolvimento mostrado neste capítulo.

4.1 Formulação do problema

Desejamos uma formulação linear por partes para a formulação apresentada na Seção 2.3. Para

isto, aplicamos o modelo de linearização proposto por Sherali [28] (Seção 3.5.3) devido a sua simpli-

cidade e características poliedrais.

A Figura 4.1 apresenta uma aproximação linear por partes de um poço n para uma curva con-

tínua. A aproximação é obtida diretamente de pontos amostrados da CPP Q

= {(q

n,1

out

), ... ,

n,κ(n)

out

)}, onde κ(n) é o número de pontos de amostra. Alternativamente, se a CPP está na

forma de uma curva contínua ˜q

out

, a aproximação linear por partes pode ser produzida tomando uma

quantidade arbitrária de pontos desta curva, que reﬂetem a qualidade da linearização. Variáveis bi-

nárias x

n,k

são necessárias para indicar qual segmento linear está representado na função objetivo:

n,1

= 1 se o poço n está desativado, neste caso q

= q

out

= 0; note que y

= 1− x

n,1

. Para k  2,

n,k

= 1 se, e somente se, (q

out

) é uma combinação convexa dos pontos extremos do k-ésimo in-

tervalo, isto é, (q

out

) = λ

n,k

n,k−1

out

) + λ

n,k

out

) com λ

n,k

+ λ

n,k

= 1 e λ

n,k

, λ

n,k

 0.

4. Modelo linear por partes 45

n,1

n,2

n,3

n,4

n,5

0 q

n,1

n,2

n,3

n,4

n,κ(n)

n,1

out

n,2

out

n,2

n,3

n,4

n,5

Figura 4.1: Linearização por partes da CPP de um poço n.

Para cada n ∈ N = {1,... ,N}, temos as seguintes restrições:

κ(n)

∑

k=1

n,k

= 1 (4.1a)

= 1− x

n,1

(4.1b)

n,k

,λ

n,k

 0, k = 2,.. . ,κ(n) (4.1c)

n,k

+ λ

n,k

= x

n,k

, k = 2,.. . ,κ(n) (4.1d)

κ(n)

∑

k=2

n,k−1

n,k

+ q

n,k

) (4.1e)

out

κ(n)

∑

k=2

n,k−1

out

n,k

+ q

n,k

out

n,k

) (4.1f)

n,k

∈ {0,1} k = 1,.. . ,κ(n) (4.1g)

Para o conjunto de pontos Q

, obtidos diretamente por testes no poço ou da linearização da apro-

ximação ˜q

out

da CPP, assumimos algumas hipóteses que não implicam em perda da generalidade do

problema:

Hipótese 4.1 Para cada poço n ∈ N :

1. 0 < q

n,k

< q

n,k+1

, para todo 1  k < κ(n), implica que as taxas de injeção são distintas e

consecutivas;

2. q

n,1

= l

e q

n,κ(n)

= u

 q

max

para eliminar pontos desnecessários; e

3. cada ponto q

n,k

= (q

n,k

out

) ∈ Q

, 2< k < κ(n), não é uma combinação convexa de (q

n,k−1

out

)

e (q

n,k+1

out

), para descartar pontos redundantes.

Seja f

n,k

= f

n,k

out

) = (p

+ p

− p

n,k

out

− p

n,k

a contribuição na função lucro do

poço n operando no ponto (q

n,k

out

), podemos levar a linearização por partes para a função objetivo:

Maximizef =

∑

n=1

κ(n)

∑

k=2

(λ

n,k

n,k−1

+ λ

n,k

) (4.2)

4. Modelo linear por partes 46

Portanto, aformulação linear inteira por partes P

(G) é composta pela função objetivo (4.2), pelas

restrições (4.1a) a (4.1g), e pelas restrições de capacidade máxima de injeção de gás e precedência. No

Apêndice B apresentamos uma formulação linear por partes para P(G) que considera a concavidade

da curva de performance do poço. Esta formulação utiliza uma propriedade do modelo de Sherali

[28] que permite uma redução no número de variáveis de decisão inteiras caso a curva linear por

partes possua regiões côncavas. O modelo apresentado não implica em uma redução da complexidade

computacional da resolução do problema, mas o menor número de variáveis inteiras pode signiﬁcar

um número menor de nós na árvore de busca de Branch and Bound, e consequentemente um menor

tempo de processamento.

Baseado na análise das restrições de P

(G), algumas variáveis de decisão podem ser descartadas,

e as restrições reformuladas para uma formulação mais compacta. Para cada poço n, as variáveis que

podem ser expressas como função de outras são:

n,k

= x

n,k

− λ

n,k

k = 2,.. . ,κ(n) (4.3a)

κ(n)

∑

k=2

n,k−1

n,k

+ q

n,k

]

κ(n)

∑

k=2

n,k

− (q

n,k

− q

n,k−1

)λ

n,k

] (4.3b)

n,1

= 1−

κ(n)

∑

k=2

n,k

(4.3c)

κ(n)

∑

k=2

n,k

(4.3d)

Aplicando à P

(G) estas substituições e algumas outras que serão apresentadas a seguir, obtemos a

formulação linear por partes compacta:

cpl

(G) : Maximize f =

∑

n=1

κ(n)

∑

k=2

[ f

n,k

− ( f

n,k

− f

n,k−1

)λ

n,k

] (4.4a)

Sujeito a:

∑

n=1

κ(n)

∑

k=2

n,k

− (q

n,k

− q

n,k−1

)λ

n,k

]  q

max

(4.4b)

κ(n)

∑

k=2

n,k



κ(m)

∑

k=2

m,k

∀(m,n) ∈ E(G) (4.4c)

κ(n)

∑

k=2

n,k

 1 ∀n ∈ R(G) (4.4d)

n,k

 0, ∀(n,k) ∈ Ω (4.4e)

n,k

− λ

n,k

 0 ∀(n,k) ∈ Ω (4.4f)

n,k

∈ {0,1} ∀(n,k) ∈ Ω (4.4g)

onde λ

n,k

= λ

n,k

, R(G) = { j ∈ V(G) : ∄(i, j) ∈ E(G)} é o conjunto das raízes de G e Ω = {(n,k) :

n = 1,.. . ,N,k = 2,... ,κ(n)} é o conjunto de pares poços e níveis de ativação, isto é, o conjunto de

índices dos pontos da representação linear por partes da CPP. Note que as restrições (4.4e) e (4.4f)

4. Modelo linear por partes 47

garantem que x

n,k

 0. Ainda, as restrições (4.4c) e (4.4d) implicam que x

n,k

 1 para qualquer

caminho i, j,... de G com i ∈ R(G), assim, é suﬁciente impor a restrição

∑

κ(i)

k=2

i,k

= y

 1.

Sejam λ

= {λ

n,k

: k = 2,. .. ,κ(n)} os fatores que induzem a combinação convexa dos elemen-

tos de Q

, e λ = ∪

n=1

. Sejam x

= {x

n,k

: k = 2,.. . ,κ(n)} as variáveis discretas que forçam a

combinação convexa a usar apenas dois elementos consecutivos de Q

, e x = ∪

n=1

. Chamemos o

conjunto das soluções factíveis do problema de alocação de gás sob restrições de precedência de X .

Deﬁnimos o poliedro P = {(x,λ) ∈ R

K−N

×R

K−N

: (x,λ) que satisfaça as restrições (4.4b) a (4.4f) },

onde K =

∑

n=1

κ(n). Então P é uma formulação para X , pois X = P ∩ (Z

K−N

× R

K−N

4.2 Desigualdades válidas

No capítulo anterior apresentamos de maneira geral como obter desigualdades válidas para o pro-

blema da mochila sob restrição de precedência. Podemos observar que P

cpl

(G) se enquadra nesta

classe de problemas, pois (4.4b) é uma restrição linear do tipo da mochila e (4.4c) é a restrição de

precedência. Nesta seção, apresentaremos famílias de desigualdades válidas de conv(X ) que serão

adicionadas a P para torná-lo mais forte. Com estas desigualdades válidas podemos utilizar o algo-

ritmo de Branch and Cut apresentado no capítulo anterior.

Começamos apresentando as condições para as quais conv(X ) possui dimensão cheia. Estas

condições garantem que o poliedro não possui variáveis redundantes e dependências lineares, sim-

pliﬁcando as provas de maximalidade das faces induzidas pelas desigualdades. Seja A

= {m ∈ V :

m ≺ n}\{n} o conjunto de predecessores do nó n. Seja σ

∑

m∈A

m,1

é a quantia mínima de gás

necessária para ativar os poços que precedem n.

Proposição 4.1 conv(X ) possui dimensão cheia se max{σ

+ q

n,κ(n)

: n ∈ N }  q

max

Prova: Seja T = n

,. ..,n

 uma ordenação topológica de G. Seja Z uma matriz 2(K − N) ×

2(K − N) em que as colunas correspondem as variáveis x

, λ

, ..., x

,κ(n

)

, λ

,κ(n

)

, ..., x

,κ(n

)

, λ

,κ(n

)

nesta ordem, da esquerda para a direita. Para i= 1,. .. ,N e k = 2,...,κ(n

seja z

i,k

= (x

i,k

,λ

i,k

) o vetor de incidência obtido deﬁnindo x

i,k

l,2

= λ

i,k

l,2

= 1 para todo l ∈ A

, e x

i,k

= 1,

enquanto todas as outras entradas são nulas. Seja ˆz

i,k

= ( ˆx

i,k

) idêntico a z

i,k

, exceto que

i,k

= 1;

como as restrições de precedência são respeitadas e max{σ

+ q

n,κ(n)

: n ∈ N }  q

max

, z

i,k

e ˆz

i,k

pertencem a P

cpl

(G).

Sejam z

i,k

e ˆz

i,k

as linhas de Z ordenadas como foram inicializadas no procedimento acima. Então

Z é uma matriz triangular inferior e sua diagonal possui apenas uns. Ainda, rank(Z) = 2(K − N) e

como o vetor nulo também pertence a P

cpl

(G), concluímos que dim(P

cpl

(G)) = 2(K − N). 

4.2.1 Coberturas

No capítulo anterior apresentamos o conceito de coberturas para o problema da mochila com res-

trições de precedência. Nesta seção apresentaremos a aplicação deste conceito aplicado ao problema

4. Modelo linear por partes 48

2 3

H(C)

Figura 4.2: Grafo de restrição de precedência G = (V,E)

Níveis de injeção q

n,k

n\k 1 2 3 4 5 6 κ(n) σ

1 0,5 2 3 4 5 6 6 0

2 1 2 3 4 5 5,5 6 0,5

3 1 2 3 4 5 6 6 0

4 1 2 3 4 4,5 5 1,5

5 1 2 3 3,5 4 2,5

6 1 2 3 4 5 5 1

7 1 2 3 4 5 6 6 0

8 1 2 2,5 3 3,5

9 1 2 3 3 3

10 1 2 3 4 5 5 1

11 1 1,5 2 4,5

12 1 1,5 2 4,5

Tabela 4.1: Taxa de injeção para os poços de petróleo

que estamos estudando. Iniciaremos com um exemplo ilustrativo, e em seguida o generalizaremos

apresentando a deﬁnição formal.

Considere um cenário simples com 12 poços e o grafo de precedência descrito da Figura 4.2. Os

valores de q

n,k

da CPP linear por partes são apresentados na Tabela 4.1. A quantia total de gás de

injeção disponível é q

max

= 6. Os valores q

n,k

out

não são necessários para a análise do poliedro conv(X ),

e estão implícitos na forma linear por partes da função objetivo.

Dado o conjunto Ω deﬁnido na seção anterior, tomamos o conjuntoC ⊂ Ω, comC = { (1,2), (2,2),

(3,2), (4,3), (5,3), (6,3) }. Considere:

i) Seja N(S) = {n : (n,k) ∈ S} o conjunto de poços com pares no subconjunto S ⊆ Ω. Como

N(C) = {1,2,3,4,5,6}, todos os pares em C são de poços distintos.

ii) Dado qualquer S ⊆ Ω, seja l(S) = ∪

n∈N(S)

∪ {n}) o conjunto de todos os predecessores

de N(S) incluindo os elementos de N(S). Observe que l(C) = N(C) signiﬁca que o subgrafo

4. Modelo linear por partes 49

induzido G[N(C)] contém todos os nós que precedem nós de N(C).

iii) Para S ⊆ Ω, seja H(S) = {(n,k) ∈ S : ∄(m, j) ∈ S tal que n ≺ m} os pares de S em que os nós

não precedam nenhum outro elemento de S. Note que H(C) = { (4,3), (5,3), (6,3) } e que para

todo (n,k) ∈ C\H(C) = { (1,2), (2,2), (3,2) } temos k = 2.

iv) Para S ⊆ Ω, seja γ(S) =

∑

(n,k)∈S

n,k−1

a quantidade mínima de gás necessário para ativar o poço

n em um nível k (x

n,k

= 1) para todo (n,k) ∈ S. Observe que γ(C) = 0,5+ 1+ 1+ 2+ 2+ 2 =

8,5 > q

max

Das considerações (i) a (iv), concluímos que os elementos de H(C) não podem ser ativados simul-

taneamente porque demandaria mais gás de injeção que o disponível. Isto signiﬁca que C é uma

cobertura que induz a desigualdade válida

∑

(n,k)∈H(C)

n,k

 |H(C)| − 1. No exemplo, a desigualdade

da cobertura é x

4,3

+ x

5,3

+ x

6,3

 2.

Deﬁnição 4.1 C ⊆ Ω é uma cobertura se:

i. C possui no máximo um elemento (n,k) ∈ Ω para cada n ∈ N ;

ii. l(C) = N(C);

iii. k = 2 para todo (n,k) ∈ C\H(C);

iv. γ(C) > q

max

Deﬁnição 4.2 Uma cobertura C é mínima se γ(C\{n,k})  q

max

para cada (n,k) ∈ H(C).

Uma cobertura é um conjunto de pontos de operação de poços em um campo de petróleo que

seja realizável (condição i) e respeite a restrição de precedência (condições ii e iii), e que não exista

recurso suﬁciente para que o campo opere nestes pontos de operação (iv). Uma covertura é mínima se

excluindo qualquer um dos pontos de operação de C, exista recurso suﬁciente para operar o conjunto

restante.

4.2.2 K-Coberturas

Dado um subconjunto de nós U ⊆ N , seja Ω(U) = {(n,k) ∈ Ω : n ∈ U} o conjunto de pares

“poço/nível de ativação” em que os poços estão em U. Para K = 2, H(C) possui três conjuntos

de cardinalidade K: S

4,5

= {(4,3), (5,3)}, S

4,6

= {(4,3), (6,3)} e S

5,6

= {(5,3), (6,3)}; que induzem

os conjuntos de precedência l(S

4,5

) = {1, 2, 3, 4, 5}, l(S

4,6

) = {1, 2, 3, 4, 6} e l(S

5,6

) = {1, 2,

3, 5, 6}. Estes conjuntos de precedêndia induzem subconjuntos de pares Φ

4,5

, Φ

4,6

e Φ

5,6

dados

por Φ

4,5

= Ω(l(S

4,5

)) ∩C = {(1,2), (2,2), (3,2), (4,3), (5,3)}, Φ

4,6

= Ω(l(S

4,6

)) ∩C = {(1,2), (2,2),

(3,2), (4,3), (6,3)} e Φ

5,6

= Ω(l(S

5,6

))∩C = {(1,2), (2,2), (3,2), (5,3), (6,3)}. Observe que γ(Φ

4,5

) =

γ(Φ

4,6

) = γ(Φ

5,6

) = 6,5 > 6 = q

max

, implicando que Φ

4,5

, Φ

4,6

e Φ

5,6

são cada um uma cobertura,

conforme deﬁnido anteriormente. Como γ(Φ

m,n

\{(i, j)}) = 4,5 < q

max

para todo (m,n) ∈ {(4,5),

4. Modelo linear por partes 50

(4,6), (5,6)} e (i, j) ∈ S

m,n

, veriﬁcamos que Φ

4,5

, Φ

4,6

e Φ

5,6

são coberturas mínimas. Como qualquer

subconjunto de H(C) com cardinalidade K = 2 induz uma cobertura mínima, C é chamado de K-

cobertura e implica na desigualdade válida:

∑

(n,k)∈H(C)

n,k

= x

4,3

+ x

5,3

+ x

6,3

 1 = K − 1, (4.5)

que é mais forte que a desigualdade anterior. O conceito K-coberturas é formalizado a seguir. Dado

uma cobertura C e um subconjunto S ⊆ Ω, Φ

= Ω(l(S))∩C denota pares deC cujos poços aparecem

na lista de predecessores de S.

Deﬁnição 4.3 Uma cobertura C é uma K-cobertura se:

i. γ(Φ

) > q

max

para todo S ⊆ H(C) com |S| = K, onde Φ

= Ω(l(S)) ∩C; mas

ii. γ(Φ

\{(n,k)})  q

max

para todo (n,k) ∈ S.

C é uma K-cobertura se for uma cobertura e todo subconjunto S de C que respeite as restrições

de precedência, e com cardinalidade K, for uma cobertura mínima de acordo com as Deﬁnições 4.1 e

4.2.

Em seguida, trataremos de um conjunto de pares expandidos de uma K-cobertura S, deﬁnido por

Γ(S) = {(n,i) : (n,k) ∈ S e 2  i  k} que adiciona a S pares cujo poço está em S e cujo nível de

ativação é menor que o de S. Para a cobertura C dada anteriormente, Γ(C) = { (1,2), (2,2), (3,2),

(4,2), (4,3), (5,2), (5,3), (6,2), (6,3) }. Note que a desigualdade (4.5) é válida porque não existe

recurso de injeção suﬁciente para simultaneamente ativar todos os pares de qualquer subconjunto de

H(C) com cardinalidade K. A proposição a seguir formaliza esta desigualdade.

Proposição 4.2 Se C é uma K-cobertura então

∑

(n,k)∈H(C)

n,k

 K − 1 (4.6)

é válida para o poliedro conv(X

) onde X

= {(x,λ) ∈ X : x

n,k

= λ

n,k

= 0 para todo (n,k) ∈ Ω\Γ(C)}

é o conjunto de soluções que podem ativar apenas pares de Γ(C).

Esta proposição mostra que a desigualdade da K-cobertura é válida para a projeção de conv(X )

no espaço expandido pelas variáveis de índices Γ(C), que é o poliedro conv(X

). Obviamente, a

desigualdade é válida para conv(X ).

Continuando o exemplo, considere Φ

4,5

de maneira que γ((Φ

4,5

\{(4,3)}) ∪ {(4,2)}) = 5,5 <

max

e γ((Φ

4,5

\{(5,3)})∪{(5,2)}) = 5,5 < q

max

. Isto signiﬁca que Φ

4,5

não é mais uma cobertura se

qualquer elemento (n,k) ∈ H(Φ

4,5

) for substituído por (n,k− 1), ou simplesmente removido quando

k = 2. Esta propriedade também pode ser veriﬁcada para Φ

4,6

e Φ

5,6

. Uma K-cobertura é estrita

se esta propriedade é satisfeita por cada cobertura induzida Φ

, onde S ⊆ H(C),|S| = K, e Φ

Ω(l(S)) ∩C.

4. Modelo linear por partes 51

Deﬁnição 4.4 Uma K-cobertura C é estrita se, para todo S ⊆ H(C), |S| = K, e todo (n,k) ∈ S valer:

i. γ(Φ

\{(n,k)}) < q

max

se k = 2; ou

ii. γ((Φ

\{(n,k)}) ∪ {(n,k− 1)}) < q

max

quando k > 2.

K-coberturas estritas possuem a propriedade de serem máximas ou facetas de conv(X

). Neste

sentido elas são o mais forte possível, pois um poliedro é representado unicamente por facetas. Antes

de apresentarmos as condições de maximalidade, deﬁnimos uma solução z

= (x

,λ

) ∈ X induzida

por S ⊆ Ω como: para todo (n,k) ∈ Ω, x

n,k

= 1 e λ

n,k

= 1 se (n,k) ∈ S, caso contrário x

n,k

= 0 e

n,k

= 0.

Proposição 4.3 Dado uma K-cobertura estritaC, a desigualdade (4.6) induz uma face máxima F

{(x,λ) ∈ conv(X

) :

∑

(n,k)∈H(C)

n,k

= K − 1} de conv(X

) se, e somente se:

{S⊆H(C):|S|=K−1}

Ω(l(S)) ∩C =

0 (4.7)

Prova: (Necessidade) Suponha que (4.7) não é obedecida e seja (m,i) ∈

{S⊆H(C):|S|=K−1}

Ω(l(S))∩

C. Para qualquer T ⊆ C tal que z(T) ∈ F

, (m,i) deve aparecer em T. Então todo z = (x,λ) ∈ F

deve satisfazer x

m,i

= 1. Como F

⊆ F = {(x,λ) ∈ conv(X

) : x

m,i

= 1}, concluímos que para F

ser

máxima, F

= F , mas (4.6) não é um múltiplo escalar de x

m,i

 1, contradizendo a suposição.

(Suﬁciência) Para mostrar que (4.6) induz uma faceta, seja F

uma face máxima de P

contendo

e induzida por:

∑

(n,k)∈Γ(C)

n,k

∑

(n,k)∈Γ(C)

n,k

 π

(4.8a)

Mostraremos que (4.6) e (4.8a) diferem apenas de uma constante multiplicativa, que prova a proposi-

ção.

[Parte I] Considere qualquer (n,k) ∈ A(C) = C\H(C). Tem que existir T ⊆ H(C) com |T| = K−1

tal que n ∈ l(T). Seja Φ

= Ω(l(T)) ∩C. Claramente z

∈ F

. Seja z

′

idêntico a z

exceto que

′

n,k

= 1 − ε. Para um ε > 0 suﬁcientemente pequeno, z

′

∈ F

pois C é uma K-cobertura estrita.

Portanto, para z

e z

′

pertencerem a F

, z

e z

′

devem satisfazer:

∑

(n,k)∈Γ(C)

n,k

∑

(n,k)∈Γ(C)

n,k

= π

(4.8b)

Subtraindo (4.8b) com z

′

de (4.8b) com z

concluímos que µ

n,k

= 0.

[Parte II] Considere qualquer (n,k) ∈ H(C) e faça T ⊆ H(C) de maneira que (n,k) ∈ T e |T| =

K−1. Claramente z

∈ F

para Φ

= Ω(l(T))∩C. Seja z

′

idêntico a z

exceto que λ

′

n,k

= 1− ε.

Com ε > 0 pequeno o suﬁciente, z

′

∈ F

. Como z

e z

′

devem satisfazer (4.8b), concluímos

que µ

n,k

= 0. Agora considere algum k

′

< k. Seja T ⊆ H(C)\{(n,k)} um sub-conjunto de maneira

que |T| = K − 1. Claramente, z

∈ F

para Φ = (Ω(l(T) ∪ A

) ∩ C) ∪ {(n,k

′

)} porque C é uma

4. Modelo linear por partes 52

K-cobertura estrita. Seja z

′

idêntico a z

exceto que λ

′

n,k

= 1− ε. Para um ε > 0 suﬁcientemente

pequeno, z

′

∈ F

. Para z

′

pertencerem a F

, z

e z

′

devem satisfazer (4.8b), que nos leva a

deduzir que µ

n,k

′

= 0. Do desenvolvimento acima, concluímos que µ

n,k

= 0 para todo (n,k) ∈ Γ(C) e,

então, (4.8a) se reduz a:

∑

(n,k)∈Γ(C)

n,k

 π

(4.8c)

[Parte III] Considere qualquer (n,k) ∈ A(C). Como (4.7) é válido, deve existir T ⊆ H(C) com

|T| = K − 1 de maneira que n ∈ l(T) e (m, j) ∈ H(C)\T com n ∈ A

. Pela deﬁnição de K-cobertura,

γ(Φ)  q

max

para Φ = Ω(l(T) ∪ A

) ∩ C, e uma vez que (A

∪ {n}) ⊆ A

, temos: (i) γ(Φ

′

)  q

max

para Φ

′

= Ω(l(T)∪A

∪{n})∩C; e (ii) γ(Φ

′′

)  q

max

para Φ

′′

= Φ

′

\{(n,k)}. Portanto, z(Φ

′

) e z(Φ

′′

)

pertencem a F

, e para tê-los em F

, devem satisfazer (4.8c) na igualdade. Que nos leva a concluir

que π

n,k

= 0.

[Parte IV] Seja (n,k) ∈ Γ(C)\(A(C)∪H(C)). ComoC é uma K-cobertura estrita, deve existir T ⊆

H(C) com |T| = K − 1 de maneira que: (i) n ∈ N(T); (ii) γ(Φ

′

)  q

max

para Φ

′

= Ω(l(T) ∪ A

) ∩C;

e (iii) γ(Φ

′′

)  q

max

para Φ

′′

= Φ

′

∪ {(n,k)}. Claramente, z

′

e z

′′

pertencem a F

, e assim (4.8c)

deve ser satisfeita na igualdade, implicando que π

n,k

= 0. Deduzimos então que (4.8c) se reduz a:

∑

(n,k)∈H(C)

n,k

 π

(4.8d)

[Parte V] Considere qualquer par de pontos distintos (n,i),(m, j) ∈ H(C) e faça S⊆ H(C)\{(n,i),

(m, j)} de maneira que |S| = K − 2. Pela deﬁnição da K-cobertura, γ(Φ

′

)  q

max

para Φ

′

= Ω(l(S∪

{(n,i)})) ∩ C e γ(Φ

′′

)  q

max

para Φ

′′

= Ω(l(S ∪ {(m, j)})) ∩C. Claramente, z

′

e z

′′

pertencem

a F

. Uma vez que z

′

e z

′′

devem pertencer a F

, eles devem satisfazer (4.8d) na igualdade,

que nos leva a deduzir que π

n,i

= π

m, j

. Assumindo, sem perda de generalidade, π

n,k

= 1 para todo

(n,k) ∈ H(C), temos que π

= K − 1. Consequentemente, (4.6) difere de (4.8a) apenas de uma

constante multiplicativa, demostrando que (4.6) é máxima.



Para a K-cobertura estrita C do exemplo ilustrativo, note que ∩

{S⊆H(C):|S|=K−1}

Ω(l(S)) ∩ C =

∩

{S⊆{(4,3),(5,3),(6,3)}:|S|=1}

Ω(l(S))∩C= Ω(l({(4,3)}))∩Ω(l({(5,3)}))∩Ω(l({(6,3)}))∩C =

0. Como

C satisfaz a condição (4.7), tempos que (4.5) induz uma faceta de conv(X

Uma K-cobertura estrita C é chamada de cobertura (estritamente) mínima se |H(C)| = K. É

evidente da deﬁnição de K-cobertura que todo S ⊆ H(C) com |S| = K induz uma cobertura mínima

= Ω(l(S)) ∩C. No exemplo ilustrativo, a K-cobertura C não é mínima, pois H(C) = 3 > 2 = K.

Com S = {(4,3),(5,3)} a cobertura Φ

é mínima, pois |H(Φ

)| = K.

Uma K-cobertura C não mínima é mais forte que qualquer cobertura mínima induzida Φ

sentido que

∑

(n,k)∈H(C)

n,k

 K − 1 =⇒

∑

(n,k)∈S

n,k

 K − 1. No exemplo, qualquer desigualdade

4,3

5,3

 1, x

4,3

6,3

 1 e x

5,3

6,3

 1, obtida de uma cobertura mínima Φ

é claramente mais

4. Modelo linear por partes 53

fraca que (4.5). É necessário aplicar um procedimento de arredondamento (2x

4,3

+ 2x

5,3

+ 2x

6,3



3)/2 =⇒ x

4,3

+ x

5,3

+ x

6,3

 ⌊3/2⌋ =⇒ x

4,3

+ x

5,3

+ x

6,3

 1) para obter (4.5).

4.3 Fatores de lifting para K-coberturas

Mostramos que uma K-cobertura estrita induz uma face máxima (faceta) de conv(X

), que é a

projeção de conv(X ) no espaco de variáveis com índices em Γ(C). Esta desigualdade também é

válida para conv(X ), entretanto podemos torná-la mais forte, estendendo-a para todos os pares de Ω:

∑

(n,k)∈H(C)

n,k

∑

(n,k)∈Ω\Γ(C)

n,k

 K − 1 (4.9)

onde α

n,k

são os fatores de lifting, que dependem da cobertura e da ordem na qual são calculados.

Para exempliﬁcar, assuma o exemplo ilustrativo e a desigualdade da K-cobertura (4.5) indu-

zida por C = { (1,2), (2,2), (3,2), (4,3), (5,3), (6,3) }. O par (n,k

′

) = (4,4) requer ao menos

min{q

n,k−1

n,k

} = min{q

4,3

4,4

} = min{3,4} = 3 unidades de gás para ser ativado. Como esta

quantia é maior que o requerido por (n,k) = (4,3) ∈ H(C), e no máximo um destes pares pode ser

ativado, a variável x

4,4

pode ser adicionado ao lado esquerdo da desigualdade (4.5). Neste raciocí-

nio, podemos adicionar as variáveis x

4,5

, x

5,4

e x

6,5

à desigualdade (4.5). Continuando a análise, o

par (n,k

′

) = (1,6) requer que ao menos min{q

n,k−1

n,k

} = min{q

1,5

1,6

} = 5. Esta quantidade é

suﬁciente para ativar o poço n no nível k = 2, que requer 1 unidade, enquanto as 4 unidades restantes

podem ativar os pares (2,2), (3,2) e (5,3) que requerem 1, 1 e 2 unidades de gás de injeção respecti-

vamente. Portanto, a ativação do par (1,6) requer tanto recurso quanto ativar (5,3) ∈ H(C), e assim,

a variável x

1,6

é adicionada ao lado esquerdo de (4.5).

Os fatores de lifting são obtidos resolvendo uma seqüência K = K

: t = 1,... ,T de problemas

cpl

(G) deﬁnidos de forma recursiva por:

: ζ

= Maximize

∑

(n,k)∈H(C)

n,k

t−1

∑

j=1

Sujeito a: x ∈ X

para t = 1,.. . , T, onde:

• X

U|W

= {x : (x,λ) ∈ X ,x

n,k

= 0 para todo (n,k) ∈ U, enquanto x

n,k

= 1 para todo (n,k) ∈ W} é

o conjunto restrito de soluções de X ;

• U

= {(n

t+1

k+1

),...,(n

)} é o conjunto de elementos a serem submetidos ao procedi-

mento de lifting; e

• W

= {(n

)} é o conjunto com o elemento que está sendo executado o lifting.

4. Modelo linear por partes 54

Os coeﬁcientes de lifting são deﬁnidos recursivamente por α

= K − 1− ζ

, j = 1,... ,t − 1.

Para que este procedimento seja bem deﬁnido é necessário que X

U|W

não seja vazio para todo t =

1,...,T. Para isto os fatores devem ser calculados segundo uma ordem topológica C

′

= {(n

),...,

)} de Ω\Γ(C). Dizemos que C

′

está ordenado topologicamente se n

⊀ n

para todo i, j, com

1  i < j  T.

Seja (C

′

) uma partição deC

′

∪C

′

= C

′

∩C

′

0, tal que (n

) ∈ C

′

pertence aC

′

se e somente se existe x

∈ X

que resolva K

e tal que:

∑

(n,k)∈Ω\U

n,k−1

n,k

< q

max

Proposição 4.4 Dado uma K-cobertura estrita e uma seqüência de lifting topologicamente ordenada

′

, a desigualdade de lifting (4.9) é válida para conv(X ).

Prova: Por indução em t. (Caso base) Para t = 0, (4.9) é reduzida à desigualdade da K-cobertura

(4.3) que é válida por deﬁnição. (Passo de indução) Considere t > 0 e qualquer solução (x,λ) ∈

conv(X ). Se x

= 0 então (4.9) é válida por indução. Se x

= 1 então (4.9) é válida apenas se:

∑

(n,k)∈H(C)

n,k

t−1

∑

j=1

+ α

 K − 1

que, por sua vez, é válida apenas se:

 K − 1−

∑

(n,k)∈H(C)

n,k

−

t−1

∑

j=1

 K − 1− max{

∑

(n,k)∈H(C)

n,k

t−1

∑

j=1

: x

∈ X

}

= K − 1− ζ

= α

Portanto (4.9) é válida. 

Corolário 4.1 Se a K-coberturaC éestrita, então a desigualdade (4.9) induz uma face F

= {(x,λ) ∈

conv(X ) : (x,λ) respeita (4.9) na igualdade } de conv(X ) com dim(F

) = 2|Ω| − |C

′

| − 1.

Prova: Seja Z ∈ R

(2|Ω|−|C

′

|)×2|Ω|

uma matriz em que as colunas estão relacionadas a x

n,k

e λ

n,k

(n,k) ∈ Ω. Sejam as colunas mais à esquerda as correspondentes às variáveis x

n,k

e λ

n,k

, (n,k) ∈ Γ(C),

e as demais correspondentes a x

n,k

e λ

n,k

, (n,k) ∈ Ω\Γ(C), posicionadas da esquerda para a direita

em uma ordem topológica dada por C

′

Sejam as 2|Γ(C)| linhas mais acima de Z correspondentes às 2|Γ(C)| soluções aﬁm independentes

pertencentes a F

de maneira que x

n,k

= 0 para todo (n,k) ∈ Ω\Γ(C) que existem de acordo com a

Proposição 4.3. Faça as demais linhas do topo à base serem obtidas como segue. Para t = 1,.. . ,T, a

próxima linha de Z é a solução x

para K

; se (n

) ∈ C

′

, então adicione outra linha abaixo, idêntica

4. Modelo linear por partes 55

Fatores de lifting α

n,k

n\k 2 3 4 5 6

1 0 0

∗

1 1

2 0 0 1 1

3 0 0 0

∗

4 1 1

5 1

6 1 1

7 0 0 0

∗

1 1

8 0 1

9 0 0

∗

10 0 0

∗

1 1

11 1

12 1

Tabela 4.2: Fatores de lifting para o exemplo da mochila

à linha de x

, exceto que λ

= 1− ε com ε > 0 suﬁcientemente pequeno para que a linha seja um

elemento de F

. Note que x

= λ

para todo (x,λ) ∈ F

se (n

) ∈ C

′

Claramente, as linhas 2|Γ(C)|+1,... ,2|Γ(C)|+T +|C

′

| de Z formam uma matriz bloco-diagonal,

com as 2|Γ(C)| linhas mais acima liearmente independentes. Portanto, dim(F

)  2|Γ(C)| + T +

′

|−1 = 2|Γ(C)|+|Ω\Γ(C)| + |C

′

|−1 = |Ω| + |Γ(C)| + |C

′

|−1 = |Ω| + |Ω|−|C

′

|−1 = 2|Ω|−

′

|−1. Como x

n,k

= λ

n,k

para todo (x,λ) ∈ F

se (n,k) ∈ C

′

, temos que dim(F

)  2|Ω|−|C

′

|−1,

que prova a proposição. 

Por conveniência, o problema de lifting K

pode ser reescrito como um problema de programação

inteira tornando X

explícito:

′

: ζ

= Maximize

∑

(n,k)∈H(C)

n,k

t−1

∑

j=1

(4.10a)

Sujeito a

∑

n∈N

∑

(n,k)∈S

t,n

n,k−1

n,k

 q

max

(4.10b)

∑

(m,i)∈S

t,m

m,i



∑

(n, j)∈S

t,n

n, j

∀(m,n) ∈ E(G[N

]) (4.10c)

∑

(n,k)∈S

t,n

n,k

 1 ∀n ∈ R(G[N

]) (4.10d)

= 1 (4.10e)

n,k

∈ {0,1} ∀(n,k) ∈ ∪

n∈N

t,n

(4.10f)

onde N

= N(C) ∪ {n

,. ..,n

} e S

t,n

= (Γ(C) ∪ {(n

),...,(n

)}) ∩ Ω({n}).

Exemplo Ilustrativo: Para aplicamos o procedimento de lifting sobre a desigualdade (4.5), C

′

é obtida arranjando os elementos de Ω\Γ(C) em ordem lexográﬁca: para todo (m,i),(n, j) ∈ C

′

(m,i) ≺ (n, j) se m < n, e caso m = n então i < j, induzindo uma ordem topológica. Os fatores de

lifting obtidos são apresentados na Tabela 4.2. As posições da tabela assinaladas com uma estrela

4. Modelo linear por partes 56

pertencem a C

′

, e os demais a C

′

, portanto |C

′

| = 5 e |C

′

| = 27. A dimensão da face F

deﬁnida

pela desigualdade (4.9), considerando os fatores da tabela, é dim(F

) = 2× 41− 5− 1 = 76, que é

um pouco menor que 81, a dimensão da face máxima de conv(X ).

Para se obter cada fator de lifting exato α

n,k

, é necessário resolver um problema da mochila K

que é NP-Difícil. Ou seja, para o caso geral, resolver K

é tão difícil quanto resolver P

cpl

(G). Entre-

tanto, se o grafo de precedência é uma ﬂoresta, K

pode ser resolvido em tempo pseudo-polinomial

utilizando programação dinâmica [9]. No Apêndice A apresentamos este algoritmo de programação

dinâmica.

4.4 Fatores de pseudo-lifting para K-coberturas

A diﬁculdade de se encontrar fatores exatos de lifting pode ser contornada buscando fatores de lift-

ing aproximados β

n,k

, que chamaremos de fatores de pseudo-lifting. Primeiro introduziremos alguns

conceitos utilizando o exemplo dado na Figura 4.2 e Tabela 4.1. Seja

Γ(C) = Ω− Γ(C) o conjunto de

índices das variáveis em que os fatores de pseudo-lifting serão obtidos. Este conjunto é dividido em

três subconjuntos, dependendo se os poços pertencem a N(H(C)), N(C\H(C)) ou N \N(C)):

•

H(C); no exemplo, C = { (1,2), (2,2), (3,2), (4,3), (5,3), (6,3) } implica

(5,4), (6,4), (6,5) }.

•

pseudo-lifting correspondentes aos predecessores C\H(C); no exemplo ilustrativo,

(1,3), (1,4), (1,5), (1,6), (2,3), (2,4), (2,5), (2,6), (3,3), (3,4), (3,5), (3,6) }.

•

(C)) é o conjunto dos índices restantes; no exemplo, Γ

Ω({7,8,9,10,11,12}).

No início da Seção 4.3, o exemplo sobre x

4,4

ilustra precisamente a obtenção do fator de pseudo-

lifting β

n,k

para (n,k) ∈

(C): a quantidade mínima de gás para ativar o poço n no nível k é q

n,k−1

;

como q

n,k−1

= q

4,3

= 3 > 2 = q

4,2

= q

n,k

′

−1

com (n,k

′

) = (4,3) ∈ H(C), β

4,4

= 1 e a variável x

4,4

pode ser adicionada à desigualdade da K-cobertura.

Similarmente, a discussão sobre x

1,6

mostra o cômputo de β

n,k

para (n,k) ∈

(C): note que

a quantidade mínima de gás para ativar o poço 1 no nível 6 é q

n,k−1

= q

1,5

= 5, que é suﬁciente

para ativar este poço no nível 2 e o par de maior demanda de recursos (m, j) ∈ H(C) com seus

predecessores, que são os pares (5,3), (2,2) e (3,2) que requerem 4 unidades; portanto β

1,6

= 1

permitindo que x

1,6

seja adicionada a desigualdade da K-cobertura.

Resta ilustrar o procedimento de pseudo-lifting para os elementos de (n,k) ∈

(C). Para este

conjunto, o cômputo é mais complicado pois as restrições de precedência devem ser levadas em conta

devido a uma liberdade de escolha adicional. Considere um caso simples onde (n,k) = (7,6) ∈

(C).

4. Modelo linear por partes 57

Como o nó 7 é uma folha de G, a desativação do poço 7 não viola restrições de precedência. Note

que q

n,k−1

= q

7,5

= 5, que é suﬁciente para ativar o maior elemento de H(C) e seus predecessores:

(5,3) ∈ H(C) e (1,2), (2,2) e (3,2), consumindo juntos 2+1+1+ 1 = 5 unidades de gás de injeção.

Consequentemente, o fator de pseudo-lifting β

7,5

= 1 e x

7,5

pode ser adicionada a desigualdade da

K-cobertura.

Algumas deﬁnições serão introduzidas a seguir com o objetivo de formalizar as noções dadas.

• para qualquer n ∈ N e (m, j) ∈ Ω\Ω({n}),

σ(n)

m, j







m, j−1

∑

l∈A

\(A

∪{n})

l,1

se m ⊀ n

m, j−1

− q

m,1

se m ≺ n

é a quantidade mínima de recursos necessários para ativar o poço m em um nível j, sendo que

o poço n foi ativado;

• H(C,n,k) = H(C)\{(n,k)}, com (n,k) ∈ H(C);

• H(C,n,k)

⊆ H(C,n,k) é o conjunto onde:

(i) |H(C, n,k)

| = h; e

(ii) min{σ(n)

m, j

: (m, j) ∈ H(C,n,k)

}  max{σ(n)

m, j

: (m, j) ∈ H(C,n,k)\H(C,n,k)

isto é, H(C, n,k)

é o subconjunto de H(C,n,k) com h pares que requerem a maior quantidade

de recursos para ser ativado, dado que o poço n ∈ N(H(C)), está ativo; e

• H(C,n)

⊆ H(C) é tal que:

(i) |H(C, n)

| = h e

(ii) min{σ(n)

m, j

: (m, j) ∈ H(C,n)

}  max{σ(n)

m, j

: (m, j) ∈ H(C)\H(C, n)

isto é, H(C,n)

é o subconjunto de H(C) com os h pares que requerem a maior quantidade de

recursos para ser ativado, dado que o par (n, j) está ativo.

Para os subconjuntos deﬁnidos acima,

(C), Γ

(C), apresentamos a seguir fatores de

pseudo-lift. Para um poço n de uma cobertura C, seja δ(n) o nível de ativação correspondente: se

n ∈ N(C) então δ(n) = k onde (n,k) ∈ C.

Deﬁnição 4.5 Para (n,k) ∈ Γ

(C), o fator de pseudo-lift é:

n,k

= 1+ max{h :

∑

(m, j)∈H(C,n,δ(n))

σ(n)

m, j

 q

n,k−1

− q

n,δ(n)−1

}

onde (n,δ(n)) ∈ H(C).

4. Modelo linear por partes 58

Deﬁnição 4.6 Para (n,k) ∈ Γ

(C), o fator de pseudo-lift é:

n,k

= max{h :

∑

(m, j)∈H(C,n)

σ(n)

m, j

 q

n,k−1

− q

n,1

}

Com respeito aos elementos de

(C), existe um procedimento para o cômputo de seus fatores

aproximados. Seja

,Θ

,. ..,Θ

uma partição de Γ

(i) H(

) = {(n

,2),.. . , (n

,κ(n

))} para algum n

∈ N \N(C);

(ii) m ≺ n

e j = 2 para todo (m, j) ∈

\H(Θ

Deﬁnição 4.7 Dado uma partição {

}

de Γ

(C), os fatores de pseudo-lifting β

n,k

para (n,k) ∈ Θ

são deﬁnidos como:

• β

n,k

= max{h :

∑

(m, j)∈H(C,n)

σ(n)

m, j

 q

n,k−1

− q

n,1

} se r = 0;

• β

n,k

= max{h:

∑

(m, j)∈H(C,n)

σ(n)

m, j

 q

n,k−1

∑

(m, j)∈

\H(Θ

)

m, j−1

} se r  1 e (n,k) ∈ H(Θ

);

• β

n,k

= 0 se r  1 e (n,k) ∈

\H(Θ

Proposição 4.5 Dado uma K-cobertura C e os fatores de pseudo-lifting β

n,k

, a desigualdade de

pseudo-lifting:

∑

(n,k)∈H(C)

n,k

∑

(n,k)∈

Γ(C)

n,k

 K − 1 (4.11)

é válida para conv(X ).

Prova: (Por contradição) Suponha que existe um (x,λ) ∈ conv(X ) que viola (4.11), e seja:

a) H(x) = {(n,k) ∈ H(C) : x

n,k

= 1};

H(x) = {(n,k) ∈ Γ

n,k

= 1} e H(x)

= {(n,k) ∈ H(x) : β

n,k

= t};

A(x) = {(n,k) ∈ Γ

n,k

= 1} e A(x)

= {(n,k) ∈ A(x) : β

n,k

= t}; e

B(x) = {(n,k) ∈ Γ

n,k

= 1} e B(x)

= {(n,k) ∈ B(x) : β

n,k

= t}.

Note que como (x,λ) viola (4.11),

|H(x)| +

K−1

∑

t=1



H(x)

| + |A(x)

| + |B(x)



> K − 1

4. Modelo linear por partes 59

Seja H

(x) = H(C)\(H(x) ∪ {(n,δ(n)) : (n,k) ∈ H(x)}). E considere ( ˜x,

λ) idêntica a (x,λ), com

exceção apenas do redeﬁnido nas Partes I, II, III e IV a seguir.

(Parte I) Seja Φ ⊆ H

(x) um subconjunto máximo com |Φ| 

∑

K−1

t=1

(t − 1)|

H(x)

|. Modiﬁque

( ˜x,

λ) fazendo:

a) ˜x

n,k

= 0 e ˜x

n,δ(n)

= 1 para todo (n,k) ∈

H(x);

b) ˜x

n, j

= 0 para todo (n,k) ∈ Φ, j = 1,...,k− 1;

c) ˜x

n,k

= 1 para todo (n,k) ∈ Φ; e

d) ˜x

n,k

= 1 para todo (n,k) ∈ {(m, j) ∈ C\H(C) : ˜x

m,t

= 0 para todo t} ∩ Ω(l(Φ)).

Como q

n,k−1

− q

n,δ(n)−1



∑

(m, j)∈H(C,n,δ(n))

t−1

σ(n)

m, j

para todo (n,k) ∈

H(x)

e todo t, temos que

( ˜x,

λ) ∈ conv(X ). Note que |H( ˜x)| = |H(x)|+

∑

K−1

t=1

H(x)| porque, caso contrário, ( ˜x,

λ) ∈ conv(X ) ⇒

(x,λ) ∈ conv(X ).

(Parte II) Seja Φ ⊆ H

( ˜x) um subconjunto máximo onde |Φ| 

∑

K−1

t=1

A(x)

|. Modiﬁque (˜x,

λ)

da seguinte maneira:

a) ˜x

n,k

= 0 e ˜x

n,2

= 1 para todo (n,k) ∈ ∪

K−1

t=1

A(x)

;

b) ˜x

n, j

= 0 para todo (n,k) ∈ Φ, j = 1,...,k− 1;

c) ˜x

n,k

= 1 para todo (n,k) ∈ Φ; e

d) ˜x

n,k

= 1 para todo (n,k) ∈ {(m, j) ∈ C\H(C) : ˜x

m,t

= 0 para todo t} ∩ Ω(l(Φ)).

Como na Parte I, ( ˜x,

λ) ∈ conv(X ) pois q

n,k−1

− q

n,1



∑

(m, j)∈H(C,n)

σ(n)

m, j

para todo (n,k) ∈

A(x)

e todo t. Ainda, Φ deve ser máximo porque, caso contrário, ( ˜x,

λ) ∈ conv(X ) ⇒ (x,λ) ∈ conv(X ).

Consequentemente, |H( ˜x)| = |H(x)| +

∑

K−1

t=1



H(x)

| + |A(x)



(Parte III) Seja Φ ⊆ H

( ˜x) um subconjunto máximo com cardinalidade |Φ| 

∑

K−1

t=1

B(x)

∩ Θ

Modiﬁque (˜x,

λ) fazendo:

a) ˜x

n,k

= 0 e ˜x

n,2

= 1 para todo (n,k) ∈ ∪

K−1

t=1

(

B(x)

∩ Θ

);

b) ˜x

n, j

= 0 para todo (n,k) ∈ Φ, j = 1,.. . ,k− 1;

c) ˜x

n,k

= 1 para todo (n,k) ∈ Φ; e

d) ˜x

n,k

= 1 para todo (n,k) ∈ {(m, j) ∈ C\H(C) : ˜x

m,t

= 0 para todo t} ∩ Ω(l(Φ)).

Como q

n,k−1

− q

n,1



∑

(m, j)∈H(C,n)

σ(n)

m, j

para todo (n,k) ∈

B(x)

∩ Θ

e todo t, temos que ( ˜x,

λ) ∈

conv(X ). Noteque |H( ˜x)| = |H(x)|+

∑

K−1

t=1



H(x)

| + |A(x)

| + |B(x)

∩ Θ



porque, caso contrário,

( ˜x,

λ) ∈ conv(X ) ⇒ (x,λ

) ∈ conv(X ).

(Parte IV) Seja Φ ⊆ H

( ˜x) um subconjunto máximo de cardinalidade |Φ| 

∑

K−1

t=1

B(x)

∩ Θ|

onde

Θ = ∪

r=1

. Modiﬁque (˜x,

λ) fazendo:

4. Modelo linear por partes 60

Valores σ(n)

m, j

n\(m, j) (4,3) (5,3) (6,3)

1 3 4 3

2 2 3 3

3 3.5 3.5 2

4 3 3

5 2 2

6 3.5 3.5

7 3.5 4.5 3

8 2 1 2

9 3.5 3.5 1

10 3.5 4.5 3

11 2 1 2

12 2 1 2

Tabela 4.3: Recursos mínimos de ativação

H(C,n)

e H(C,n,k)

n : (m, j) h = 1 h = 2 h = 3

1 {(5,3)} {(5,3),(4,3)} {(5,3),(4,3),(6,3)}

2 {(6,3)} {(6,3),(5,3)} {(6,3),(5,3),(4,3)}

3 {(4,3)} {(4,3),(5,3)} {(4,3),(5,3),(6,3)}

(4,3) {(5,3)} {(5,3),(6,3)}

(5,3) {(4,3)} {(4,3),(6,3)}

(6,3) {(4,3)} {(4,3),(5,3)}

7 {(5,3)} {(5,3),(4,3)} {(5,3),(4,3),(6,3)}

8 {(4,3)} {(4,3),(6,3)} {(4,3),(6,3),(5,3)}

9 {(4,3)} {(4,3),(5,3)} {(4,3),(5,3),(6,3)}

10 {(5,3)} {(5,3),(4,3)} {(5,3),(4,3),(6,3)}

11 {(4,3)} {(4,3),(6,3)} {(4,3),(6,3),(5,3)}

12 {(6,3)} {(6,3),(4,3)} {(6,3),(4,3),(5,3)}

Tabela 4.4: Subconjuntos para ativação de H(C)

a) ˜x

n,k

= 0 para todo (n,k) ∈ Ω− Ω(N(C));

b) ˜x

n, j

= 0 para todo (n,k) ∈ Φ, j = 1,.. . ,k− 1;

c) ˜x

n,k

= 1 para todo (n,k) ∈ Φ; e

d) ˜x

n,k

= 1 para todo (n,k) ∈ {(m, j) ∈ C\H(C) : ˜x

m,t

= 0 para todo t} ∩ Ω(l(Φ)).

Considerando que q

n,k−1

∑

(m, j)∈

\H(Θ

)

m, j−1



∑

(m, j)∈H(C,n)

σ(n)

m, j

para todo (n,k) ∈

∩B(x)

r, e t, temos (˜x,

λ) ∈ conv(X ). Note que

∑

(n,k)∈H(C)

˜x

n,k

= H( ˜x)  |H(x)|+

∑

K−1

t=1

t(|

H(x)

|+|A(x)

B(x)

|)  K pois (x,λ) viola (4.11). Isto implica que ( ˜x,

λ) ∈ conv(X ) ⇒ (x,λ) ∈ conv(X ), contradi-

zendo a hipótese inicial. 

Exemplo ilustrativo: Continuando o exemplo anterior, iniciamos calculando as quantidades míni-

mas de recursos de ativação σ(n)

m, j

que estão na Tabela 4.3. Os conjuntos H(C,n,k)

e H(C,n) estão

4. Modelo linear por partes 61

Coeﬁcientes β

n,k

para {Θ

′

} Coeﬁcientes β

n,k

para {

′′

}

n\k 2 3 4 5 6 2 3 4 5 6

1 0 0 0

∗

1 0 0 0

∗

2 0 0 1 1 0 0 1 1

3 0 0 0 1 0 0 0 1

4 1 1 1 1

5 1 1

6 1 1 1 1

7 0 0 0 0

∗

1 0 0 0 0

∗

8 0 1 0 0

∗

9 0 0 0 0

10 0 0 0

∗

0 0 0

∗

11 0

∗

12 0

∗

Tabela 4.5: Coeﬁcientes de pseudo-lifting

na Tabela 4.4. Os parâmetros destas tabelas serão necessários para o cálculo dos fatores de pseudo-

lifting. Para a K-cobertura C = {(1,2),(2,2),(3,2),(4,3),(5,3),(6,3)}, os conjuntos de índices das

variáveis cujos fatores de lifting β

n,k

serão calculados são:

•

n=7

Ω

Considere a partição {

′

} de Γ

′

0, Θ

′

= Ω({7}) com n

= 7, Θ

′

= Ω({8})

com n

= 8,

′

= Ω({9}) com n

= 9,

′

= Ω({10}) com n

= 10,

′

= Ω({11}) com n

= 11, e

′

= Ω({12}) com n

= 12.

Considere também a partição {

′′

} dada por

′′

= {(7,3), (7,4), (7,5), (7,6), (8,3)},

′′

= {(9,2),

(9,3), (9,4)} com n

= 9,

′′

= {(7,2), (10,2), (10,3), (10,4), (10,5)} com n

= 10, Θ

′′

= {(8,2),

(11,2)} com n

= 11, e

′′

= {(12,2)} com n

= 12.

Os fatores de pseudo-lifting para os conjuntos

fatores para

(C), que variam de acordo com as partições {Θ

′

} e {Θ

′′

}. As posições da tabela mar-

cadas com uma estrela correspondem às instâncias cujos fatores de pseudo-lifting β

n,k

são diferentes

dos fatores exatos α

n,k

Podemos observar que os fatores de pseudo-lifting são bastante próximos dos fatores exatos, di-

vergindo apenas em alguns pontos. Note também que a escolha das partições {

} inﬂuencia nos

resultados obtidos.

4. Modelo linear por partes 62

4.5 Resultados computacionais

Foram realizados testes computacionais para avaliar o impacto da aplicação de cortes sobre o

poliedro P

cpl

(G) no desempenho do algoritmo de Branch and Bound. As curvas de performance

dos poços utilizadas são baseadas nas de Buitrago et al. [4], em que o campo em estudo possui 56

poços, com várias conﬁgurações de CPPs (uma CPP para cada poço), algumas com resposta imediata

(representando poços surgentes) enquanto outras com a necessidade de uma injeção mínima de gás

para iniciar a produção. A forma linear por partes destas curvas consiste em 20 regiões lineares para

cada poço n. Realizamos testes com instâncias de 32, 64 e 85 poços. Nas instâncias de 32 poços,

utilizamos as primeiras curvas de [4]. As instâncias de 64 e 85 poços possuem as 56 curvas de

Buitrago et al., e as restantes foram obtidas aplicando-se perturbações às primeiras.

Os grafos de restrição de precedência G = (V,E) foram gerados aleatoriamente, com densidades

que variam desde o caso irrestrito (E =

0) até grafos densos (|E| ≈ ⌊|V|

/2⌋), formando 13 densidades

de grafo para cada grupo de poços. A quantidade total de gás disponível q

max

também variou de pouco

gás de injeção até grande capacidade de compressão, formando 5 níveis de injeção para as instâncias

com 32 poços, 4 níveis para as de 64 poços e 5 níveis para as de 85 poços.

Foram realizados testes comparando o desempenho do algoritmo sobre as instâncias puras, com

as instâncias após a aplicação de cortes, que são apresentados em duas tabelas. As instâncias foram

resolvidas em uma estação rodando o sistema operacional GNU/Linux, com 1GB de RAM e 2GB de

espaço de disco para memória virtual, e equipado com um processador Intel Pentium IV de 3GHz.

Na Tabela 4.6 podemos avaliar o impacto da geração de cortes em cada uma das taxas de injeção

de gás, com a média dos resultados obtidos variando o tamanho do grafo de precedência. A Tabela

4.7 apresenta o impacto da geração de cortes de acordo com a densidade do grafo de restrições de

precedência, com a média obtida nas instâncias que diferem pela capacidade de compressão de gás

de injeção.

Os resultados apresentados nas colunas “Sem cortes” foram obtidos resolvendo as instâncias de

cpl

(G) correspondentes utilizando o programa ILOG CPLEX [31], que é tido como uma das fer-

ramentas mais poderosas para resolução de problemas de programação inteira-mista das existentes

no mercado. As tabelas apresentam o número de iterações realizadas, o número de nós gerados, e o

tempo em segundos para resolução do algoritmo de Branch and Bound.

Também foram aplicados cortes através de coberturas às instâncias, e em seguida foram subme-

tidas ao mesmo programa de resolução de problemas de programação inteira-mista. Os resultados

obtidos destas instâncias são apresentados nas colunas “Com cortes” das Tabelas 4.6 e 4.7. A fase

de geração de cortes resolve iterativamente a relaxação linear de cada instância, busca uma cobertura

cuja desigualdade obtida a partir do processo de pseudo-lifting corte a solução fracionária, e a adici-

ona ao conjunto de restrições. Este processo ﬁnaliza após produzir certo número de planos de corte,

ou atingir um número de tentativas mal sucedidas. Como o problema de separação é difícil, isto é, não

é fácil encontrar uma cobertura cuja desigualdade corte a solução fracionária, foi desenvolvida uma

heurística simples, porém rápida, que sistematicamente busca por coberturas mínimas, aplica o pro-

cesso de pseudo-lifting, e veriﬁca se a desigualdade resultante é um plano de corte. O procedimento

4. Modelo linear por partes 63

Sem cortes Com cortes Redução (%)

max

Iterações Nós CPU Iterações Nós CPU Iterações Nós CPU Relax.

N = 32

300 25063 12271 5.7 310 13 0.28 98.76 99.89 95.09 16.06

500

2590 1409 3.40 375 13 1.00 85.52 99.08 70.59 4.77

700

46389 24476 19.21 19190 9309 10.65 58.63 61.97 44.56 4.99

1100

67905 32907 28.55 45236 22207 22.94 33.38 32.52 19.65 2.38

1500

28672 10845 13.16 25001 10906 11.30 12.80 -0.56 14.13 1.30

Total 170619 81908 70.02 90112 42448 46.17 47.19 48.18 34.06 5.90

N = 64

700 1159402 553323 694.26 37293 8611 18.88 96.78 98.44 97.28 4.20

2300

7653030 3552912 6131.32 5981043 2708404 5079.69 21.85 23.77 17.15 1.23

2700

3464600 1552803 2698.16 3022232 1330704 2545.21 12.77 14.30 5.67 1.09

3500

377212 163308 304.78 259068 105303 220.64 31.32 35.52 27.61 0.86

Total 12654244 5822346 9828.52 9299636 4153022 7864.42 26.51 28.67 19.98 1.85

N = 85

730 13879 8207 28.80 2134 712 8.44 84.62 91.32 70.69 1.51

996

1565583 828402 1618.51 260601 81406 205.68 83.35 90.17 87.29 1.56

1261

17398974 8915702 19555.33 8074359 3183605 10381.58 53.59 64.29 46.91 3.35

2058

15704801 7406702 15340.51 5221739 1803605 4455.65 66.75 75.65 70.96 1.16

2324

3570 1019 24.25 3501 1017 16.15 1.93 0.20 33.40 0.46

4648

4591 1208 23.64 2828 438 11.28 38.40 63.74 52.28 0.46

Total 34691398 17161240 36591.04 13565162 5070783 15078.78 60.90 70.45 58.79 1.42

Total 47516261 23065494 46489.58 22954910 9266253 22989.37 51.69 59.83 50.55 3.03

Tabela 4.6: Impacto dos planos de corte por taxa de injeção de gás

de geração de cortes foi implementado em linguagem C++ [32], utilizando as bibliotecas ILOG [31]

para resolver as relaxações lineares e as estruturas de dados avançadas suportadas pelo pacote LEDA

[33].

A coluna “Redução” apresenta o impacto da aplicação dos cortes em relação às instâncias puras

no número de iterações e de nós do algoritmo de Branch and Bound. A coluna “Relax.” apresenta a

redução relativa no valor da relaxação linear devido à aplicação dos planos de corte.

Apresentamos a seguir uma visão geral da heurística debusca dos cortes. Inicialmente são compu-

tados os conjuntos A

e os parâmetros σ(n,m, j) que não dependem da cobertura. Seja

κ= max{κ(n) :

n ∈ N }. Este pré-processamento é executado em tempo O(N

κ), ou O(N

) dado que

κ ∈ O(N). Para

a busca de cada cobertura, os seguintes passos são executados:

1. Inicie com uma cobertura vazia, C =

0 e H(C) =

2. Escolha aleatoriamente pares de (n,k) ∈ Ω, para o qual x

n,k

= 0 no par (x,λ) e n ∈ N(C),

atualizando C, H(C), e γ(C), até que uma cobertura seja obtida ou sejam realizadas no máximo

escolhas aleatórias. Este passo é executado em tempo O(ε

N(logN +

κ)) = O(N

) para

= N

κ e

κ ∈ O(N).

3. Se o passo 2 falhar na busca de uma cobertura, então busque nos pares (n,k) ∈ Ω em ordem ar-

bitrária, não levando em conta o valor de x

n,k

, e execute as mesmas ações para gerar a cobertura

C. Este passo possui a mesma complexidade.

4. SeC não é uma cobertura, então aborte a heurística e notiﬁque a falha. Caso contrário, remova

os elementos de H(C) e C até que seja obtida uma cobertura mínima. Este passo é executado

em tempo O(N

4. Modelo linear por partes 64

Sem cortes Com cortes Redução (%)

|E(G)|

Iterações Nós CPU Iterações Nós CPU Iterações Nós CPU Relax.

N = 32

0 30495 20300 13.34 82 5 0.11 99.73 99.98 99.18 3.57

⌊N/8⌋

34755 18300 12.34 21280 10903 9.92 38.77 40.42 19.61 3.50

⌊N/4⌋

36700 19000 14.02 33911 18302 17.28 7.60 3.67 -23.25 3.21

⌊N/3⌋

23309 10200 7.33 4869 1904 1.96 79.11 81.33 73.26 3.31

⌊N/2⌋

10344 3601 3.72 8067 3802 3.65 22.01 -5.58 1.88 2.70

⌊2N/3⌋

17536 6101 5.36 10713 4202 5.06 38.91 31.13 5.60 3.13

13510 3926 6.15 8572 3102 4.53 36.55 20.99 26.34 2.37

1484 302 1.54 1148 203 1.3 22.64 32.78 15.58 3.14

799 70 0.95 316 5 0.78 60.45 92.86 17.89 3.26

576 69 0.99 320 5 0.48 44.44 92.75 51.52 3.99

396 27 1.08 320 5 0.48 19.19 81.48 55.56 6.74

⌊N

/3⌋

365 5 1.45 257 5 0.31 29.59 0 78.62 5.65

⌊N

/2⌋

350 7 1.75 257 5 0.31 26.57 28.57 82.29 10.18

Total 170619 81908 70.02 90112 42448 46.17 47.19 48.18 34.06 5.90

N = 64

0 2492947 1318200 1978.32 114 4 0.21 100.00 100.00 99.99 1.86

⌊N/8⌋

5067958 2577200 4297.35 4797594 2443601 4271.98 5.33 5.18 0.59 1.26

⌊N/4⌋

1673498 708800 1258.03 1528423 645101 1352.08 8.67 8.99 -7.48 1.27

⌊N/3⌋

1931502 793100 1394.37 1752252 707301 1354.86 9.28 10.82 2.83 1.34

⌊N/2⌋

569639 176100 338.66 485924 153501 344.51 14.70 12.83 -1.73 1.27

⌊2N/3⌋

427275 128900 233.11 271137 89001 226.08 36.54 30.95 3.02 1.29

418611 109800 254.93 414835 106400 265.90 0.90 3.10 -4.30 0.10

31470 5200 18.76 16532 3301 13.33 47.47 36.52 28.94 0.37

12886 1900 10.47 12590 1800 12.04 2.30 5.26 -15.00 1.30

25509 3001 19.50 17282 2901 17.42 32.25 3.33 10.67 0.84

1003 103 5.99 1713 103 4.05 -70.79 0.00 32.39 3.26

⌊N

/3⌋

1196 38 5.72 535 4 0.77 55.27 89.47 86.54 3.06

⌊N

/2⌋

750 4 13.31 705 4 1.19 6.00 0.00 91.06 6.74

Total 12654244 5822346 9828.52 9299636 4153022 7864.42 26.51 28.67 19.98 1.85

N = 85

0 7014551 4607700 9366.13 87 4 0.28 100.00 100.00 100.00 1.95

⌊N/8⌋

7159944 4125100 8660.61 87 4 0.28 100.00 100.00 100.00 1.15

⌊N/4⌋

6041502 3048500 6297.51 82 4 0.29 100.00 100.00 100.00 1.11

⌊N/3⌋

8740144 3816200 8235.11 7932336 3504502 10688.01 9.24 8.17 -29.79 0.51

⌊N/2⌋

2776802 823500 1920.01 2746963 828601 2062.87 1.07 -0.62 -7.44 0.16

⌊2N/3⌋

1420430 369300 976.18 1426351 363800 1084.78 -0.42 1.49 -11.12 0.08

1336313 343601 916.20 1300825 349701 1094.43 2.66 -1.78 -19.45 3.16

134951 19401 80.24 115668 17901 69.26 14.29 7.73 13.68 0.16

16013 1601 15.30 13983 1601 16.27 12.68 0.00 -6.34 0.31

24479 2401 18.88 10407 1501 13.74 57.49 37.48 27.22 0.23

16533 1701 17.07 10621 1701 16.73 35.76 0.00 1.99 0.91

⌊N

/3⌋

659 4 14.75 736 4 1.62 -11.68 0.00 89.02 4.64

⌊N

/2⌋

916 4 25.16 687 4 2.79 25.00 0.00 88.91 4.04

Total 34683237 17159013 36543.15 13558833 5069328 15051.35 60.91 70.46 58.81 1.42

Total 34691398 17161240 36591.04 13565162 5070783 15078.78 60.90 70.45 58.79 3.03

Tabela 4.7: Impacto dos planos de corte por densidade do grafo

4. Modelo linear por partes 65

5. Calcule todos os conjuntos H(C,n)

e H(C,n,k)

. Este passo executa em tempo O(N

6. Obtenha

Γ(C),

(C),

(C), que é executado em O(N

logN).

7. Obtenha os fatores de pseudo-lifting β

n,k

para todos (n,k) ∈

(C), que executa em

tempo O(N

8. Em no máximo ε

= N passos, sugira uma partição {

}

r=0

gualdade de pseudo-lifting que corte a solução:

(a) Seja U o conjunto de folhas de G que não está em N(C).

(b) Para cada n ∈ U, deﬁna o conjunto

= Ω({n}) com n

= n.

(d) Para cada n ∈ A, deﬁna o conjunto

= Ω({n}) com n

= n.

(e) Seja

= {(n,k) ∈ Ω : n ∈ B,k = 3,... ,κ(n)}.

(f) Para cada n ∈ B, adicione (n,2) a um conjunto aleatório

, r > 0, de maneira que n≺ n

(g) Compute os fatores de pseudo-lifting (n,k) ∈

}

r=0

(h) Se a desigualdade de pseudo-lifting corta a solução corrente, então pare a busca e retorne

o plano de corte.

Os passos 8-(a) à 8-(h) executam em tempo O(N

), portanto, este passo executa em O(N

9. Se o passo 8 não encontrou um plano de corte, notiﬁque a falha da heurística.

Dos passos acima concluímos que a heurística de separação é executada em tempo O(N

). Esta

análise considera o pior caso, sendo que uma análise mais apurada pode levar a resultados melhores.

Uma análise mais otimista pode assumir

κ ∈ O(1).

Da Tabela 4.6 podemos inferir que a aplicação de planos de corte promove uma diminuição subs-

tancial do esforço computacional para resolução do problema em termos do número de iterações e nós

de Branch and Bound. Reduções maiores são observadas em circunstâncias em que a disponibilidade

de gás de injeção é limitada.

A Tabela 4.7 apresenta a inﬂuência da densidade do grafo e seus ganhos com a aplicação de pla-

nos de corte. Os resultados indicam que o problema se torna mais difícil à medida que a densidade do

grafo diminui. Ainda podemos observar que os ganhos absolutos da aplicação de planos de corte di-

minuem com o aumento da densidade do grafo, enquanto os ganhos relativos aumentam nos extremos

(devido às restrições de precedência e cenários altamente restritivos).

Os resultados computacionais mostram que a geração de planos de corte pode participar do pro-

cesso de resolução do problema. Entretanto, para um aproveitamento completo da teoria, a geração de

planos de cortes deveria ocorrer em todos os nós da árvore de soluções, resultando em um algoritmo

de Branch and Cut; e não apenas no poliedro completo, como foi implementado. Conforme a busca

avança nos ramos da árvore de soluções, as variáveis discretas são deﬁnidas como 0 ou 1, tornando o

grafo de precedência esparso e permitindo que os cortes locais reduzam a distância primal-dual.

4. Modelo linear por partes 66

4.6 Sumário

Neste capítulo vimos uma formulação do problema de alocação ótima de gás de injeção sob

restrições de capacidade máxima e de precedência utilizando linearização por partes e programação

matemática inteira-mista. Observamos que esta formulação é reduzida a um problema da mochila sob

restrições de precedência, assim, pudemos expandir a teoria de coberturas para buscar desigualdades

válidas fortes para a formulação. Projetamos as desigualdades para todas as variáveis de decisão,

com os fatores de lifting, e propusemos uma maneira alternativa, computacionalmente mais leve,

para o cômputo de valores aproximados dos fatores de lifting, que chamamos de pseudo-lifting. Por

ﬁm, apresentamos resultados computacionais comparativos que comprovam a eﬁcácia da inserção de

planos de corte no problema.

Capítulo 5

Interface de otimização

Como parte deste trabalho implementamos uma interface de usuário para resolução de problemas

de alocação ótima de gás de injeção. Desenvolvemos uma ferramenta de auxílio à tomada de decisão

para operação de campos de petróleo operados por gas-lift.

Os algoritmos de otimização são de natureza não similar e com interface algumas vezes complexa.

Buscamos criar um ambiente que abstraia os modelos de otimização, para que o operador se preocupe

apenas com as informações referentes ao campo de petróleo, de maneira que a visualização dos dados

seja o mais próximo da realidade. Assim, ﬁca a cargo do sistema a interpretação dos dados e a

montagem e resolução das instâncias, retirando do usuário a necessidade de compreender o modelo.

Esta propriedade do sistema permite que para um mesmo cenário possam ser aplicados diferentes

algoritmos de otimização.

Utilizamos uma estrutura cliente/servidor para resolução dos algoritmos. Procuramos desenvolver

uma interface geral, que não seja aplicável apenas ao problema de interesse. A interface do cliente

permite especiﬁcar problemas de alocação ótima de gás de injeção e possui ﬂexibilidade para que

sejam incluídas restrições diferentes das tratadas em nosso trabalho como, por exemplo, restrições da

tubulação, topologia da tubulação, perda de cargas, acoplamento de poços e dinâmica do processo.

O servidor para algoritmos de otimização por sua vez, permite que qualquer algoritmo de otimização

seja utilizado, não apenas os que tratam de problema de determinação de pontos de operação para

campos de petróleo.

A estrutura cliente/servidor foi empregada para permitir que seja utilizada uma máquina diferente

para a caracterização do problema da máquina em que a otimização será executada. A resolução

de problemas de otimização, em geral, necessita de muito esforço e recursos computacionais para

instâncias médias e grandes, exigindo um computador potente. Assim, destinamos a uma máquina

adequada, o servidor, a resolução destes problemas; enquanto as máquinas em que as instâncias

do problema são geradas podem ter recursos restritos. Outro fator considerado é que algumas das

ferramentas utilizadas para a resolução dos problemas de otimização são proprietárias [31], então

esta estrutura requer apenas uma licensa de uso das ferramentas no servidor.

5. Interface de otimização 68

Figura 5.1: Ambiente de especiﬁcação do problema

5.1 Ambiente de especiﬁcação do problema

A interface de otimização possui um módulo de especiﬁcação do problema em que o usuário

descreve cada um dos elementos que compõem um campo de petróleo. Este módulo foi estruturado

de maneira bottom-up, para permitir que o sistema seja facilmente expandido, possibilitando que

novas características sejam acrescentadas ao sistema de acordo com o surgimento das necessidades.

A linguagem escolhida para implementação deste sistema foi a Java [34], devido principalmente

a sua portabilidade entre sistemas operacionais e facilidade de implementação de ambientes gráﬁcos.

Na Figura 5.1 podemos visualizar o ambiente desenvolvido e seus componentes. Este ambiente está

dividido em painéis, cada um responsável pela edição de um elemento ou característica do campo de

petróleo:

Editor gráﬁco: este painel permite que o usuário formule um diagrama esquemático dos compo-

nentes do campo (poços, compressores, separadores e manifolds

) e suas conexões através das

tubulações, facilitando a visualização e navegação entre os elementos. Na Figura 5.2 temos

um exemplo de um diagrama representativo de um campo de petróleo, seus componentes e

tubulações.

Preços: nesta guia o usuário informa ao sistema os preços de mercado do óleo e gás produzidos,

assim como o custo de processamento da água extraída. Estes valores são necessários pois,

nossos algoritmos de otimização utilizam um critério econômico na função objetivo, buscando

o maior lucro da operação do campo.

Elementos de conexão de tubulação.

5. Interface de otimização 69

Figura 5.2: Editor gráﬁco

Grafo de precedência: este painel permite que o usuário informe ao sistema as arestas que com-

põem o grafo de restrições de precedência de ativação. Os vértices do grafo são os próprios

poços. Uma aresta signiﬁca que um poço só será ativado se seu predecessor estiver operando,

pelo menos, em seu nível mínimo de produção. O grafo de precedência não possui relação

com o grafo criado no editor gráﬁco, então um poço pode preceder outro mesmo que eles não

estejam conectados.

Compressor: um campo de petróleo operado por gas-lift possui pelo menos um compressor para

produzir o gás de injeção, podendo ter várias unidades formando um banco de compressores.

Cada compressor possui uma capacidade máxima de compressão, que é somada com a capa-

cidade total do banco. Possui também um custo de compressão associado. Uma característica

comum dos compressores, separadores e poços é um nome que identiﬁca o componente no

campo, e a possibilidade de desabilitá-lo. Um compressor desabilitado pode representar, por

exemplo, que ele está desligado para manutenção, que gera a necessidade do recômputo das

taxas de injeção de cada poço, pois a capacidade total de injeção é uma restrição signiﬁcativa.

Separador: este painel permite que o usuário informe ao sistema o limite de separação do petróleo

produzido em óleo, gás e água, assim como as capacidades máximas de tratamento de cada um

dos sub-produtos da extração. Estes limites são tratados como restrições por Camponogara e

Nakashima [35], e foram incluídos para tornar o programa compatível com esta formulação.

Poço: nesta guia o usuário pode descrever cada um dos poços do campo operados por gas-lift.

Para cada poço o usuário pode inserir várias CPPs, utilizando uma descrição linear por partes,

polinomial, polinomial-logarítmica (polilog) ou exponencial (veja Seção 2.3). São permitidas

múltiplas curvas, pois podemos utilizar tipos diferentes de expressões para representar a mesma

CPP. Também é possível que o operador não tenha certeza da curva que melhor descreve o poço,

5. Interface de otimização 70

∗

WellField

ComponentCompressor

Separator

Well

Manifold

Pipe

PrecedenceGraph

PrecedenceEdge

AbstractWpc

ExponentialWpc

PolynomialWpc

PolylogWpc

PiecewiseLinearWpc

PwlPoint

Figura 5.3: Diagrama de classes da estrutura de dados da interface

e deixa para o algoritmo a escolha da curva baseada em algum critério como, por exemplo, o

pior caso ou caso médio [9]. Associado a cada CPP também temos as frações médias de óleo,

gás e água presentes no petróleo produzido pelo poço.

Outra capacidade do sistema é a de transformar curvas de um tipo para outro. Curvas descritas

como lineares por partes podem ser convertidas em polinomiais ou polilogs em um processo

de ajuste por mínimos quadrados. O ajuste de curva pode ser irrestrito ou com garantia que a

curva seja côncava em seu intervalo de interesse. A garantia de concavidade é uma exigência

de alguns algoritmos de otimização que utilizam programação dinâmica [9].

5.1.1 Estrutura de dados

O sistema foi estruturado internamente em um conjunto de classes que descrevem o campo de

petróleo. A Figura 5.3 mostra um diagrama de classes UML

[36, 37] que representa as principais

classes desta estrutura. Nele apresentamos apenas os nomes das classes, omitindo seus atributos e

métodos. A classe base

WellField

representa o campo como um todo, e é passada para todos os

objetos que a utilizam ou manipulam. A classe

PrecedenceGraph

representa o grafo de restrições de

precedência. Ela possui uma lista de arestas (

PrecedenceEdge

) e seus vértices são os próprios poços

do campo.

A classe abstrata

Component

representa todos os elementos que compõem ﬁsicamente o campo.

Dela herdam os compressores (

Compressor

), separadores (

Separator

), poços de petróleo (

Well

tubos (

Pipes

) e conexões de tubos (

Manifold

). A ampliação dos tipos de elementos do campo

pode ser feita herdando novas classes de

Component

. A estrutura do campo possui uma lista para

cada classe ﬁlha de

Component

. Elas estão ordenadas com base em um atributo identiﬁcador de

WPC - Well Performance Curve, Curva de Performance do Poço.

UML - Uniﬁed Modeling Language, linguagem de modelagem que utiliza diagramas padronizados.

5. Interface de otimização 71

Component

, assim a busca de um elemento na lista, método mais utilizado na implementação, pode

ser feita como uma busca binária, que executa em tempo Θ(log

n)[38]. Esta política de manter a

lista ordenada, em contrapartida, penaliza outros métodos, como a inserção de novos elementos que

é executada em Θ(n).

Cada poço pode ter várias CPPs. A base para estas curvas é a classe abstrata

AbstractWpc

. Desta

classe herdam as especializações da curva, cada uma para sua expressão matemática equivalente: ex-

ponencial (

ExponentialWpc

), polinomial (

PolynomialWpc

), polinomial-logarítmica (

PolylogWpc

)

e linear por partes (

PiecewiseLinearWpc

), que por sua vez possui um conjunto de pontos

PwlPoint

Caso se deseje que o sistema trabalhe com alguma outra formulação para a CPP basta herdar uma nova

classe de

AbstractWpc

e desenvolver a interface com o usuário para a curva.

5.1.2 Ajuste de curvas

O sistema possui a capacidade de transformar curvas entre as formulações aceitas no sistema.

Especiﬁcamente, foram implementadas transformações da curva linear por partes para as curvas po-

linomiais de terceira ordem e polilog. Estas transformações são feitas por um método de ajuste de

curvas por mínimos quadrados, que tenta aproximar a curva ao máximo dos pontos que formam a

curva linear por partes. Algoritmos como o de programação dinâmica apresentado em [9] exigem que

as curvas de entrada no sistema sejam côncavas, por isso o sistema possui a capacidade de garantir a

concavidade da curva no ajuste.

Outra transformação possível é uma discretização de qualquer uma das outras curvas em linear

por partes. Entretanto, este processo considera apenas que a distribuição dos pontos seja feita em

intervalos constantes, não levando em conta a correlação da curva proposta.

A seguir apresentaremos a base matemática utilizada para os ajustes para curvas polinomias e

polilog.

Polinomial

Considerando a equação polinomial de terceira ordem

) = q

out

= c

+ c

(5.1)

e um conjunto de k pontos Q= {(q

out

),...,(q

out

)}. Se substituirmos cada ponto de Q em (5.1),

chegamos a um sistema linear com 4 incógnitas e k equações, que pode ser escrito matricialmente







1 (q

) (q

)

1 (q

) (q

)

1 (q

) (q

)

























out







5. Interface de otimização 72

Como k ≫ 4 neste sistema linear Ax = b, minimizamos o resíduo  Ax− b  para obter uma solução

que melhor se ajuste aos pontos, ou seja:

Minimize

 Ax− b 

(5.2)

Para resolver (5.2) desenvolvemos a função objetivo

 Ax− b  =

(Ax− b)

− b

)(Ax− b)

Ax− x

b− b

Ax+ b

Ax− b

Ax+

b. (5.3)

Como

b é constante, pode ser removido da função objetivo sem que seja alterado o valor das

variáveis de decisão na solução do problema. Minimizar a expressão (5.3) consiste em um problema

de Programação Quadrática. Note que x

Ax = Ax 

 0, ∀x, ou seja, a matriz A

A é positiva

semi-deﬁnida. Se o posto de A é completo, rank(A) = 4, então A

A é inversível e a solução para (5.2)

pode ser obtida com x = (A

−1

Desejamos poder impor que o polinômio p

) seja côncavo em todo o intervalo [q

]. Para

isto sua segunda derivada deve ser negativa em todo o intervalo contínuo,

′′

) = 6c

+ 2c

 0,∀q

∈ [q

Isto implica em um número inﬁnito de restrições para cobrir todo o intervalo. Este número de restri-

ções pode ser reduzido segundo a seguinte proposicão:

Proposição 5.1 Se p

) for côncava em q

e q

, então p

) é côncava para todo q

∈ [q

Prova: Como p

′′

) é um polinômio de primeira ordem (c

= 0), ele possui no máximo uma raiz

no intervalo [q

]. Se p

′′

)  0, q

∈ {q

}, segundo o Teorema de Bolzano [39], existe um

número par de raízes para p

′′

) em [q

]. Então p

′′

) não possui raízes em [q

], ou seja,

não ocorre alteração na concavidade de p

) no intervalo em questão. Como p

) é côncava em

e q

, então p

) é côncava ∀q

∈ [q

]. 

Esta proposição restringe para dois o número de restrições, que são lineares. Isto faz com que

seja possível utilizar um algoritmo de Programação Quadrática com Restrições para ajustar a curva

polinomial aos pontos com garantia de concavidade.

5. Interface de otimização 73

Polinomial-logarítmica

Considere agora a equação polinomial-logarítmica

) = q

out

= c

+ c

ln(1+ q

) (5.4)

e o conjunto de k pontos Q = {(q

out

),...,(q

out

)}. De maneira análoga à seção anterior subs-

tituímos cada ponto de Q em (5.4) e obtemos o sistema linear representado matricialmente







1 (q

) (q

)

ln(1+ q

)

1 (q

) (q

)

ln(1+ q

)

1 (q

) (q

)

ln(1+ q

)

























out







Com o mesmo raciocínio que foi visto anteriormente, podemos obter a curva que melhor se ajuste

a Q sem garantia de que a curva seja côncava.

Para que p

) seja côncava em [q

] sua derivada segunda deve ser negativa no intervalo,

′′

) = 2c

− c

(1+ q

)

< 0,∀q

∈ [q

]

Proposição 5.2 Se p

) for côncava em q

e q

, então p

) é côncava para todo q

∈ [q

Prova: Se p

′′

) < 0 e c

> 0, conforme q

decresce a partir de q

, p

′′

) se torna mais negativa,

garantindo que p

) seja côncava para todo q

 q

. Caso c

< 0, p

′′

) decresce conforme q

cresce, então é necessário que p

′′

) < 0. Como c

pode assumir qualquer sinal, é necessário que

nos dois casos a concavidade seja veriﬁcada. 

Assim, é necessário apenas impor garantia de concavidade nos limites do conjunto para que a

função seja côncava em todo o intervalo.

Na ﬁgura 5.4 apresentamos a guia utilizada para caracterizar um poço de petróleo, na aba de CPP

(WPC). No lado esquerdo o usuário informa separadamente as características de cada uma das curvas.

No caso, está sendo editada a curva número 1, que é uma curva linear por partes com pontos de acordo

com os da tabela. No topo à direita estão as frações de óleo, gás e água produzidas pelo poço. Abaixo

está um gráﬁco que mostra as curvas (algumas ou todas) do poço. A curva descontínua desenhada

representa a linear por partes que está sendo editada. A curva de melhor correlação (mais próxima) à

descontínua foi gerada a partir do ajuste da primeira em uma expressão polinomial-logarítmica com

garantia de concavidade, resultando na expressão:

out

= −5,5069· 10

− 9,3484· 10

−1

· q

+ 3,7372· 10

−5

· q

+ 1,2951· 10

· ln(1+ q

5. Interface de otimização 74

Figura 5.4: Guia de caracterização de poço com exemplo de ajuste de curva

A terceira curva é uma polinomial de terceira ordem, que também foi gerada com garantia de conca-

vidade:

out

= 5,5866· 10

+ 2,7233· q

− 9,4509· 10

−4

· q

+ 8,439· 10

−8

· q

5.1.3 Padrão dos arquivos

É desejável no sistema que o usuário possa gravar e recuperar os dados referentes ao campo

de petróleo que está sendo estudado, para que o processo de caracterização do campo e invocação

dos algoritmos de otimização possa ser interrompido e recuperado a qualquer momento. Como um

requisito do nosso sistema é a capacidade de expansão, buscamos uma estrutura aberta e facilmente

manipulável. Para isto, utilizamos a linguagem XML

[40], que procura padronizar a representação

de dados. Este padrão é bastante abrangente, sendo que foi utilizado apenas uma pequena parte de

suas funcionalidades.

Na Figura 5.5 apresentamos um exemplo da estrutura do arquivo para um campo de petróleo. Nela

podemos observar os preços do óleo e gás, e o custo do tratamento da água extraída. Observamos

também que o campo possui um poço (Well), um compressor (Compressor) e um tubo (Pipe). O poço,

por sua vez, é descrito por duas CPPs: uma linear por partes, com quatro pontos, e outra polinomial-

logarítmica, ajustada a partir da primeira. O compressor possui sua capacidade máxima de injeção de

gás e seu custo de operação. Tanto no poço como no compressor, existe uma informação de posição,

que é utilizada no editor esquemático do campo. O tubo liga o poço “1” ao compressor “1”, e possui

uma quina. Para os atributos que não estão descritos no arquivo são assumidos valores padrão, como

por exemplo, o “Habilitado”, que assume que o poço e o compressor estão em operação.

XML - eXtensible Markup Language, linguagem de marcação extensível. É uma recomendação para gerar linguagens

de marcação cujo propósito principal é facilitar o compartilhamento de informações através da Internet.

5. Interface de otimização 75

<?xml version="1.0"encoding="UTF-8"?>

<Well>

<Function Type="PieceWise"

</Function>

<Function Type="Polylog"

</Function>

</Well>

</Compressor>

<Pipe>

</Pipe>

</WellField>

Figura 5.5: Exemplo do formato de gravação dos dados

5. Interface de otimização 76

5.2 Servidor de otimização

O servidor é a implementação que permite que algoritmos de otimização possam ser executados

remotamente. A máquina que hospeda o servidor pode possuir programas especíﬁcos de otimização,

assim não é necessário que estes programas sejam instalados na máquina do usuário.

Em nossa aplicação utilizamos ferramentas proprietárias para resolução de nossos algoritmos.

Fica a cargo do servidor disponibilizar o uso destas ferramentas para todos os usuários do sistema.

Outro aspecto é o sistema operacional necessário para a execução das ferramentas. Como desejáva-

mos um ambiente de especiﬁcação de problema livre desta restrição, precisamos criar uma interface

genérica para os algoritmos. Desejávamos também que esta funcionalidade não estivesse disponível

apenas para algoritmos de otimização de taxas de injeção de gás, mas que pudesse resolver outros

problemas de otimização.

Para deixar a interface do servidor o mais genérica possível, optamos por utilizar uma estrutura

baseada em arquivos. O usuário envia um, ou vários, arquivos para o servidor contendo a instância

do problema e mais algum arquivo que possa necessitar, como por exemplo, o modelo caso não esteja

junto com a instância. Envia também um arquivo com um ou mais comandos, que indica ao servidor

quais devem ser as ações tomadas com os arquivos de instância. O servidor, por sua vez, grava todas

as mensagens de resposta recebidas da execução das instâncias do problema em um arquivo de saída

e outro de erros, que é enviado ao usuário. Caso o usuário deseje direcionar passos intermediários

para arquivos auxiliares, também é possível, podendo consultá-los posteriormente. Uma desvantagem

desta estrutura é que não permite que o usuário monitore a resolução de seu problema enquanto ela é

executada; apenas permite que veja a resposta após a resolução ter sido concluída.

Um grande desaﬁo enfrentado foi que o computador que possui os recursos para executar os

algoritmos de otimização estava localizado dentro de uma rede segura. Desejávamos que este servidor

pudesse ser acessado a partir de qualquer computador, ou seja, que também pudesse ser acessado a

partir de computadores localizados fora da rede segura. A conexão direta entre estas duas máquinas

não é permitida, pois abre um caminho para falhas na segurança da rede.

Para resolver este problema foram desenvolvidos dois programas. O primeiro é o gerenciador das

instâncias, responsável por receber, gerenciar eexecutar as instâncias, e enviar e permitir consultas das

soluções obtidas. Este programa está instalado e executa no computador com recursos para resolver

os problemas de otimização. O segundo programa é uma interface do servidor, e ﬁca alojado na

máquina que conecta a rede segura ao meio externo. Ele é responsável por receber as instâncias,

veriﬁcar se elas são seguras (não são arquivos maliciosos, com intenção de “atacar” a rede interna), e

encaminhar ao servidor; assim como pesquisar as respostas e apresentar para o usuário.

A seguir, apresentamos detalhadamente cada um dos programas que formam o sistema.

5. Interface de otimização 77

5.2.1 Gerenciador de instâncias

O gerenciador de instâncias é o núcleo do servidor de otimização. Desenvolvido em linguagem

C++ [32, 41] para o sistema operacional Linux, osistema foi estruturado utilizando programação con-

corrente [42], que permite que várias ações sejam executadas simultaneamente (na realidade, ocorre

um pseudo-paralelismo entre os processos [43]). No computador em que está sendo executado, o ge-

renciador roda em segundo plano (background), ﬁcando totalmente transparente para algum usuário

que eventualmente esteja utilizando aquela máquina.

Os processos que compõem o gerenciador são:

Gerenciador de conexões: Este processo é responsável por receber e despachar novas conexões de

rede executadas no servidor. Quando um usuário deseja conectar-se com o servidor, ele realiza

uma solicitação em uma porta TCP-IP [44] especíﬁca do servidor. Este processo, por sua vez,

ﬁca travado, aguardando esta solicitação. Quando ela ocorre, o processo avalia se a conexão

pode ser estabelecida (limitando o número máximo de conexões), e caso positivo dispara um

novo processo que faz a comunicação com o usuário.

Conexões: Cada conexão estabelecida com o servidor gera um novo processo desta classe. Este

processo recebe comandos do usuário e responde de maneira apropriada, por exemplo, a carga

de uma nova instância ou obtenção de uma resposta.

Monitor de processador: Quando existe uma nova instância para ser executada, o sistema neces-

sita saber se a máquina está disponível para executá-la. Algoritmos de otimização são CPU

bounded, isto é, necessitam do processador intensamente. Adotamos então como métrica para

saber se é possível executar o algoritmo um histórico (de aproximadamente um minuto) de ocu-

pação do processador. Se o processador estiver sendo pouco utilizado (no caso menos de 50%

em todos os pontos do histórico), o sistema está apto para disparar processos de otimização.

Este processo tem como função veriﬁcar ciclicamente (em intervalos de aproximadamente 20

segundos) a ocupação do processador e montar um histórico de uso, assim como permitir ou

bloquear que novas instâncias sejam iniciadas.

Gerenciador deexecução: Quando o processo de conexões recebe uma nova instância e manda que

seja executada, ela é colocada em uma ﬁla. Este processo é responsável por veriﬁcar se existem

elementos nesta ﬁla e, quando for permitido, executar os comandos da instância. Enquanto

se busca a solução de uma instância, este processo também é responsável por veriﬁcar quanto

tempo de processador o problema utilizou, o limitando de acordo com os direitos do usuário,

evitando assim que problemas muito grandes sejam resolvidos por usuários com pouco direito

de acesso. Finalizada a execução da instância, este gerenciador é responsável por enviar a

resposta ao usuário.

Gerenciador de instâncias antigas: Este processo é executado em intervalos de tempo bastante

longos. Sua função é monitorar há quanto tempo cada instância está armazenada no servi-

dor, e descartá-la se este período for maior que um certo limite. Isto faz com que instâncias

5. Interface de otimização 78

muito antigas, e potencialmente não mais necessárias ao usuário, sejam eliminadas do servidor,

liberando espaço de armazenamento.

O protocolo de conexão com o servidor foi feito inspirado nos protocolos SMTP [45] e POP [46].

A troca de dados é feita utilizando caracteres ASCII

, que torna a comunicação bastante simples.

Comandos são enviados ao servidor em um formato texto, interpretados e as respostas geradas são

enviadas. Podemos dividi-los em três grupos: identiﬁcação, que permite que o usuário se apresente

ao servidor através de uma identiﬁcação (comando

) e uma senha (comando

PSW

). Caso o usuário

não se identiﬁque, o servidor vai admitir que a conexão é anônima, e seus direitos (como por exemplo

o tempo de processador para rodar sua instância) serão restritos.

Um segundo grupo de comandos permite que o usuário informe ao servidor o problema a ser

resolvido. Os comandos

FILE

CMD

permitem que o usuário envie arquivos contendo a instância e

os comandos que serão executados, respectivamente. Para solicitar que o servidor execute a instância

enviada utiliza-se os comandos

RUN

RUNMAIL

, sendo que o último envia a resposta por e-mail para

o usuário.

O último grupo de comandos é utilizado para veriﬁcar a resposta da execução de um problema.

Eles são apresentados no exemplo da Figura 5.6, em que é estabelecida uma conexão com o servidor

e solicitada esta resposta. As sentenças grifadas são os comandos enviados pelo usuário, e as sem

grifo são as respostas obtidas. Na primeira linha é solicitada uma conexão com o servidor, que

está hospedado no mesmo computador em que o teste foi realizado, na porta 1209. A conexão é

estabelecida e na linha 2 o servidor envia uma mensagem de boas vindas. Em seguida o usuário

informa que deseja trabalhar com a instância número 18, e solicita que o sistema informe o seu

estado. O servidor responde (na linha 6) que já executou a instância. Outras respostas poderiam ser

que está na ﬁla aguardando (Queue) ou que está sendo executada naquele momento (Running). Por

ﬁm, o usuário solicita a resposta gerada, que está no arquivo

out.txt

5.2.2 Interface

Para abstrair os comandos do gerenciador de conexões, e permitir que este seja acessado de fora

da rede segura, foi desenvolvida uma interface amigável para o servidor. Esta interface é acessada

como uma página de Internet

e ﬁca hospedada no computador que faz a conexão da rede segura

com o meio externo. Esta parte do código do servidor foi escrita em linguagem PHP [47], que é uma

linguagem que permite gerar páginas dinâmicas. Quando a página é solicitada ao servidor de páginas,

o código escrito em PHP é executado e uma página é gerada especiﬁcamente para aquela conexão.

Isto permite que quando o usuário solicitar uma página de respostas, por exemplo, o servidor de

páginas se conecta com o gerenciador de instâncias, consulta as informações necessárias e gera a

página de acordo com a resposta do gerenciador.

ASCII - American Standard Code for Information Interchange, código padronizado americano para troca de informa-

ções. Conjunto de códigos criado em 1961 para o computador representar números, letras, pontuação e outros caracteres.

No momento da escrita desta dissertação esta interface pode ser acessada pelo endereço

http://www.das.ufsc.br/otimizacao

5. Interface de otimização 79

1 deconto@deconto:

∼

telnet localhost 1209

2 100 hello. welcome to das-ufsc optimization server

SETINST 18

4 100 working with instance 18

GETSTATUS

6 101 6 FINISHED

GETFILE out.txt

8 100 sending file

9 ANP/PRH34 Gas-lift Optimization

10 MILP answer

11 ---------------------

12 Optimum profit: 30787.4

13 Oil Well Injection Rate

14 1 - Oil Well 80

15 2 - Oil Well 154

16 3 - Oil Well 0

17 4 - Oil Well 0

18 .

19 100 end of file

QUIT

21 100 bye

Figura 5.6: Exemplo de conexão com o gerenciador de instâncias

A interface possui dois grupos de código bastante semelhantes. O primeiro possui um ambiente

amigável para ser acessado pelo usuário, e permite que este escolha quais arquivos serão carregados,

e veriﬁque o estado de execução e a resposta de sua instância. No segundo as funcionalidades são

as mesmas do primeiro, mas o ambiente não permite interação com o usuário (como botões e links).

Foi gerado para que outros programas utilizem os recursos do servidor (no caso, o Ambiente de

Especiﬁcação de Problema), uma vez que a comunicação do programa com o servidor é feita de

maneira mais direta, com chamadas http [48, 49].

Na Figura 5.7 apresentamos o ambiente para utilizar o servidor de otimização a partir de uma

página de Internet. No topo podemos observar as três funcionalidades disponíveis: Submit data

permite que o usuário submeta uma nova instância para ser executada no servidor; Get Status é

utilizado para veriﬁcar o estado de uma instância submetida, podendo ser Aguardando, Executando

ou Concluído; a opção Get Answer retorna para o usuário a resposta obtida da execução de uma dada

instância. Abaixo estão os campos para submeter uma nova instância: E-mail é o endereço eletrônico

do usuário, caso ele deseje que a resposta lhe seja enviada por este meio; Commands é o arquivo

que contém os comandos que o servidor deve utilizar; e Data File n são os campos destinados aos

arquivos de instância que o usuário deseja submeter.

5.3 Estudo de caso

Nesta seção apresentaremos como utilizar a interface de otimização para obter as taxas de injeção

ótimas em uma instância pequena. Para problemas em escala maior o procedimento é exatamente o

mesmo.

Considere um campo de petróleo com quatro poços operando por gas-lift. Este campo possui um

banco com três compressores e toda a produção é enviada para um separador. Na interface é possível

5. Interface de otimização 80

Figura 5.7: Interface para o usuário do servidor de otimização

n,1

out

) (q

n,2

out

) (q

n,3

out

) γ

1 ( 80, 960) (200, 1044) (267, 1060) 0,70 0,20 0,10

( 80, 998) (133, 1140) (200, 1412) 0,75 0,17 0,08

( 80, 1108) (133, 1132) (267, 1652) 0,65 0,25 0,10

( 80, 1090) (133, 1200) (267, 1500) 0,66 0,24 0,10

Tabela 5.1: Descrição dos campos de petróleo para o estudo de caso

abrir um editor esquemático do campo, e montar um diagrama como o apresentado na Figura 5.2

arrastando os componentes para dentro do painel de edição. Este diagrama não é necessário para que

os problemas sejam instanciados, mas em casos de tamanho médio e grande ele pode ajudar o usuário

organizando as informações do campo.

Em seguida devemos caracterizar o campo. Como nossos algoritmos são baseados em um critério

econômico, é necessário que sejam informados os preços do óleo e gás produzido, assim como o

custo de tratamento da água extraída. Em nosso exemplo assumimos $ 20,00 e $ 2,00 para os preços

do óleo e gás produzidos, e $ 1,00 para o custo de tratamento da água. Descrevemos cada poço n com

uma CPP contendo três pontos cada. A Tabela 5.1 apresenta os pontos da curva de cada poço, assim

como suas proporções de óleo, gás e água (γ

, γ

e γ

) produzidas.

No banco de compressores consideramos que a capacidade de cada compressor é 60, 60 e 80

unidades de gás comprimido, resultando em 200 unidades de capacidade total de injeção, a um custo

comum de $ 5,00. Como o algoritmo de otimização que utilizaremos não considera restrições no

separador, ele não foi caracterizado. Admitimos também que não existe restrição de precedência em

nossa instância, mas um grafo de precedência pode ser facilmente introduzido.

5. Interface de otimização 81

Figura 5.8: Apresentação da solução de um problema

A caracterização do campo não precisa ser feita nesta seqüência. O sistema dá total liberdade

para o usuário, de maneira que ele insira as informações conforme elas lhe forem disponibilizadas.

Também é possível fazer a qualquer momento alterações na estrutura do campo, como adicionar

novos poços ou os excluir.

Montado o campo é possível fazer chamadas ao algoritmo de otimização para que as melhores

taxas de injeção de gás sejam calculadas. A primeira etapa consiste em escolher qual algoritmo será

utilizado. Em seguida é aberto um diálogo com o usuário para que este conﬁgure detalhes da execução

do algoritmo. No caso do modelo apresentado nesta dissertação, é possível conﬁgurar se deseja-se

ou não que as restrições de precedência sejam consideradas. O passo seguinte é executar um pré-

processamento dos dados do campo. Nesta etapa são veriﬁcadas inconsistências na instância, como

por exemplo, um poço não caracterizado por sua CPP, ou um compressor habilitado com capacidade

de compressão nula. Se o sistema gerar mensagens de alerta como as exempliﬁcadas, o usuário ainda

pode continuar o processo, mas mensagens de erro como incoerência nas frações de produção, exigem

correções do usuário.

Por ﬁm os dados são submetidos ao servidor. É possível escolher se a resposta deve ser enviada

para a caixa de correio eletrônico do usuário, ou apenas poderá ser consultada pelo sistema. Então é

aberto um diálogo com o usuário informando a solução ótima para sua instância (Figura 5.8).

5.4 Sumário

Neste capítulo apresentamos a ferramenta desenvolvida para o cômputo das taxas ótimas de inje-

ção de gás em um campo operando por gas-lift. Adotamos uma estrutura cliente-servidor que permite

5. Interface de otimização 82

que o usuário caracterize localmente o problema, e que seja resolvido em uma máquina especíﬁca

para este ﬁm. O ambiente de especiﬁcação do problema permite que o usuário desenhe um esquema

do campo de petróleo que está tratando, e descreva cada um de seus componentes, permitindo inclu-

sive adicionar características que possam ser utilizadas em outros algoritmos de otimização. Permite

também que a partir do próprio ambiente, solicite que o servidor obtenha as taxas ótimas de gás de

injeção.

O servidor foi desenvolvido em duas partes: um gerenciador de instâncias, que efetivamente

realiza as chamadas dos algoritmos de otimização; e uma interface que permite que o gerenciador

seja acessado de maneira segura e amigável. Por ﬁm, apresentamos um estudo de caso, em que

mostramos passo a passo como utilizar o sistema para obter uma resposta ótima para um campo de

petróleo simulado.

Capítulo 6

Conclusões e trabalhos futuros

A atual competição no mercado do petróleo e os altos custos envolvidos tornam qualquer ganho

relativo no lucro de extração de hidrocarbonetos signiﬁcativos. Neste contexto, a obtenção de taxas

ótimas de injeção de gás no processo de elevação por gas-lift, que permitam maximizar o lucro da

extração assume um papel de destaque nestes campos de produção. Apresentamos uma formulação

para este problema baseada em programação linear inteira mista com restrições de quantidade máxima

de gás de injeção e precedência de ativação de poços. Também foi implementada uma ferramenta para

especiﬁcação e resolução destes problemas.

A programação linear inteira mista é uma ferramenta poderosa que permite o cômputo de soluções

ótimas globais com variáveis de decisão inteiras em problemas que a função objetivo é linear. Para

o problema da mochila as coberturas permitem buscar facetas para o poliedro de restrições. Se adi-

cionarmos restrições de precedência, temos as K-coberturas que permitem gerar desigualdades fortes

para o poliedro. Caso a função objetivo não seja linear, é possível linearizá-la por partes adicionando

variáveis binárias de decisão. O modelo proposto por Sherali [28] se mostrou muito melhor que os

outros devido a sua simplicidade e características poliedrais.

A formulação do problema de alocação ótima de gás de injeção utilizando programação linear

inteira mista apresenta uma série de vantagens: generaliza os modelos existentes tratando explici-

tamente as decisões de ativação e desativação dos poços de petróleo; permite a aplicação intensiva

da teoria e ferramentas algorítmicas do domínio da programação inteira, que permitem a obtenção

de ótimos globais e uma medida da qualidade de soluções aproximadas; o modelo pode ser facil-

mente expandido para comportar outras restrições. Esta classe de problemas é NP-Difícil no sentido

forte, então é importante a inserção de cortes para agilizar o processo de busca, principalmente em

instâncias de grande porte.

Apresentamos uma formulação para obter desigualdades válidas para um subconjunto das variá-

veis de decisão do problema, e um procedimento de lifting para expandir estas desigualdades para

todo o espaço das variáveis de decisão. Este procedimento de lifting envolve a resolução de uma

seqüência de problemas, tão difíceis quanto resolver o próprio problema de alocação de gás. Então

apresentamos um procedimento para o cômputo de fatores aproximados de lifting. Experimentos

6. Conclusões e trabalhos futuros 84

computacionais mostraram que estas desigualdades de coberturas podem reduzir o número de itera-

ções e o tamanho da árvore de Branch and Bound.

Criamos uma ferramenta para especiﬁcação e resolução de problemas de alocação de gás de in-

jeção. Sua estrutura faz com que o cômputo das taxas de injeção seja realizada em um computador

especíﬁco, com capacidade de processamento suﬁciente para resolver o problema. O emprego desta

ferramenta permite que o operador do campo utilize a formulação desenvolvida sem necessariamente

conhecer detalhes do modelo e do algoritmo de resolução. Em um estudo de caso mostramos que são

tratadas apenas características que descrevem a operação do campo, sendo que detalhes do funciona-

mento do algoritmo são abstraídos do usuário.

Como sugestão para trabalhos futuros propomos que no algoritmo de Branch and Bound para

resolução do problema sejam gerados cortes em cada nó da árvore de busca, que pode agilizar o

processo de resolução, e sejam feitos estudos comparativos. No Apêndice B apresentamos uma for-

mulação para o problema que leva em consideração a concavidade da curva de performance do poço.

Propomos que esta formulação seja explorada, inicialmente fazendo um comparativo dos ganhos na

diminuição do esforço computacional desta formulação, por reduzir o número de variáveis de deci-

são, com a formulação P

(G). Em seguida, podem ser expandidos os conceitos de K-coberturas e

lifting para esta formulação.

Na interface de otimização, propomos que seja estudada uma forma mais direta de conexão do

ambiente de especiﬁcação do problema com o servidor, que permita o acompanhamento do cálculo da

solução. Também propomos uma ampliação do modelo para outros tipos de restrições, como perdas

de cargas na tubulação, interferência entre poços e acompanhamento da dinâmica do reservatório.

Apêndice A

Fatores de lifting exatos para uma

ﬂoresta

Nesta seção apresentamos um algoritmo em programação dinâmica para o cômputo dos fatores

exatos de lifting caso o grafo de restrições de precedência de ativação seja uma ﬂoresta. Tomemos

como referência a formulação K

′

apresentada em (4.10), da Seção 4.3.

As simpliﬁcações sobre (4.10e) podem ser programadas sequencialmente por (4.10e)–(4.10e)

para reescrever o problema como:

′′

: ε

= δ

+ Maximize

∑

n∈A

∑

(n,k)∈B

t,n

n,k

(A.1a)

Sujeito a

∑

n∈A

∑

(n,k)∈B

t,n

n,k

 b (A.1b)

∑

(m,i)∈B

t,m

m,i



∑

(n, j)∈B

t,n

n, j

, ∀(m,n) ∈ E(

) (A.1c)

∑

(n,k)∈B

t,n

n,k

 1,∀n ∈ r(

) (A.1d)

n,k

∈ {0,1}, ∀(n,k) ∈ ∪

n∈A

t,n

(A.1e)

para os conjuntos A

⊆ N

, B

t,n

⊆ S

t,n

= G[A

]; e o escalar δ

. Podemos assumir sem perda de

generalidade que b e b

n,k

são inteiros. Existe uma solução recursiva para K

′′

é uma ﬂoresta. Seja

T = {n

,. ..,n

} uma ordenação topológica de

. Para simpliﬁcar a notação, tomemos B

= B

t,n

A. Fatores de lifting exatos para uma ﬂoresta 86

e seja R

os ﬁlhos de n em

, isto é, R

= {m : (n,m) ∈ E(

)}. A recursão é:

(n,q) :

(n,q) = Maximize

∑

(n,k)∈B

n,k

+ J

,q− ˆq) (A.2a)

Sujeito a

∑

(n,k)∈B

n,k

= y (A.2b)

∑

(n,k)∈B

n,k

 ˆq (A.2c)

ˆq ∈ {0,. .. ,q} (A.2d)

n,k

∈ {0,1}, ∀(n,k) ∈ B

(A.2e)

(R,q) :

(R,q) = Maximize J

ˆy

(n, ˆq) + J

(R\{n},q− ˆq) (A.3a)

Sujeito a ˆy ∈ {0} ∪ {y} (A.3b)

ˆq ∈ {0,1,.. . ,q} (A.3c)

n ≺ ˆn, ∀ ˆn ∈ R\{n} de acordo com T (A.3d)

onde a interpretação dos problemas está a seguir.

(n,q) é a forma restrita de K

′′

, para um t particular, incluindo o poço n e seus sucessores em

, isto é, S

= {m ∈ V(

) : n ≺ m}, e tendo uma capacidade de compressão de gás de q unidades.

Ainda, o poço n está ativado se y = 1 e desativado se y = 0. J

(n,q) é o valor da função objetivo de

uma solução ótima para P

(n,q). Note que P

(n,q) é sempre factível se y = 0. Se y = 1 e q unidades

são insuﬁcientes para ativar o poço n, então P

(n,q) é infactível e J

(n,q) = −∞. Note também que

os sucessores de n, S

, podem ser ativados apenas se o poço n estiver ativo.

(R,q) é a forma restrita de K

′′

, para um t particular, considerando apenas as árvores com

raízes nos elementos de R ⊆ V(

) onde (S

∪ {m}) ∩ (S

∪ {n}) =

0 para todos m,n ∈ R distintos,

e possuindo apenas q unidades de capacidade de compressão. Ainda, cada poço n ∈ R deve estar

inativo se y = 0, mas os poços podem estar ativos ou inativos se y = 1. J

(R,q) é o valor de uma

solução ótima para P

(R,q). Note que P

(R,q) é sempre factível independente dos valores de y e q,

garantindo que J

(R,q)  0.

As recorrências (A.2a)–(A.2e) e (A.3a)–(A.3d) levam o problema à equivalência K

′′

≡ P

(r(

),b)

e, portanto, ε

= δ

+ J

(r(

),b). Um algoritmo em programação dinâmica pode ser desenvolvido

a partir de uma execução seqüencial destas recorrências. A seguir, apresentamos uma visão geral do

algoritmo.

Seja J

(n) = {J

(n,q) : q = 0,.. . , b} um conjunto de soluções para P

(n,q) variando q, em que

J (n) = J

(n) ∪ J

(n) é o conjunto de todas as soluções. Seja J

(R) = {J

(R,q) : q = 0,... ,b} o

conjunto de soluções para P

(R,q) variando q e y ∈ {0,1}, onde R ⊆ R

para algum n ∈ V(

) ou

R ⊆ r(

). Ainda, seja J (R) = J

(R) ∪ J

(R) o conjunto de todas as soluções.

A. Fatores de lifting exatos para uma ﬂoresta 87

O algoritmo consiste em varrer os nós de

em ordem reversa de T , isto é, das folhas da

ﬂoresta até as raízes, computando J (n) em cada nó n, sobre J (R

n,i

) para i = j, j − 1,... ,1, onde

n,i

= {r

,. ..,r

} e R

= {r

,. ..,r

} é o conjunto de ﬁlhos de n obtidos de acordo com a ordem

topológica T . Pode ser mostrado que este algoritmo é executado em tempo Θ(4|V|q

) e utiliza

Θ(4|V|q) unidades de memória para armazenar as tabelas.

Apêndice B

Modelo linear por partes considerando

concavidade

Propomos aqui um modelo linear por partes para o problema de alocação ótima de gás de injeção

que considera a concavidade das curvas. Segundo Sherali [28], se um conjunto de pontos formar uma

região côncava, é necessário apenas uma variável de decisão binária por região.

Esta formulação aproveita o fato que a curva de performance do poço (CPP) ou é côncava, ou

pode ser dividida em regiões côncavas. Esta formulação não reduz a complexidade computacional da

resolução do problema. Entretanto, há uma redução no número de variáveis de decisão inteiras, que

pode levar a um número menor de nós no algoritmo de Branch and Bound ou de planos de corte, e

por conseqüência em uma redução nos custos computacionais para obtenção da resposta.

Para formulação deste modelo utilizamos as deﬁnições apresentadas no Capítulo 4.

Deﬁnição B.1 Para um poço n, um conjunto T

= {k : q

n,k

∈ Q

} = {t

,. .. ,t

} de índices consecu-

tivos de pontos representam uma região côncava se para todos os índices a, b e c ∈ T

, a < b < c,

valer:

n,b

out

 (

n,c

− q

n,b

n,c

− q

n,a

out

+ (

n,b

− q

n,a

n,c

− q

n,a

n,c

out

(B.1)

Uma região côncava é máxima se T

∪{t

−1} e T

∪{t

+1} não representam uma região côncava.

Dividimos K

= {1,. .. ,κ(n)}, que é o conjunto dos índices de Q

, em µ(n) conjuntos T

que

representam regiões côncavas, tal que:

• ∪

µ(n)

m=1

= K

;

• |T

|  2, m = 1,... ,µ(n);

• t

m−1,θ

= t

m,1

, m = 2,. ..,µ(n).

B. Modelo linear por partes considerando concavidade 89

Se os conjuntos T

, m = 1,. .. ,µ(n), representarem regiões côncavas máximas, a representação é

ótima no número de variáveis de decisão.

con

(G) : Maximize f =

∑

n=1

µ(n)

∑

m=1

∑

k∈T

n,k

m,k

(B.2a)

Sujeito a:

∑

n=1

 q

max

(B.2b)

µ(i)

∑

m=1



µ( j)

∑

m=1

∀( j,i) ∈ E(G) (B.2c)

µ(n)

∑

k=1

 1 ∀n ∈ R(G) (B.2d)

µ(n)

∑

m=1

∑

k∈T

n,k

m,k

n = 1,...,N (B.2e)

∑

k∈T

m,k

= x

∀(n,m) ∈ Ξ (B.2f)

m,k

 0

∀(n,m) ∈ Ξ

∀k ∈ T

(B.2g)

 0 ∀(n,m) ∈ Ξ (B.2h)

∈ Z ∀(n,m) ∈ Ξ (B.2i)

onde Ξ = {(n,m) : n = 1,. .. ,N e m = 1,...,µ(n)}.

Se cada conjunto de pontos T

possuir cardinalidade |T

| = 2, então P

con

(G) pode ser reduzido a

(G). Isto é, se cada conjunto T

possui dois pontos consecutivos que representam uma região de

(G), então P

con

(G) é equivalente a P

(G).

B.1 Exemplo ilustrativo

Considere que para um dado poço n a CPP possui a conﬁguração apresentada na Figura B.1.

Observe que os pontos (1,1), (2,3) e (3,2) formam uma região côncava máxima, e que os pontos

(3,2), (4,3), (5,3) e (6,2) formam outra região. Assim, assumimos µ(n) = 2 regiões côncavas, e

temos que T

= {1,2,3} e T

= {3,4,5,6}. Note que T

∪ T

= {1,2,3,4,5,6} = K

Utilizando esta formulação temos 8 variáveis de decisão reais (λ e q

) e 2 variáveis inteiras

para representar este poço n. Se aplicarmos esta curva no modelo P

(G) teremos 11 variáveis de

decisão reais e 5 inteiras. Podemos observar uma redução signiﬁcativa nas variáveis de decisão,

principalmente nas inteiras, que levam a uma redução dos custos computacionais para resolução do

problema.

Se ﬁzermos T

= {1,2}, T

= {2,3}, T

= {3,4}, T

= {4,5} e T

= {5,6}, serão necessárias

11 variáveis reais e 5 inteiras, que corresponde à formulação P

(G) original.

B. Modelo linear por partes considerando concavidade 90

3 4 5 6

1,1

1,2

1,3

2,3

2,4

2,5

2,6

out

Figura B.1: Exemplo de CPP considerando concavidade nas variáveis de decisão.

Referências Bibliográﬁcas

[1] MCKIE,C. et al. Economic beneﬁts from automated optimization of high pressure gas usage in an

oil productin system. In: SPE Production and Operation Symposium. Oklahoma City, Oklahoma:

[s.n.], 2001. Paper SPE 67187.

[2] THOMAS, J. Fundamentos de Engenharia de Petróleo. [S.l.]: Editora Interciência Ltda, 2001.

[3] JAHN, F.; COOK, M.; GRAHAM, M. Hydrocarbon exploration and production. [S.l.]: Elsevier

Science, 2003.

[4] BUITRAGO, S.; RODRÍGUEZ, E.; ESPIN, S. D. Global optimization techniques in gas allo-

cation for continuous ﬂow gas lift systems. In: Proc. SPE Gas Technology Conference. Calgary,

Canada: [s.n.], 1996. p. 375–379. Paper SPE 15616.

[5] ECONOMIDES, M.; HILL, A.; EHLIG-ECONOMIDES, C. Petroleum Production Systems.

[S.l.]: Prentice Hall, 1993.

[6] KANU, E. P.; MACH., J. M.; BROWN, K. E. Economic approach to oil production and gas

allocation in continuous gas lift. Journal of Petroleum Technology, p. 1887–1892, Outubro 1981.

[7] MACH, J.; PROANO, E.; BROWN, K. E. A nodal approach for applying systems analysis to the

ﬂowing and artiﬁcial lift of oil or gas well. In: Society of Petroleum Engineers. [S.l.: s.n.], 1979.

Paper SPE 8025.

[8] ALARCÓN, G.; TORRES, C.; GÓMEZ, L. Global optimization of gas allocation to a group of

wells in artiﬁcial lift using nonlinear constrained programming. ASME Journal of Energy Resour-

ces Technology, v. 124, p. 262–268, Dezembro 2002.

[9] NAKASHIMA, P.; CAMPONOGARA, E. Solving a gas-lift optimization problem by dynamic

programming. IEEE Transactions on Systems, Man, and Cybernetics—Part A, v. 36, n. 2, p. 407–

414, 2006.

[10] GAREY, M.; JOHNSON, P. A Guide to Theory or NP-Completeness. New York, NY: W.H. Fre-

eman, 1979.

[11] MAYHILL, T. D. Simpliﬁed method for gas-lift well problem identiﬁcation and diagnosis. In:

Proc. SPE Annual Fall Meeting. Houston, Texas: [s.n.], 1974. Paper SPE 5151.

Referências Bibliográﬁcas 92

[12] REDDEN, J. D.; SHERMAN, T. A. G.; BLANN, J. R. Optimizing gas-lift systems. In: Proc.

of the 49th Annual Fall Meeting of the Society of Petroleum Engineers of AIME. Houston, Texas:

[s.n.], 1974. Paper SPE 5150.

[13] NISHIKIORI, N. et al. An improved method for gas lift allocation optimization. In: Proc. SPE

Annual Technical Conference and Exhibition. San Antonio, TX: [s.n.], 1989. Paper SPE 19711.

[14] NISHIKIORI, N. et al. An improved method for gas lift allocation optimization. ASME Journal

of Energy Resources Technology, v. 117, p. 87–92, 1995.

[15] FANG, W. Y.; LO, K. K. A generalized well-management scheme for reservoir simulation. SPE

Reservoir Engineering, v. 11, n. 2, p. 116–120, May 1996.

[16] WANG, P.; LITVAK, M.; AZIZ, K. Optimization of production operations in petroleum ﬁelds.

In: Proc. 17th World Petroleum Congress. Rio de Janeiro, Brazil: [s.n.], 2002.

[17] CAMPONOGARA, E.; NAKASHIMA, P. H. R. Applying dynamic programming to a gas-lift

optimization problem. In: Proc. 2nd Brazilian Congress on Research and Development in Oil and

Gas. Rio de Janeiro, Brazil: [s.n.], 2003.

[18] WILLIAMS, H. Model Building in Mathematical Programming. 4. ed. New York, NY: John

Wiley & Sons, 1999.

[19] NAKASHIMA, P. Otimização de Processos de Produção de Petróleo via Injeção Contínua de

Gás. Tese (Doutorado) — Universidade Federal de Santa Catarina, Florianópolis, Maio 2004.

[20] VANDERBEI, R. J. Linear Programming: Foundations and Extensions. Boston: Kluwer Aca-

demic Publishers, 1996. Disponível em: <citeseer.ist.psu.edu/vanderbei96linear.html>.

[21] WOLSEY, L. Integer Programming. New York, NY: Wiley-Interscience, 1998. (Wiley-

Interscience series in discrete mathematics and optimization).

[22] NEMHAUSER, G. L.; WOLSEY, L. A. Integer and Combinatorial Optimization. [S.l.]: John

Wiley & Sons„ 1988.

[23] WRIGHT, S. Primal-Dual Interior-Point Methods. Philadelphia, PA: Soc for Industrial & Ap-

plied Math, 1997.

[24] BALAS, E.; ZEMEL, E. Facets of the knapsack polytope from minimal covers. SIAM Journal

on Applied Mathematics, v. 34, n. 1, p. 119–148, 1978.

[25] KAPARIS, K.; LETCHFORD, A. A cut-and-branch algorithm for the multidimensional knap-

sack problem. Lancaster University. nov 2005.

[26] BOYD, E. Polyhedral results for the precedence-constrained knalsack problem. Discrete Applied

Mathematics, v. 41, p. 185–201, 1993.

[27] PADBERG, M. Approximating separable nonlinear functions via mixed zero-one programs.

Operations Research Letters, v. 27, p. 1–5, 2000.

Referências Bibliográﬁcas 93

[28] SHERALI, H. On mixed-integer zero-one representations for separable lower-semicontinuous

piecewise-linear functions. Operations Research Letters, v. 28, p. 155–160, 2001.

[29] CONTO, A. de; CAMPONOGARA, E. Alocação Ótima de lift-gas: Modelos de linearização

por partes. In: 3o

Congresso Brasileiro de P&D em Petróleo e Gás. Salvador, BA: [s.n.], 2005.

[30] CAMPONOGARA, E.; CONTO, A. de. Gas-lift allocation under precedence constraints:

Piecewise-linear formulation and k-covers. In: Proc. of the 44th IEEE Conference on Decision

and Control, and the European Control Conference 2005. Sevilha, Espanha: [s.n.], 2005. p. 4422–

4427.

[31] ILOG INCORPORATED. ILOG CPLEX 9.0: Getting Started. Mountain View, CA, 2003.

[32] STROUSTRUP, B. The C++ Programming Language. 3. ed. Reading: Addison-Wesley, 1997.

[33] MEHLHORN, K.; NAHER, S. LEDA: A Platform for Combinatorial and Geometric Compu-

ting. [S.l.]: Cambridge University Press, 1999.

[34] DEITEL, H.; DEITEL, P. Java How to Program. 6. ed. Upper Saddle River, NJ: Prentice-Hall,

2004.

[35] CAMPONOGARA,E.; NAKASHIMA, P. Optimal allocation of lift-gas rates under multiple fa-

cility constraints: A mixed-integer linear programming approach. A ser publicado no Transactions

of ASME, 2007.

[36] MARTIN, R. UML Tutorial: Part 1 - Class Diagram. [S.l.]. Disponível em:

<www.objectmentor.com/publications/umlClassDiagrams.pdf>.

[37] FOWLER, M.; KOBRYN, C.; BOOCH, G. UML Essencial. 3. ed. Porto Alegre: Bookman,

2005.

[38] CORMEN, T. et al. Introduction to Algorithms. 2. ed. [S.l.]: MIT Press, 2001.

[39] LEITHOLD, L. O Cálculo com Geometria Analítica. 3. ed. São Paulo: Harbra, 1993.

[40] DEITEL, A.; DEITEL, P.; NIETO, R. XML: Como Programar. 1. ed. Porto Alegre: Bookman,

2003.

[41] MITCHELL, M.; OLDHAM, J.; SAMUEL, A. Advanced Linux Programming. 1. ed. Indiana-

polis, Indiana: New Riders, 2001.

[42] OLIVEIRA, R.; CARISSIMI, A.; TOSCANI, S. Sistemas Operacionais. 3. ed. Porto Alegre:

Editora Sagra-Luzzato, 2004.

[43] TANENBAUM, A. Sistemas Operacionais Modernos. 2. ed. Upper Saddle River, NJ: Prentice-

Hall, 2003.

[44] CASAD, J.; WILLSEY, B. Aprenda TCP/IP em 24 horas. 5. ed. São Paulo: Campus, 1999.

[45] POSTEL, J. RFC 821 - Simple Mail Transfer Protocol. University of Southern California, 1982.

Disponível em: <http://www.ietf.org/rfc/rfc0821.txt>.

Referências Bibliográﬁcas 94

[46] MYERS, J.; ROSE, M. RFC 1725 - Post Ofﬁce Protocol - Version 3. Carnegie-Mellon Univer-

sity, 1994. Disponível em: <http://www.ietf.org/rfc/rfc1725.txt>.

[47] SOARES, W. Programando em PHP: Conceitos e Aplicações. São Paulo: Érica, 2000.

[48] HAROLD, E. Java Network Programming. 3. ed. Cambridge, Massachusetts: O’Reilly Media,

2004.

[49] FIELDING, R. et al. RFC 2616 - Hypertext Transfer Protocol - HTTP/1.1. The Internet Society,

1999. Disponível em: <http://www.ietf.org/rfc/rfc2616.txt>.

Livros Grátis
( http://www.livrosgratis.com.br )
 
Milhares de Livros para Download:
 
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas

Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
 
 