Algoritmos de Optimizacao para Planeamento Florestal

Amandio de Jesus Cordeiro Almada

Dissertacao para obtencao do Grau de Mestre em

Engenharia Informatica e de Computadores

Orientadores: Prof. Vasco Miguel Gomes Nunes Manquinho

Prof.ª Maria Ines Camarate de Campos Lynce de Faria

Juri

Presidente: Prof. Luıs Manuel Antunes Veiga

Orientador: Prof. Vasco Miguel Gomes Nunes Manquinho

Vogal: Prof. Luıs Manuel Silveira Russo

Abril 2018

Resumo

O desenvolvimento industrial e um dos maiores factores que contribuem para destruicao do habitat

da vida selvagem existente nas florestas, principalmente quando se faz recurso das florestas para

aquisicao de materia prima. Todas as alteracoes a floresta, como por exemplo a colheita de madeira

ou a construcao, devem seguir um plano de boas praticas para garantir a consistencia da floresta.

A destruicao da vida selvagem e seu habitat pode ser minimizada com a criacao de uma reserva

florestal conectada. Quando se elabora agendamento de colheitas, e recomendavel reservar lotes

para construcao de uma reserva para as especies locais.

Este trabalho propos uma formulacao que combina o problema de agendamento de colheitas e a

criacao de reservas conectadas e compactas para a proteccao das especies. Foi desenvolvida uma

formulacao multi-objectivo que combinou o modelo URM de Murray [Murray, 1999] para o agenda-

mento de colheitas e um modelo para reservas conectadas e compactas denominado de RCC-nR. A

formulacao multi-objectivo apresentou-se com dois modelos: o modelo CRC caracterizado por deixar

lotes livres na floresta e o modelo CRC-T que reaproveita esses lotes para adicionar qualidade no

habitat das especies. Para ambos, o numero de variaveis e linear no numero de lotes e verifica-se

que calculam a fronteira de Pareto, onde o modelo CRC-T apresenta um numero inferior de solucoes.

Adicionalmente foi desenvolvido solucoes singulares tanto para colheita como para as reservas.

Palavras Chave

Programacao Linear Inteira; Satisfacao Modulo Teorias; Algoritmos de Optimizacao; Planeamento Flo-

restal; Proteccao de Especies; Agendamento de Colheitas.

i

Abstract

Industrial development is one of the major factors contributing to wildlife habitat destruction in forests,

especially due to resource exploration. The process of harvesting wood, construction or any alteration

that changes the forest should follow a plan of good practices in order to ensure its consistency. The des-

truction of wildlife and its habitat can be minimized with the creation of a connected forest reserve. When

scheduling a harvest it is advisable to take into account the arrangement of stands for the construction

of a reserve for local species.

This work proposes a formulation that combines both harvest scheduling and the creation of con-

nected and compacted reserves for the protection of species. The development of this multi-objective

formulation combines, the URM of Murray [Murray, 1999] for the harvest scheduling and a model for con-

nected and compacted reserves known as RCC-nR. The multi-objective formulation is presented with

two models: the model CRC characterized by leaving free stands in the forest and the model CRC-T

which utilize these stands to add quality to the species habitat. In both cases, the number of variables

is linear for the number of stands and it is possible to verify that they calculate the Pareto front in which

the CRC-T model presents a lower number of solutions. In addition, single-objective formulations were

developed for both the harvest and the reserves.

Keywords

Satisfiability Modulo Theories; Integer Linear Programming; Forest Planning Model; Optimization Algo-

rithm; Harvest Scheduling.

iii

Conteudo

1 Introducao 1

1.1 Objectivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2 Contribuicoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.4 Organizacao da Dissertacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 Conceitos Fundamentais e Trabalhos Relacionados 7

2.1 Conceitos Fundamentais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.1.1 Plano Florestal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.1.2 Programacao Linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.1.3 Satisfacao Modulo Teoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.1.3.A Combinacao dos Objectivos . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.2 Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.2.1 Agendamento de Colheitas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.2.2 Proteccao de Especies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2.3 Conectividade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.2.4 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3 Desenvolvimento das Formulacoes 23

3.1 Formulacao para Reservas Compactas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.1.1 Solucao 1: Modelo RCC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.1.2 Solucao 2: Modelo RCC-nR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.2 Formulacao para Agendamento de Colheitas . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.2.1 Modelo ARM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.2.2 Modelo URM Estocastico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.3 Formulacao Multi-Objectivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.4 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

v

4 Avaliacao dos Resultados 37

4.1 Componentes de Implementacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.1.1 Ferramentas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.1.2 Dados e Requisitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

4.2 Avaliacao dos Resultados para Reservas Compactas . . . . . . . . . . . . . . . . . . . . 42

4.2.1 Modelo RCC vs Modelo RCC-nR . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4.2.2 Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

4.3 Avaliacao dos Resultados para Agendamento de Colheita . . . . . . . . . . . . . . . . . . 46

4.3.1 Modelo GMU vs Modelo URM-S . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.3.2 Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.4 Avaliacao dos Resultados para Formulacao Multi-Objectivo . . . . . . . . . . . . . . . . . 49

4.5 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5 Conclusao 55

5.1 Trabalho Futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

vi

Lista de Figuras

2.1 Exemplo de floresta dividida em 104 lotes. . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2 Solucoes optimas dos exemplos apresentados de Programacao Linear, da expressao

em Ingles Linear Programming (LP) com conjuntos Inteiros. Os pontos sao as solucoes

encontradas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.3 Satisfacao Modulo Teorias, da expressao em Ingles Satisfiability Modulo Theories (SMT),

uma extensao de Problema de Satisfacao Booleana, da expressao em Ingles Boolean

Satisfiability Problem (SAT) que adiciona teorias. . . . . . . . . . . . . . . . . . . . . . . . 13

2.4 Exemplo de colheita para Modelo de Restricao por Unidade, da expressao em Ingles Unit

Restriction Model (URM) e Modelo de Restricao por Area, da expressao em Ingles Area

Restriction Model (ARM), assumindo que a area maxima contıgua de 32 hectares. . . . . 15

2.5 Exemplo de floresta com tres lotes, A, B e C [McDill et al., 2002]. . . . . . . . . . . . . . 16

2.6 Exemplo de reserva conectada e desconectada [Onal and Briers, 2006]. . . . . . . . . . . 17

2.7 Exemplo de uma reserva na forma longa e estreita, as partes de cor preta representa a

reserva [Carvajal et al., 2013]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.1 Reserva nao compacta com lotes ilha, zona escura e a reserva. . . . . . . . . . . . . . . 26

3.2 Reserva compacta, lote nao reservado inacessıvel. A zona escura representa a reserva. 27

3.3 Reserva compacta e conectada, zona nao reservada e acessıvel. A zona escura repre-

senta a reserva. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.4 Agendamento de colheitas, modelo URM com tres perıodos. cada cor representa um

perıodo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.5 Avaliacao paisagıstica da solucao URM-Estocastico (URM-S) e Unidade de Gestao Ge-

neralizada, da expressao em Ingles Generalized Management Unit (GMU), ambas em 30

minutos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.6 Colheita em tres perıodos e criacao de reserva. A cor verde simboliza a reserva, a branca

a zona livre e as restantes cores os perıodos colhidos. . . . . . . . . . . . . . . . . . . . . 35

vii

4.1 Diagrama do processo de preparacao das instancias. . . . . . . . . . . . . . . . . . . . . 40

4.2 Reservas Conectadas e Compactas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4.3 Tempo de execucao para reservas conectadas e compacta, Reserva Conectada e Com-

pacta (RCC) vs Reserva e Nao-Reserva Conectadas e Compactas (RCC-nR). O eixo

vertical representa o tempo em segundos e o eixo horizontal representa o percentual da

qualidade mınima da reserva por calcular. . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.4 Tempo e qualidade para reservas conectadas e compacta, RCC vs RCC-nR. . . . . . . . 44

4.5 Em 4 horas de execucao, RCC nao obteve uma solucao satisfeita para as instancias

Hardwicke e Shulkell. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

4.6 Lucro adquirido com a colheita, A solucao optima de GMU e representado pela cor ver-

melha e URM-S pela cor azul. Para cada instancia, variou-se os limites inferior e superior

do volume de madeira. Os limites variam em percentagem do total da floresta. URM-S,

em 10% de volume, esteve a 0, 01% de distancia para o valor optimo (o que nao e per-

ceptıvel e da a impressao que tem o mesmo lucro). . . . . . . . . . . . . . . . . . . . . . 46

4.7 Lucro adquirido com a colheita, GMU e representado pela cor vermelha e URM-S pela cor

azul. Para cada instancia, variou-se os limites inferior e superior do volume de madeira.

Os limites variam em percentagem relativamente ao total da floresta. . . . . . . . . . . . 47

4.8 Agendamento de colheita, GMU nao consegue calcular solucao em 30 minutos. GMU vs

URM-S. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.9 Solucao URM-S em 2 horas, 25% de volume de madeira e tres perıodos de colheita para

instancia El Dorado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4.10 Solucao multi-objectivo, instancia FLG 1 e 3 perıodos. 50% de qualidade mınima para

reserva e 25% de volume de madeira para colheita. A cor verde representa a reserva e a

branca significa lotes livres, as restantes cores ilustram a colheita em diferentes perıodos. 49

4.11 Instancia FLG 1, tempo de execucao para o calculo da primeira solucao na fronteira de

Pareto. Linha vermelha identifica Colheita e Reserva Compacta (CRC) e a linha azul

identifica Colheita e Reserva Compacta Total (CRC-T). As variacoes da instancia foi feita

com a alternancia do volume de madeira e a qualidade da reserva (e.g. v50.q10 significa

50% de volume de madeira como limite e 10% de qualidade mınima da reserva). . . . . . 50

4.12 Instancia FLG 2, tempo de execucao para o calculo da primeira solucao na fronteira de

Pareto. Linha vermelha identifica CRC e a linha azul identifica CRC-T. Verifica-se que

CRC nao resolve para uma instancia quando se limita o tempo para 8 horas. . . . . . . . 50

viii

4.13 Fronteira de Pareto para o modelo CRC, instancia FLG 1 e 3 perıodos. 50% de quali-

dade mınima para reserva e 25% de volume de madeira para colheita. O eixo vertical

representa a maximizacao da funcao objectivo do agendamento de colheitas e o eixo

horizontal representa a minimizacao da funcao objectivo da reserva compacta. . . . . . . 51

4.14 Fronteira de Pareto para o modelo CRC-T, instancia FLG 1 e 3 perıodos. 50% de qua-

lidade mınima para reserva e 25% de volume de madeira para colheita. O eixo vertical

representa a maximizacao da funcao objectivo do agendamento de colheitas e o eixo

horizontal representa a minimizacao da funcao objectivo da reserva compacta. . . . . . . 52

4.15 Total de solucoes na fronteira de Pareto. A cor vermelha simboliza o modelo CRC-T e

a azul o modelo CRC. Instancia FLG 1 com variacoes no volume de madeira e quali-

dade da reserva (e.g. v75.q10 significa 75% de volume de madeira como limite e 10% de

qualidade mınima da reserva). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

ix

x

Lista de Tabelas

2.1 Caracterizacao dos trabalhos relacionados. . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.1 Caracterısticas das instancias. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.2 Estrutura da instancia obtida em Lotes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.3 Estrutura da instancia obtida em Colheita. . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

xi

xii

Lista de Algoritmos

3.1 Metodo recursivo Gi com os parametros Ci, Ni e αi . . . . . . . . . . . . . . . . . . . . . . 31

3.2 Estrategia para gerar paisagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

xiii

xiv

Acronimos

ARM Modelo de Restricao por Area, da expressao em Ingles Area Restriction Model

BnB Ramificacao e Limitacao, da expressao em Ingles Branch-and-Bound

CRC Colheita e Reserva Compacta

CRC-T Colheita e Reserva Compacta Total

FLG Gerador de Paisagem Florestal, da expressao em Ingles Forest Landscape Generator

FMOS Forest Management Optimization Site (2017)

GMU Unidade de Gestao Generalizada, da expressao em Ingles Generalized Management Unit

GIA Guided Improvement Algorithm

IDE Ambiente de Desenvolvimento Integrado, da expressao em Ingles Integrated Development

Environment

ILP Programacao Linear Inteira, da expressao em Ingles Integer Linear Programming

LP Programacao Linear, da expressao em Ingles Linear Programming

MILP Programacao Linear Inteira Mista, da expressao em Ingles Mixed-Integer Linear

Programming

SAT Problema de Satisfacao Booleana, da expressao em Ingles Boolean Satisfiability Problem

SMT Satisfacao Modulo Teorias, da expressao em Ingles Satisfiability Modulo Theories

TS Theory Solver

URM Modelo de Restricao por Unidade, da expressao em Ingles Unit Restriction Model

URM-S URM-Estocastico

RCC-nR Reserva e Nao-Reserva Conectadas e Compactas

xv

RCC Reserva Conectada e Compacta

xvi

1Introducao

Conteudo

1.1 Objectivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2 Contribuicoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.4 Organizacao da Dissertacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1

2

Desde os tempos remotos que a evolucao do homem e combinada com a destruicao do habitat e

vida selvagem. O desenvolvimento industrial tem provocado a excessiva exploracao das florestas em

busca de materia prima. A criacao de novas vias de comunicacao que atravessam a floresta, o desvio

dos rios e outros factores tem vindo a destruir o habitat das vidas selvagens e a reduzir a capacidade

da natural proliferacao. No entanto, para minimizar a destruicao do habitat, para qualquer uma das

actividades com impacto negativo nas florestas, devem elaborar planos que preveem a proteccao das

especies.

De modo a proteger algumas especies e o seu habitat, e habitual seleccionar zonas conectadas

da floresta para garantir a criacao de reservas naturais. A conectividade e um requisito presente na

criacao dos planos florestais, facto esse que o torna importante na proteccao do habitat das especies.

Uma reserva natural com uma configuracao optima e com corredores largos favorece o habitat e

garante parcialmente que as especies nao saiam da reserva devido a largura que possui. E portanto

recomendavel que as reservas nao obriguem a muito esforco por parte das especies para se des-

locarem dentro da reserva, garantindo que a zona seja funcional. Um espaco da reserva pode ser

considerado funcional para uma especie quando facilita os esforcos da especie para se deslocar (e.g.

zonas com muitas arvores para os macacos).

A maximizacao do lucro de uma colheita esta habitualmente associado a um plano de longo prazo

denominado agendamento de colheitas. Este plano tem normalmente a garantia de adquirir uma

producao balanceada para todas as colheitas em perıodos diferentes. Quando se efectua um agen-

damento de colheitas e comum, para a proteccao da vida selvagem e seu habitat, garantir uma reserva

natural conectada cuja zona tenha uma tempo mınimo definido antes do agendamento.

Considerando um conjunto de requisitos associado a um plano florestal, calcular a melhor solucao

(o melhor plano) e um problema de optimizacao. Os requisitos avaliados no calculo do melhor plano

variam de acordo ao problema a ser tratado. Por exemplo, efectuar a colheita de madeira de forma

a maximizar o lucro obtido [Murray, 1999, McDill et al., 2002], criar reservas florestais naturais para a

proteccao do maior numero de especie Animal com um custo financeiro reduzido [Dilkina et al., 2016],

planear a melhor configuracao paisagıstica de uma reserva [Onal et al., 2016], passar uma estrada

na floresta evitando que as especies tenham de fazer uma travessia garantindo um custo baixo na

construcao da estrada, entre outros tipos de necessidades.

Para a optimizacao dos planos, sao elaborados algoritmos ou formulacoes de Programacao Linear

Inteira, da expressao em Ingles Integer Linear Programming (ILP) e Programacao Linear Inteira Mista,

da expressao em Ingles Mixed-Integer Linear Programming (MILP). Estas formulacoes sao maiorita-

riamente resolvidas com a ferramenta CPLEX 1 e e expectavel resolver para esta dissertacao numa

ferramenta diferente. No mesmo campo de optimizacao, os metodos heurısticos sao recursos indis-

1https://www.ibm.com/analytics/data-science/prescriptive-analytics/cplex-optimizer

3

pensaveis quando e muito difıcil calcular optimalidade e por vezes faz-se recurso de algoritmos como

o Ramificacao e Limitacao, da expressao em Ingles Branch-and-Bound (BnB), para calcular a melhor

solucao ou entao a solucao aceitavel de acordo um intervalo.

1.1 Objectivos

A presente dissertacao e direcionada ao estudo dos algoritmos de optimizacao para elaboracao dos

planos florestais. O seu principal objectivo e o seguinte:

• Propor formulacoes de optimizacao para elaboracao dos planos florestais para o agendamento

de colheitas. Essas formulacoes devem garantir os seguintes requisitos:

– Proteccao do habitat e da vida selvagem.

– Criacao das reservas naturais conectadas e com corredores largos que facilitam a deslocacao

das especies.

– Maximizacao do lucro das colheitas.

Para concretizar este objectivo, e expectavel combinar o problema da criacao de agendamentos

para colheitas e o problema da criacao de reservas para protecao do habitat.

1.2 Contribuicoes

O desenvolvimento da dissertacao resultou nas contribuicoes que incluem:

• Uma formulacao ILP para criacao de reservas conectadas e compactas para a proteccao das

especies, baseada na formulacao apresentada por Onal et al. [Onal et al., 2016].

• Um modelo ILP URM estocastico para o agendamento de colheitas, capaz de calcular solucoes

de ARM. E feita a respectiva avaliacao com o modelo GMU que inclui restricao de adjacencia

baseada em ARM [McDill et al., 2002].

• Uma formulacao ILP multi-objectivo que combina a maximizacao do lucro das colheitas e garante

a criacao de reservas com as qualidades necessarias para a preservacao das especies.

Foram desenvolvidos dois modelos tanto para a formulacao para a criacao de reservas conectadas

e compactas, como para a formulacao multi-objectivo.

A implementacao das formulacoes foi feita com o formalismo SMT.

4

1.3 Metodologia

O presente trabalho foi elaborado de acordo as seguintes fases:

1. Revisao da literatura e estudo das solucoes relacionadas directa e indirectamente com os objec-

tivos do trabalho.

2. Familiarizacao com as ferramentas essenciais de trabalho e preparacao de modelos e regras para

entrada e saıda dos dados.

3. Desenvolvimento e implementacao dos modelos, nomeadamente as reservas compactas e o

agendamento de colheitas.

4. Avaliacao das reservas e colheitas calculadas pelos modelos a fim de serem melhorados.

5. Desenvolvimento e implementacao do modelo que combina objectivos como a criacao de reserva

e o agendamento de colheitas.

6. Testes e avaliacao dos resultados obtidos.

1.4 Organizacao da Dissertacao

Esta dissertacao esta organizada em 5 capıtulos, com o Capıtulo 1 a introduzir e os restantes dis-

postos do seguinte modo:

• O Capıtulo 2 aborda essencialmente os conceitos fundamentais para o suporte e compreensao

do conteudo deste documento. Aborda tambem as formulacoes que resolvem problemas afectos

a proteccao do habitat da vida selvagem e a criacao de agendamento de colheitas. O agenda-

mento de colheitas, a proteccao de especies e a conectividade sao os problemas abordados neste

capıtulo.

• O Capıtulo 3 e reservado ao desenvolvimento das formulacoes, com destaque para a formulacao

ILP multi-objectivo que resolve e combina o problema de maximizar o lucro das colheitas com o

problema da criacao de reservas para a proteccao do habitat. O desenvolvimento comeca pelo

estudo e melhoria das formulacoes para reservas conectadas e compactas, e posteriormente para

o agendamento de colheitas.

• O Capıtulo 4 e reservado a avaliacao dos resultados obtidos. Apresenta os resultados produzidos

e um estudo comparativo das solucoes desta dissertacao. Apresenta tambem uma comparacao

com os trabalhos relacionados apresentados no Capıtulo 2.

5

• O Capıtulo 5 apresenta a conclusao do trabalho desenvolvido e propoe ideias para continuacao

do trabalho.

6

2Conceitos Fundamentais e Trabalhos

Relacionados

Conteudo

2.1 Conceitos Fundamentais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2 Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

7

8

Este capıtulo aborda essencialmente conceitos fundamentais para o suporte e compreensao do

conteudo deste documento. Aborda tambem as formulacoes que resolvem problemas afectos a proteccao

do habitat da vida selvagem e a criacao de agendamento de colheitas. O agendamento de colheitas, a

proteccao de especies e a conectividade, sao os problemas abordados e com solucoes dispostas em

formulacoes neste capıtulo.

2.1 Conceitos Fundamentais

Nesta seccao apresenta-se os conceitos e definicoes determinadas como essenciais para a com-

preensao das proximas seccoes. A subseccao 2.1.1 apresenta conceitos referentes a floresta, a

subseccao 2.1.2 apresenta os conceitos sobre Programacao Linear e a subseccao 2.1.3 finaliza com

overview sobre Satisfacao Modulo Teorias, da expressao em Ingles Satisfiability Modulo Theories

(SMT).

2.1.1 Plano Florestal

Ao efectuar uma tarefa, e necessario elaborar um plano de modo a nao o fazer empiricamente, sem

nocao dos efeitos e consequencias. Quando se trata de tarefas/problemas complexos ou de impacto

abrangente, elaborar um plano torna-se um requisito obrigatorio que leva a uma visao antecipada da

viabilidade antevendo metodos para colmatar as necessidades.

Todas as alteracoes a floresta provocada pelo homem, como colher madeira ou construir industria,

devem seguir um plano de boas praticas. Esse plano deve garantir a consistencia da floresta.

Tres factores importantes devem ser considerados na criacao dos planos florestais com o objectivo

de a tornar consistente.

Factores ambientais e biologicos, avaliam as caracterısticas significativas das especies que ocorrem

na area, o que cresce, e o que pode crescer em um determinado terreno, como tambem o tipo de terreno

que esta disponıvel para o plano florestal. Factores economicos e de mercados, considera o potencial

de uma area para producao do retorno financeiro suficiente. E o factor socio-economico que se refere

as pessoas e suas condicoes socio-economicas (e.g. posse de terras, valores e crencas) [Asia-Pacific

Forestry Commission, 1999].

Uma floresta e dividida em partes que iremos denominar por lotes 1. A Figura 2.1 apresenta uma

floresta que foi dividida em 104 lotes.

Quando o plano florestal e voltado a colheita, e feito um plano de longo prazo (varios perıodos) e

considera os seguintes pontos [Asia-Pacific Forestry Commission, 1999]:

1 Alguns estudos usam o termo cell quando se trata de areas uniformes e quadradas [Onal et al., 2016] e stands ou polıgonosquando sao areas nao uniformes [Carvajal et al., 2013]. Neste documento usaremos o termo lote.

9

Figura 2.1: Exemplo de floresta dividida em 104 lotes.

• Lotes a serem reservados para a conservacao da biodiversidade.

• Lotes a serem reservados dentro das areas de colheita propostas (e.g. proteccao do cursos de

agua).

• As futuras areas de colheita e uma agenda para a colheita.

• O tamanho aproximado e os limites de cada lote de colheita.

• Os volumes aproximados de madeira a serem colhidas em cada perıodo.

Um remendo representa o conjunto de lotes conectados. O conjunto de lotes conectados ou

contıguos e de tal forma que uma determinada especie consegue deslocar-se entre os lotes sem difi-

culdades e riscos. O conjunto de remendos seleccionados e protegidos constitui uma reserva.

A conectividade entre lotes pode ser classificada em conectividade estrutural e conectividade fun-

cional, em que a conectividade estrutural ou fısica trata de garantir que os lotes sejam adjacentes

(partilham uma fronteira fısica), permitindo que as especies habitem na reserva sem ter de sair da

mesma. A conectividade funcional esta relacionada com o grau de uma reserva facilitar a capacidade

das especies de se deslocarem entre os lotes (e.g. uma ave, nao necessita que os lotes tenham fron-

teiras fısicas) [Onal et al., 2016].

2.1.2 Programacao Linear

A Programacao Linear, da expressao em Ingles Linear Programming (LP) e um metodo utilizado

para optimizar funcoes lineares sujeitas a restricoes lineares. A optimizacao consiste em maximizar ou

minimizar a funcao linear e as restricoes lineares podem ser igualdades ou desigualdades lineares. A

funcao linear a ser optimizada e chamada de funcao objectivo [Igor Griva, 2009].

Supondo a existencia de duas especies animais que precisam expandir o seu habitat para os lotes

vizinhos. As variaveis x1 e x2 denotam o numero de hectares por especie. A expansao por hectare

acresce 3 e 5 para x1 e x2, respectivamente. No entanto, existem restricoes que dizem respeito a 50

10

hectares sem grandes arvores e 45 com acesso a recursos hıdricos, dando maior poder de escolha

para x2. Esse problema, pode ser formulado da seguinte forma:

Maximizar 3x1 + 5x2

Sujeito a:

3x1 + 2x2 ≤ 50

5x1 + 3x2 ≤ 45

x1, x2 ≥ 0

Este problema pode ser expandido para n especies e m restricoes. Denota-se j pela especie e sua

qualidade representada por qj . O limite para cada restricao i e dado por bi e aij representar o poder de

escolha das especies para restricao i. Com isso, ilustra-se a formulacao generica:

Maximizarn∑j=1

qjxj

Sujeito a:n∑j=1

aijxj ≤ bi, i = 1, . . . , m

xj ≥ 0, j = 1, . . . , n

De modo a familiarizar com as formulacoes LP, e dado mais um exemplo em que as variaveis

pertencem ao conjunto dos Inteiros: Dado as variaveis x1 e x2;

Maximizar x2

Sujeito a:

x1 + x2 ≤ 6

x1 ≥ 2 ; x2 ≥ 0 x1, x2 ∈ N

Neste exemplo, a funcao objectivo e x2, por ser a funcao a optimizar. Temos duas variaveis (x1 e x2

sao variaveis inteiras) e tres restricoes. Todas as restricoes sao lineares e por casualidade sao todas

desigualdades (tambem poderiam ser igualdades). A Figura 2.2(a) ilustra a solucao optima para x2.

A Programacao Linear Inteira, da expressao em Ingles Integer Linear Programming (ILP) e definido

como um problema de LP em que as variaveis pertencem ao conjunto dos numeros Inteiros. Quando no

conjunto de variaveis, algumas pertencem aos Inteiros e outras aos Nao-Inteiros, considera-se como

extensao de ILP e denomina-se Programacao Linear Inteira Mista, da expressao em Ingles Mixed-

11

Integer Linear Programming (MILP).

Um algoritmo muito utilizado para a resolucao dos problemas ILP e o algoritmo Ramificacao e

Limitacao, da expressao em Ingles Branch-and-Bound (BnB) que consiste na identificacao de todos

os candidatos a solucao (efectua uma enumeracao desses candidatos), descartando subconjuntos de

candidatos invalidos de acordo aos limites superior e inferior do valor optimizado.

Quando o problema a ser optimizado tem apenas uma funcao objectivo conforme mostra a formulacao

anterior, diz-se formulacao de objectivo unico. E quando tem mais de uma funcao objectivo, dizemos

que a formulacao e multi-objectivo. Uma formulacao multi-objectivo, se tiver definido uma hierarquia

para as funcoes objectivo, apresenta apenas uma solucao optima (a solucao optima e calculada de

acordo a hierarquia). Caso nao exista hierarquia das funcoes objectivo, a formulacao pode apresentar

varias solucoes optimas. O conjunto de solucoes optimas numa formulacao multi-objectivo, e conhecido

por Fronteira de Pareto [Pareto, 1906].

Uma formulacao multi-objectivo pode ser escrita da seguinte forma:

Maximizar x2

Minimizar x2 − x1Sujeito a:

x1 + x2 ≤ 6

x1 ≥ 2 ; x2 ≥ 0 x1, x2 ∈ N

1.8 2 2.2 2.4

3.5

4

4.5

x1

x2

(a) Solucao da formulacao de funcao objectivounico.

2 3 4 5 6

0

1

2

3

4

x1

x2

(b) Solucao da formulacao multi-objectivo.Varias solucoes optimas, nao existe hie-rarquia nos objectivos.

Figura 2.2: Solucoes optimas dos exemplos apresentados de LP com conjuntos Inteiros. Os pontos sao assolucoes encontradas.

Podemos ver na Figura 2.2, para a primeira formulacao apresentada com uma e unica funcao objec-

12

tivo (Maximizar x2), a Figura 2.2(a) nos apresenta apenas uma solucao que a considera como a optima.

Mas, a Figura 2.2(b) que esta relacionada com a formulacao a seguir (multi-objectivo e sem hierarquia

das funcoes objectivo) apresenta varias solucoes optimas ou a fronteira de Pareto.

2.1.3 Satisfacao Modulo Teoria

O Problema de Satisfacao Booleana, da expressao em Ingles Boolean Satisfiability Problem (SAT)

e o problema de determinar se uma formula proposicional e satisfeita. Uma formula proposicional e

satisfeita quando e possıvel atribuir alguns valores verdadeiros-falsos para as variaveis da formula, de

modo que seja satisfeita. Caso contrario, a formula e insatisfeita.

SMT e uma extensao de SAT, que adiciona argumentos de igualdade, aritmetica, bit-vectors, arrays,

quantificadores e outras teorias de primeira ordem uteis [Barrett et al., 2009]. A Figura 2.3 resume essa

extensao, adicionado as teorias (Theory Solver (TS)) a SAT que resulta em SMT.

Figura 2.3: SMT, uma extensao de SAT que adiciona teorias.

Uma ferramenta Solver de SMT decide a satisfacao ou e a validade das formulas nessas teorias.

Existem varios solvers para SMT, mas esta dissertacao limita-se num overview do Z3.

Z3 e um solver de SMT da Microsoft Research [de Moura and Bjørner, 2008]. Utiliza por padrao

o Simplex primario para optimizar formulacoes com restricoes aritmeticas, e ainda possui metodos de

decisao alternativos [Bjørner and Phan, 2014].

2.1.3.A Combinacao dos Objectivos

As solucoes de uma formulacao multi-objectivo de Z3, pode ser combinada usando a prioridade le-

xicografica, fronteira de Pareto ou objectivos box independente. De modo a sumarizar as combinacoes,

considere dois objectivos, t1 e t2 por maximizar e sujeito a restricao F :

Combinacoes Lexicografica: A combinacao lexicografica resume-se em encontrar o modelo M , tal

que M satisfaz F e o par 〈M(t1),M(t2)〉 e o maximo lexicograficamente. De outro modo, nao

existe um modelo M ′ que satisfaz F tal que M ′(t1) > M(t1) ou M ′(t1) =M(t1), M′(t2) > M(t2).

Fronteira de Pareto: A fronteira de Pareto, e obtida pelo conjunto de modelosM1, · · · ,Mi, · · · ,Mj , · · · ,

tal que, ou Mi(t1) > Mj(t1) ou Mi(t2) > Mj(t2), ao mesmo instante, ou Mi(t1) < Mj(t1) ou

Mi(t2) < Mj(t2). Para cada Mi, nao existe M ′ que domina Mi. O Z3 utiliza o Guided Improve-

ment Algorithm (GIA) para calcular a fronteira de Pareto [Bjørner and Phan, 2014].

13

Objectivos box: A combinacao box calcula dois modelos M1 e M2, tal que M1(t1) e o valor optimo de

t1 e M2(t2) e o optimo de t2.

2.2 Trabalhos Relacionados

Nesta seccao, sao apresentados os algoritmos de optimizacao para a criacao de planos florestais.

A presente seccao esta estruturada por quatro subseccoes, nomeadamente, a subseccao 2.2.1 aborda

o agendamento de colheitas (elaborar cronograma para colheita dos lotes) e apresenta dois modelos

fundamentais. A subseccao 2.2.2, apresenta solucoes de optimizacao para a proteccao das especies,

criando reservas conectadas e garantindo que as especies protegidas possam usufruir do seu habitat

sem sair da reserva. Tanto a subseccao 2.2.1 quanto a subseccao 2.2.2, avaliam em seus metodos

restricoes de adjacencias ou de conectividade. Na subseccao 2.2.3 sao apresentadas solucoes focadas

na conectividade dos lotes de uma reserva. Por fim, a subseccao 2.2.4 faz um resumo que classifica

os trabalhos relacionados.

2.2.1 Agendamento de Colheitas

Relativamente ao problema de agendamento de colheitas, dois modelos de optimizacao com restri-

coes de adjacencia foram definidos [Murray, 1999]. O Modelo de Restricao por Unidade, da expressao

em Ingles Unit Restriction Model (URM) impoe que para cada adjacencia, no maximo um lote seja

colhido. A Figura 2.4(a) exemplifica a colheita pela abordagem URM. O Modelo de Restricao por Area,

da expressao em Ingles Area Restriction Model (ARM) permite a colheita dos lotes adjacentes desde

que o tamanho do remendo colhido 2 nao seja superior ao tamanho maximo permitido. Na Figura 2.4(b),

definiu-se uma area contıgua maxima de 32 hectares. Em seguida e apresentada a formulacao ILP do

modelo URM por ser mais simples de compreender e de seguida sao apresentadas as mudancas para

se tornar no modelo ARM.

Consideremos a notacao em que L representa o conjunto dos lotes e T o conjunto dos perıodos das

colheitas. Temos i ∈ L a representar o ındice dos lotes e t ∈ T o ındice do perıodo. Adicionalmente,

temos que xit denota uma variavel binaria que especifica se o lote e colhido/tratado ou nao, onde

xit = 1 indica que o lote i e tratado no perıodo t e xit = 0 caso contrario. O sımbolo `it denota o lucro

associado ao tratamento do lote i no perıodo t e βit o volume (volume de madeira) de contribuicao para

o tratamento do lote i no perıodo t. It e St definem os limites inferior (It) e superior (St) para o volume

total produzido no perıodo t. Ni representa o conjunto dos lotes adjacentes ao lote i.

A funcao objectivo (2.1), maximiza o lucro associado ao tratamento da actividade agendada. A

restricao (2.2) impoe que cada lote seja tratado no maximo uma vez. A restricao (2.3) garante que o

2 Tamanho do remendo colhido pode ser chamado de area de corte aberta.

14

(a) Abordagem URM. (b) Abordagem ARM.

Figura 2.4: Exemplo de colheita para URM e ARM, assumindo que a area maxima contıgua de 32 hectares.

Maximizar∑i∈L

∑t∈T

`itxit (2.1)

Sujeito a:

∑t∈T

xit ≤ 1 ∀ i ∈ L (2.2)

It ≤∑i∈L

βitxit ≤ St ∀ t ∈ T (2.3)

xit + xjt ≤ 1 ∀ i ∈ L, t ∈ T, j ∈ Ni (2.4)

xit ∈ {0, 1} ∀ i ∈ L, t ∈ T (2.5)

volume produzido em cada perıodo esteja entre os limites It e St. A restricao (2.4) e a restricao para

o tratamento de lotes adjacentes. A restricao (2.5) define os valores inteiros que a variavel de decisao

pode ter. Para termos uma formulacao ARM, consideremos A que corresponde a area (tamanho)

maxima contıgua permitida, αi denota o tamanho do lote i e Ci que representa o conjunto de todos os

lotes tratados e contıguos ao lote i. Substitui-se a restricao (2.4) pela restricao (2.6), permitindo assim,

xit ·∑

j∈Ni∪Ci

αjxjt ≤ A ∀ i ∈ L, t ∈ T (2.6)

colher lotes adjacentes e contıguos desde que a area nao seja superior a A.

Entretanto, a restricao (2.6) e recursiva devido a expressao j ∈ Ni ∪ Ci presente no somatorio.

15

Com isso, Ci era pre-calculado atraves da programacao dinamica 3. E as tecnicas heurısticas para a

identificacao de solucoes aproximadas foram essenciais [Murray, 1999].

Portanto, ARM nao era considerado como um problema de LP e so uns anos depois e que foram

apresentadas duas formulacoes MILP que incluem restricoes de adjacencias baseadas em ARM [McDill

et al., 2002], nomeadamente o Path Algorithm e um modelo que define o conjunto de Unidade de Gestao

Generalizada, da expressao em Ingles Generalized Management Unit (GMU). O conjunto GMU baseia-

se na identificacao de todas as combinacoes de lotes adjacentes em que a sua area total contıgua

nao ultrapassa o maximo autorizado. Consideremos u como a representacao de uma combinacao dos

lotes adjacentes e Gi o conjunto formado por todas as combinacoes que contem o lote i. Para cada

combinacao, GMU cria uma variavel de decisao xut ∈ {0, 1}, tal que se xut = 1 temos que cada lote

da combinacao u foi colhido no perıodo t, no entanto, para controlar os lotes ao ponto de nao serem

colhidos mais de uma vez no mesmo perıodo, aplica-se a restricao∑u∈Gi xut ≤ 1 ∀ i ∈ L, t ∈ T .

Enquanto que Path Algorithm baseia-se em, tendo os lotes A, B e C, onde AB e BC sao adjacentes de

acordo a Figura 2.5, numa visao basica sao criadas restricoes com os lotes adjacentes xAt + xBt ≤ 1

e xBt + xCt ≤ 1, se uma entre as restricoes tiver a area inferior que o maximo permitido entao e

excluıda, permanecendo apenas a que possuı a area superior ou igual ao maximo permitido. Caso

ambas tenham a area inferior e a combinacao dos tres lotes (ABC) for superior, entao coloca-se a

restricao xAt + xBt + xCt ≤ 2 da exclusao das anteriores. Avalia-se que ABC formam um caminho e

limita-se em nao criar restricoes redundantes [McDill et al., 2002].

Figura 2.5: Exemplo de floresta com tres lotes, A, B e C [McDill et al., 2002].

Surge duas formulacoes ILP para ARM em que uma trabalha com variaveis para os lotes e restricoes

explıcitas para as areas restritas e a outra utiliza variaveis para grupos que correspondem a area de

corte aceitavel. Essas formulacoes apresentaram um numero exponencial de variaveis e restricoes

de acordo ao numero de lotes. No entanto, dessas formulacoes, foi apresentado um modelo que as

combina (variaveis para lotes e variaveis para grupos que correspondem a area de corte aceitaveis) e

reduz o numero de variaveis e restricoes para polinomial [Constantino et al., 2008], resolvida usando

BnB.

3 Sobre programacao dinamica siga a referencia [Cormen et al., 2009].

16

2.2.2 Proteccao de Especies

Um estudo feito por Cerdeira et al. [Cerdeira et al., 2010], conclui que a incorporacao da conectivi-

dade como funcao objectivo para identificar a maxima ocorrencia e conectividade das especies, pode

levar a resultados de alta conectividade para algumas especies e nula para outras. No entanto, o

mesmo estudo apresentou uma abordagem alternativa que considera explicitamente os requisitos de

conectividade como parte do modelo e nao como parte da funcao objectivo. Para a solucao do pro-

blema foram usados tres algoritmos 4, entre eles, dois de corte mınimo que garantem a optimalidade e

uma heurıstica.

Um outro estudo por Onal and Briers [Onal and Briers, 2006], preocupou-se com o problema no que

diz respeito a deslocacao das especies entre os lotes sem sair da reserva e propos uma formulacao

ILP a qual e apresentada e explicada.

Entretanto, para melhor compreensao da formulacao, o mesmo estudo [Onal and Briers, 2006] divi-

diu a potencial area para reserva em lotes quadrados (conforme apresenta a Figura 2.6) e fez uso da

teoria dos grafos para desenvolver a formulacao. Denomina um lote seleccionado para a reserva por no,

a adjacencia dos lotes por arcos (neste caso por arcos direccionados) e evita que a reserva crie ciclos.

A Figura 2.6(a) mostra uma reserva com duas componentes desconectada, com uma delas que forma

ciclo (3, 4, 5, 6, 7 e 8). A Figura 2.6(b) apresenta uma reserva conectada, onde, o lote 9 representa

um no de direccao (todos os outros nos tem os seus arcos direccionados para ele). O comprimento da

cauda, dado um no, calcula-se de acordo ao numero de nos com os arcos direccionados para ele (o

no) (e.g. o no 8 tem o comprimento 2, o no 5 tem o comprimento 4).

(a) Exemplode reservacom lotesdesconec-tados e umciclo.

(b) Exemplo de reserva conectadacom o lote 9 como no de direcao.

Figura 2.6: Exemplo de reserva conectada e desconectada [Onal and Briers, 2006].

4 Dois algoritmos que garantem a optimalidade onde sIC (specialized Integer Cutting) e mais rapido que IC (Integer Cutting)em tempo de execucao e uma heurıstica que obtem solucoes em pouco tempo para instancias que IC e sIC nao gerem.

17

Consideremos a notacao em que L representa o conjunto de lotes. As variaveis i ∈ L e j ∈ L

denotam os lotes individuais, onde, se o lote i e seleccionado entao o no i e incluıdo na rede de

reservas. Nj corresponde ao conjunto dos lotes que sao adjacentes ao lote j. S e o conjunto das

especies identificadas para a preservacao e s corresponde a uma especie, s ∈ S. φsi especifica se

a especie esta presente no lote, onde φsi = 1 se a especie s esta presente no lote i, caso contrario,

φsi = 0. Ks e o parametro que representa o numero mınimo de lotes na reserva que deve ter a especie

s. M representa um numero arbitrariamente grande que serve como superestimacao do numero de

lotes na reserva. xi e a variavel binaria, onde, xi = 1 se o lote i esta na reserva, caso contrario, xi = 0.

yij e a variavel binaria definida para cada j e i ∈ Nj , onde yij = 1 se o arco dirigido tem origem no no i

e fim no no j, yij = 0 caso contrario. wj e uma variavel nao-negativa que representa o comprimento da

cauda do no j e zij uma variavel nao-negativa que representa o comprimento da cauda do no i quando

esta ligado ao no adjacente j. A formulacao tem como objectivo minimizar o numero de lotes da reserva

satisfazendo a representacao das especies. Segue-se a formulacao [Onal and Briers, 2006]:

Minimizar∑i∈L

xi (2.7)

Sujeito a:

∑i∈L

φsixi ≥ Ks ∀ s ∈ S (2.8)

∑i∈Nj

yij ≤ 4xj ∀ j ∈ L (2.9)

∑j∈Ni

yij ≤ xi ∀ i ∈ L (2.10)

∑i∈L

∑j∈L

yij =∑i∈L

xi − 1 (2.11)

zij ≥ wi + 1−M(1− yij) ∀ i, j ∈ L onde i 6= j (2.12)

wj =∑i∈L

zij ∀ j ∈ L (2.13)

xi ∈ {0, 1}; yij ∈ {0, 1} ∀ i, j ∈ L (2.14)

18

A funcao objectivo (2.7) minimiza o numero de lotes na reserva. Ja a restricao (2.8) garante as

exigencias das especies asseguradas (a reserva deve incluir pelo menos Ks lotes para cada especie).

A restricao (2.9) garante que se o lote j nao for seleccionado entao nenhum lote adjacente i direcciona-

se para j (yij = 0), caso contrario (se o lote j for selecionado, xj = 1), entao podera ter ate 4 arcos

em sua direccao com origem dos seus adjacentes i. A restricao (2.10) trata de garantir que se o no

i nao e reservado, entao nenhum arco com inıcio em i pode ser seleccionado (o inverso diz que no

maximo deve existir um arco com inıcio em i seleccionado). A restricao (2.11) garante que o numero

de arcos dirigidos seja igual ao numero de lotes menos 1. Ja as restricoes (2.12) e (2.13) restringem a

possibilidade de se formarem ciclos (a Figura 2.6(a) ilustra a formacao de ciclo).

Foram adicionadas melhorias a formulacao que acelerou em tempo de execucao em aproximada-

mente 4, 5 vezes no encontro da solucao [Billionnet, 2012]. As melhorias levaram a substituicao da

restricao (2.9) por yij ≤ xi para todo o i e j, a nova restricao impoe que se o lote i nao for se-

leccionado (xi = 0) entao nenhum arco com inıcio em i deve existir (essa substituicao aumenta o

numero total de restricoes, mas no entanto torna a formulacao mais eficiente [Billionnet, 2012]). E a

substituicao das restricoes que tratam de restringir a possibilidade de se criarem ciclos (2.12) e (2.13)

por Tj ≥ Ti+1−M(1− yij) para todo o i e j, onde Ti ≥ 0 e uma variavel que pertence ao conjunto dos

reais e que esta associada a cada lote i. Se tiver um arco do lote i para o seu adjacente j (yij = 1) entao

o valor associado ao lote j deve ser maior ou igual que o valor mais 1 do lote i (Tj ≥ Ti + 1) e se nao

tiver arco (yij = 0), a condicao sera sempre verdadeira porque M representa um valor arbitrariamente

grande (conforme detalhado na notacao). Essa restricao evita que sejam criados ciclos na reserva.

No que diz respeito a corredores com restricoes orcamentais, um estudo recente [Dilkina et al.,

2016] desenvolveu um modelo MILP e adicionou restricoes espaciais para resistencias especıficas de

especies.

2.2.3 Conectividade

Nas subseccoes 2.2.1 e 2.2.2 vimos que os requisitos de adjacencias ou conectividade sao indis-

pensaveis. Visto que sao esses requisitos e restricoes que nos levam a promover nas formulacoes o

cumprimento das necessidades como o controlo da area de colheita maxima, a criacao de corredores,

criacao de reservas conectadas e outras restricoes associadas a preservacao das especies.

Portanto, a conectividade e um factor importante para o funcionamento eficiente na conservacao

das reservas [Onal et al., 2016]. Foi apresentada uma formulacao ILP [Carvajal et al., 2013], capaz de

impor conectividade para instancias com mais de 1.000 lotes e para diferentes restricoes ambientais,

onde a promocao de lotes conectados por si so leva a reservas antigas que podem ter a forma longa e

estreita [Carvajal et al., 2013,Rebain and McDill, 2003] conforme ilustra a Figura 2.7.

No entanto, um trabalho mais recente [Onal et al., 2016], preocupou-se com a configuracao optima

19

Figura 2.7: Exemplo de uma reserva na forma longa e estreita, as partes de cor preta representa a reserva [Car-vajal et al., 2013].

das reservas conectadas e compactas, onde a conectividade pode ser aplicada sob a forma estrutural

e/ou funcional. O mesmo trabalho, apresentou um modelo ILP e aplicou essa abordagem na proteccao

de especies que necessitam das duas formas de conectividade. Neste trabalho sera apresentada

apenas a conectividade estrutural. Para a notacao dessa formulacao, temos N a denotar o numero

de reservas, com N ≥ 1. L corresponde ao conjunto de todos os lotes, em que o lote pode ser

representado por i, j e k ∈ L. A variavel binaria xki representa o lote seleccionado a que reserva

pertence, onde xki = 1 indica que o lote i foi seleccionado e pertence a reserva cujo o centro e o lote k.

Caso contrario, xki = 0. xkk = 1 significa que o lote k foi seleccionado para tornar-se o centro de uma

reserva. A constante Dki denota a distancia entre os lotes k e i. A qualidade do lote i para o habitat

de especies e representado por Qi. A constante Q determina o mınimo de qualidade que uma reserva

deve apresentar com o objectivo de albergar as especies alvo. Por fim a constante Q∗ determina o

mınimo de qualidade total do habitat fornecido por todas as reservas.

A funcao objectivo (2.15) minimiza a soma das distancias de cada lote em relacao ao centro da

reserva em que pertence, soma de todas as areas protegidas. Ja a restricao (2.16) garante que sejam

criadas N reservas. A restricao (2.17) impoe que cada lote seleccionado deve pertencer a apenas uma

reserva cuja o centro e k, enquanto que a restricao (2.18) diz que o lote centro k tem a sua volta ate

M lotes, onde M e dado como um numero inteiro arbitrario e positivo. A restricao (2.19) garante que

cada reserva deve ter o mınimo de qualidade para o habitar e a restricao (2.20) assegura que o total de

qualidades apresentadas pelas reservas seja pelo menos Q∗.

Quanto a conectividade, temos a restricao (2.21). Nj representa o conjunto de todos os lotes ad-

jacente a j. A restricao (2.21) garante que se j for seleccionado para fazer parte da reserva com k o

centro, entao, pelo menos um dos lotes i adjacentes a j deve fazer parte desta reserva, com o detalhe

de que a distancia de i em relacao ao de j deve ser menor (Dki < Dkj).

20

Minimizar∑k∈L

∑i∈L

Dkixki (2.15)

Sujeito a:

∑k∈L

xkk = N (2.16)

∑k∈L

xki ≤ 1 ∀ i ∈ L (2.17)

∑i∈L

xki ≤Mxkk ∀ k ∈ L (2.18)

∑i∈L

Qixki ≥ Qxkk ∀ k ∈ L (2.19)

∑k∈L

∑i∈L

Qixki ≥ Q∗ (2.20)

xkj ≤∑i∈Nj

Dki<Dkj

xki ∀ k ∈ L, j ∈ L nao adjacentes (2.21)

xki ∈ {0, 1} ∀ k ∈ L, i ∈ L (2.22)

2.2.4 Resumo

A conectividade entre lotes e um factor a considerar na elaboracao de planos florestais. A sua im-

portancia e inclusao e avaliada de acordo com os objectivos do plano. A revisao da literatura esteve

focada nas solucoes (em especial as formulacoes) para proteccao de especies e a criacao de cro-

nogramas para colheita, que por sua vez, necessitou da inclusao de solucoes para conectividade de

lotes.

A colheita de madeira e uma actividade necessaria para industrias que utilizam essa materia prima.

As solucoes para o agendamento de colheitas seguem duas abordagens diferentes, nomeadamente,

a abordagem URM que cria um cronograma restringindo que os lotes adjacentes nao sao colhidos no

mesmo perıodo, ganhando um impacto positivo na consistencia da floresta e a abordagem ARM em

que a restricao de adjacencia e abrangida por um limite superior de area a colher (com bons estudos

e limites beneficos para o habitat, tem um impacto tambem positivo). URM e ARM foram estudados

21

por Murray [Murray, 1999] que apresentou uma formulacao ILP para URM e considerou heurısticas e

a programacao dinamica para resolver ARM. McDill et al. [McDill et al., 2002] apresentou solucoes

LP para ARM que tenho a destacar apenas o modelo GMU que trabalha em volta do conjunto Gi

denominado de todas as combinacoes de lotes adjacentes em que i pertence e que cumpre com o

limite da area estabelecida.

Quanto a proteccao de especies, ate mesmo os modelos URM e ARM incorporam essa pratica

implicitamente, mas, Onal and Briers [Onal and Briers, 2006] propuseram uma formulacao ILP a qual

preocupava-se com a deslocacao das especies entre os lotes sem sair da reserva. Entretanto, esta

formulacao foi melhorada e transformada em MILP por Billionnet [Billionnet, 2012] ao nıvel de reduzir o

tempo de execucao em aproximadamente 4, 5 vezes.

A conectividade e um facto inevitavel porque existe e esta presente na elaboracao de planos flo-

restais, onde, o objectivo desses planos menosprezam ou prezam a sua importancia. Uma formulacao

ILP capaz de impor conectividade para diferentes restricoes ambientais foi apresentada por Carvajal et

al. [Carvajal et al., 2013] e que promove a criacao de reservas antigas com uma estrutura paisagıstica

longa e estreita. Esta estrutura paisagıstica motivou a inclusao na dissertacao a criacao de reserva

compacta e conectada sem a forma longa e estreita. Ainda nos trabalhos relacionados, Onal et al. [Onal

et al., 2016] preocupou-se com a configuracao optima das reservas com a conectividade a ser aplicada

na forma estrutural e/ou funcional. Para esta formulacao usou ILP.

A Tabela 2.1 mostra-nos as relacoes entre os trabalhos quanto aos tipos de problemas tratados, as

formulacoes utilizadas para resolve-las e o modelo resolvido.

Tabela 2.1: Caracterizacao dos trabalhos relacionados.

Trabalhos Problemas Modelos Formulacoes[Dilkina et al., 2016] especies min-custo MILP

[Onal and Briers, 2006,Billionnet, 2012] especies min-lotes MILP[Cerdeira et al., 2010] especies min-lotes ILP‡

[Onal et al., 2016] especies∗ † ILP[Carvajal et al., 2013] ∗ max-lucro ILP

[Murray, 1999] colheita∗ max-lucro ILP‡§[McDill et al., 2002] colheita∗ max-lucro MILP

∗ inclui Conectividade† minimizar distancia entre os lotes‡ inclui Heurısticas§ inclui Programacao Dinamica

Verifica-se que da pesquisa feita, nao se identificou uma solucao LP que impoe em suas funcoes

objectivo a proteccao de especies e a maximizacao do lucro da colheita. Esse facto motivou o desen-

volvimento de uma solucao multi-objectivo que responde a esta exigencia.

22

3Desenvolvimento das Formulacoes

Conteudo

3.1 Formulacao para Reservas Compactas . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.2 Formulacao para Agendamento de Colheitas . . . . . . . . . . . . . . . . . . . . . . . 28

3.3 Formulacao Multi-Objectivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.4 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

23

24

Garantir a proteccao do habitat e obter o melhor lucro da colheita numa floresta, sao dois problemas

que esse capıtulo unifica e apresenta uma formulacao ILP multi-objectivo.

O desenvolvimento, comeca com o estudo e melhoria das solucoes para reservas compactas e

posterior para o agendamento de colheitas. E determinado tanto para reserva, como para colheita,

as melhores solucoes combinadas na multi-objectivo. A formulacao multi-objectivo termina com dois

modelos a custa de duas versoes de uma restricao, que calculam estrutura paisagıstica diferente.

3.1 Formulacao para Reservas Compactas

Para o calculo de reservas compactas, baseou-se na formulacao apresentada por Onal et al. [Onal

et al., 2016] por se tratar de uma solucao muito proxima do desejado. Inicialmente implementou-se a

formulacao original e verificou-se nao escalavel quando todos os lotes sao candidatos para o centro da

reserva, incluindo o calculo optimo para mais de uma reserva.

E determinado que precisa-se de apenas uma reserva (de acordo aos objectivos), conectada e

compacta. Tambem ponderou-se que o lote centro da reserva seria identificado a priori, de acordo com

as condicoes apresentadas pelo habitat. Depois dessas avaliacoes, excluiu-se restricoes e variaveis

para obter a formulacao deseja e descrita mais abaixo.

Consideremos a notacao, L representa o conjunto de lotes da floresta em estudo e xiγ a variavel

binaria que representa o lote, com i ∈ L e γ o lote centro identificado a priori (e uma constante). Quando

xiγ = 1, indica que o lote i faz parte da reserva, caso contrario xiγ = 0. A distancia entre os lotes γ e i e

dado por Diγ , enquanto que a qualidade dos lotes representa-se por Qi. A constante Q∗, diz respeito a

qualidade mınima que a reserva deve ter. Por fim, o conjunto de todos os vizinhos de i e representado

por Ni.

Minimizar∑i∈L

Diγxiγ (3.1)

Sujeito a:

∑i∈L

Qixiγ ≥ Q∗ (3.2)

xiγ ≤∑j∈Ni

Djγ<Diγ

xjγ ∀ i ∈ L nao adjacente a γ (3.3)

xiγ ∈ {0, 1} ∀ i ∈ L (3.4)

25

A funcao objectivo (3.1), minimiza a soma das distancias dos lotes pertencentes a reserva. A

restricao (3.2), garante que a reserva criada tenha o mınimo de qualidade exigida por Q∗. A restricao

de adjacencia e imposta pela restricao (3.3), onde, se um lote xiγ for reservado, entao, pelo menos um

dos seus vizinhos tambem sera desde que esteja mais proximo do centro γ. A restricao (3.4) limita os

valores da variavel xiγ , tornando-a binaria.

Apos testes, verificou-se que a formulacao nao e capaz de criar uma reserva compacta para todas

as instancias. A formulacao apresenta um resultado nao desejado quando esta perante instancias com

lotes de variadas caracterısticas, tais como a forma geometrica, a qualidade do habitat e o numero de

vizinhos. Na Figura 3.1 e ilustrada uma amostra da solucao dada pela formulacao, a zona escura e a

reserva e verifica-se que nao criou reserva compacta, permitindo a existencia de lotes ilhas na reserva.

Figura 3.1: Reserva nao compacta com lotes ilha, zona escura e a reserva.

Esses resultados motivou a criacao de duas solucoes que garantem a criacao da reserva compacta.

3.1.1 Solucao 1: Modelo RCC

Para esta solucao, a motivacao esteve a volta da restricao (3.3), que e satisfeita desde que pelo

menos um lote vizinho de xiγ mais proximo do centro γ seja reservado. Daı surgiu a hipotese de

reservar todos os lotes vizinhos de xiγ desde que a distancia seja menor relativamente ao centro γ.

Para tal, foi necessario definir a constante Ciγ que indica o numero de vizinhos do lote i cuja

distancia com o lote centro γ seja menor. Esta constante pode ser calculada pela expressao (3.5).

Ciγ =∑j∈Ni

Djγ<Diγ

1 ∀ i ∈ L nao adjacente a γ (3.5)

Substitui-se a restricao (3.3) pela restricao (3.6) de modo a garantir a reserva de todos os lotes que

26

estejam no interior da reserva. Tornando-a uma reserva compacta.

Ciγxiγ ≤∑j∈Ni

Djγ<Diγ

xjγ ∀ i ∈ L nao adjacente a γ (3.6)

Foi feito testes e verificou-se que a hipotese e valida, mas, em alguns casos a reserva separa os

lotes nao reservados, tornando-o inacessıvel sem ter que passar pela reserva ou entao dar a volta

pela floresta. A Figura 3.2 ilustra a amostra obtida da solucao, com a zona escura a indicar a reserva.

Verifica-se que existe um lote na extremidade da floresta que nao foi reservado e no entanto inacessıvel

sem passar pela reserva ou entao dar a volta pela floresta.

Figura 3.2: Reserva compacta, lote nao reservado inacessıvel. A zona escura representa a reserva.

Esta e uma solucao que preocupou-se apenas com a reserva e passara a ser denominada de

Reserva Conectada e Compacta (RCC), nao da importancia aos lotes nao reservados. Daı ter uma

solucao que abrange ate aos lotes nao reservados na subseccao 3.1.2.

3.1.2 Solucao 2: Modelo RCC-nR

E certo que o objectivo centra-se na criacao de reservas e agendamento de colheitas, nessa ordem,

ao criar as reservas e torna-la num habitat melhor e necessario evitar que a colheita seja um motivo

para entrar na reserva. A subseccao 3.1.1 apresenta a solucao RCC com reservas compactas, mas

nao deixa os lotes nao reservados acessıveis para uma colheita que reduz a perturbacao do habitat.

Esta nova solucao tem como hipotese a definicao de dois lotes centros, uma para reserva e outra

para os lotes nao reservados. E indicado α para o lote centro dos lotes nao reservados e γ para o lote

centro da reserva (com α 6= γ).

Adiciona-se a restricao (3.7), essa restricao impoe que o lote i faca parte da reserva ou da nao-

27

reserva.

xiα 6= xiγ ∀ i ∈ L (3.7)

Substitui-se a restricao (3.3) pela restricao (3.8) de modo a garantir que a reserva seja conectada e

os lotes nao reservados tambem. Com isso, tem-se a possibilidade de existir uma reserva compacta e

a zona nao reservada ligada.

xjk ≤∑i∈Nj

Dik<Djk

xik ∀ k ∈ {γ, α}, j ∈ L nao adjacente a k (3.8)

Foi feito os testes e verificou-se que a hipotese e valida. A solucao e capaz de criar reservas

compactas e garantir que a zona nao reservada seja acessıvel sem perturbar o habitat da reserva. A

Figura 3.3 ilustra a configuracao paisagıstica da solucao calculada. A zona escura representa a reserva

e verifica-se a configuracao de uma reserva conectada e compacta ao mesmo tempo que os lotes nao

reservados sao conectados.

Figura 3.3: Reserva compacta e conectada, zona nao reservada e acessıvel. A zona escura representa a reserva.

Devido a caracterıstica de tornar a reserva e os lotes nao reservados conectados, esta solucao

passara a denominar-se de Reserva e Nao-Reserva Conectadas e Compactas (RCC-nR).

3.2 Formulacao para Agendamento de Colheitas

Existem dois modelos fundamentais para o agendamento de colheitas, a citar o modelo URM que

impede colher no mesmo perıodo os lotes adjacentes e o modelo ARM que permite colher lotes adja-

centes no mesmo perıodo desde que a area total seja menor que a area maxima indicada.

A formulacao que optimiza o agendamento de colheitas desta dissertacao baseou-se nesses mode-

28

los, a comecar pelo URM descrito de seguida e posteriormente o modelo ARM reservado na subsec-

cao 3.2.1.

Quanto a formulacao do modelo URM, utilizou-se a solucao ILP apresentada por Murray [Murray,

1999]. Apresento uma variacao deste modelo.

Consideremos a notacao, L representa o conjunto dos lotes e T o conjunto dos perıodos das colhei-

tas. Temos xit, a variavel binaria de controle do lote, com i ∈ L e t ∈ T . Quando xit = 1, indica que o

lote i e colhido no perıodo t, caso contrario, xit = 0. A constante `it denota o lucro associado ao lote i

no perıodo t e βit o volume de madeira. It e St definem os limites inferior e superior, respectivamente,

de volume total por produzir no perıodo t.

Maximizar∑t∈T

∑i∈L

`itxit (3.9)

Sujeito a:

∑t∈T

xit ≤ 1 ∀ i ∈ L (3.10)

It ≤∑i∈L

βitxit ≤ St ∀ t ∈ T (3.11)

xit + xjt ≤ 1 ∀ i > j, i ∈ L, j ∈ Ni, t ∈ T (3.12)

xit ∈ {0, 1} ∀ t ∈ T, i ∈ L (3.13)

A funcao objectivo (3.9) pretende maximizar o lucro das colheitas. Temos a restricao (3.10) a impor

que um lote seja colhido no maximo em um perıodo e a restricao (3.11) a garantir que em cada perıodo

de colheita seja obtido um volume de madeira compreendido entre It e St. A restricao (3.12) impoe a

restricao de adjacencia que identifica o modelo URM, com i > j para que nao seja repetida restricoes.

Por fim, o domınio da variavel xit e limitada para binaria na restricao (3.13).

Esta solucao apresentou o comportamento esperado quanto a distribuicao dos lotes a serem colhi-

dos em cada perıodo. Foram feitos testes com tres perıodos de colheita e e ilustrada na Figura 3.4 o

cronograma da colheita representada na floresta (cada cor representa um perıodo).

29

Figura 3.4: Agendamento de colheitas, modelo URM com tres perıodos. cada cor representa um perıodo.

3.2.1 Modelo ARM

ARM e um modelo mais complexo que URM, uma vez que URM e visto como um caso particular

de ARM. Isso tambem aplica-se ao tempo de execucao, URM e mais rapido. Isto motivou a criacao da

hipotese de calcular solucoes ARM tirando proveito do modelo URM.

Esta hipotese pauta na geracao de instancias descendente da original de ARM para URM. Este

processo e explicado na subseccao 3.2.2, mas antes, foi necessario implementar o modelo GMU que

baseia-se no modelo ARM de modo a medir a veracidade da hipotese e qualidade da solucao.

O modelo GMU, trabalha em torno de um conjunto Gi, designado por conjunto de todas as combi-

nacoes de lotes adjacentes em que i pertence e cuja a area nao ultrapassa o maximo determinado.

Utilizou-se o conjunto Gi para impor restricoes ARM e modificou-se o modelo URM de modo a

alcancar a implementacao do modelo GMU. Para tal, definiu-se k ∈ Gi e a variavel binaria ykt que

recebe o valor 1 quando a combinacao dos lotes k forem colhidos no perıodo t e 0 caso contrario.

Em termos de formulacao, substituiu-se a restricao (3.12) que trata das adjacencias do modelo URM

pela restricao (3.14) que garante a restricao GMU, mas que so produz efeitos positivos quando tambem

e incluıda a restricao (3.15), garante que os lotes combinados em k nao sejam colhidos mais de uma

vez.

ykt + xjt ≤ 1 ∀ t ∈ T, i ∈ L, k ∈ Gi, j ∈ Nk (3.14)

xit =∑k∈Gi

ykt ≤ 1 ∀ t ∈ T, i ∈ L (3.15)

30

Por fim, adiciona-se a restricao (3.16) para tornar a variavel ykt binaria.

ykt ∈ {0, 1} ∀ k ∈ Gi, t ∈ T, i ∈ L (3.16)

Antes das consideracoes sobre o comportamento da formulacao, determinou-se necessario abor-

dar sobre como calcular o conjunto Gi. O Algoritmo 3.1 apresenta um algoritmo recursivo capaz de

determinar o conjunto para todo i dado a instancia. De forma pragmatica, a constante A representa a

area maxima permitida, αi simboliza a area do lote i. Uma combinacao que pertence ao conjunto Gi

e representada por Ci e por fim, Ni representa os lotes adjacentes a i. O algoritmo verifica para cada

vizinhanca de i se a combinacao das areas esta dentro dos requisitos, caso afirmativo, entao actualiza

as componentes e invoca recursivamente de modo a incluir outros elementos que nao sao vizinhos de

i mais que sao vizinhos dos vizinhos escolhidos para o conjunto.

Algoritmo 3.1: Metodo recursivo Gi com os parametros Ci, Ni e αibegin

A←− getArea()

for each l ∈ Ni do

if αi + αl ≤ A then

Ni+1 ←− Ni ∪NlCi+1 ←− Ci ∪ {l}αi+1 ←− αi + αlreturn Ci ∪Gi(Ci+1, Ni+1, αi+1)

return Ci

Os testes realizados permitiram consolidar que nao e recomendavel a solucao GMU, porque alem

do tempo de execucao ser muito elevado, tambem e muito elevado o numero de variaveis e restricoes

a medida que o tamanho da instancia cresce comparativamente ao modelo URM. Consolidou e serve

como um medidor de avaliacao da hipotese criada e que e apresentada de seguida.

3.2.2 Modelo URM Estocastico

Dado que, calcular solucoes URM e menos difıcil que ARM pelo facto de URM ser um caso particular

de ARM, surgiu a hipotese de calcular solucoes ARM com a complexidade de URM.

Para ser possıvel calcular solucoes ARM no modelo URM, e necessario converter as instancias

originais em instancias menores, fruto dos agrupamentos dos lotes dentro do requisito da area maxima.

Esses lotes agrupados sao considerados como um lote 1, o que torna mais facil de calcular solucoes

1 Actualiza-se tambem as componentes, tais como a area, a vizinhanca e outros.

31

(diminui o tamanho da instancia e resolve-se no modelo URM).

A dificuldade que surge nessa abordagem, e que o numero de instancias/paisagens convertidas da

original seria exponencial de acordo ao numero de lotes e a area maxima permitida. Eis que surge a

ideia de nao gerar todas as paisagens e sim gerar de forma estocastica num tempo finito. A medida

que gera, calcula a solucao URM e guarda a melhor solucao entre as paisagens que sao executadas.

Essa abordagem sera denominada de URM-Estocastico (URM-S).

O Algoritmo 3.2 espelha a estrategia por tras da geracao das paisagens.

Algoritmo 3.2: Estrategia para gerar paisagembegin

A←− getArea()L←− getInstancia()paisagem←− {}

while len(L) > 0 do

i←− escolhe elemento na LL←− L \ i

while escolhe(0, 1) = 1 and len(L) > 0 and A < αi do

j ←− escolhe elemento na Ni ⊂ L

if A > αi + αj then

L←− L \ {j}i←− i ∪ {j}

paisagem←− paisagem ∪ {i}return paisagem

Relativamente ao Algoritmo 3.2, a letra A representa a area maxima permitida, enquanto que αi

simboliza a area de i (onde i representa um conjunto de lotes contıguos). L e a lista de controlo

dos elementos que falta escolher. Para cada iteracao, escolhe um lote de forma aleatoria. Depois,

enquanto tiver lotes em L e a area combinada entre os lotes escolhidos estiver dentro dos requisitos,

entao, aleatoriamente decide se continua a escolher lotes para essa combinacao. O algoritmo executa

enquanto tiver elementos nao escolhidos em L.

De acordo aos testes elaborados, e comparados com a solucao oferecida pelo modelo GMU, verificou-

se que o modelo URM-S apresenta solucoes muito proximas ao optimo apresentado por GMU e me-

lhores solucoes quando e limitado a execucao em 30 minutos.

As Figuras 3.5(a) e 3.5(b) ilustram as amostras das solucoes obtidas por URM-S e GMU, respec-

tivamente. Considerando que os modelos foram executados num limite de 30 minutos. Mais detalhes

sobre a avaliacao sao apresentados no Capıtulo 4.

32

(a) Solucao URM-S (b) Solucao GMU

Figura 3.5: Avaliacao paisagıstica da solucao URM-S e GMU, ambas em 30 minutos.

3.3 Formulacao Multi-Objectivo

Nesta seccao, e apresentado o estudo da combinacao entre a formulacao para o agendamento de

colheitas e a de reserva compacta. Combinacao essa que da origem a formulacao multi-objectivo, que

maximiza o lucro das colheitas e garante a criacao da reserva para proteccao do habitat. De acordo as

solucoes obtidas na seccao 3.1 e na seccao 3.2, decidiu-se utilizar a solucao RCC-nR (subseccao 3.1.2)

e o modelo URM de Murray [Murray, 1999], reserva compacta e agendamento de colheita, respectiva-

mente.

Para o agendamento de colheitas, nao se recomenda a utilizacao do modelo GMU baseado em

ARM devido a complexidade comparativamente ao URM. Quanto ao modelo URM-S, sua integracao

iria transformar a solucao multi-objectivo com a mesma caracterıstica estocastica, isso e algo nao pre-

tendido. Para a reserva compacta, foi manifestado que o modelo RCC-nR e o unico que preocupou-se

em conectar tanto a reserva como os lotes nao reservados, que possibilita a colheita sem atravessar a

reserva.

As funcoes objectivo (3.17) e (3.18), maximiza o lucro das colheitas e minimiza a soma das distancias

dos lotes da reserva, respectivamente. Para a reserva, a restricao (3.19) garante a sua qualidade

mınima, enquanto que as restricoes (3.20) e (3.21) tratam de garantir a conectividade da reserva e

dos lotes nao reservados. Enquanto que para o agendamento de colheitas, a restricao (3.22) impoe

os limites superior e inferior do volume de madeira a ser colhido em cada perıodo, e a restricao (3.23)

garante a restricoes de adjacencia de URM.

A primeira restricao que relaciona os modelos (URM e RCC-nR), parte da restricao (3.24) que

restringe a variavel xik para binaria, uma vez que essa variavel representa tanto para colheita, como

para reserva.

Por fim e para completar a formulacao, e necessario restringir que cada lote xit nao seja colhido em

33

Maximizar∑t∈T

∑i∈L

`itxit (3.17)

Minimizar∑i∈L

Diγxiγ (3.18)

Sujeito a:

∑i∈L

Qixiγ ≥ Q∗ (3.19)

xjk ≤∑i∈Nj

Dik<Djk

xik ∀ k ∈ {γ, α}, j ∈ L nao adjacente a k (3.20)

xiα 6= xiγ ∀ i ∈ L (3.21)

It ≤∑i∈L

βitxit ≤ St ∀ t ∈ T (3.22)

xit + xjt ≤ 1 ∀ i > j, i ∈ L, j ∈ Ni, t ∈ T (3.23)

xik ∈ {0, 1} ∀ i ∈ L, k ∈ T ∪ {γ, α} (3.24)

mais de um perıodo ou que seja reservado. Para este caso, fez-se uso da restricao (3.10) do modelo

URM para dar origem a restricao (3.25). Esta restricao permite garantir que se o lote e colhido (no

maximo em um perıodo) jamais deve ser reservado e vice-versa.

xiγ +∑t∈T

xit ≤ 1 ∀ i ∈ L (3.25)

Apos os testes, apercebeu-se pela estrutura paisagıstica que quando a instancia possui qualidades

superior que o exigido pelos limites do volume de madeira e qualidade da reserva, passa a existir lotes

nao colhidos e nao reservado (de acordo a Figura 3.6(a), esses lotes sao denominados de lotes livre).

Os lotes livres, continuam a ter acesso livre sem ter de passar pela reserva, mas estaria melhor

se fossem aproveitados para acrescer qualidades a reserva. Esta avaliacao deu origem a substituicao

da restricao (3.25) pela restricao (3.26) para impor aos lotes que sejam colhidos ou reservados. Os

34

(a) Colheita e reserva com a restricao (3.25) (b) Colheita e reserva com a restricao (3.26)

Figura 3.6: Colheita em tres perıodos e criacao de reserva. A cor verde simboliza a reserva, a branca a zona livree as restantes cores os perıodos colhidos.

resultados paisagısticos e tal ilustrado na Figura 3.6(b).

xiγ 6=∑t∈T

xit ≤ 1 ∀ i ∈ L (3.26)

O modelo com a restricao (3.25) passara a ser denominado de Colheita e Reserva Compacta (CRC),

enquanto que com a restricao (3.26) se denominara de Colheita e Reserva Compacta Total (CRC-T).

Quanto aos modelos CRC e CRC-T, nao e determinado qual a melhor paisagisticamente. Depen-

dendo dos objectivos de quem utiliza, ditara o melhor modelo para a solucao. Para esta dissertacao,

tanto uma como outra apresentam solucoes optimas que serao avaliadas no Capıtulo 4.

3.4 Resumo

Este Capıtulo apresentou o desenvolvimento das formulacoes que garantem a proteccao do habitat

e obtem o maximo lucro de colheita de madeira. Para a solucao, foi apresentada uma formulacao multi-

objectivo que combinou a formulacao para reserva compacta (proteccao do habitat das especies) e a

formulacao para o agendamento de colheitas.

A solucao desenvolvida para a criacao de reservas conectadas e compactas baseou-se na solucao

ILP apresentada por Onal et al. [Onal et al., 2016] por apresentar restricoes de adjacencias muito similar

ao pretendido. Apos modificacoes e avaliacoes, obteve uma formulacao que cria reserva com lotes ilha.

Os lotes ilhas motivou a criacao de duas solucoes, a destacar o modelo RCC com restricoes que so

preocupa-se com a reserva e o modelo RCC-nR que preocupa-se em conectar tambem os lotes nao

35

reservados.

Enquanto que para formulacao de agendamento de colheitas, considerou-se os modelos fundamen-

tais URM e ARM, utilizou-se a solucao ILP do modelo URM de Murray [Murray, 1999] e verificou-se

que seu comportamento e o ideal para integrar na multi-objectivo. No entanto, criou-se a hipotese de

ser possıvel obter bons resultados equivalentes ao modelo ARM, usando URM. Daı desenvolveu-se

um algoritmo que gera de forma estocastica paisagens descendente da instancia original e executada

no modelo URM (denominada de URM-S). Para avaliar esse resultado foi necessario implementar

o modelo GMU e verificou-se que URM-S apresenta resultados satisfatorios (a avaliacao e feita no

Capıtulo 4).

Por fim, foram escolhidas as formulacoes RCC-nR e URM, para reservas compactas e agendamento

de colheitas, respectivamente, com motivos justificados para a criacao da formulacao multi-objectivo.

Essa solucao multi-objectivo apresentou-se com dois modelos, a destacar o modelo CRC-T que nao

deixa lotes livre (colhe ou reserva) e o modelo CRC que depois de adquirir o optimo das suas funcoes

objectivo pode deixar lotes livre.

36

4Avaliacao dos Resultados

Conteudo

4.1 Componentes de Implementacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.2 Avaliacao dos Resultados para Reservas Compactas . . . . . . . . . . . . . . . . . . 42

4.3 Avaliacao dos Resultados para Agendamento de Colheita . . . . . . . . . . . . . . . 46

4.4 Avaliacao dos Resultados para Formulacao Multi-Objectivo . . . . . . . . . . . . . . 49

4.5 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

37

38

Este capıtulo e reservado para avaliacao e discussao dos resultados obtidos pelas formulacoes

desenvolvidas. Inicialmente e abordado sobre as componentes mais importantes que serviram para

implementacao e avaliacao dos resultados (Seccao 4.1). De seguida, nas Seccoes 4.2, 4.3 e 4.4 faz-se

as avaliacoes dos resultados das formulacoes para reservas compactas, agendamento de colheitas e

multi-objectivo, respectivamente. O capıtulo termina com um resumo na Seccao 4.5.

Os testes foram efectuados num PC com processador 1400 MHz CPU e 132 GB de memoria RAM.

4.1 Componentes de Implementacao

Para a avaliacao das formulacoes foram utilizadas varias instancias, quatro delas podem ser obtidas

no repositorio de instancias florestais da Forest Management Optimization Site (2017) (FMOS) 1, a

destacar o El Dorado, NBCL9 1.0, Shulkell e Hardwicke. As outras instancias, foram geradas pela

ferramenta denominada Gerador de Paisagem Florestal, da expressao em Ingles Forest Landscape

Generator (FLG) disponıvel online 2. A Tabela 4.1 apresenta as caracterısticas das instancias de acordo

ao numero de lotes e areas totais da instancia florestal.

Tabela 4.1: Caracterısticas das instancias.

Nome da instancia Area (hectare) Numero de LotesFLG 1 2.970 21FLG 2 2.990 57FLG 3 1.495 62FLG 4 1.495 63FLG 5 1.497 100FLG 6 2.098 203

Hardwicke 6.948 423Shulkell 4.499 1.039

El Dorado 21.135 1.363NBCL9 1.0 140.766 19.024

Obteve-se tambem instancias menores com a ferramenta FLG relativamente as da Tabela 4.1, tudo

com objectivo de facilitar na correcao das formulacoes e testes preliminares.

4.1.1 Ferramentas

De seguida apresentamos um breve sumario das ferramentas utilizadas para o desenvolvimento e

producao dos resultados.

ArcView: Software de informacao geografica, parte integrante do software ArcGIS 3. Foi utilizada no

processo de geracao das instancias, com o proposito de tornar funcional o gerador FLG.

1 http://ifmlab.for.unb.ca/fmos/2 http://ifmlab.for.unb.ca/fmos/tools/DistributeFLG.zip3 http://www.esri.com/arcgis/about-arcgis

39

Linguagem R: Ambiente e linguagem para graficos e calculos estatısticos [Maindonald and Braun,

2010]. Com o Ambiente de Desenvolvimento Integrado, da expressao em Ingles Integrated De-

velopment Environment (IDE) RStudio 4, a linguagem foi util para o tratamento das instancias e

visualizacao dos resultados.

SMT: Apesar das formulacoes desenvolvidas serem ILP (Capıtulo 3), e existirem muitos formalismos

para o implementar, decidiu-se o SMT por se tratar de um formalismo que combina varias teorias

(que poderia ser util se necessario).

Z3: Solver escolhido e utilizado para solucionar SMT neste trabalho. Existem varios Solvers para

SMT (e.g. Yices [Dutertre, 2014], CVC [Barrett et al., 2011] e MathSAT [Cimatti et al., 2013]),

mas, Z3 tem recursos para formulacoes multi-objectivo uteis para o trabalho (fronteira de Pareto

e objectivos box).

4.1.2 Dados e Requisitos

Todas as instancias adquiridas, tem suas particularidades quanto ao numero de ficheiros e estrutura

interna. De modo a uniformizar e facilitar a entrada de dados, as instancias tiveram um processo de

transformacao que implicou, a definicao do numero de ficheiros para dois, inclusao de dados bem

definidos (novos atributos) e exclusao dos dados desnecessarios.

Figura 4.1: Diagrama do processo de preparacao das instancias.

Para compreensao do processo de transformacao, foi preparado um diagrama ilustrado na Fi-

gura 4.1. Entendemos os retangulos por fases do processo, com inıcio nas origens das instancias

e as setas direcionais indicarem as fases seguintes.

Em cada fase, sucede-se:

FLG e FMOS: As instancias com origem da FMOS, depois da avaliacao visual, e verificar-se con-

sistencia no conteudo, passa para fase seguinte. Quanto ao FLG, por se tratar de um pacote

dependente, foi necessario utilizar a ferramenta ArcView para gerar as instancias e so assim pas-

sar para a proxima fase.

4 https://www.rstudio.com

40

R: Faz-se recurso da linguagem R para o tratamento das instancias manualmente. Esta fase trans-

forma a entrada (exclui o desnecessario) para uma saıda homogenea, independentemente das

diferentes entradas de dados.

Unifica: Na fase anterior, os dados sao extraıdos separadamente, o que da origem a varios ficheiros

com os dados. Razao que incentivou criar uma pequena rotina para unificar esses ficheiros e ter

como saıda o ficheiro da fase seguinte.

Lotes: Apos unificar o ficheiro, gera a saıda do primeiro ficheiro a ser utilizado como instancia valida

e constituıdo com a estrutura de dados encontrada na Tabela 4.2. Antes dessa estrutura, o fi-

cheiro tem uma linha (primeira linha, nao representada) composta por 4 campos separados com

espacos, nomeadamente o numero de lotes, a qualidade mınima da reserva a ser obtida e por

fim dois campos que indicam os lotes centro da reserva e o centro da nao-reserva (sobre os lotes

centro, o Capıtulo 3 explica com mais propriedade).

Tabela 4.2: Estrutura da instancia obtida em Lotes.

ındice area coordenada ponto x coordenada ponto y qualidade do lote total vizinhos vizinhos

De forma pragmatica, descrevo os campos menos obvios existente na Tabela 4.2. Todos os

dados de uma linha, estao afectos ao lote indicado no campo ındice, assim sendo, os campos

coordenada ponto x e coordenada ponto y juntos formam a coordenada do centro do lote, utilizada

para calcular a distancia entre lotes.

Complemento: O resultado de Lotes e usado como um dos ficheiros de entrada, mas a instancia e

composta por dois ficheiros. Nesta fase, utiliza-se o conteudo de Lotes e cria-se um segundo

ficheiro que contem parte dos dados para o problema do agendamento de colheitas.

Colheita: A Tabela 4.3 ilustra a estrutura de dados desse ficheiro, a semelhanca do Lotes, este tambem

tem uma linha primaria, composta por numero de lotes, numero de perıodos por colher e um

conjunto de pares, nomeadamente os limites inferior e superior de volume de madeira permitido

a ser colhido em cada perıodo.

Tabela 4.3: Estrutura da instancia obtida em Colheita.

lucro do perıodo 1 volume do perıodo 1 ... lucro do perıodo n volume do perıodo n

Caso um lote seja selecionado para colheita, a estrutura de dados da Tabela 4.3 mostra o volume e

lucro que pode ser obtido em cada um dos perıodos.

41

4.2 Avaliacao dos Resultados para Reservas Compactas

Para as formulacoes para reservas conectadas e compactas, desenvolveu-se os modelos RCC

(Subseccao 3.1.1) e RCC-nR (Subseccao 3.1.2). Nos testes efectuados se verificou resultados com

configuracoes de reservas aceitaveis e que cumprem com a criacao das reservas conectadas e com-

pactas (ver Figura 4.2). No entanto, trata-se de duas solucoes e que possuem suas particularidades,

algumas melhores que outras que sao discutidas na Subseccao 4.2.1.

(a) Modelo RCC, 30%de qualidade.

(b) Modelo RCC-nR,30% de qualidade.

(c) Modelo RCC, 60%de qualidade.

(d) Modelo RCC-nR,60% de qualidade.

Figura 4.2: Reservas Conectadas e Compactas.

4.2.1 Modelo RCC vs Modelo RCC-nR

Relativamente as restricoes, o modelo RCC e caracterizado pela restricao (3.6), que impoe reservar

os lotes a volta do centro, ao passo que o modelo RCC-nR impoe conectividade para a reserva e para os

lotes nao reservados (caracterizada pela restricao (3.8)). O modelo RCC tem variaveis para a reserva

e RCC-nR tem tanto para a reserva, como para a nao-reserva.

Pelo facto de RCC-nR avaliar os lotes nao reservados, implicou que tivesse duas vezes mais

variaveis que o modelo RCC. Considerando que o numero de variaveis e linear no numero de lotes

das instancias.

Quanto ao aspecto paisagıstico, se verificou que RCC criar reservas com uma configuracao que

tende a forma circular, pode ser observada nas Figuras 4.2(a) e 4.2(c). A medida que a qualidade da

reserva cresce (mais de 40% do total da floresta), implica uma reserva maior e desconecta os lotes

nao reservados (ver Figura 4.2(c), com 60% de qualidade). Esta caracterıstica tambem e observada

quando o centro da reserva e indicado para lotes proximos ao extremo da paisagem, mesmo quando a

qualidade da reserva e inferior a 40% (no Capıtulo 3, se verifica na Figura 3.2).

O modelo RCC-nR, devido a sua caracterıstica, liga os lotes nao reservados independentemente

da qualidade mınima definida para se calcular a reserva. A sua configuracao paisagıstica nao tem um

padrao tao definido como da RCC, mas garante a criacao de reservas compactas e sem caminhos

42

(a) Instancia FLG 4, modelo RCC e a linha azul e o modelo RCC-nR a linha vermelha.

(b) Instancia FLG 5, modelo RCC e a linha azul e o modelo RCC-nR a linha vermelha.

Figura 4.3: Tempo de execucao para reservas conectadas e compacta, RCC vs RCC-nR. O eixo vertical re-presenta o tempo em segundos e o eixo horizontal representa o percentual da qualidade mınima dareserva por calcular.

estreitos (ver Figuras 4.2(b) e 4.2(d)).

O tempo de execucao, e influenciado pelo tamanho das instancias e a qualidade mınima da reserva.

Se verificou que quando a qualidade mınima varia entre 30% a 70%, relativamente ao total de quali-

dade que a floresta oferece, encontra-se o tempo mais elevado no calculo da solucao optima (ver as

Figuras 4.3(a), 4.3(b) e 4.4(a)), com maior incidencia a variar na qualidade mınima entre 40% a 60%.

De acordo com os testes, se verificou na generalidade que o modelo RCC e relativamente mais

rapida que RCC-nR no que refere ao calculo da optimalidade. As Figuras 4.3(a), 4.3(b) e 4.4(a) ilustram

os tempos das execucoes em segundos para as qualidades mınimas em percentagem indicada pelo

conjunto {10, 20, 30, 40, 50, 60, 70, 80, 90}. Verifica-se que a solucao RCC-nR (linha vermelha) acima

da solucao RCC. Na Figura 4.3(a), a solucao RCC-nR esteve sempre acima e teve um tempo maximo

de 14 segundos para cada qualidade, enquanto que a solucao RCC precisou apenas 4 segundos. Para

43

(a) Instancia FLG 6, RCC e a linha azul e RCC-nR a linha vermelha.

(b) Instancias FLG 5 e FLG 6, observa-se o numero de lotes reservado, soma dasdistancias e qualidade da reserva.

Figura 4.4: Tempo e qualidade para reservas conectadas e compacta, RCC vs RCC-nR.

a Figura 4.3(b), apenas com 80% da qualidade mınima e que a solucao RCC-nR foi dominada, mas

para cada qualidade precisou de 100 segundos no maximo, enquanto que 40 segundos foi o tempo

maximo para RCC. Por fim, na Figura 4.4(a) se verifica que RCC-nR precisou mais de 1 hora para

obter o optimo, enquanto que RCC, para 50% e 60% nao calculou o optimo em menos de 6 horas, mas

a solucao de RCC-nR foi mais demorada na maioria das qualidades (ver Figura 4.4(a), nao e ilustrado

o tempo de RCC para 50% e 60%).

Um outro aspecto a considerar, e o numero de lotes que cada modelo selecciona para a reserva,

a soma das distancias dos lotes da reserva relativamente ao centro e a qualidade obtida pela reserva.

Relativamente ao numero de lotes reservados, o modelo RCC-nR reserva um numero inferior de lotes,

e se verifica que obtem a qualidade e distancia dos lotes equivalente ao de RCC (ver Figura 4.4(b)).

O facto do modelo RCC-nR reservar menos lotes, obter uma qualidade equivalente e permitir que os

lotes nao reservados sejam conectados, atribui vantagens relativamente ao modelo RCC. Isso porque

44

(a) Instancia Hardwicke. (b) Instancias Shulkell.

Figura 4.5: Em 4 horas de execucao, RCC nao obteve uma solucao satisfeita para as instancias Hardwicke eShulkell.

a zona nao reservada e conectada e maior, beneficiando para outros fins (nesta dissertacao e benefico

para o agendamento de colheitas).

4.2.2 Trabalhos Relacionados

A formulacao de Carvajal et al. [Carvajal et al., 2013], impoe conectividade nas instancias com ate

1.000 lotes e calcula reservas cuja configuracao paisagıstica tem a forma longa e estreita, ao passo

que RCC e RCC-nR sao capazes de calcular reservas conectadas e compactas. No entanto, RCC e

RCC-nR sao incapazes de calcular solucoes optimas nas instancias com mais de 400 lotes (instancias

Hardwicke, Shulkell e NBCL9 1.0) num tempo limitado por 4 horas.

A abordagem aplicada para a conectividade e apenas estrutural. Se considerarmos florestas com

rios e lotes sem vizinhanca estrutural, verificou-se que RCC-nR nao se aplica por impor conectividade

tambem nos lotes nao reservados. A formulacao de Onal et al. [Onal et al., 2016], na qual foi baseada

para a construcao dos modelos, considera a conectividade estrutural e funcional, sendo capaz de re-

solver problemas que RCC-nR nao resolve. Mas, a solucao de Onal et al. [Onal et al., 2016] permite

a existencia de lotes ilhas dentro da reserva e RCC-nR nao. O modelo RCC, apesar de tambem nao

impor a conectividade funcional, e capaz de resolver instancias com lotes sem vizinhancas. Isso e

possıvel porque RCC impoe conectividade apenas na reserva, podendo deixar os lotes sem vizinhanca

e separados estruturalmente para zona nao reservada.

As Figuras 4.5(a) e 4.5(b) ilustram as solucoes obtidas com o modelo RCC, nao sao optimas e

calculadas em 4 horas de execucao. Os lotes de cor verde representam os lotes nao reservados, os

lotes escuros representam a reserva e os lotes de cor branca sao considerados de espacos vazios

(podendo ser considerado qualquer coisa excepto de lotes da floresta).

45

4.3 Avaliacao dos Resultados para Agendamento de Colheita

Sendo o modelo URM considerado um caso particular do modelo ARM, e por sua vez ser menos

difıcil obter resultados optimos, implementou-se uma abordagem URM-S com objectivo de calcular

solucoes de ARM. Neste caso, URM-S e avaliado com os resultados da implementacao GMU que

integra restricoes ARM.

4.3.1 Modelo GMU vs Modelo URM-S

GMU e um modelo que requer um numero exponencial de variaveis que varia conforme a relacao

entre o numero de lotes, area maxima permitida para colheita e o numero de perıodos. Este facto,

torna GMU exigente em capacidade de armazenamento no acto da execucao, enquanto que URM-S

necessita apenas de um numero linear de variaveis que varia de acordo ao produto do numero de lotes

e o numero de perıodos.

URM-S e um metodo desenvolvido que serve para calcular solucoes proximas do optimo, embora

nao se exclui a possibilidade de apresentar solucoes optimas.

Relativamente ao tempo de execucao, se verificou que GMU calcula solucoes optimas em menos

de 30 minutos para instancias com ate 21 lotes e limitado por 10% do volume de madeira colhida em

cada perıodo. Com parametros com valores superiores (numero de lotes e limite do volume), GMU e

incapaz de calcular solucoes optimas, mesmo considerando 3 horas como tempo limite. Para URM-S,

com as mesmas instancias que GMU, se verificou solucoes muito proximas do optimo. A Figura 4.6

ilustra o lucro optimo de GMU com a cor vermelha e o aproximado do optimo por URM-S (cor azul).

Figura 4.6: Lucro adquirido com a colheita, A solucao optima de GMU e representado pela cor vermelha e URM-Spela cor azul. Para cada instancia, variou-se os limites inferior e superior do volume de madeira. Oslimites variam em percentagem do total da floresta. URM-S, em 10% de volume, esteve a 0, 01% dedistancia para o valor optimo (o que nao e perceptıvel e da a impressao que tem o mesmo lucro).

Depois de limitar o tempo de execucao em 30 minutos, para ser obtida solucoes de GMU e ser

avaliada com URM-S (sempre em 30 minutos), com instancias com mais de 21 lotes, verificou-se que

46

(a) Instancia FLG 2, lucro adquirido.

(b) Instancia FLG 3, lucro adquirido.

Figura 4.7: Lucro adquirido com a colheita, GMU e representado pela cor vermelha e URM-S pela cor azul. Paracada instancia, variou-se os limites inferior e superior do volume de madeira. Os limites variam empercentagem relativamente ao total da floresta.

URM-S apresenta lucros superiores que GMU consegue calcular nesse intervalo de tempo. As Figu-

ras 4.7(a) e 4.7(b), com os limites dos volumes de madeira definidos por 10%, 30% e 50% do total da

floresta, se pode verificar que URM-S calcula lucros superiores relativamente a GMU.

Verificou-se ainda na Figura 4.7(b), com 50% de volume de madeira, GMU nao conseguiu calcular

uma solucao em 30 minutos e na Figura 4.8(b), GMU nao obteve solucoes independentemente do limite

do volume. Nestas mesmas instancias (Figuras 4.7(b) e 4.8(b)), se verifica que URM-S e capaz de

calcular solucoes. E ilustrada na Figura 4.8(a) a selecao dos lotes para instancia FLG 5 e 4 perıodos,

obtida por URM-S e que GMU foi incapaz.

De acordo com os resultados avaliados e discutidos, GMU nao e uma solucao recomendada para os

objectivos dessa dissertacao porque, alem do numero exponencial de variaveis, o tempo de execucao

para calcular solucoes optimas e superior a 5 horas para instancias maiores que URM-S calcula boas

solucoes em 30 minutos.

De forma geral, URM-S tem um numero de variaveis linear no numero de lotes e calcula melhores

47

(a) Instancia FLG 5 e 4perıodos (cada coridentifica um perıodo),agenda de colheitaproduzida por URM-S.

(b) Instancia FLG 5, lucro produzido por URM-S, GMU sem solucao em30 minutos.

Figura 4.8: Agendamento de colheita, GMU nao consegue calcular solucao em 30 minutos. GMU vs URM-S.

solucoes que GMU quando e limitado o tempo de execucao para 30 minutos. O modelo URM-S nao

permite provar optimalidade da solucao encontrada.

4.3.2 Trabalhos Relacionados

As formulacoes MILP apresentadas por McDill et al. [McDill et al., 2002], nomeadamente o Path

Algorithm e GMU, determina-se que Path Algorithm precisa de 5 vezes ou mais tempo de execucao

que URM para calcular solucoes e consequentemente, pelo facto de URM-S reduzir o tamanho das

instancias antes de executar e ter a mesma complexidade de URM, verifica-se que precisa menos

tempo de execucao para calcular solucoes. Verifica-se ainda que URM-S utiliza um numero de variaveis

inferior, por ser linear no numero de lotes e o Path Algorithm ser exponencial. Tambem foi determinado

por McDill et al. [McDill et al., 2002] que a formulacao MILP GMU precisa de mais tempo de execucao e

utiliza mais variaveis e restricoes que Path Algorithm, resultando em URM-S precisar de menos tempo

e ter um numero inferior de variaveis.

Foi feito um teste com tres perıodos de colheita e 40 hectares de area maxima com a instancia

El Dorado e verificou-se que URM-S em 2 horas foi capaz de apresentar solucoes quando se limita o

volume de madeira ate 25% por perıodo (ver Figura 4.9). Esta mesma instancia, foi objecto de teste

para Constantino et al. quando apresentaram as duas formulacoes ILP para ARM e resolvida usando

BnB [Constantino et al., 2008]. No entanto, as formulacoes de Constantino et al. precisaram de um

numero polinomial (quadratico) de variaveis, ao passo que URM-S e linear.

O modelo URM-S, apesar de se apresentar superior em qualidade do numero de variaveis e tempo

48

Figura 4.9: Solucao URM-S em 2 horas, 25% de volume de madeira e tres perıodos de colheita para instancia ElDorado.

de execucao (devido o facto de utilizar URM como a base), nao e capaz de provar optimalidade das

solucoes encontradas devido a componente estocastica utilizada na geracao das instancias de tamanho

menor que a instancia original.

4.4 Avaliacao dos Resultados para Formulacao Multi-Objectivo

Na Seccao 3.3 (Capıtulo 3), verificou-se que os modelos CRC e CRC-T proporcionam solucoes com

impacto no aproveitamento dos lotes, quando o limite superior do volume de madeira combinado com

a qualidade mınima da reserva nao impoe o aproveitamento de todos os lotes. A tıtulo ilustrativo, a

Figura 4.10(a) ilustra uma solucao com aproveitamento total dos lotes (proporcionado por CRC-T) e na

Figura 4.10(b) verifica-se que ha lotes nao aproveitados (proporcionado por CRC).

Os lotes livres (nao aproveitados) proporcionado pelo modelo CRC, sao aproveitados e adicionados

na reserva compacta pelo modelo CRC-T. Neste caso, CRC impoe na formulacao multi-objectivo,

(a) Solucao CRC-T. (b) Solucao CRC.

Figura 4.10: Solucao multi-objectivo, instancia FLG 1 e 3 perıodos. 50% de qualidade mınima para reserva e 25%de volume de madeira para colheita. A cor verde representa a reserva e a branca significa lotes livres,as restantes cores ilustram a colheita em diferentes perıodos.

49

Figura 4.11: Instancia FLG 1, tempo de execucao para o calculo da primeira solucao na fronteira de Pareto. Linhavermelha identifica CRC e a linha azul identifica CRC-T. As variacoes da instancia foi feita com aalternancia do volume de madeira e a qualidade da reserva (e.g. v50.q10 significa 50% de volume demadeira como limite e 10% de qualidade mınima da reserva).

solucoes com reservas compactas cuja qualidade e muito proxima a qualidade mınima. Enquanto que

o modelo CRC-T reaproveita todos os lotes livres para adicionar qualidades na reserva.

Relativamente ao numero de variaveis, a formulacao multi-objectivo combina as variaveis dos mo-

delos URM e RCC-nR. Ambos sao lineares no numero de lotes, portanto, a formulacao multi-objectivo

e linear.

Quanto ao tempo de execucao para calcular uma solucao, verificou-se que o modelo CRC precisa de

mais tempo para solucionar relativamente ao modelo CRC-T. A Figura 4.11 ilustra o tempo de execucao

para ambos, verifica-se a linha azul (modelo CRC-T) sempre abaixo da linha vermelha (modelo CRC).

Figura 4.12: Instancia FLG 2, tempo de execucao para o calculo da primeira solucao na fronteira de Pareto. Linhavermelha identifica CRC e a linha azul identifica CRC-T. Verifica-se que CRC nao resolve para umainstancia quando se limita o tempo para 8 horas.

50

Figura 4.13: Fronteira de Pareto para o modelo CRC, instancia FLG 1 e 3 perıodos. 50% de qualidade mınimapara reserva e 25% de volume de madeira para colheita. O eixo vertical representa a maximizacaoda funcao objectivo do agendamento de colheitas e o eixo horizontal representa a minimizacao dafuncao objectivo da reserva compacta.

Verifica-se ainda na Figura 4.12 para instancia FLG 2, um momento em que CRC-T demorou mais

tempo, mas que depois de variar o volume de madeira CRC foi incapaz de calcular solucao, ate mesmo

com 8 horas de tempo limite.

A formulacao multi-objectivo, com o modelo CRC, qualifica os lotes com tres possıveis estados,

nomeadamente para reserva, colheita e livre. Enquanto que o modelo CRC-T qualifica apenas com

dois estados (reserva e colheita). Esse aspecto podem ser verificados nas restricoes 3.25 e 3.26, e

impulsiona CRC-T ser relativamente mais rapida que CRC.

Outro aspecto que se verificou, e que CRC-T e tambem relativamente mais rapido em calcular a

fronteira de Pareto. Esse aspecto verificou-se para todos os testes, inclusive houve instancias que CRC

nao calculou nenhuma solucao da fronteira de Pareto enquanto que CRC-T calculou.

Na avaliacao do comportamento das solucoes de CRC e CRC-T para o calculo da fronteira de

Pareto, se verificou que ambos calculam para instancia FLG 1 (independentemente da variacao dos

parametros e limitado em 30 minutos). Enquanto que para as instancias FLG 2 e FLG 3, o tempo de

execucao nao nos permitiu verificar o modelo CRC, mas, CRC-T calculou a fronteira de Pareto. Se

verifica na Figura 4.13 a fronteira de Pareto para o modelo CRC com a instancia FLG 1, calculada em

um tempo inferior a 30 minutos e a Figura 4.14 ilustra a fronteira de Pareto para o modelo CRC-T, com a

mesma instancia e o mesmo limite superior de tempo de execucao. Se verifica claramente que CRC-T

tem um numero inferior de solucoes (ver Figuras 4.13 e 4.14).

Outro aspecto verificado nas Figuras 4.13 e 4.14 e o facto de CRC obter melhores solucoes para

as funcoes objectivo. Obtem um lucro superior e uma distancia inferior, relativamente ao que CRC-T

calcula. Para o modelo CRC-T, as solucoes da funcao objectivo da reserva, justifica-se com o reapro-

51

Figura 4.14: Fronteira de Pareto para o modelo CRC-T, instancia FLG 1 e 3 perıodos. 50% de qualidade mınimapara reserva e 25% de volume de madeira para colheita. O eixo vertical representa a maximizacaoda funcao objectivo do agendamento de colheitas e o eixo horizontal representa a minimizacao dafuncao objectivo da reserva compacta.

veitamento dos lotes livres, enquanto que para as solucoes da funcao objectivo da colheita e justificada

com a imposicao da conectividade dos lotes nao reservados.

Apesar da variacao do numero de solucoes na fronteira de Pareto nao serem uniformes para CRC-T

e CRC (comparativamente), pode-se verificar que CRC-T apresenta um numero inferior de solucoes

em mais ocasioes. Este aspecto pode ser verificado na Figura 4.15.

Na avaliacao dos modelos CRC e CRC-T, conclui-se que ambos tem um numero linear de variaveis

herdadas da combinacao dos modelos URM e RCC-nR. Apesar de se verificar optimalidade em ambos,

CRC-T e relativamente mais rapido no calculo da primeira solucao e na fronteira de Pareto. Verificou-se

tambem que o modelo CRC-T cria reservas com qualidades superior, fruto do aproveitamento dos lotes

livres de CRC.

Figura 4.15: Total de solucoes na fronteira de Pareto. A cor vermelha simboliza o modelo CRC-T e a azul o modeloCRC. Instancia FLG 1 com variacoes no volume de madeira e qualidade da reserva (e.g. v75.q10significa 75% de volume de madeira como limite e 10% de qualidade mınima da reserva).

52

Em termos da apresentacao paisagıstica, CRC deixa lotes livres quando os parametros (volume de

madeira e qualidade mınima da reserva) permitem, enquanto que CRC-T reaproveita esses lotes para

adicionar qualidades na reserva. Nesse aspecto, nao se verifica qual a melhor, mas quanto a perfor-

mance dos resultados obtidos da avaliacao, verifica-se que CRC-T e melhor em tempo de execucao e

em numero inferior de solucoes na fronteira de Pareto (generalizando).

4.5 Resumo

A avaliacao dos resultados foi dividida em 3 seccoes, de acordo com o tipo de problema que as

formulacoes resolvem. Relativamente a formulacao para criacao de reservas conectadas e compactas,

avaliou-se os modelos RCC e RCC-nR. RCC e um modelo com um numero de variaveis linear no

numero de lotes e que impoe restricoes de conectividade apenas para a reserva, enquanto que o

modelo RCC-nR tem o dobro das variaveis e impoe restricoes de conectividade para a reserva e para

os lotes nao reservados. Verificou-se que quando e limitado o tempo de execucao para 2 horas, ambos

nao calculam solucoes optimas para instancias com mais de 400 lotes e tambem que RCC-nR nao se

aplica a instancias que possuem lotes sem vizinhanca (ao passo que RCC aplica-se). Outro aspecto

verificado tem a ver com RCC ser relativamente mais rapido ao passo que RCC-nR calcula solucoes

que favorece a melhor utilizacao dos lotes nao reservados.

Quanto a formulacao para o agendamento de colheitas, avaliou-se os modelos URM-S e GMU. O

modelo URM-S e caracterizado por calcular solucoes de ARM com os recursos do modelo URM e

instancias geradas estocasticamente de uma instancia original de ARM. URM-S tem a mesma com-

plexidade de URM (restricoes e numero de variaveis) para as instancias geradas. O modelo GMU e

caracterizado por definir as variaveis a partir dos conjuntos de todas as combinacoes de lotes contıguos

e restringidos por uma area maxima. GMU calcula solucoes optimas e serviu de metrica para avaliar o

modelo URM-S que nao prova optimalidade. Na avaliacao, verificou-se que URM-S e capaz de apre-

sentar solucoes de melhor qualidade quando o tempo e limitado em 30 minutos. Quando as instancias

tem pelo menos 100 lotes, verificou-se que GMU nao consegue calcular solucoes em 30 minutos, ao

passo que URM-S consegue encontrar solucoes aproximadas do optimo.

Por fim, na formulacao multi-objectivo avaliou-se os modelos CRC e CRC-T. Um lote para a

formulacao multi-objectivo, tem por default um entre dois estados, nomeadamente o estado reserva

ou o estado colheita. O modelo CRC-T impoe apenas esses dois estados para os lotes, enquanto

que CRC adiciona mais um estado (denominado de estado livre) e permite que alguns lotes sejam

desaproveitados e deixados livres. O modelo CRC-T mostrou-se relativamente mais rapido no calculo

da primeira solucao e da fronteira de Pareto. Verificou-se tambem que CRC-T apresenta um numero

inferior de solucoes na fronteira de Pareto em mais ocasioes.

53

54

5Conclusao

Conteudo

5.1 Trabalho Futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

55

56

O desenvolvimento industrial e um dos principais factores que contribuem para a destruicao do ha-

bitat da vida selvagem existente nas florestas, principalmente quando se faz recurso para aquisicao

de materia prima. A destruicao da vida selvagem e seu habitat e minimizada com a criacao das re-

servas florestais conectadas. Quando se pretende elaborar um agendamento de colheitas, e indis-

pensavel reservar lotes para constituir uma reserva para especies locais. Este trabalho desenvolveu

tres formulacoes afectas a colheitas e proteccao das especies, nomeadamente:

• Formulacao para o agendamento de colheitas que implementa restricoes que garantem uma co-

lheita balanceada para todos os perıodos e cuja funcao objectivo maximiza o lucro da colheita.

• Formulacao para a criacao de uma reserva conectada e compacta que garante a criacao de uma

reserva com qualidades necessarias para o habitat das especies.

• Formulacao multi-objectivo que combina as formulacoes anteriores e garante a criacao de um

agendamento para colheitas preservando dentro do possıvel o habitat das especies.

As formulacoes ILP desenvolvidas, foram implementadas e testadas no formalismo SMT com o sol-

ver Z3 da Microsoft. Este solver foi escolhido por disponibilizar as ferramentas uteis para formulacoes

multi-objectivo (e.g. fronteira de Pareto e objectivos box).

Na formulacao para o agendamento de colheitas, foi desenvolvido o modelo URM-S com uma com-

ponente estocastica que calcula solucoes do modelo ARM na complexidade de URM. Conclui-se que

o modelo URM-S e incapaz de provar a optimalidade das solucoes, mas num tempo limitado de 30

minutos calcula solucoes com qualidades superiores ao modelo GMU para instancias com mais de 21

lotes.

O modelo URM-S nao apresentou as caracterısticas esperadas para a formulacao multi-objectivo,

devido a componente estocastica e por nao provar optimalidade das solucoes. No entanto, esperava-se

que o modelo GMU fosse candidato ate que se verificou que sua complexidade nao e recomendavel

para os objectivos por atingir, entao, nao se descartou o modelo URM de Murray [Murray, 1999].

Relativamente a formulacao para reservas conectadas e compactas, foram desenvolvidos dois mo-

delos: o modelo RCC que impoe conectividade apenas para a criacao da reserva e o modelo RCC-nR

que impoe conectividade para a reserva e para os lotes nao reservados. Dos resultados conclui-se que

RCC e relativamente mais rapido no calculo das solucoes. No entanto, as suas solucoes podem separar

as zonas nao reservadas pela reserva e o total de lotes reservados e superior. Esta formulacao, inde-

pendentemente do modelo, cumpriu o objectivo de calcular solucoes com configuracoes paisagısticas

aceitaveis, ou seja, as reservas nao apresentam uma configuracao longa e estreita.

Uma configuracao paisagıstica aceitavel melhora o habitat das especies e influencia a sua prolifera-

cao. Como o modelo RCC-nR define a zona nao reservada como ligada, entao sera possıvel efectuar

57

a colheita dos lotes exteriores a reserva sem ter de entrar em lotes reservados para o habitat das

especies. Este aspecto do modelo RCC-nR o tornou candidato forte para a formulacao multi-objectivo.

A formulacao multi-objectivo combinou as formulacoes para o agendamento de colheitas e para

reservas conectadas e compactas. Por se tratarem de solucoes nao relacionadas, avaliou-se o melhor

par de modelos para a formulacao multi-objectivo.

O modelo URM para o agendamento de colheitas e o modelo RCC-nR para reservas conectadas

e compactas, foi o par utilizado para construcao da formulacao multi-objectivo. Foram desenvolvidos

dois modelos para a formulacao multi-objectivo. O modelo CRC com restricoes que permitem o nao

aproveitamento de alguns lotes e o modelo CRC-T que impoe colher ou reservar os lotes. Ambos sao

capazes de calcular a fronteira de Pareto. O modelo CRC-T mostrou-se relativamente melhor em tempo

de execucao, apresentou um numero inferior de solucoes e as suas funcoes objectivo calculam solucoes

com menos qualidade (relativamente ao lucro das colheitas e soma das distancias dos lotes para o

centro da reserva), mas conclui-se que a qualidade da reserva e melhor quando a funcao objectivo da

reserva e elevada.

O modelo CRC permite a ocorrencia de lotes livres e apresenta maior lucro na colheita, enquanto

que CRC-T nao permite tal ocorrencia e inclui esses lotes na reserva (acresce a qualidade da reserva

e aumenta a distancia dos lotes para com o centro). A abordagem de CRC-T reduz o lucro da colheita

influenciado pelo comportamento do modelo RCC-nR que impoe conectividade para a reserva e para

os lotes nao reservados.

5.1 Trabalho Futuro

Quando uma determinada especie nao necessita de grandes esforcos para se deslocar entre os

diferentes lotes conclui-se que para esta especie os lotes estao conectados de forma funcional. Os

rios, lagos, espacos subterraneos, pequenos desertos e zonas montanhosas, sao alguns factores que

influenciam o nıvel de dificuldade que uma determinada especie pode encarar para a sua deslocacao.

A formulacao para reservas conectadas e compactas e limitada pela conectividade estrutural/fısica e

nao preve aspectos de conectividade funcional. O modelo RCC-nR nao e aplicavel para instancias que

tenham lotes sem vizinhanca, devido a impor a conectividade da reserva e dos lotes nao reservados,

enquanto que o modelo RCC e aplicavel nessas instancias.

No entanto, a formulacao para reservas conectadas e compactas pode ser aplicada em problemas

com conectividade funcional. Para esta aplicacao, e necessario transformar a instancia de modo a

indicar as conectividades funcionais como estruturais para as especies. Assumindo que o objectivo e

criar uma reserva para uma especie, a transformacao seria feita em apenas tres passos:

1. Identificar a especie.

58

2. Agrupar lotes sem conectividade estrutural entre os quais a especie se possa deslocar facilmente.

3. Definir conectividade estrutural com os lotes mais proximos ou conectados de forma funcional.

Esta abordagem de transformar a instancia, pode ser aproveitada quando estamos perante uma

floresta cujas as zonas subterraneas sao consideradas como lotes diferentes dos lotes por cima desta

zona.

Relativamente aos aspectos verificados no desenvolvimento deste trabalho que nao foram imple-

mentados devido a questao de calendario, sumarizo-os como trabalho futuro:

• Relativamente a formulacao para reservas conectadas e compactas, construir um modelo capaz

de combinar a conectividade estrutural com a funcional. Onal et al. [Onal et al., 2016] desenvolveu

uma formulacao capaz de assegurar os dois tipos de conectividade separadamente, em que a

reserva permite a existencia de lotes nao reservados no interior da mesma.

• Para a formulacao para o agendamento de colheitas, foi desenvolvido o modelo URM-S que tem

uma componente estocastica ao gerar as instancias proveniente da instancia de ARM. Propoe-se

o desenvolvimento de um metodo heurıstico para a componente estocastica de URM-S, de modo

a garantir maior confianca e melhores resultados.

• O modelo para definir a qualidade das solucoes produzidas nesta dissertacao, requer outra solucao

equivalente de acordo com os valores optimos calculados. Por isso, e proposta a utilizacao de fer-

ramentas que facilitam a identificacao de um intervalo das solucoes quando nao sao optimas, de

modo a auferir ou definir as qualidades aceites (e.g. BnB).

• A formulacao multi-objectivo para o agendamento de colheitas aplica o modelo URM devido a

reduzida complexidade relativamente ao modelo ARM. Propoe-se um estudo de viabilidade da

integracao do modelo ARM (e.g. integracao de uma versao melhorada de URM-S).

• Por fim, propoe-se a avaliacao de todas as formulacoes utilizando outros formalismos. Quando foi

feito o estudo da literatura, verificou-se que as formulacoes LP sao maioritariamente resolvidas

na ferramenta CPLEX. Recomenda-se a avaliacao com os formalismos ASP [Lifschitz, 2016] e

PBO [Roussel and Manquinho, 2009], efetuando um estudo comparativo.

59

60

Bibliografia

[Asia-Pacific Forestry Commission, 1999] Asia-Pacific Forestry Commission (1999). Code of practice

for forest harvesting in Asia-Pacific. FAO Regional Office for Asia and the Pacific (RAP).

[Barrett et al., 2011] Barrett, C., Conway, C. C. L., Deters, M., Hadarean, L., Jovanovic, D., King, T.,

Reynolds, A., and Tinelli, C. (2011). Cvc4. Proceedings of the 23rd International Conference on

Computer Aided Verification, pages 171–177.

[Barrett et al., 2009] Barrett, C. W., Sebastiani, R., Seshia, S. A., and Tinelli, C. (2009). Satisfiability

Modulo Theories. In Biere, A., Heule, M., van Maaren, H., and Walsh, T., editors, Handbook of

Satisfiability, volume 185 of Frontiers in Artificial Intelligence and Applications, pages 825–885. {IOS}

Press.

[Billionnet, 2012] Billionnet, A. (2012). Designing an optimal connected nature reserve. Applied Mathe-

matical Modelling, 36(5):2213–2223.

[Bjørner and Phan, 2014] Bjørner, N. and Phan, A.-d. (2014). νZ - Maximal Satisfaction with Z3. Sccss,

30:1–10.

[Carvajal et al., 2013] Carvajal, R., Constantino, M., Goycoolea, M., Vielma, J. P., and Weintraub,

A. (2013). Imposing Connectivity Constraints in Forest Planning Models. Operations Research,

61(4):824–836.

[Cerdeira et al., 2010] Cerdeira, J. O., Pinto, L. S., Cabeza, M., and Gaston, K. J. (2010). Species

specific connectivity in reserve-network design using graphs. Biological Conservation, 143(2):408–

415.

[Cimatti et al., 2013] Cimatti, A., Griggio, A., Schaafsma, B. J., and Sebastiani, R. (2013). The Math-

SAT5 SMT solver. In Chechik, M. and Raskin, J.-F., editors, Lecture Notes in Computer Science

(including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vo-

lume 7795 LNCS of Lecture Notes in Computer Science, pages 93–107. Springer Berlin Heidelberg,

Berlin, Heidelberg.

61

[Constantino et al., 2008] Constantino, M., Martins, I., and Borges, J. G. (2008). A New Mixed-Integer

Programming Model for Harvest Scheduling Subject to Maximum Area Restrictions. Operations Re-

search, 56(3):542–551.

[Cormen et al., 2009] Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction

to Algorithms. Computer science. MIT Press, 3rd edition.

[de Moura and Bjørner, 2008] de Moura, L. and Bjørner, N. (2008). Z3: An Efficient SMT Solver. In

[cited 2010 July]; Available from:http://research.microsoft.com/projects/Z3, volume 4963 LNCS, pages

337–340.

[Dilkina et al., 2016] Dilkina, B., Houtman, R., Gomes, C. P., Montgomery, C. A., Mckelvey, K. S., Ken-

dall, K., Graves, T. A., Bernstein, R., and Schwartz, M. K. (2016). Trade-offs and efficiencies in optimal

budget-constrained multispecies corridor networks. Conservation Biology, 31(1):192–202.

[Dutertre, 2014] Dutertre, B. (2014). Yices 2.2. In Biere, A. and Bloem, R., editors, Computer-Aided Ve-

rification (CAV’2014), volume 8559 of Lecture Notes in Computer Science, pages 737–744. Springer.

[Igor Griva, 2009] Igor Griva, Stephen G. Nash, A. S. (2009). Linear and Nonlinear Optimization. Society

for Industrial and Applied Mathematics (SIAM, 3600 Market Street, Floor 6, Philadelphia, PA 19104,

second edition.

[Lifschitz, 2016] Lifschitz, V. (2016). Answer Sets and the Language of Answer Set Programming. AI

Magazine, 37(3):7–12.

[Maindonald and Braun, 2010] Maindonald, J. and Braun, W. J. (2010). Data Analysis and Graphics

Using R. Cambridge University Press.

[McDill et al., 2002] McDill, M. E., Rebain, S. A., and Braze, J. (2002). Harvest scheduling with area-

based adjacency constraints. Forest Science, 48(4):631–642.

[Murray, 1999] Murray, A. T. (1999). Spatial restrictions in harvest scheduling. Forest Science, 45(1):45–

52.

[Onal and Briers, 2006] Onal, H. and Briers, R. a. (2006). Optimal Selection of a Connected Reserve

Network. Operations Research, 54(2):379–388.

[Onal et al., 2016] Onal, H., Wang, Y., Dissanayake, S. T., and Westervelt, J. D. (2016). Optimal de-

sign of compact and functionally contiguous conservation management areas. European Journal of

Operational Research, 251(3):957–968.

[Pareto, 1906] Pareto, V. (1906). Manuale di economia politica. Piccola Biblioteca Scientifica, Societa

Editrice.

62

[Rebain and McDill, 2003] Rebain, S. and McDill, M. E. (2003). Can mature patch constraints mitigate

the fragmenting effects of harvest opening size restrictions? International Transactions in Operational

Research, 10(5):499–513.

[Roussel and Manquinho, 2009] Roussel, O. and Manquinho, V. M. (2009). Pseudo-Boolean and Car-

dinality Constraints. In Biere, A., Heule, M., van Maaren, H., and Walsh, T., editors, Handbook of

Satisfiability, volume 185 of Frontiers in Artificial Intelligence and Applications, pages 695–733. {IOS}

Press.

63