Partição Retangular Mínima de um Retângulo com Pontos no …repositorio.unicamp.br/bitstream/REPOSIP/275993/1/... · 2018. 7. 22. · UNICAMI> CM-00102277-4 FICHA CATALOGRÁFICA

Partição Retangular Mínima de um Retângulo

com Pontos no Interior: Uma Abordagem em

Programação Linear Inteira

Cláudio Nogueira de Meneses

Dissertação de Mestrado

'··

. ' <:..,

Partição Retangular Mínima de um Retângulo com

Pontos no Interior: Uma Abordagem em


Este exemplar corresponde à redação final da Dissertação devidamente corrigida e defendida por Cláudio Nogueira de Meneses e aprovada pela Banca Examinadora.

Campinas, 11 de julho de 1997.

///~ L.~-.////~~~~ Pro f. Dr. Cid Carvalho de Souza

(Orientador)

Dissertação apresentada ao Instituto de Computação, UNICAMP, como requisito parcial para a obtenção do título de Mestre em Ciência da

Computação .

UNICAMI>

CM-00102277-4 FICHA CATALOGRÁFICA ELABORADA PELA

BIBLIOTECA DO IMECC DA UNICAMP

Meneses, Cláudio Nogueira de

M524p Partição retangular núnima de um retângulo com pontos no

interior: uma abordagem em programação linear inteira I Cláudio

Nogueira de Meneses-- Campinas, [S.P. :s.n.], 1997.

Orientador : Cid Carvalho de Souza

Dissertação (mestrado) - Universidade Estadual de Campinas,

Instituto de Computação.

1. Programaçio inteira. 2. Otimizaçio combinatória.. 3.

Otimização matemática. 5. Algoritmos. I. Souz., Cid Catnlho de. 11.

Universidade Estadual de Campinas. Instituto de Computação. III.

Título.

Instituto de Computação Universidade Estadual de Campinas

Partição Retangular Mínima de um Retângulo com

Pontos no Interior: Uma Abordagem em


Cláudio Nogueira de Meneses

Julho de 1997

Banca Examinadora:

• Prof. Dr. Cid Carvalho de Souza (Orientador)

• Prof. Dr. Abílio Pereira de Lucena Filho Laboratório Nacional de Computação Científica- LNCC

• Prof. Dr. Carlos Eduardo Ferreira Departamento de Ciência da Computação - USP

• Pro f. Dr. Pedro J ussieu de Rezende Instituto de Computação - UNICAMP

• Prof. Dr. Jorge Stolfi (suplente) Instituto de Computação- UNICAMP

Tese de Mestrado defendida e aprovada em 20 de junho de 1997

pela Banca Examinadora composta pelos Professores Doutores

Prof. Dr. Abílio Pereira de Lucena Filho

Prof. Dr. Pedro Jussieu de Réíende

@ Cláudio Nogueira de Meneses, 1997.

Todos os direitos reservados.

IV

Agradecimentos

Aos meus pais e irmãos pelo incentivo e carinho.

Ao professor Cid Carvalho de Souza pela orientação e amizade.

Aos amigos Sr. Adilson, Terezinha, Victor, Cristina e Sandra pelos vários momentos em família.

Aos amigos do grupo de otimização: Aminadab, Cristina, Eduardo U choa, Elder e Maria do Socorro pelas discussões sobre combinatória.

Ao professor Pedro J. de Rezende por ter contribuído com este trabalho.

Aos conterrâneos cearenses: Roberto Façanha e Gutemberg Guerra pelos divertidos almoços em seu apartamento.

Aos professores: Fernando Carvalho (UFC), José Everardo (UECE) e Roberta Almeida (UECE) por terem contribuído com a minha formação na graduação.

Ao Conselho Nacional de Desenvolvimento Científico e Tecnológico- CNPq e à Fundação de Amparo à Pesquisa do Estado de São Paulo- FAPESP pelo apoio financeiro (Processo

No. 96/0945-8).

v

Resumo

Dado um retângulo R e um conjunto finito nao vazio P de pontos no interior de R, estudamos o problema de particionar R em retângulos menores tal que nenhum ponto em P está no interior de qualquer retângulo da partição. O objetivo é minimizar a soma dos comprimentos dos segmentos de reta definindo a partição. Este problema é NP-difícil e uma generalização deste tem aplicação em projeto de circuitos VLSI. Neste

trabalho implementamos os principais algoritmos de aproximação que têm sido propostos

para este problema e propomos dois diferentes modelos de programação linear inteira. No primeiro modelo, onde variáveis são associadas a segmentos de reta, fazemos uma investigação do poliedro associado ao problema. Inequações lineares definindo facets são

apresentadas e resultados computacionais para um algoritmo Branch-and-Cut baseado

nestas inequações são reportados. O segundo modelo é baseado em uma redução do problema em questão para o problema set partitioning. Um algoritmo Branch-and-Price

para este modelo foi implementando e os resultados são comparados com aqueles obtidos pelo algoritmo Branch-and-Cut. Os experimentos computacionais realizados mostraram a viabilidade da resolução exata deste problema através de técnicas de programação linear

inteira, pelo menos para instâncias de médio porte (IPI = 200).

Vl

Abstract

Given a rectangle R in the plane anci a non empty finite set P of points in the interior of R, we stuciy the problem of partitioning R into smaller rectangles such that no point in P is interior to any rectangle of the partition. The goal is to minimize the sum of the lengths of the straight line segments ciefining the partition. This problem is JVP-harci anci a generalization of it have application in VLSI ciesign. In this work we implement the main approximation algorithms that have been proposeci for this problem anci propose two ciifferent integer programming mociels. In the first one, the variables are associateci to line segments anci we investigate the polyheciron associateci to this mociel. Facet ciefining inequalities are presenteci anci computational results obtaineci by a Branch-anciCut algorithm baseci on these inequalities are reporteci. The seconci mociel is baseci on a Set Partitioning formulation. A Branch-anci-Price algorithm for this mociel has been implementeci anci the results are compareci with those obtaineci by the Branch-anci-Cut algorithm. The computational results show that, at least for meciium sizeci instances (IPI = 200), the problem can be solveci exactly using Integer Programming techniques.

Vll

5 Modelando o RG-P como um Set Partitioning Problem 5.1 Set Partitioning Problem (SPP) ...... . 5.2 Modelando o Problema RG-P como um SPP

6 Resultados Computacionais 6.1 Algoritmo Branch-and-Cut

6.1.1 Política de Separação . 6.1.2 Seleção do Nodo 6.1.3 Regra de Branching . . 6.1.4 Deteção de Tailing-off

6.2 Algoritmo Branch-and-Price .

6.2.1 Conjunto Inicial de Colunas 6.2.2 Subproblema de Pricing .. 6.2.3 Estratégia de Seleção de Colunas 6.2.4 Regra de Branching .

6.3 Testes Computacionais . . . : . . . . . . 6.3.1 Instâncias ............ . 6.3.2 Resultados para o~ Algoritmos GZ85, GRZ93 e DPS86 6.3.3 Resultados para o Branch-and-Cut .

6.3.4 Resultados para o Branch-and-Price

7 Generalizações e Conclusões 7.1 Generalizações . 7.2 Conclusões ......... .

A Descrição do Algoritmo DPS86

Bibliografia

lX

54 54 55

62 62 63 63 63 63 64 64 64 65 66 67 67 67 68 71

80 80 82

85

88

Lista de Tabelas

2.1 Complexidades de problemas de decisão. . . . . . . . . . . . 6 2.2 Melhores algoritmos de aproximação para o problema RG-P. 9

6.1 Instâncias com pontos co-retilineares para um retângulo 20 x 20. 68 6.2 Instâncias com pontos não co-retilineares para um retângulo 20 x 20. 68 6.3 Instâncias com pontos não co-retilineares para um retângulo 50 x 50. 69 6.4 Instâncias com pontos co-retilineares para um retângulo 20 x 20. For-

mulação apenas com as classes de inequações I e II. . . . . . . . . . . . . . 71 6.5 Instâncias com pontos co-retilineares para um retângulo 20 x 20. Incluindo

todas as inequações das classes I, II, III, IV, V e VI na formulação. 72 6.6 Instâncias com pontos co-retilineares para um retângulo 20 x 20. For

mulação apenas com as classes de inequações I e I I. As classes III, IV, V e VI são incluídas na formulação somente quando são violadas em um nodo da árvore de branch-and-cut. . . . . . . . . . . . . . . . . . . . . . . . . . . 72

6. 7 Instâncias com pontos não co-retilineares para um retângulo 20 x 20. Formulação apenas com as classes de inequações I e II. . . . . . . . . . . . . . 73

6.8 Instâncias com pontos não co-retilineares para um retângulo 20 x 20. Incluindo todas as inequações das classes I, II, IV, V e VI na formulação. A configuração de pontos da classe III não ocorre em instâncias com P não co-retilinear. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

6.9 Instâncias com pontos não co-retilineares para um retângulo 20 x 20. Formulação apenas com as classes de inequações I e II. As classes IV, V e VI são incluídas na formulação somente quando são violadas em um nodo da árvore de branch-and-cut. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

6.10 Instâncias com pontos não co-retilineares para um retângulo 50 x 50. For-mulação apenas com as classes de inequações I e II. . . . . . . . . . . 74

6.11 Instâncias com pontos não co-retilineares para um retângulo 50 x 50. In-cluindo todas as inequações das classes IV, V e VI na formulação. . . 75

X

...

6.12 Instâncias com pontos co-retilineares para um retângulo 20 x 20. Resul-tados para estratégia de seleção com adição de no máximo 100 colunas ao restricted master LP, em cada iteração do algoritmo de geração de colunas. 77

6.13 Instâncias com pontos co-retilineares para um retângulo 20 x 20. Resul-tados para estratégia de seleção com adição da coluna com custo reduzido mínimo ao restricted master LP. . . . . . . . . . . . . . . . . . . . . . . . . 78

6.14 Instâncias com pontos não co-retilineares para um retângulo 20 x 20. Re-sultados para estratégia de seleção com adição de no máximo 100 colunas ao restricted master LP, em cada iteração do algoritmo de geração de colunas. 78

6.15 Instâncias com pontos não co-retilineares para um retângulo 20 x 20. Resul-tados para estratégia de seleção com adição da coluna com custo reduzido mínimo ao restricted master LP. . . . . . . . . . . . . . . . . . . . . . . . . 79

6.16 Instâncias com pontos não co-retilineares para um retângulo 50 x 50. Re-sultados para estratégia de seleção com adição de no máximo 500 colunas ao restricted master LP, em cada iteração do algoritmo de geração de colunas. 79

Xl

Lista de Figuras

1.1 (a) Uma instância do problema RG-P e (b) uma partição retangular de R. 2

2.1 Um polígono retilinear com três buracos (um é degenerado). . . . . . . . . 4 2.2 (a) Polígono retilinear com dois buracos (um é degenerado). (b) Uma

partição retangular do polígono em (a) (as linhas tracejadas são segmentos

de reta usados para particionar o polígono). . . . . . . . . . . . . . . . . . 5 2.3 (a) Uma instância I do problema RG-P. (b) Uma partição retangular (não

guilhotina) de I. (c) Uma partição guilhotina de I. . . . . . . . . . . . . . 5

2.4 (a) Instância do RP-HF. (b) Instância do RG-NLP. (c) Instância do RP-NLP. 7

2.5 (a) Instância do RG-P. (b) Instância do RP-P. (c) Instância do RG-RP. . . 7

2.6 (a) Instância do RP-RP. (b) Instância do RG-RPP. (c) Instância do RP-RPP. 7 2.7 Reduções entre problemas da Tabela 2.1 . . . . . . . . . . . . . . . . . . . 8 2.8 (a) Instância I=( x 0 , y0 , X, Y, P) = (0, O, 12, 8, {(2, 4), ( 4, 2), (8, 2), (10, 6)} ).

(b) Um corte composto. (c)-(d) As situações após a introdução dos cortes

simples passando pelos pontos (2,4) e (10,6) respectivamente. (e) Partição retangular com comprimento total igual a 24. . . . . . . . . . . . . . . . . 11

2.9 (a) Instância da Figura 2.5.a. (b) e (e) são "mid-cuts". (c),(d),(f) e (g) são "end-cuts". (h) Partição retangular com comprimento total igual a 32. 14

2.10 Uma partição guilhotina ótima, com comprimento total igual a 24, para a instância na Figura 2.6.a . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

4.1

4.2 4.3

4.4

4.5 4.6

Uma instância do RG-P com quatro pontos terminais e cinco pontos de Steiner. Os segmentos de reta tracejados definem a grade induzida pelos pontos terminais. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 (a) Exemplo de um joelho e (b) exemplo de uma ilha em um ponto terminal. 23 (a) Segmentos incidentes no ponto terminal i. (b) Suporte da inequação

xi + x 2 2: 1. (c) Retângulo suporte da inequação XI+ x 2 2: 1. 24 Segmentos de reta incidentes no ponto i. . . . . . . . . . . . . . . . . 26 Instância I= (0,0,6,4, {(3,2)}).. . . . . . . . . . . . . . . . . . . . . 27 Uma instância do problema RG-P. O ponto i é um ponto de Steiner. . 27

Xll

4. 7 Um retângulo com um ponto terminal i no seu interior e os segmentos .s e t incidentes em i. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.8 Um retângulo com um ponto de Steiner i no seu interior e os segmentos .s, t, u e v incidentes em i. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.9 O ponto i é um ponto terminal. Em (a) representamos uma solução para urna instância do RG-P tal que o vetor de incidência x = (x1 , ... , xM) =

(1, O, 1, 1, ... , 1). Em (b) tem-se urna solução com vetor característico x =

(1, O, 1, O, 1, 1, ... , 1), ou seja, x é a solução obtida de x fazendo x4 =O. . . 32 4.10 O vetor de incidência da solução em (a) é dado por x = (0, 1, O, 1, 1, ... , 1).

Em (b) estão representados os eixos de simetria do suporte da inequação x1 + x2 ~ 1, ou seja, provar algo sobre o segmento A equivale a provar algo para A'. Esta mesma equivalência é verdadeira entre os segmentos B e B', C e C', D e D'. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4.11 O ponto i é um ponto de Steiner. Em (a) representamos urna solução cujo vetor de incidência é x = (1, O, 1, 1, ... , 1). Em (b) tem-se u·rna solução com vetor característico x = (1, O, 1, O, 1, 1, ... , 1). . . . . . . . . . . . . . . . . . 34

4.12 Em (a) ternos urna solução com vetor característico x = (1, O, 1, 1, ... , 1). Em (b) representamos os eixos de simetria que passam pelo ponto de Steiner i. 34

4.13 Urna solução com vetor de característico x = (0, 1, ... , 1). . . . . . . . . . . 35 4.14 Três pontos terminais e um de Steiner formando um retângulo em G I ( P). . 36 4.15 Uma solução com vetor característico x. . . . . . . . . . . . . . 37 4.16 Uma solução com vetor característico x. . . . . . . . . . . . . . 37 4.17 (a) Urna solução com vetor de incidência x = (1,0,1,0,1,1, ... ,1). (b)

Urna solução com vetor de incidência x obtido de x fazendo xc = O. . . . . 38 4.18 (a) Uma solução com vetor de incidência x e o eixo de simetria da inequação

X 1 + X 2 + X 3 + X 4 ~ 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.19 Urna solução com vetor de incidência x = (0, 1, 1, O, 1, 1, ... , 1). Seja

xQ(xR) o vetor de incidência obtido de x removendo o segmento Q(R res-pecti varnente). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.20 Um ponto terminal e três de Steiner formando um retângulo em GI(P). Os pontos p2 ,p3 ,p4 e p5 são pontos terminais ou de Steiner. A linha pontilhada passando pelo ponto terminal representa o eixo de simetria. . . . . . . . . . 40

4.21 Solução com vetor de incidência x. Assuma xA ( xc, xE, xF, xG, xH) o vetor característico obtido de x ao remover o segmento A (C, E, F, G, H respectivamente). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.22 Solução com vetor de incidência x. . . . . . . . . . . . . . . . . . . . . . 41 4.23 (a) Solução com vetor de incidência x. (b) Solução com vetor de incidência

x .................... . 42

Xlll

4.24 Solução com vetor de incidência x. Os pontos p2, p3, p4 e p5 são pontos na borda do retângulo suporte da inequação x 1 + x2 + x 3 + x 4 2: 1. ..... .

4.25 Três pontos terminais e seis de Steiner em G I( P). A linha pontilhada representa o eixo de simetria. . . . . . . . . . . . . . . . . . . . . . . . . .

4.26 Solução com vetor de incidência x. Assuma xA (x 8 ,xc,xF,xr,x,:v1,xN') o

vetor de incidência resultante ao remover o segmento A (B, C, F, I, i\1!, N' respectivamente). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4. 27 (a) Solução com vetor de incidência x. Removendo o segmento E' ( K') de x obtemos o vetor de incidência xE' (xK'). (b) Uma solução com vetor

característico x. Removendo o segmento D' ( J') de x obtém-se o vetor de . 'd' . -D' (-J') 1nc1 enc1a x x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.28 Solução com vetor de incidência x. Ao remover o segmento G' (H') de x

obtém-se o vetor de incidência xG' (xH') . .... . 4. 29 (a) e (b) Soluções com vetores de incidência x e x. . . . . . 4.30 (a) e (b) Soluções com vetores de incidência x e x . .... . 4.31 (a), (b) e (c) Soluções com vetores de incidência x, x ex·.

42

43

45

46

46 47

47

48 4.32 Quatro pontos terminais e doze de Steiner em GI(P). As linhas pontilhadas

representam os eixos de simetria. . . . . . . . . . . . . . . . . . . . . . . . 49 4.33 Solução com vetor de incidência x. Assuma xA o vetor de incidência obtido

ao remover qualquer segmento A. . . . . . . . . . . . . . . . . . . . . . . . 50 4.34 Solução com vetor de incidência x. Removendo qualquer segmento rotu-

lado com uma letra, exceto os segmentos A, A', C, C', D, F', obtém-se uma solução com vetor de incidência x. Agora ao remover conjuntamente os

segmentos A, C, H ou A', C', H' de x obtém-se uma solução com vetor característico x-. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.35 Solução com vetor de incidência x. Removendo o segmento K (K') obtémse o vetor de incidência xK (xK'), ou removendo conjuntamente os segmen-

tos A, E, K (A', E', K') obtém-se o vetor x-. . . . . . . . . . . . . . . . . . 51

4.36 (a) Solução com vetor de incidência x. Removendo os segmentos G' e H' de x obtém-se uma solução com vetor de incidência x*. (b) Solução com vetor característico x. Removendo os segmentos K' e L' de x obtém-se uma solução com vetor de incidência x-. . . . . . . . . 52

4.37 (a) e (b) Soluções com vetores de incidência x e x. . . . . . . . . . . . . . . 52

5.1 (a) Uma instância I= (R, P) do problema RG-P. (b) Retângulos canônicos em R. (c) Retângulos definidos em R, sem pontos terminais no interior,

que contêm no mínimo um retângulo canônico (p.ex. o retângulo E contém os retângulos canônicos A e B). . . . . . . . . . . . . . . . . . . . . . . . . 56

XIV

.5.2 Uma instância I = (R, P) = (0, O, 2, 2, {1, 1}) do problema RG-P. Considere R1 com vértices (0, 0), (1, 0), (1, 1), (0, 1). Como R1 tem os lados [(0, 0), (1, O)] e [(0, 0), (0, 1)] que estão na borda de R, então estes lados terão

peso 2 no cálculo do perímetro ponderado, isto é, Cj = 2 * c[(O, 0), (1, O)]+ c[(1, 0), (1, 1)] + c[(1, 1), (0, 1)] + 2 * c[(O, 1), (0, O)], onde c[(t, u), (v, x)] representa o comprimento do segmento [(t,u),(v,x)]. Para o retângulo Rj tem-se que Cj = 6. . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.3 Retângulo com os segmentos incidentes em um ponto terminal i. Os 57

retângulos R1, R2

, R3 e R4 são retângulos canônicos. . . . . . . . . . 58

5.4 Retângulo com os segmentos incidentes em um ponto de Steiner i. Os t A 1 Rl R2 R3 R4 - t A 1 A • re angu os , , e sao re angu os canomcos. . ....... .

5.5 (a) Uma instância do problema RG-P e sua grade induzida. (b) Uma

solução ótima fracionária resultante da relaxação linear de Fseg· (c) Uma solução ótima inteira obtida da relaxação linear de FRet· Em (b) os valores

das variáveis associadas aos segmentos pontilhados tem valor 0.5. Em (b) e (c) os valores das variáveis associadas aos segmentos de reta "cheios" tem

59

valor 1. Os custos das soluções em (b) e (c) são 14.5 e 15, respectivamente. 61

7.1 (a) Polígono retilinear com um buraco no seu interior. Em (b) cada vértice côncavo do polígono em (a) está indicado por um círculo. . . . . . . . . . . 81

7.2 Polígono retilinear e sua grade induzida. Os pontos terminais são representados por círculos "cheios" e os pontos de Steiner por círculos vazios. . . 81

XV

Capítulo 1

Introdução

Geometria Computacional é um ramo da ciência da computação que estuda algoritmos para resolver problemas geométricos. Algoritmos geométricos exercem um importante papel em muitas áreas da ciência da computação, incluindo computação gráfica, projeto auxiliado por computador, projeto de circuitos VLSI (Very Large Scale Integrated circuit) e robótica. Vários problemas nestas áreas envolvem a manipulação de objetos geométricos. Uma vez que o tamanho da entrada para estes problemas pode ser bastante grande é essencial desenvolver algoritmos eficientes para eles.

Nos últimos quinze anos alguns pesquisadores da área de geometria computacional vêm demonstrando grande interesse por um problema conhecido como "Problema da Partição Retangular de um Retângulo com Pontos no Interior" (RG-P). O problema RG-P pode ser definido como:

INSTÂNCIA: Um retângulo R e um conjunto finito não vazio P de pontos localizados no interior de R.

SOLUÇÃO: Uma partição retangular de R, isto é, um conjuntoS de segmentos de reta que particionaR em retângulos tal que todo ponto em P está na borda de algum retângulo.

MEDIDA: O comprimento total dos segmentos de reta em S, isto é, L:ees ce, onde Ce é o comprimento do segmento de reta e.

A Figura l.l.a mostra uma instância do problema RG-P. O problema de encontrar um conjuntoS (solução viável para uma instância do RG-P)

cujo comprimento total dos segmentos de reta em Sé mínimo é NP-difícil (18]. A motivação para se estudar o problema RG-P é que uma generalização deste tem

aplicação em projeto de circuitos VLSI. Como mostraremos no capítulo 7 todos os resultados que obtivemos, neste trabalho, para o RG-P são facilmente aplicáveis para o problema mais geral.

1

1.1. Objetiv·os do Trabalho

• • • • • •

(a)

' ' ' ' ' • • r~-----•-r·-----1 ' ' ' ' ' ' ' ' ' ' . : . r-- ........ .! ............. ..

.. ........ .~ ................... ~ ' ' '

(.b)

Figura 1.1: (a) Uma instância do problema RG- P e (b) urna partição retangular de R.

1.1 Objetivos do Trabalho

Os objetivos deste trabalho são:

2

• Desenvolver algoritmos exatos para o problema RG-P baseados em programação linear inteira.

• Realizar um estudo computacional comparativo dos algoritmos de aprox1maçao, existentes na literatura, para o problema RG-P.

Os objetivos acima se justificam pelo fato da inexistência de estudos desta natureza

para o problema em questão.

1.2 Organização da Dissertação

Esta dissertação está organizada da seguinte maneira. No capítulo 2 fazemos urna revisão dos resultados apresentados na literatura para o problema RG-P. No capítulo 3 relembrarnos alguns conceitos de Programação Linear e Combinatória Poliédrica, e descrevemos, brevemente, alguns algoritmos normalmente usados na resolução exata de problemas combinatórios baseados em programação linear. No capítulo 4 realizamos um estudo poliédrico

do problema RG-P: apresentamos uma formulação em programação linear inteira 0-1 e mostramos alguns resultados sobre a estrutura facial do poliedro associado ao problema.

No capítulo 5 reduzimos o problema RG-P ao Set Partitioning Problem. No capítulo 6 apresentamos resultados computacionais. Finalmente no capítulo 7 estendemos os resultados apresentados nos capítulos 4 e 5 e apresentamos as conclusões deste trabalho.

Capítulo 2

Trabalhos Anteriores

Neste capítulo apresentamos uma revisão de alguns resultados encontrados na literatura, para problemas de particionamento de polígonos retilineares em retângulos. Na seção 2.1 daremos algumas definições básicas necessárias ao bom entendímento do texto desta

dissertação. Na seção 2.2 são apresentados os principais resultados referentes à complexidade de problemas de partição retangular de polígonos retilineares. Finalmente, as seções 2.3, 2.4 e 2.5 são dedicadas à descrição de alguns algoritmos de aproximação propostos

na literatura para o RG-P.

2.1 Definições

Definição 2.1 {25} Por Ed denotamos o espaço Euclidiano d-dimensional, isto é, o

espaço das d-tuplas (x 1 , .•• ,xd) de números reais Xi, i= l, ... ,d.

Definição 2.2 {25} Em E 2 um polígono é definido por um conjunto finito de segmentos de reta tal que todo extremo de um segmento é compartilhado por exatamente duas arestas

e nenhum subconjunto de arestas tem a mesma propriedade. Os segmentos são as arestas

e seus extremos são os vértices do polígono.

Definição 2.3 {25} Um polígono é simples se não existe um par de arestas não conse

cutivas compartilhando um ponto.

Definição 2.4 Um polígono retilinear é um polígono simples com a restrição adicional

que todos os seus lados são paralelos ou perpendiculares uns aos outros.

Definição 2.5 Um buraco é um polígono retilinear localizado no interior de um polígono

retilinear R e cujos lados são paralelos ou perpendiculares aos lados de R. Um buraco é chamado de degenerado se ele consiste de um único ponto (veja Figura 2.1).

3

2.1. Definições

Por todo o texto desta dissertação, quando dissermos que um polígono retilinear tem buracos, estes buracos são disjuntos dois a dois. A Figura 2.1 mostra um polígono retili

near com três buracos no seu interior.

•

Figura 2.1: Um polígono retilinear com três buracos (um é degenerado).

Definição 2.6 Seja A(F) a área no interior do polígono retilinear F e seja A(H) a

área dos buracos no interior de F. Uma partição retangular de F é um conjunto de

segmentos de reta que particiona a _área A (F) - A (H) em retângulos que não contêm como

pontos interiores qualquer buraco degenerado (veja Figura 2.2.b).

Definição 2. 7 Uma instância do problema RG-P é definida como: I= (R, P), sendo

R= ((x0 , y0 ), L, A), onde (x 0 , y0 ) é o vértice inferior esquerdo do retângulo R, L e A são

a largura e a altura, respectivamente, do retângulo R, P = {Pll ... , Pn} é um conjunto

finito não vazio de pontos no interior de R.

Definição 2.8 Uma partição retangular ótima de uma instância do problema RG-P

é uma partição retangular de comprimento total mínimo.

Definição 2.9 Uma partição guilhotina de uma instância do problema RG-P é uma

partição retangular, que é gerada por uma seqüência de cortes guilhotina. Cada corte guilhotina corta a parte conectada atual em duas partes menores ao longo de um seg

mento de reta horizontal ou vertical (veja Figura 2.3.c).

Note que toda partição guilhotina é uma partição retangular, mas o contrário não é verdade.

Definição 2.10 Uma partição guilhotina ótima é uma partição guilhotina de com

primento total mínimo.

Definição 2.11 Um conjunto finito não vazio P de pontos é dito ser co-retilinear se

pelo menos dois pontos em P estão localizados na mesma reta vertical ou horizontal.

2.1. Definições .j

•

(a) (b)

Figura 2.2: (a) Polígono retilinear com dois buracos (um é degenerado). (b) Uma partição retangular do polígono em (a) (as linhas tracejadas são segmentos de reta usados para particionar o polígono).

• • •

• (a)

I I I • I I I

~-,------·----1 I

----·------L-~ I I •

(b)

I I

I I

~------~--------~ I I I I I I

: . . : I I

I I

----L--------·------~

(c)

Figura 2.3: (a) Uma instância I do problema RG-P. (b) Uma partição retangular (não guilhotina) de I. (c) Uma partição guilhotina de I.

2.2. Resultados Importantes 6

2.2 Resultados Importantes

O problema de obter uma partição convexa de um polígono R qualquer (uma decomposição de R em polígonos convexos menores s 1 , s 2 , •.• , Sn tal que Ui;:1 Si= R e Si n Sj =

0, V i, j, i =J. j), usando o número mínimo de polígonos convexos menores, tem recebido considerável atenção [3, 9, 19, 27]. Em [18], Lingas et al. introduziram três novos aspectos ao problema: dois com relação à forma e um com relação ao critério de minimalidade. Primeiro, eles consideraram somente polígonos retilineares; tais polígonos podem ser sempre particionados em retângulos. Segundo, foi permitida a inclusão de buracos no interior destes polígonos. Finalmente, foi introduzido um novo critério de minimalidade: o comprimento total dos segmentos de reta usados para formar uma partição retangular. Os mesmos autores mostraram que a característica crítica de uma instância do problema de particionamento de polígonos retilineares é se ela tem ou não buracos. Na ausência de buracos, um algoritmo de tempo polinomial ([18]) existe para resolvê-la; caso contrário, o problema é NP-difícil (mesmo se os buracos são degenerados).

Resultados conhecidos sobre as complexidades computacionais dos problemas de decisão, correspondentes ao particionamento retangular de comprimento total mínimo de polígonos retilineares são mostrados na Tabela 2.1 [12]. As Figuras 2.4, 2.5 e 2.6 ilustram instâncias dos problemas na Tabela 2.1.

Problema Borda Pontos e buracos Complexidade RP-HF Polígono Retilinear Sem buracos (Hole Free) p RG-NLP Retângulo Pontos Não co-retilineares NP RP-NLP Polígono Retilinear Pontos Não co-retilineares NP RG-P Retângulo Pontos NP -completo RP-P Polígono Retilinear Pontos NP -completo RG-RP Retângulo Polígonos Retilineares NP -completo RP-RP Polígono Retilinear Polígonos Retilineares NP -completo

RG-RPP Retângulo Polígonos Retilineares e Pontos NP -completo RP-RPP Polígono Retilinear Polígonos Retilineares e Pontos NP-completo

Tabela 2.1: Complexidades de problemas de decisão.

A notação usada na Tabela 2.1 é a seguinte: por RP-NLP queremos dizer "Partição retangular de comprimento total mínimo de um Polígono Retilinear com Pontos (buracos degenerados) Não coretiLineares (Rectilinear Polygon with N on-corectzLinear Points)".

As outras abreviações são auto-explicativas. Na quarta coluna da Tabela 2.1 estamos usando a sigla P para dizer que o problema

2.2. Resultados Importantes

• • • • • • • • • • (a) (b) (c)

Figura 2.4: (a) Instância do RP-HF. (b) Instância do RG-NLP. (c) Instância do RP-NLP .

• • • • • • • T • • • • • • (a) (b) (c)

Figura 2.5: (a) Instância do RG-P. (b) Instância do RP-P. (c) Instância do RG-RP .

•

• • •• • T • • • •

•

(a) (b) (c)

Figura 2.6: (a) Instância do RP-RP. (b) Instância do RG-RPP. (c) Instância do RP-RPP.

2.2. Resultados Importantes 8

RP-HF pertence à classe P, isto é, é conhecido um algoritmo determinístico com complexidade de tempo polinomial no tamanho da entrada para o problema RP-HF. Este problema pode ser resolvido otimamente em tempo O(n4

), onde n é o número de vértices do polígono retilinear [18]. Por NP estamos querendo dizer que embora os problemas RG-NLP e RP-NLP pertençam à classe NP (admitem algoritmos não determinísticos de complexidade de tempo polinomial no tamanho da entrada) não se sabe se eles pertencem à classe P ou à classe de problemas NP-completos (supondo P :/= NP).

Gonzalez e Zheng [12] conjecturam que estes problemas são NP-completos. Eles usam o seguinte argumento: "como uma solução ótima para uma dada instância do RG-NLP poderia ser muito complexa e parece que não existe uma maneira de obter uma solução ótima sem uma busca exaustiva, conjecturamos fortemente que ambos os problemas são NP -completos".

No capítulo de Resultados Computacionais apresentamos alguns indicadores que nos fazem acreditar que os problemas RG-NLP e RP-NLP pertencem à classe NP-completo.

A Figura 2. 7 mostra um esquema de reduções polinomiais entre os problemas da Tabela 2.1, onde "problema A -+ problema B" significa que o problema A é polinomialmente redutível ao problema B [12].

RP-HF - RP-NLP - RP-P - RP-RP - RP-RPP

f f f f RG-NLP - RG-P - RG-RP - RG-RPP

Figura 2.7: Reduções entre problemas da Tabela 2.1

A partir deste ponto vamos nos concentrar em trabalhos anteriores que tratam exclusivamente do problema RG-P.

Pesquisadores da área de geometria computacional que estudam o problema RG-P têm concentrado esforços no desenvolvimento de algoritmos de aproximação para este problema. Estes algoritmos garantem que, para toda instância I do problema L(Eapx(I)) ~ c L(Eopt(I)), onde Eapx(I) é o conjunto de segmentos de reta resultante da aplicação do algoritmo de aproximação à instância I, Eopt(I) é o conjunto de segmentos de reta em uma solução ótima, c é uma constante e L(E(I)) é a soma dos comprimentos dos segmentos de reta em E(I). Não foi possível encontrar na literatura um estudo computacional comparativo destes algoritmos de aproximação.

Em [12], Gonzalez e Zheng apresentam um algoritmo de aproximação para o RG-P, que usa a técnica de divisão e conquista e gera soluções com L(Eapx(I)) ~ (3 + ..;3)L(Eopt(I)). A complexidade de tempo deste algoritmo é O(n2

), onde n é a cardinalidade do conjunto P. Levcopoulos [17] mostrou que é possível implementar este algoritmo em tempo O(n log n). Gonzalez e Zheng [14] apresentam um algoritmo de aproximação com com-

2.:3. Algoritmo de Aproximação GZ8.5 9

plexidade de tempo O(n4) que garante soluções com L(Eapx(I)):::; 3L(Eopt(I)). O limite

de aproximação é menor do que o do algoritmo em [12], entretanto, há uma substancial diferença entre as complexidades de tempo destes dois algoritmos. O segundo algoritmo ([14]) consiste de dois passos. No primeiro passo, o problema original é transformado no problema RP-HF. No segundo passo, um algoritmo com complexidade de tempo O(n 4 )

([18]) é usado para resolver RP-HF. A Tabela 2.2 mostra os melhores algoritmos de aproximação para resolver o problema RG-P.

Os resultados, quanto ao limite de aproximação, nas duas últimas linhas da Tabela 2.2 referem-se ao mesmo algoritmo. Em [8], é provado que um algoritmo de corte guilhotina ótimo (ver definição 2.10) gera uma partição retangular de uma instância I do problema RG-P, que tem comprimento total de no máximo duas vezes o valor de uma partição retangular ótima de I. Em [10], Gonzalez et al. apresentam uma prova mais simples para este resultado. Em [13], Gonzalez e Zheng provam que este mesmo algoritmo tem limite de aproximação igual a 1. 75 ao invés de 2.

Limite de Complexidade de Referência Método Aproximação Tempo

3 + V'3 O(n 2 ),0(n log n) [12, 17] Divisão e Conquista 4 O(n log n) [11] Divisão e Conquista 3 O(n4

) [14] Programação Dinâmica 2 O(n5

) [8, 10] Programação Dinâmica 1.75 O(n5

) [13] Programação Dinâmica

Tabela 2.2: Melhores algoritmos de aproximação para o problema RG-P.

2.3 Algoritmo de Aproximação GZ85

O algoritmo proposto em [12] por Gonzalez e Zheng usa a técnica de divisão e conquista.

De acordo com a definição 2.7 uma instância do RG-P é dada por: I= (x 0 , y0 , X, Y, P), onde (x0 , y0 ) é o vértice inferior esquerdo do retângulo R, X e Y são a largura e a altura, respectivamente, do retângulo R e P o conjunto de pontos terminais no interior de R.

Abaixo descrevemos o algoritmo apresentado em [12], que denotaremos por PartitionGZ, e na Figura 2.8 mostramos os passos de execução deste algoritmo para urna

instância do problema RG-P. Denotaremos um segmento de reta pelos pares de pontos extremos do segmento, isto

é, [(xi, Yi), (xj, Yj)] representa o segmento de reta com pontos extremos (xi, Yi) e (xj, Yj)·

2.3. Algoritmo de Aproximação GZ85 10

O conjunto Eapx denota a solução gerada pelo algoritmo. No algoritmo abaixo Eapx e inicialmente vazio.

O algoritmo PartitionGZ introduz a cada iteração um corte composto ou um corte simples. Um corte composto consiste de um par de segmentos de reta ortogonais ao eixo

x passando pelas abscissas Xc e xu.+l ou Xc e Xc- 1 (para c e u como definidos nos passos 5 e 6 do algoritmo). Um corte simples consiste de um segmento de reta ortogonal ao e1xo x passando pela abscissa Xc.

Procedimento PartitionGZ(xo,Yo,X,Y,P) Inicio

1. Seja n a cardinalidade do conjunto P; Se (n =O) então retorne;

2. Se (X < Y) então rotacione o retângulo em 90 graus e considere ( xo, Yo) ser o vértice inferior esquerdo do retângulo;

3. Rearrange os pontos tal que xo ~X! · · · ~ Xn;

4. x' = Xl(1 + V3);

5. c= min{i llx,- (xo + Xl2)1 = min{lx1 - (xo + Xl2)1, 1 ~ j ~ n} };

6. u. = max{i I Xi = Xc};

7. Caso

:xc está localizado à esquerda do centro do retângulo, Xc- xo ~ x' eu.< n:

Início r corte composto *I

Eap:& = Eap:& U {[(xc, yo), (xc, Yo + Y)], ((xu+l, Yo ), (xu+l, YO + Y)]};

P1 = {Pk E P I Xk < Xc, Pie= (xle,Yk)};

P2 = {Pie E P I x1e > Xu, Pie = (x~e, Yle)};

Xt = Xc- xo;X2 =X- (xu+l - xo);

PartitionGZ(ro,Yo ,X 1 ,Y,Pt );

PartitionGZ(xu+t•Yo ,X2 ,Y ,P2);

Fim

:xc está localizado à direita do centro do retângulo, X- (xc- xo) ~ x' e c> 1:

Início r corte composto *I

Eap:& = Eap:& U {[(xc, Yo), (xc, Yo + Y)], [(xc-1• Yo), (xc-1• Yo + Y)]}

P1 ={Pie E P I Xle < Xc-!.Pie = (x~e,Yie)};

P2 ={Pie E P I x1e > Xc,Pic = (xle,Yk)};

Xt = Xc-1- xo;X2 =X- (xc- xo);

PartitionGZ(xo,Yo ,Xt ,Y ,Pt );

PartitionGZ(xc,yo,X2 ,Y ,P2);

Fim

:Senão: /* corte simples *I

Início

Eap:c = Eap:r U {((r c, yo), (xc, Yo + Y)]};

2.3. Algoritmo de Aproximação GZ8.5

Pt = {Pk E P I Xk < Xc,Pk = (XkoYk)}; P2 = {Pk E P I Xk > Xc.Pk = (xkoyk)};

X 1 = X c - Xo ;X2 = X - (xc -X o);

PartitionGZ(ro,Yo ,Xt ,Y,Pt );

PartitionGZ(rc,Yo ,X2 ,Y ,P2 );

Fim

Fim Caso

FimGZ

•

• •

(a)

•

• I I

' I I (b)

I

I

' I I

•

. . --·--

(c) (d)

(e)

11

Figura 2.8: (a) Instância l=(xo,Yo,X,Y,P) = (0,0,12,8,{(2,4),(4,2),(8,2),(10,6)}). (b) Um corte composto. (c)-(d) As situações após a introdução dos cortes simples passando pelos pontos (2,4) e (10,6) respectivamente. (e) Partição retangular com comprimento total igual a 24.

Teorema 2.1 {12} Para qualquer instância I do RG-P o algoritmo PartitionGZ gera uma

solução Eapx tal que L(Eapx(I)) :'S: (3 + .J3)L(Eopt(I)).

2.4. Algoritmo de Aproximação GRZ93 12

Teorema 2.2 {11} A complexidade de tempo do algoritmo PartitionGZ é O(n log n),onde

n =IPI.

2.4 Algoritmo de Aproximação GRZ93

Em [11], Gonzalez et al. apresentam um algoritmo de divisão e conquista que gera soluções com limite de aproximação igual a 2d e complexidade de tempo O(dn log n) para o problema RG- Pd, uma generalização do RG-P no espaço d-dimensional.

O algoritmo abaixo é uma versão modificada do algoritmo apresentado em [11] para tratar do caso d = 2, isto é, do problema RG-P. Denotaremos por PartitionGRZ esta versão modificada.

O algoritmo PartitionGRZ introduz a cada iteração um "mid-cut" ou um "end-cut". Um "mid-cut" é um segmento de reta ortogonal ao eixo x que intercepta o centro do retângulo. Um "end-cut" é um segmento de reta ortogonal ao eixo x que contém o ponto "mais à esquerda" ou o ponto "mais à direita" em um subproblema. Por "mais à esquerda"("mais à direita") queremos dizer um ponto com menor (maior) abscissa. Um "mid-cut" é introduzido quando os dois subproblemas resultantes têm no mínimo um ponto cada. Caso contrário, um "end-cut" é introduzido.

Procedimento PartitionGRZ(xa,Yo ,X ,Y,P) Início

1. Seja n a cardinalidade do conjunto P;

2. Se (n =O) então retorne;

3. Se (X< Y)

então rotacione o retângulo em 90 graus e considere ( xo, Yo) ser o vértice inferior esquerdo do retângulo;

6. Caso

Início f* "mid-cut" *I Eapz = Eapz U {((xo + Xl2, Yo), (xo + Xl2, YO + Y)]};

X1 = Xl2- xo;X2 =X- (XI2- xa);

PartitionGRZ(xo,yo,Xl,Y,Pl);

PartitionGRZ(xo + Xl2,yo,X2,Y,P2);

Fim

: Senão : I* "end-cut" *I Início

c= {xi llxi- (xo + Xl2)i = min{ixJ- (xo + Xl2)1,1 ~ j ~ n}};

') --.0. Algoritmo de Aproximação DPS86 •

Eap:c = Eap:c U {((lc- (xo + X/2)1,yo).(lc- (xo + X/2)I.Yo + Y)]};

P1 = P1 \ {Pk I Pk E P1 e Xk =c, Pk = (xk.Yk)};

P2 = P2 \ {Pk I Pk E P2 e Xk =c, Pk = (xk•Yk)};

X1 =c- xo;X2 =X- (c- xo);

PartitionGRZ(xo,Yo ,X 1,Y ,P1 );

PartitionGRZ(c,yo,X2.Y,P2);

Fim

Fim Caso

FimGRZ

13

Teorema 2.3 {11} Para qualquer instância I do RG-P o algoritmo PartitionGRZ gera

uma solução Eapx tal que L(Eapx(I)) ~ 4L(Eopt(I)).

Teorema 2.4 {11} O algoritmo PartitionGRZ tem complexidade de tempo O(n log n)J

onde n =IPI.

Na Figura 2.9 mostramos os passos de execução do algoritmo GRZ93 para a instância da Figura 2.8.a.

2.5 Algoritmo de Aproximação DPS86

Em [8], Du et al. provam (Teorema 2.5) que é possível construir um algoritmo de aproximação, com garantia de performance igual a 2, baseado na idéia de corte guilhotina ótimo (veja def. 2.10), ou seja, dada uma instância I do problema RG-P este algoritmo gera "todas" as partições guilhotina de I e escolhe a de menor comprimento. Um resultado interessante mostrado neste artigo é que uma partição guilhotina ótima pode ser computada em tempo O(n5 ) usando programação dinâmica. Gonzalez e Zheng [13] provaram que este algoritmo tem limite de aproximação igual a 1.75, ou seja, no pior caso uma solução obtida por este algoritmo tem valor 75% maior do que o valor de uma partição retangular ótima.

Uma pergunta que surge é se existe um limite inferior ( lower bound) não trivial para este limite de aproximação. A resposta é sim e foi respondida por Du et al. [8], quando eles mostraram que liiiLn .... oo L(Eapx(I))j L(Eopt(I)) = 1.5, ou seja, eles apresentaram uma instância I do problema RG-P tal que o comprimento de uma partição guilhotina ótima de I é 50% maior do que o comprimento de uma partição retangular ótima de I. Estes autores conjecturam que este algoritmo tem na realidade limite de aproximação igual a 1.5, ao invés de 1. 75.

2.5. Algoritmo de Aproximação DPS86 14

• •

• •

• • • •

(a) (.b)

• • __ ._., ____ _

I I

• • • • I I

(c) (d)

• •

~~--.--+---------I I

• • I I

(e) (!)

I I

• I I

(B) (h)

Figura 2.9: (a) Instância da Figura 2.5.a. (b) e (e) são "mid-cuts". (c),(d),(f) e (g) são "end-cuts". (h) Partição retangular com comprimento total igual a 32.

2.5. Algoritmo de Aproximação DPS86 1.5

Teorema 2.5 (8, 13} Uma partição guilhotina ótima para o problema RG-P pode ser

construída em tempo O(n5), onde n =IPI.

Prova:

Seja g(xi,Xf,Yi,YJ) o valor do comprimento de uma partição guilhotina ótima para o retângulo r definido pelos pontos (vértices) (xi,Yi), (xi,YJ), (xJ,YJ), (xJ,Yi), onde xi(oux1) é o valor da abscissa de um ponto em P. Para qualquer retângulo r pode-se computar

g( X i, x f, Yi, Y!) recursivamente calculando todos os 2n cortes guilhotina (onde n é o número de pontos de P, que estão no interior do retângulo r) e então selecionar o de valor mínimo. Como existem O(n2

) combinações de Xi, X f e O(n2) combinações de Yi, YJ, isto implica

que existem O(n4) retângulos definidos por X i, x h Yi, Y!· Portanto, existem O(n 4 ) g' s que

precisam ser computados a fim de encontrar o comprimento de uma partição guilhotina ótima. Então, usando programação dinâmica, a complexidade de tempo total deste algoritmo é O(n5

). O

A partir da prova do Teorema 2.5 construímos o algoritmo descrito no apêndice A. A Figura 2.10 mostra uma partição guilhotina ótima para a instância na Figura 2.9.a.

Coincidentemente esta partição é uma partição retangular ótima.

(a)

Figura 2.10: Uma partição guilhotina ótima, com comprimento total igual a 24, para a instância na Figura 2.6.a

Note que os três algoritmos apresentados neste capítulo geram partições guilhotina, mas somente o algoritmo DPS86 é que garantidamente gera uma partição guilhotina ótima. No te também que para a instância na Figura 2.8.a, a partição gerada pelo algoritmo PartitionGZ é uma partição guilhotina ótima.

Capítulo 3

Programação Linear e Combinatória Poliédrica

Como pretendemos resolver o problema RG-P usando uma abordagem em Combinatória Poliédrica, relembramos alguns conceitos básicos de Programação Linear e Combinatória Poliédrica.

Os teoremas e definições abaixo foram compilados de (2, 7, 20, 29]. Um problema de Programação Linear (PL) pode ser definido como o problema de

otimizar uma função linear sobre uma região descrita por um conjunto de inequações e equações lineares. Os pontos nesta região formam o conjunto de soluções viáveis do problema PL. Tal problema pode ser escrito na forma de matriz como

min{ ex : Ax ::; b, x E IR~},

onde c E IRn' A é uma matriz m X n e b E JRm

Definição 3.1 Um conjunto X é convexo se dados x 1 e x 2 E X todos os pontos da

forma ax 1 + (1- a)x2 (combinação convexa) também pertencem a X, VO::; a::; 1.

Definição 3.2 A envoltória convexa de um conjunto arbitrárioS, Conv(S), é o menor

conjunto convexo que contém S.

Teorema 3.1 O conjunto de soluções viáveis X = { x E IR~ : Ax ::; b} para um problema

PL é um conjunto convexo.

Definição 3.3 O conjunto convexo X= {x E IR~ : Ax ::; b} é denominado um poliedro. Se X é limitado, i.e., se Vx E X satisfaz -w:::; Xj:::; w,V j E {1,2, ... ,n} para algum

w E IR+, então X é chamado de politopo.

16

17

Definição 3.4 Um vértice de um poliedro .1:' é qualquer ponto x E X o qual não pode

ser expresso como uma combinação convexa de outros pontos de X\ { x}.

Teorema 3.2 Se o valor ótimo de uma função linear num poliedro X Ç IRn é finito,

então ele é atingido em pelo menos um vértice. Se este for obtido em mais que um

vértice, então pode ser obtido também por qualquer ponto que seja uma combinação linear

convexa destes vértices.

Teorema 3.3 Um problema de PL onde os elementos da matriz A são racionais pode

ser resolvido em tempo polinomial sobre n, m e (), onde n é o número de variáveis do

problema, m é o número de restrições, e () é tamanho da maior representação binária de

um coeficiente da matriz A.

Definição 3.5 Seja S Ç IRn, 1r E IRn e 1r0 E IR. Uma inequação 1rx :::; 7ro é válida em

relação aS se S Ç {x E IRn l1rx:::; 7ro}.

Definição 3.6 Seja P Ç IRn um poliedro. Um conjunto F Ç P é uma face de P, se

existe uma inequação 1rx :::; 1r0 válida em relação a P, tal que F = P n { x l1rx = 1r0 }.

Dizemos que F é uma face própria de P se F =J. P; e F é não trivial se 0 =J. F =J. P. Se

1rx :::; 1r0 é válida em relação a P, então dizemos que F é a face induzida ou definida por 1ri :::; 1r0 •

Definição 3. 7 Um conjunto de pontos x1 , ..• , xk E IRn é afim-independente se a única

solução de I:f=1 aixi = O, I:f=1 ai =O, onde ai E IR, é a1 = · · · = ak =O.

Definição 3.8 A dimensão de um conjunto F, denotada por dim(F) é d se F contém

exatamente d + 1 vetores afim-independentes.

Definição 3.9 Um poliedro P Ç IRn tem dimensão plena se dim(P) = n.

Teorema 3.4 Seja P Ç IRn um poliedro de dimensão plena e F = { x E P I wx = w0 }

uma face de P definida pela inequação válida wx :::; w0 . São equivalentes:

(a) F é uma facet de P; (b) dim(F) = n- 1; (c) se 1rx:::; 1r0 , 1r =J. O, é uma inequação válida para P tal que F Ç {x E P l1rx = 7ro},

então existe a E IR, a > O tal que 1r = aw e 7ro = awo.

Teorema 3.5 Seja P = {x E IR~ : Ax :::; b, Dx = c} um poliedro. O conjunto de

inequações e equações definindo P é minimal se e somente se nenhuma equação de Dx = c

pode ser escrita como uma combinação linear das outras equações e toda inequação de

Ax :::; b representa uma facet distinta de P.

.'3.1. Programação Linear lnteira ( PLl) 18

3.1 Programação Linear Inteira (PLI)

Nesta seção discutiremos alguns métodos normalmente usados na resolução de problemas, que admitem uma formulação em programação linear, onde exigem-se soluções inteiras.

Os conceitos discutidos nesta seção foram compilados de [7, 21, 30]. Considere o problema de programação linear

min{cx: Ax:::; b, x E IR~},

onde c E IRn, A é uma matriz m X n e b E IRm. Se as variáveis são restritas a serem inteiros ( x E ~~ ao invés de x E IR~) o problema

é chamado de problema de Programação Linear Inteira. Além disso, se as variáveis são restritas a valores O ou 1, então temos um problema PLI 0-1. As soluções do problema PLI 0-1 são pontos (O - 1) n satisfazendo o sistema linear Ax :::; b.

Geralmente problemas PLI 0-1 são NP-difíceis. Uma maneira de atacar estes problemas é resolver suas relaxações lineares. Numa relaxação linear as restrições de integralidade são substituídas por restrições lineares. Existem duas abordagens clássicas para resolver problemas PLI 0-1 usando relaxações lineares: algoritmo de Planos-de-Corte Fracionário (APCF) e o algoritmo branch-and-bound ou enumeração implícita. Denotaremos por S o conjunto de soluções viáveis do problema PLI 0-1.

3.1.1 Algoritmo de Planos-de-Corte

APCF são baseados no uso de inequações válidas (cortes) para S. A cada iteração i de APCF, uma relaxação LPi do problema PLI é resolvida. Seja

xi uma solução ótima obtida ao se resolver a relaxação linear LPi. Se xi está em S, o algoritmo pára, retornando xi como uma solução ótima do problema PLI. Caso contrário, a relaxação deve ser melhorada. Para isto, encontra-se uma inequação válida 1rx :::; 1r0

para S que é violada por xi. Uma nova iteração é executada para a relaxação LPi+l,

obtida de LPi incluindo-se a inequação 1rx :::; 1r0 .

Seja zi e zi+l os valores das soluções ótimas de LPi e LPi+1 respectivamente, isto é, zi = cxi e zi+1 = cxi+l. Assumindo que o PLI é um problema de minimização, tem-se que zi+l ~ zi, ou seja, o lower bound fornecido pelo valor ótimo da relaxação linear cresce monotonicamente a cada iteração, aproximando-se do valor ótimo do PLI.

O estudo inicial de adição de inequações válidas para problemas PLI gerais foi feito por Gomory na década de 50. Embora o algoritmo proposto por ele sempre termine em tempo finito, as inequações que ele sugeriu para adicionar à formulação (cortes de Gomory) são pouco eficientes na prática, pois o algoritmo torna-se muito lento.

3.1. Programação Linear Inteira (PLI) 19

Mais tarde, percebeu-se que o motivo do insucesso obtido pela aplicação dos cortes de

Gomory, era decorrente do seu excesso de generalidade. Independente do problema PLI

que se esteja resolvendo, sempre é possível gerar um corte de Gomory que elimina uma solução contínua. No entanto, este corte pode não ser suficiente para capturar a estrutura

da envoltória convexa das soluções inteiras do PLI. Cortes com esta propriedade são o objeto de estudo da Combinatória Poliédrica que fez ressurgir, principalmente a partir da década de 80, o interesse pelos algoritmos de corte.

Note que pelos Teoremas 3.4 e 3.5 para termos uma descrição minimal da envoltória convexa das soluções inteiras do PLI precisamos encontrar inequações definindo facets

desta envoltória convexa. Este fato justifica o estudo da estrutura facial do poliedro

associado ao problema RG-P que apresentamos no próximo capítulo.

3.1.2 Algoritmo Branch-and-Bound

Branch-and-Bound são esquemas enumerativos fundamentados em duas operações básicas. A primeira é a decomposição do problema original em subproblemas. A segunda operação envolve o cálculo de limites inferiores e superiores ao valor da função objetivo. O propósito

é acelerar o processo de descarte de subproblemas que não podem gerar soluções promissoras, diminuindo, conseqüentemente, a enumeração.

Normalmente, a decomposição é construída recursivamente. Isto permite uma representação gráfica de todo o processo em termos de uma árvore de enumeração. Nesta

representação, os filhos de um dado nodo formam a decomposição da região viável de seu

pai. Em geral, para problemas PLI 0-1, a árvore de enumeração é uma árvore binária. Cada

nodo i da árvore corresponde a uma relaxação linear LPi do problema PLI definido em um subconjunto Si de S. Seja xi a solução ótima encontrada para LPi e zi = ex i. Dependendo

do valor de zi ( bound), o nodo i pode ser expandido ( branching) para outros dois nados

(seus filhos) ou pode ser cortado (ou podado), i.e, o subconjunto de soluções viáveis do nodo i é particionado em dois novos subconjuntos ou ele não será mais particionado

durante os passos seguintes do algoritmo. O algoritmo termina quando todos os nados estiverem podados. Retoma-se como solução do PLI, a solução inteira do nodo da árvore

com menor valor (para um problema de minimização) de função objetivo.

3.1.3 Algoritmo Branch-and-Cut

Seja Conv(S) a envoltória convexa do conjunto viável S. A envoltória convexa de Sé um poliedro e portanto, pode ser descrita por um sistema de inequações e equações lineares.

Se o sistema linear que descreve completamente Conv(S) está disponível, o problema

PLI pode, em princípio, ser resolvido eficientemente por programação linear, visto que

3.1. Programação Linear Inteira ( P LI) 20

todos os pontos extremos são soluções viáveis inteiras em S (veja Definição 3.4 e Teorema 3.3). Infelizmente, para problemas JYP-difíceis, geralmente o número de inequações de tal sistema é exponencial, no tamanho da entrada, e somente algumas inequações da descrição de Conv(S) são conhecidas.

Assuma, portanto que uma certa classe :F de inequações válidas para Conv(S) é conhecida. Além disso, dado um ponto qualquer x E IR~ assuma que dispõe-se de um algoritmo que procura por uma inequação em :F que é violada por x. Tal algoritmo é chamado uma rotina de separação para :F.

Branch-and-Cut é um método para resolver problemas PLI, que incorpora uma fase

de cutting planes em cada nodo da árvore de enumeração de um algoritmo de branch

and-bound. Na fase de cutting plane o algortimo só irá gerar inequações que pertençam à classe :F definida anteriormente.

Para cada nodo i da árvore de enumeração pi = {X E mn : Aix :::; b, o :::; X :::; 1} é o poli topo correspondente à relaxação linear LPi. Se xi é a solução ótima desta relaxação linear e ela tem variáveis fracionárias, a rotina de separação é diamada para procurar uma inequação violada em :F. Se a rotina de separação retoma uma inequação 1rx :::; 1r0 ,

então esta inequação é incluída no sistema de inequações definindo pi, e LPi é resolvido novamente. Isto é feito até que xi seja inteiro ou zi seja maior do que o atual upper bound

(supondo um problema de minimização) disponível, ou ainda se rotina de separação falhar em produzir uma nova inequação em :F que corte o ponto xi. Neste último caso, uma variável é escolhida para fazer um branching.

Aplicações bem sucedidas de algoritmos branch-and-cut para resolver problemas difíceis PLI 0-1, por exemplo, problema do caixeiro viajante [23, 24], serviram de motivação para o desenvolvimento de um algoritmo deste tipo para o problema RG-P. O sucesso de algoritmos branch-and-cut depende muito do conhecimento da estrutura de Conv(S).

Desta forma, neste trabalho estuda-se o poliedro inteiro ( envoltória convexa) correspondente ao problema RG-P, no intuito de obter classes de inequações :F, que permitam ao algoritmo encontrar soluções exatas em tempo computacional aceitável. Para tanto, precisamos inicialmente formular o problema RG-P como um problema de programação linear inteira. Esta formulação é discutida no próximo capítulo.

3.1.4 Algoritmo de Geração de Colunas

Quando tem-se um modelo, em programação linear, com um número muito grande de variáveis, resolver a relaxação linear do modelo completo pode ser praticamente impossível. Uma alternativa para resolver a relaxação linear deste modelo é usar um al

goritmo de geração de colunas (variáveis). Um algoritmo de geração de colunas começa com uma solução viável básica da re

laxação linear do modelo que se quer resolver. Esta solução inicial pode ser gerada usando

.3.1. Programação Linear Inteira (PU) 21

uma heurística. O algoritmo prossegue checando se existe alguma variável que não está na formulação e tem custo reduzido negativo (para um problema de minimização). Caso

exista alguma variável que satisfaça esta condição, então ela é incluída na formulação. A

nova formulação é otimizada usando um resolvedor de programação linear e repete-se o

processo de checagem de variáveis. Quando não existe uma variável com custo reduzido negativo, então a relaxação do linear do modelo completo foi resolvida.

3.1.5 Algoritmo Branch-and-Price

Um algoritmo Branch-and-Price consiste em incorporar uma fase de geração de colunas

em cada nodo da árvore de enumeração de um algoritmo Branch-and-Bound.

Em Barnhart et al. [1], o leitor encontra um texto bastante atual que trata dos vários aspectos envolvidos no desenvolmento de um algoritmo branch-and-price.

No capítulo 6 discutimos algumas questões importantes, que aparecem no desenvolvi

mento de um algoritmo branch-and-price.

Capítulo 4

Formulação e Estudo Poliédrico do Problema RG-P

Neste capítulo formulamos o problema RG-P usando programação linear inteira 0-1, pro

vamos que o poliedro associado a este problema tem dimensão plena e apresentamos algumas classes de inequações lineares que definem facets para este poliedro. Estas inequações serão incorporadas à formulação através de um algoritmo de planos-de-corte cujos

resultados são apresentados no capítulo 6.

Este capítulo está organizado da seguinte maneira. A seção 4.1 contém algumas de

finições que irão nos auxiliar na descrição da formulação PLI do RG-P. A seção 4.2 contém a formulação proposta por nós e apresenta dois teoremas fundamentais que servem para provar a sua corretude. A seção 4.3 descreve os estudos poliédricos que empreendemos para o problema RG-P. Ao nosso conhecimento, os resultados desta seção são originais.

4.1 Definições e Notações

Nesta seção daremos algumas definições adicionais que ajudarão a compreender a for

mulação PLI proposta para o RG-P.

Definição 4.1 Seja I= (R, P) uma instância do problema RG-P (veja definição 2. 7). A

grade induzida pelos pontos de P, denotada por GI(P), é o conjunto finito de segmentos

de reta definidos no interior de R pelas retas verticais e horizontais, que passam pelos

pontos de P. Diz-se que i é um ponto da grade induzida se i está na intersecção de duas

retas que definem segmentos de GI(P).

A Figura 4.1 mostra uma instância do problema RG-P e sua grade induzida.

22

4.1. Definições e iVotações 2:3 •

Definição 4.2 Em uma instância I do RG-P, os pontos que pertencem ao conjunto P são chamados de pontos terminais e os que não pertencem a P e estão em GI(P) são

chamados pontos de Steiner.

Na Figura 4.1 círculos cheios representam pontos terminais, enquanto círculos vazios representam pontos de Steiner.

Definição 4.3 Seja I = (R, P) uma instância do problema RG-P. Um conjunto C de

segmentos de GI(P) contém um joelho em um ponto i (terminal ou de Steiner) se o

número de segmentos em C que incidem em i é exatamente dois e estes segmentos são

ortogonais entre si (veja Figura 4 .2.a).

' ' --- ;--------;---<>------

' ' ' ---~ --------<>- ---+-------

' ' ' --- ~--- -----~--4- -----' ' ' ' ' ' ' ' '

Figura 4.1: Uma instância do RG-P com quatro pontos terminais e cinco pontos de S teiner. Os segmentos de reta tracejados definem a grade induzida pelos pontos terminais.

r T

(a) (b)

Figura 4.2: (a) Exemplo de um joelho e (b) exemplo de uma ilha em um ponto terminal.

Definição 4.4 Seja I = (R, P) uma instância do problema RG-P. Um conjunto C de

segmentos de GI(P) contém uma ilha em um ponto i (terminal ou de Steiner) se o

número de segmentos em C que incidem em i é exatamente um (veja Figura 4.2.b).

Na definição a seguir particularizamos a Definição 2.6 para tratar apenas do problema RG-P.

Definição 4.5 Seja I = (R, P) uma instância do problema RG-P. Uma partição retangular de R é um conjunto de segmentos de GI(P) que particiona R em retângulos

que não contêm pontos de P no seu interior.

4.2. Uma Formulação em PU 0-1 para o RG-P 2!

Definição 4.6 Suporte de uma inequação linear é o conjunto dos segmentos de reta

cujos coeficientes correspondentes às suas variáveis na inequação são não nulos (veja Fig.

4.3.b).

Definição 4. 7 O retângulo suporte de uma inequação linear é o menor retângulo

retilinear que contém o suporte desta inequação estritamente no seu interior (veja Fig.

4.3.c).

2 2

L 3

i

(a) (b) (c)

Figura 4.3: (a) Segmentos incidentes no ponto terminal i. (b) Suporte da inequação x 1 + x2 2: 1. (c) Retângulo suporte da inequação x 1 + x 2 2: 1.

4.2 Uma Formulação em PLI 0-1 para o RG-P

Nesta seção apresentamos uma formulação em programação linear inteira 0-1 e um estudo poliédrico para o problema RG-P. Os Teoremas 4.1 e 4.2 a seguir são fundamentais para a compreensão da formulação PLI proposta, além de permitirem provar a correção da mesma.

Teorema 4.1 Dado um retângulo R e um conjunto finito nao vazzo P de pontos no

interior de R, se S é um conjunto de segmentos de GI(P) que não contém joelhos nem

ilhas e S é tal que em todo ponto de P incidem pelo menos 2 segmentos de S, então S é

uma partição de R em retângulos.

Prova:

Os segmentos de S juntamente com a fronteira de R induzem uma partição do plano de modo que, como S não tem ilhas (vértices de grau 1), cada face da partição é um polígono possivelmente não simplesmente conexo (i.e., com buracos).

Suponha, por absurdo, que existe uma face F na partição S que é um polígono com pelo menos um buraco B. A fronteira (externa) de B é, por definição, desconexa da fronteira de F, e portanto, seu vértice superior mais à direita tem grau 2 (é um joelho). Contradição.

4.2. L'ma Formulação em PLI 0-1 para o RG-P :2.3

Por conseguinte, todas as faces são polígonos simplesmente conexos. Como os únicos polígonos convexos, de vértices e arestas restritos à GI(P), são retân

gulos, basta mostrar que todas as faces são convexas. Suponha, por absurdo, que alguma das faces não é convexa. Como esta face é sim

plesmente conexa, pela definição de convexidade, ela tem que conter algum vértice com ângulo interno reflexo. A restrição dos segmentos à G I( P) implica que as únicas possibilidades para ângulos reflexos são 270 graus (joelhos) e 360 graus (ilhas). Contradição. O

A prova do Teorema 4.1 é devida ao Prof. Pedro J. de Rezende (IC/UNICAMP). Note que pela Definição 4.5 e pelo Teorema 4.1, para que um conjuntoS de segmentos

de GI(P) seja uma partição retangular de R é suficiente que S não contenha joelhos nem ilhas em pontos terminais e de Steiner e que todo ponto de P seja ponto extremo de pelo menos dois segmentos de S. A formulação em programação linear inteira 0-1 apresentada a seguir é fundamentada neste argumento.

O teorema a seguir fornece as condições para que o RG-P possa ser formulado como um problema de programação linear inteira em variáveis 0-1.

Teorema 4.2 {18} Em qualquer solução ótima, S*, de uma instância do problema RG-P, todos os segmentos de reta de S* encontram-se em GI(P).

Devido ao Teorema 4.2 é suficiente considerarmos partições retangulares, de instâncias do RG-P, formadas de segmentos de reta da grade induzida. Portanto, daqui em diante quando falarmos de partições retangulares estaremos nos referindo a partições retangulares formadas de segmentos da grade induzida.

Como resultado do Teorema 4.2, podemos caracterizar o problema RG-P como sendo o problema de decidir, para cada segmento de GI(P) se este segmento pertence ou não a uma partição retangular de custo mínimo. Portanto, definimos as variáveis binárias Xe

como

_ { 1 se o segmento e em GI(P) pertence a solução viável S Xe - O caso contrário

SejaM o número de segmentos em GI(P). Então x E IRM com os componentes definidos como acima é chamado vetor de incidência ou vetor característico de uma partição

retangular S. A função objetivo do problema RG-P é dada por 2:~1 dexe, onde de é o comprimento do segmento e em GI(P).

Para descrevermos as inequações da formulação, usaremos a seguinte convenção: para

todo ponto i (terminal ou de Steiner) de GI(P), os índices Í(l)' Í(2), Í(3) e Í(4) referem-se aos segmentos incidentes em i conforme indicado na Figura 4.4.

4.2. Uma Formulação em PLI 0-1 para o RG-P

i(l)

i(4) i(2)

i(3)

Figura 4.4: Segmentos de reta incidentes no ponto i.

Uma formulação em programação linear inteira para o RG- P é dada por

Sujeito a

Xi(l) + Xi(2) 2: 1 Xi(l) + Xi(4) 2: 1

Xi(3) + Xi(2) 2: 1

Xi(3) + Xi(4) 2: 1

Xi(l) + Xi(2) - Xi(3) 2: 0

Xi(l) + Xi(2)- Xi(4) 2: 0

Xi(l) + Xi(4) - Xi(2) 2: 0

Xi(l) + Xi(4) - Xi(3) 2: 0

Xi(3) + Xi(2) - Xi(l) 2: 0

Xi(3) + Xi(2) - Xi(4) 2: 0

Xi(3) + Xi(4) - Xi(l) 2: 0

Xi(3) + Xj( 4) - X i(2) 2: 0

(1) ) (2) (3) (4)

(5) (6) (7) (8) (9) (10) (11) (12)

o::;x::;1 x inteiro

para todo ponto terminal i

para todo ponto de Steiner i

26

Denotaremos por classe I as inequações de ( 1) a ( 4) e por classe II as inequações de (5) a (12). O programa linear acima tem O(n2

) variáveis, O(n) inequações da classe I e O(n2

) inequações da classe II.

Proposição 4.1 As inequações da classe I impedem a formação de ilhas e joelhos em

pontos terminais.

Prova:

4.2. Uma Formulação em PLI 0-1 para o RG-P

Para mostrar que as inequações da classe I evitam a formação de ilhas e joelhos, em pontos terminais, é suficiente analisar as situações seguintes. Considere a instância do RG-P dada na Figura 4.5. Primeiro, para mostrar que a classe I evita a formação de

ilhas, suponha sem perda de generalidade, que Xi(l) = 1 e X;(z) = X;(3) = X;(4) = O, isto é, existe urna ilha no ponto i. Neste caso as inequações (3) e ( 4) são violadas. Segundo, para mostrar que a classe classe I evita joelhos, suponha sem perda de generalidade, que

Xi(2) = Xi(3) = 1 e Xi(l) = Xi(4) = O. Neste caso a inequação (2) é violada. Por simetria os outros joelhos e ilhas são evitados. O

o o

: Zi(l)

"'i(4) i zi(2)

l -------------~--------------

o o

:i o

i "'i(3) o o o

4 .5 6

Figura 4.5: Instância I = (0, O, 6, 4, { (3, 2)} ).

Proposição 4.2 As inequações da classe li impedem a formação de ilhas e joelhos em

pontos de Steiner.

Prova:

É suficiente analisar as situações seguintes. Considere a instância do RG-P dada na Figura 4.6. Para mostrar que a classe II evita a formação de ilhas, suponha sem perda

de generalidade, que Xi(l) = 1 e X;(z) = X;(3) = X;(4) = O. Neste caso as inequações (9) e (11) são violadas. Para mostrar que a classe II evita joelhos, suponha sem perda de generalidade, que Xi(l) = Xi(Z) = 1 e X;(3) = Xi(4) =O. Neste caso as inequações (11) e (12) são violadas. Por simetria, pode-se concluir que as outras ilhas e joelhos associados ao ponto i também são eliminadas pelas inequações da classe II. O

o o o o o o

--- -(>---- -- -----~---- --.--0 o o o o o : : J:i(l) o o o o, o s.,., 0 1 S;m

---·-----_., ~-- -<>--- -'"'--o o

! ! zi(J) o o o o

Figura 4.6: Urna instância do problema RG-P. O ponto i é um ponto de Steiner.

O teorema a seguir mostra a corretude da formulação.

4.3. Resultados para o Poliedro do Problema RG-P ..

Teorema 4.3 O sistema acima define uma formulação em PLI 0-1 para o problema RGP.

Prova:

Provar o Teorema 4.3 é equivalente a mostrar que: um ponto inteiro x 5 satisfaz as classes I e II se e somente se S é uma partição retangular de uma instância do problema RG-P, onde x 5 representa o vetor de incidência de S.

( =:}) Conseqüência direta do Teorema 4.1 e das Proposições 4.1 e 4.2.

( <==) Se S é uma partição retangular, então S não tem joelhos nem ilhas, portanto S satisfaz as classes I e II.

o

4.3 Resultados para o Poliedro do Problema RG-P

Seja I uma instância do problema RG-P e Pn a envoltória convexa dos vetores de incidência de partições retangulares de I, isto é, Pn := Conv{x5 E JR:'vf I Sé uma partição retangular de I}. Pn é chamado o poliedro das partições retangulares de I.

O problema RG-P pode ser visto como um programa linear da forma

mznzmzze

Sujeito a x E Pn,

visto que toda solução básica deste programa linear é um vetor de incidência de uma partição retangular e vice-versa. A fim de aplicar técnicas de programação linear para

resolver este problema, precisamos de uma descrição de Pn por meio de um sistema de inequações lineares.

Com intuito de analisar a qualidade das inequações das classes I e II e de outras classes

que apresentaremos a seguir, enunciamos o teorema seguinte.

Teorema 4.4 O poliedro Pn tem dimensão plena, ou seja, dim(Pn) = M, onde M = IGI(P)I.

Prova:

Mostrar que Pn tem dimensão plena é equivalente a provar que Ox = O é a única igualdade satisfeita por todos os pontos de Pn.

Suponha que a inequação linear 1rx ~ 1r0 é satisfeita na igualdade 'Vx E Pn. Desejamos

provar que dim(Pn) = M. Para isto vamos mostrar que 1ri =O V i = O, ... , M.

4.3. Resultados para o Poliedro do Problema RG-P 29

Caso 1: x i = 1 V i = 1, ... , LVI

Note que x = (x1, x2, ... , xAJ) E Pn., isto é, x é um vetor de incidência de uma partição retangular de uma instância do problema RG- P. Logo,

ivf

Ltr; = tro i=l

Caso 2: Xj =O para algum j E {1, ... , N!} e Xi = 1 V i E {1, ... , M} \ {j}

Note que x E Pn.. Logo,

M

L 1ri = tro i=l,i;éj

(4.1)

(4.2)

Subtraindo a equação 4.2 da equação 4.1 concluímos que 7rj = O para algum j E

{1, ... , M}. Como o segmento j foi escolhido arbitrariamente, então temos que 1ri

O V i E { 1, ... , A1}. Logo,

tro =O (4.3)

A prova está completa. o

Agora apresentamos uma caracterização parcial da estrutura poliédrica de Pn.. Como

vimos no capítulo anterior, para obtermos uma boa caracterização de Pn. é importante

que encontremos inequações lineares que definam facets deste poliedro. Pelos Teoremas

3.4 e 4.4, podemos provar que uma inequação válida wT x 2:: w 0 define uma facet F em

Pn. se e somente se toda inequação válida 1rT x 2:: 7ro para Pn. cuja face contém F pode

ser obtida de wT x 2:: w 0 multiplicando-se esta última por um escalar positivo.

Para todas as provas de inequações definindo facets que são apresentadas neste capítu

lo, nós nos concentramos em analisar os segmentos de reta que estão no retângulo suporte

destas inequações. O Lema a seguir justifica esta decisão.

Lema 4.1 Seja wT x 2:: w 0 uma inequação válida para Pn. e Rw o retângulo suporte desta

inequação. Seja Fw = { x E Pn. : wT x = w0 } =I 0 a face definida por wT x ~ w 0 em Pn..

Suponha que 1!'T x 2:: 7!'0 é uma inequação válida para Pn. cuja face definida em Pn. é tal

que Fw Ç Frr. Então1 1ri = O para todo segmento i externo a Rw.

Prova:

4.3. Resultados para o Poliedro do Problema RG-P

Seja I uma instância do problema RG-P, x o vetor de incidência de uma partição retangular de I tal que wT x = w 0 (x E Fw) e x o vetor de incidência de uma partição retangular de I, obtido a partir de x ao acrescentar: todos os segmentos da grade induzida de I externos a Rw e mais os segmentos que definem a borda de Rw. Assuma :i como sendo o vetor característico obtido de x fazendo-se Xi = O, para alguma componente correspondente a um segmento externo a R'-'1. Note que x e :i E Fw, e por hipótese a Frr também. Logo tem-se que:

e

comparando estas duas equações conclui-se que 1ri = O. O

Os Teoremas 4.5, 4.7 e 4.8 caracterizam as inequações da formulação que definem facets de Pr<..

Teorema 4.5 A inequação Xs ~ 1 V s E GI(P) define uma facet de Pr<..

Prova:

(a) Validade

Trivial. (b) Facet

Seja F = { x E Pr<. : x s = 1} a face definida pela inequação x s ~ 1. Corno os vetores de incidência x = (1, 1, ... , 1) e xi para i = 1, ... , IGJ(P)I e i =f. s, onde xi é obtido de x fazendo a componente i igual a zero, pertencem a F e são afim-independentes, então

dim(F) = IGI(P)I- 1 e, portanto, Xs ~ 1 define urna facet de Pr<.. O

Teorema 4.6 A inequação Xs ~ O V s E GI(P) não define uma facet de Pr<..

Prova:

Caso 1: Assuma que sé incidente em um ponto terminal i (veja Figura 4.7) .

• t

i

Figura 4. 7: U rn retângulo com um ponto terminal i no seu interior e os segmentos s e t

incidentes em i.

•l .. 'J. Resultados para o Poliedro do Problema RG-P :31

A prova consistirá em mostrar que Xs ;::: O é uma combinação linear de inequações válidas para Pn.

Somando as duas inequações válidas Xs + Xt ;::: 1 (inequação da classe I) e -Xt ;::: -1 tem-se que Xs ;::: O.

Caso 2: Assuma que sé incidente em um ponto de Steiner i (veja Figura 4.8) .

• y t

i

u

Figura 4.8: Um retângulo com um ponto de Steiner i no seu interior e os segmentos s, t, u e v incidentes em i.

Como i é um ponto de Steiner, se Xs = O então Xt e xv devem ser ambos nulos ou ambos iguais a 1, caso contrário haverá a formação de uma ilha ou joelho em i. Portanto,

a face F= {x E PR: Xs =O} está contida na face {x E PR: Xs + Xt- Xv = 0}. Logo F não é uma Jacet de Pn.

o

Teorema 4. 7 Cada inequação da classe I define uma facet do poliedro Pn.

Prova:

(a) Validade

Tomando-se a inequação (1) da classe I, a única forma de violá-la seria para um vetor

de incidência x tal que Xi(l) + Xi(2) = O. Neste caso x não pode representar um vetor de incidência de uma partição retangular de R, pois as únicas possibilidades para o ponto i são: (a) i não é extremo de nenhum segmento de GI(P) da partição, o que é impossível

para um ponto terminal; (b) i é extremo de um único segmento e, neste caso, haveria uma ilha em i ou (c) i é extremo de dois segmentos ortogonais e, neste caso haveria um

joelho em i.

(b) Facet

Provaremos apenas que a primeira inequação da classe I define uma facet de Pn. As provas para as outras inequações desta classe são análogas.

Denote por wT x;::: wo a inequação x 1 +x2 ;::: 1 e seja Fw = {x E Pn I wT x = wo} a face definida por ela. Note que Fw =f. Pn, pois o ponto x, com Xi = 1 Y i E GI(P), pertence a Pn, mas não pertence a Fw. Assuma que 1rT x ;::: "Tro é uma inequação válida para Pn tal


que Fw Ç Ftr = {x E Pn I r.T x = r.o}. Desejamos mostrar que r. = aw e r.0 = O"'-'o para

algum a E IR+·

Lembre-se que pelo Lema 4.1 é suficiente analisarmos os segmentos de reta que estão no retângulo suporte da inequação x 1 + x2 2: 1, ou seja, pelo Lema 4.1 temos que r.i =O para todo segmento i externo ao retângulo suporte de x 1 + x2 2: 1.

Caso 1: Considere as soluções na Figura 4.9.

1 1

4

i o.

I

3 3

(a) (b)

Figura 4.9: O ponto i é um ponto terminal. Em (a) representamos uma solução para uma instância do RG-P tal que o vetor de incidência x = (x 1 , ... , xM) = (1, O, 1, 1, ... , 1). Em (b) tem-se uma solução com vetor característico x = (1, O, 1, O, 1, 1, ... , 1 ), ou seja, x é a solução obtida de x fazendo x4 = O.

Note que x e x E Fw e portanto x e x E F1r. Logo r.T x = 7ro e 1rTx = 1r0 • Comparando estas duas equações conclui-se que 1r 4 = O. Fazendo uma rotação na solução da Figura 4.9 prova-se que 11'3 = O.


' ' ' ' ' A' 4 - 2 -

D' , , , , , , , ,

(a)

' ' ,

' ,

4 'o._~' ,-.., ,

' , ' ,

D (b)

, , ,

2

' ' '

c

, ,

' '

B'

c·

', ',

Figura 4.10: O vetor de incidência da solução em (a) é dado por x = (0, 1, O, 1, 1, ... , 1). Em (b) estão representados os eixos de simetria do suporte da inequação x 1 + x2 2: 1, ou seja, provar algo sobre o segmento A equivale a provar algo para A'. Esta mesma equivalência é verdadeira entre os segmentos B e B', C e C', D e D'.

Ao removermos A' ( B', C', D') de x obtemos o vetor de incidência xA' ( x 8', xc', xn' I

respectivamente) que pertence a Fw e portanto a F1r. Logo 1rT x = 1r0 e r.T xA = 1r0 .

) ___ ,...,_ ~\ . -

4.3. Resultados para o Poliedro do Problema RG-P :n ..

Comparando estas duas equações obtém-se r.A = r.A' =O (r.s = r.8 , = r.c = r.c' = r.o =

r.D' = 0).

Resumindo, temos que r.;= O Vi E GI(P) \ {1, 2} e r.1 = r.0 (caso 1) e r.2 = r.0 (caso 2).

Assim podemos concluir que existe um o: E IR+ tal que

A prova está completa.

ViE{1,2} para i= O

Vi E GI(P) \ {1,2}

Teorema 4.8 Cada inequação da classe li define uma facet do poliedro PR.

Prova:

(a) Validade

o

Tomando-se a inequação (5) da classe II, a única forma de violá-la seria para um vetor

de incidência x tal que Xi(l) = X;(2) = O e xi{J) = 1. Mas neste caso, x não pode ser vetor de incidência de uma partição retangular, pois haveria uma ilha (se Xi( 4) = O) ou

um joelho (se Xi(4 ) = 1) em i.

(b) Facet

Provaremos apenas que a primeira inequação da classe II define uma facet de PR. As

provas para as outras inequações desta classe são análogas.

Denote por wT x ~ w 0 a inequação x1 + x2- x 3 ~O e seja Fw = {x E PR I wT x = wo} a face definida por ela. Note que Fw =f. PR, pois o ponto x, com Xi = 1 V i E GI(P), pertence a PR, mas não pertence a Fw. Assuma que r.T x ~ 7ro é uma inequação válida

para PR tal que Fw Ç F-,r = {x E PR I 1rT x = 1r0 }. Desejamos mostrar que 1r = o:w e

7ro = o:w0 para algum o: E IR+·

Pelo Lema 4.1 temos que 1ri = O para todo segmento i externo ao retângulo suporte

de X1 + X2 - X3 ~ 0.


Note que x e x E Fw. Logo 1rT x = 7ro e 1rTx = 1r0 e, portanto, 1r 4 = O.


Ao removermos A(B,C,D) de x obtemos o vetor característico xA(x8 ,xc,xD respec

tivamente) que pertence a Fw. Portanto, 1rT x = 1r0 e 1rT xA = 1r0. A partir destas duas

equações concluímos que 1l'A = 1l'A' =O (1rs = 1l'B' = 1rc = 1l'D = 0).

4.3. Resultados para o Poliedro do Problema RG-P :3-l

1 1

4

i o.

1

3 3

(a) (b)

Figura 4.11: O ponto i é um ponto de Steiner. Em (a) representamos uma solução cujo vetor de incidência é x = (1, O, 1, 1, ... , 1). Em (b) tem-se uma solução com vetor característico x = (1, O, 1, O, 1, 1, ... , 1).

' ' ' ' A D ' ' ' ' ' ' ' 1

4

' 1 ' ' ' ' A' ' ' ' ' ,

4 '·i_/ ' , ' ' ' ' '

3 ' ' B ' ,

3 ' ' ' ' ,

' , ' , '

' ' B' c '

(a) (b)

Figura 4.12: Em (a) temos uma solução com vetor característico x = (1,0, 1, 1, ... , 1). Em (b) representamos os eixos de simetria que passam pelo ponto de Steiner i.


Caso 3: Considere a solução na Figura 4.13.

D' 4

~ 2

3 c·

Figura 4.13: Uma solução com vetor de característico x = (0, 1, ... , 1).

Removendo D' (C') de x obtemos o vetor de incidência xD' ( xc' respectivamente) que pertence a Fw. Logo 1T'D' =O (1rc' = 0). Além disso, comparando as soluções representadas pelas Figuras 4.12.a e 4.13, temos que 1r1 = 1r2 .

Caso 4: Seja x o vetor característico de uma solução, onde Xi =O Vi E {1,2,3,4} e Xi = 1 Vi E GJ(P) \ {1,2,3,4}.

Note que x E Fw, logo 1rT x = 1r0 . Como já mostramos 1ri =O Vi E GI(P) \ {1, 2, 3}, então concluímos que 1r0 = O.

Resumindo, temos que 1ri =O Vi E GI(P) \ {1, 2, 3}, 1r1 = 1r2 (caso 3), 1r0 =O (caso 4) e 1r1 = 1r2 = -1r3 (a partir dos casos 1,3 e 4).

Assim podemos concluir que existe um a E IR+ tal que

ViE{1,2} para i= 3 Vi E (GI(P) U {O})\ {1,2,3}

o

A seguir apresentamos quatro outras classes de inequações para Pn. Embora estas inequações não façam parte da formulação de PLI 0-1 descrita na seção 4.2, mostraremos que estas definem facets de Pn e, portanto, são fundamentais na descrição deste poliedro.

Classe III: Para cada quatro pontos, sendo três terminais e um de Steiner, definindo os vértices de um retângulo em GI(P), conforme a Figura 4.14 temos que

( 4.4)

O número de inequações da classe III é O(n).

4.:J. Resultados para o Poliedro do Problema HG-P

pl p2

2

3 p4 H p3

4

Figura 4.14: Três pontos terminais e um de Steiner formando um retângulo em GI(P).

Teorema 4.9 A inequação da classe III define uma facet do poliedro Pn.

Prova:

(a) Validade

Para mostrar que a inequação. da classe III é válida é suficiente analisar os seguintes três casos.

Caso 1: x 1 = 1 e x2 = O

Sendo x 2 =O, então o valor de XH deve ser 1 para que a inequação (2) da classe I seja

satisfeita no ponto p3 • Como conseqüência de XH = 1, x 3 ou x 4 precisa ter valor 1 para que não haja uma ilha ou joelho no ponto p4 .

Caso 2: x 1 = O e x2 = 1

Simétrico ao caso 1.

Caso 3: x 1 = 1 e x2 = 1

Claramente a inequação da classe III é satisfeita.

O caso onde x 1 = x 2 = O não ocorre, senão a inequação ( 4) da classe I estaria sendo

violada no ponto P2·

(b) Facet

Denote por wT x ~ w0 a inequação x1+x2+x3+x4 ~ 2 e seja Fw = {x E Pn I wT x = wo} a face definida por ela. Note que Fw =f. Pn, pois o ponto x, com Xi = 1 V i E GI(P), pertence a Pn, mas não pertence a Fw. Assuma que 1rT x ~ 1r0 é uma inequação válida

para Pn tal que Fw Ç Frr = { x E Pn I 1rT x = 1r0 }. Desejamos mostrar que 1r = a.w e

7ro = a.w0 para algum a. E IR+·

4 .. >. Resultados para o Poliedro do Problema RG-P

Pelo Lema 4.1 temos que r.i = O para todo segmento i externo ao retângulo suporte

de Xt + x2 + X3 + X4 ~ 2.

Caso 1: Considere a solução mostrada na Figura 4.1.5 cujo vetor de incidência x está em Fw.

B c

1 o

2

E

Figura 4.15: Uma solução com vetor característico x.

Removendo o segmento B (C, D, E) de x obtemos o vetor de incidência x 8 ( xc, xD, xE

respectivamente) que pertence a Fw. Logo r.T x = r.T x8 = r.0 e, portanto, r.8 = O

(r.c = 7rD = 7rE = 0).

Caso 2: Considere a solução mostrada na Figura 4.16 cujo vetor de incidência x está em

Fw.

A

2

H

4 p

Figura 4.16: Uma solução com vetor característico x.

Removendo o segmento A (F, H) respectivamente) que pertence a Fw. (r.F = 1rH = 0).

de x obtemos o vetor de incidência xA ( xF, xH

Logo 1rT x = 1rT xA = 7ro e, portanto, r. A = O

Caso 3: Como os vetores de incidência x e x correspondentes às soluções mostradas,

respectivamente, nas Figuras 4.17.a e 4.17.b estão em Fw, temos que 1rT x = r.Tx = r.0 e,

portanto, 1ra = O.

Caso 4: Considere a solução na Figura 4.18.

4.3. Resultados para o Poliedro do Problema RG-P :38

1 1

o 3 3 ,... ....,

(a) (b)

Figura 4.17: (a) Uma solução com vetor de incidência x = (1, O, 1, O, 1, 1, ... , 1). (b) Uma solução com vetor de incidência x obtido de x fazendo xc =O.

J'

, , ,

, ,--...:___,...__::M::.._~__::K~,' , , , , , , , K'

,

2 N

L'

p o L

Figura 4.18: (a) Uma solução com vetor de incidência x e o eixo de simetria da inequação X1 + X2 + X3 + X4 ~ 2.


Ao removermos o segmento J ( K, L) de x obtemos o vetor de incidência x 1 ( xK, xL

respectivamente) que pertence a Fw. Logo 7rJ = 1rJ' =O (1rK = 7rK' = 7rL = 1ru =O). Ao removermos o segmento !vi ( N, O, P) de x obtém-se o vetor xAI ( xN, x0 , xP res

pectivamente) que pertence a Fw. Logo 7rM = 7rN = 1ro = 7rp =O.

A partir da solução na Figura 4.19 concluímos que 7rQ = 7rR =O .

•• R 2

3

Q

Figura 4.19: Uma solução com vetor de incidência x = (0, 1, 1, O, 1, 1, ... , 1). Seja xQ(xR)

o vetor de incidência obtido de x removendo o segmento Q(R respectivamente).

Os casos anteriores mostram que 1ri = O para todo segmento i interno ao retângulo suporte e diferente de 1, 2, 3 e 4. A partir destes resultados, comparando-se as soluções mostradas nas Figuras 4.15, 4.16, 4.17.a e 4.19 temos que 1r1 = 1r2 = 1r3 = 1r4 = 1r0 j2.


Vi E {1,2,3,4} para i= O Vi E GI(P) \ {1,2,3,4}

o

Classe IV: Para cada quatro pontos em GI(P), sendo um terminal e três de Steiner, formando a configuração mostrada na Figura 4.20 temos que

( 4.5)

O número de inequações da classe IV é O(n).

Teorema 4.10 Uma inequação da classe IV é válida para P1<. e define uma facet deste

poliedro se e somente se ambos os pares de pontos (p2 , P3) e (p4, Ps) contém pelo menos

um ponto de Steiner.

Prova:


1

.:) p3

2 ,' ,

, ,

,

, , , ,

C D ,,' 3 ----~~J---~~,,o-------~~p4

B ,' ,' ,

, , ,

D'

4 A ,.,,' B' --~~~----~--o-------<)v p5

,' pl -, ,' , ,

,' A' c· ,' , ,

40

Figura 4.20: Um ponto terminal e três de Steiner formando um retângulo em GI(P). Os pontos P2,p3,p4 e Ps são pontos terminais ou de Steiner. A linha pontilhada passando pelo ponto terminal representa o eixo de simetria.

(a) Validade

Note que:

XD = 1 ou XD' = 1 implica em x2 = 1 ou x3 = 1 e a inequação é válida.

Vamos supor então que XD = XD' =O. Como p1 é um ponto terminal XA' e xa devem

ser 1 e/ou XA e XB' devem ser 1. Se XA' = xa = 1 e XD =O, então x 1 = 1. Se XA = XB' = 1 e XD' =O, então x 4 = 1. Logo a inequação é válida.

(b) Facet

Condição necessária:

Suponha que P2 e P3 são pontos terminais. Para todo vetor de incidência x E Fw implica que Xp2p3 = 1 (variável associada ao segmento de reta que une p2 a p3 ), caso contrário x 1 = x 2 = 1. Em outras palavras, a face definida pela inequação da classe IV

está contida na face definida por Xp2p3 ~ 1 quando p2 e P3 são pontos terminais. Um raciocínio análogo pode ser feito para o par de pontos (p4 , p5 ).

Condição suficiente:

Denote por wT x ~ wo a inequação Xt +x2+x3+x4 ~ 1 e seja Fw = {x E Pn. I wT x = wo} a face definida por ela. Note que Fw =J Pn., pois o ponto x, com Xi = 1 V i E GI(P), pertence a Pn., mas não pertence a Fw. Assuma que 1rT x ~ 1r0 é uma inequação válida

para Pn. tal que Fw Ç F-rr = { x E Pn. I 1rT x = 1r0 }. Desejamos mostrar que 1r = aw e

7ro = aw0 para algum a E IR+·

Pelo Lema 4.1 temos que 1r i = O para todo segmento i externo ao retângulo suporte

4.:J. Resultados para o Poliedro do Problema RG-P

de X1 + X2 + X3 + X4 2: 1.

Caso 1: Observe a solução na Figura 4.21.

E

F 1 1'

c

o l'

A

H E'

H' o• F

Figura 4.21: Solução com vetor de incidência x. Assuma xA (xc, xE, xF, xa, xH) o vetor característico obtido de x ao remover o segmento A (C, E, F, G, H respectivamente).

ComoxA (xc,xE,xF,xG,xH) E Fw,então1ri =OVi E {A,C,E,F,G,H}. Porsimetria mostra-se que 1ri = O Vi E {A', C', E', F', G', H'}.

Caso 2: Observe a solução na Fig~ra 4.22.

2 J'

B

B'

Figura 4.22: Solução com vetor de incidência x.

Ao removermos o segmento J (B) do vetor x obtemos o vetor de incidência xJ (x8 ).

Como x e xJ (x8 ) E Fw, concluímos que 1!'J =O (1rB = 0). Por simetria pode-se concluir

que 1l'B' = 1!'J' =O.

Caso 3: Observe as soluções na Figura 4.23.

Como x e x E Fw, concluímos que 1r D = O. Por simetria conclui-se que 1r D' = O.


Subcaso 4.1: Se o ponto P3 (p5 ) é um ponto de Steiner, então assuma x o vetor de incidência obtido de x ao remover os segmentos incidentes em P3 (ps). Como x ex E Fw, conclui-se que 1!'[ =O (1rl' = 0).


2 2

..... D - C)

D' D'

- -

(a) (b)

Figura 4.23: (a) Solução com vetor de incidência x. (b) Solução com vetor de incidência x.

p2 I p3 -1

c~ pS

I'

c•

Figura 4.24: Solução com vetor de incidência x. Os pontos p2, p3, P4 e Ps são pontos na borda do retângulo suporte da inequação x 1 + x 2 + x 3 + x 4 2: 1.

4.3. Resultados para o Poliedro do Problema RG-P 43 ..

Subcaso 4.2: Se o ponto P2 (p4 ) é um ponto de Steiner e p3 (p5 ) é um ponto terminal, então assuma x o vetor de incidência da solução na Figura 4.22 e x o vetor de incidência obtido de x ao remover os segmentos incidentes no ponto p2 (p4 ). Note que x e x E Fw, logo 1r I = O ( 1r l' = O).

Resumindo temos que 1r; = O Vi E GI(P) \ {1, 2, 3, 4} e 1r1 = 1r4 = 1r0 (rotacionando a solução na Figura 4.21); 1r2 = 1r3 = 7ro (rotacionando a solução na Figura 4.22); 1r1 = 1r2 = 1r0 (casos 1 e 2) e, portanto, 1r1 = 1r2 = 1r3 = 1r 4 = 7ro.


Vi E {1,2,3,4} para i= O Vi E GI(P) \ {1,2,3,4}

D

Classe V: Para cada nove pontos, sendo três terminais e seis de Steiner em GI(P), formando a configuração mostrada na Figura 4.25 temos que

8 12 14

2 L: X; + L: X; - L: X; ~ 6 ( 4.6) i=l i=9 i=13

' ' ' ' ' ' ' ' A 9 8 Coefici.eate = 2

' ' ' A' ' p1 11 p4 13 p2 7 ' r', >------ Coefici.eate = 1

' ' ' 12 ' ' B D - - - - - · Coefici.eate = -1 ' ' ' 10 p3 B' ' ' c p5 6

' 'r' ' ' I ' ' I 14 c· ' ' E I ' ' I ' ' 1 Jp6 D' p7 E' ' ' p8 5

' ' ' ' ' ' 2 3 4 ' ' ' ' ' ' ' '

Figura 4.25: Três pontos terminais e se1s de Steiner em GI(P). A linha pontilhada representa o eixo de simetria.

O número de inequações da classe V é O(n).

·LJ. Resultados para o Poliedro do Problema RG-P

Teorema 4.11 A inequação da classe V define uma facet do poliedro Pn.

Prova:

(a) Validade

Para mostrar que a inequação da classe V é válida é suficiente analisar os segmentos in

cidentes nos pontos terminais P7 e p5 na Figura 4.25, isto é, xc', X3, xn', XE'e xn, XE, xc, x 6.

Esta suficiência deve-se ao fato que em cada ponto terminal pelo menos uma das seguintes situações ocorre: ou os dois segmentos verticais ou os dois segmentos horizontais estão na partição retangular.

Note que a inequação da classe V pode ser reescrita da seguinte forma

8

2 2::: X;+ (xn + Xg- Xt3) + (x12 + X1Q- Xt4) ;::::: 6 i=l

(4.7)

Os termos entre parênteses são ambos não-negativos, pois correspondem a inequações

da classe II nos pontos de Steiner p3 e p4 . Logo, se encontrarmos três segmentos de 1 a 8 que devem estar na solução, então a validade da inequação estará garantida. É isto que

ocorre nos casos 1 e 2 descri tos a seguir.

Caso 1: xn = XE = xc' = X3 = 1

Sendo xn = XE = 1, então x 7 ou x8 precisa ter valor 1 e x 4 ou x 5 precisa ter valor 1 para evitar ilha ou joelho nos pontos p2 e p8 .

Caso 2: xn = XE = xn' = XE' = 1

Sendo XD' = 1, então para que não haja uma ilha no ponto p6, x 1 ou x2 precisa ser

igual a 1. Sendo xn = XE = 1, então x 7 ou x8 deve ter valor 1 e x 4 ou Xs deve ter valor

1.

Caso 3: xc = x6 = xc' = X3 = 1

Se x 13 = 1, então 2(x7 + x8 ) ;::::: 2 e x 9 + x 11 2:: 1, fazendo com que a inequação da classe V torne-se verdadeira, pois de 4.7 temos que a primeira e a segunda parcelas já

somam pelo menos 6 (por simetria, se x 14 = 1 implica que 2( x1 + x2) ;::::: 2 e X to + X12 ;::::: 1 que faz a inequação verdadeira). Logo, se houver uma solução violando a inequação, ela deve satisfazer x 13 = x 14 = O. Por outro lado, x 11 + x 12 ;::::: 1 pois estes segmentos são

incidentes num ponto terminal (inequação (3) da classe I). Se xu = 1 (x12 = 1), como x 13 =O (x14 = 0), então x9 (x 10 ) deve ser igual a 1, satisfazendo a inequação da classe V.

Caso 4: xc = x 6 = XD' = XE' = 1



(b) Facet

Denote por wT x ;::: w0 a inequação da classe V e seja Fw = { x E Pn I wT x = w0 } a face

definida por ela. Note que F.JJ =J Pn., pois o ponto x, com x; = 1 V i E G I( P), pertence a Pn., mas não pertence a Fw. Assuma que 1'iT x ;::: 7'io é uma inequação válida para Pn. tal

que Fw Ç F1r = {x E Pn I 1'iT x = 7ro}. Desejamos mostrar que 7'i = aw e 7'io = aw0 para

algum a E IR+.

Pelo Lema 4.1 temos que 7'i; = O para todo segmento i externo ao retângulo suporte da inequação da classe V.


F N

F A

A' 11 13 7

12 B

B' c

14 c· 1 s

N' M

I' M'

Figura 4.26: Solução com vetor de incidência x. Assuma xA (xB, xc, xF, x 1, xM, xN') o vetor de incidência resultante ao remover o segmento A (B, C, F, I, M, N' respectivamente).

Como x e xA (xB, xc, xF, x 1, xM, xN') E Fw, então 1'iA = 1'iB = 7rc = 1'iF = 1'if = 1'iM =

1'iN' = O. Como A e A', B e B', C e C', F e F', I e I', Me M', N e N' são segmentos

simétricos pode-se mostrar que 1'iA' = 1'iB' = 7'iC' = 1'iF' = 1'if' = 1'iM' = 1'iN =O.


Note que X e xE' (x e xK') E Fw e X e xD' (x e xJ') E Fw. Logo 7'iD' = 1'iE' = 7'iJ' =

1'iK' =O. Como De D', E e E', J e J', K e K' são segmentos simétricos pode-se mostrar

que 7'iD = 1'iE = 7'iJ = 1'iK = 0.


Como x e xG' (x e xH') E Fw, então 7'iG'

segmentos simétricos, então 7'iG = 1'iH = O.

O. Como G e G', H e H' sao

Relações: 7'ii =O Vi E GI(P) \ {1, ... , 14}; 7r1 = 1'i2, 7r4 = 7'is e 1'i7 = 7'is (na Figura 4.26 trocando-se os pares correspondentes na solução); 7r1 = 7r2 = 7r3 (soluções nas Figuras


- 11 13 7 - ~

12

( ~ 6 -

K 14

E' D'

3 4 2 3

K' J' (a) (b)

Figura 4.27: (a) Solução com vetor de incidência x. Removendo o segmento E' (K') de x obtemos o vetor de incidência xE' (xK'). (b) Urna solução com vetor característico x. Removendo o segmento D' (J') de x obtém-se o vetor de incidência xD' (x1').

O H

8

11 13 -o•

10 ,... ~

H' 14

1 --4

Figura 4.28: Solução com vetor de incidência x. Ao remover o segmento G' (H') de x obtém-se o vetor de incidência xG' ( xH').


4.27.a e 4.29.a), 1r4 = 1r6 (soluções nas Figuras 4.27.a e 4.29.b), 1r6 = 1r8 (soluções na Figura 4.30); 1r11 + 1r13 = 1r12 + 1r14 = O (soluções nas Figuras 4.30.a e 4.3l.a); 1r2 = 1r4

(ií6 = 1r7 = 1r8 e soluções na Figura 4.27); í'ri = ~Jro i= 1, ... ,8 (relações anteriores e solução na Figura 4.26); Jr1o + 11'12 = ~Jro ( 11'3 = 11'6 = ~71'0 e solução na Figura 4.3l.b );

Jrg + 1r11 = ~Jro (situação simétrica a Jr1o + 11'12 = ~7ro); Jr1o + 11'14 =O ( 11'2 = 1r 4 = 71's = ~Jro, Jru + 1r13 = O e solução na Figura 4.3l.c); Jrg + 11'13 = O (simétrico a 1r1o + 1r14 = O); 1r1o = 1r12 = -1r14 (de 11'12 + 11'14 = O e Jrw + 11'14 = O); Jrg = Jru = -1r13 (simétrico a 1r1o = 11'12 = -1r14); Jr1o = 11'12 = ~Jro e 11'14 = -~Jro (de 11"10 = 11"12 = -1r14 e 11"1o+11"12 = ~7ro); 7rg = 7ru = ~7ro e 1r13 = -~11"o (simétrico à relação anterior).

- ,... 7 - 11 13 ,... 7

• - 6 -1 ,... -- •

4 3

(a) (b)

Figura 4.29: (a) e (b) Soluções com vetores de incidência x e x.

8

u (

u u ,... - 6 - - <> •

14 14

1 - ,... s 1 s -

(a) (b)


Assim podemos concluir que existe um o: E IR+ tal que


8

11 '"'

13 - 4 - 11 -- '-'

12 12

<) 4 10 - 6 10 -'-'

14 14 1 - s • -

3 2

(a) (b) (c)

Figura 4.31: (a), (b) e (c) Soluções com vetores de incidência x, x ex*.

1ri=

a

a/2 -a/2

Vi E {1,2, ... ,8} V i E {9, ... , 12} ViE{13,14}

3a para i= O O Vi E GI(P) \ {1, ... ,14}

48

8

13

4

o Classe VI: Para cada dezesseis pontos, sendo quatro terminais e doze de Steiner, em GI(P), formando a configuração mostrada na Figura 4.32 temos que

(4.8)

O número de inequações da classe VI é O( n).

Teorema 4.12 A inequação da classe VI define uma facet do poliedro Pn.

Prova:

(a) Validade

Para mostrar que a inequação da classe VI é válida é suficiente analisar os segmentos incidentes nos pontos terminais p2 ,p3,p5 ,p6 e nos pontos de Steiner PI,P4 na Figura 4.32.

Caso 1: xF' = xo = xn' = XM = 1

Sendo xF' = x 0 = 1, então x 7 + x 8 ~ 1 e sendo XD' = XM = 1, então xs + x6 ~ 1.

4 . .'3. Resultados para o Poliedro do Problema RG-P 49

' ' , ,

' ' ,

' Q M , ' 2 , , ' '

, ' pl p2

, 1 ' G' H' I'

, , ' '

, , ' '

, ' c· o· , , I ' , ' ,

p3 c ', s , , o N ' , ' , ' ,

H ' , K 8 ,>, 6 p6 , '

p F ,' 7 ', E l,p4 R , ' ' , , '

I , , F' E'"", L , ' , pS ' ' , , 1' K' ' 3

, ' , ' , ' , ' , o 4 ' , ' , ' , ' , ' , '

Figura 4.32: Quatro pontos terminais e doze de Steiner em GI(P). As linhas pontilhadas representam os eixos de simetria.

Caso 2: XF = Xp = XD = XN = 1


Caso 3: XF = xp = XD' = XM = 1

Sendo XF = xp = 1 e XD' = XM - 1 implica em xr + x 8 > 1 e x 5 + x 6 > 1 respectivamente.

Caso 4: xF' = xo = XD = XN = 1


Caso 5: XJ' = XK' = XH' = Xf' = 1

Como XH' = 1, então x 1 +x2 +x5 +xs ~ 1. Como XK' = 1, então X3 +x4 +x6 +xr ~ 1. Caso 6: XH = XJ = Xf = XK = 1


Caso 7: XH = XJ = xF' = xo = 1

Primeiramente nota-se que x 7 + x 8 ~ 1. Se a inequação não for válida, devemos ter XD' = XD =O, caso contrário x 5 +x6 ~ 1. Neste caso, devemos ter XI= x 1, = xH' = XK = 1. Mas XK = 1 implica que XE +XL ~ 1 (classe li) e conseqüentemente que x 3 + x 4 ~ 1 ou X6 + Xr ~ 1. Analogamente, XH' = 1 implica que x 5 + x 8 ~ 1 ou x 1 + x 2 ~ 1. Logo a inequação é válida.

Se Xf = XK = XL = 1, então x 3 + x 4 ~ 1 e a inequação é satisfeita. Suponha que xc' = XQ = XD = XN = 1, então Xs + Xs ~ 1 e X6 + Xr ~ 1 e a inequação é satisfeita.


Caso 8: x D' = x A-t = x D = x N = 1


Não é difícil ver por enumeração que estes correspondem a todos os casos poss1Ve1s,

pois os pontos terminais tem que ter ou os dois segmento verticais e/ou os dois segmentos horizontais incidentes a eles na solução.

(b) Facet

Denote por wT x 2:: wo a inequação L~=l Xi 2:: 2 e seja Fw = {x E PR I wT x = w0 }

a face definida por ela. Note que Fw =/= PR, pois o ponto x, com Xi = 1 V i E GI(P), pertence a PR, mas não pertence a Fw. Assuma que 1rT x 2:: 1r0 é uma inequação válida

para PR tal que Fw Ç F~r = {x E PR I 1rT x = 1r0 }. Desejamos mostrar que 1r = aw e

7ro = awo para algum a E IR+·


B B A A A

A A A A A 1 A

A A A A

A A A A

A B A

A A A • A B

A A A A A

Figura 4.33: Solução com vetor de incidência x. Assuma xA o vetor de incidência obtido ao remover qualquer segmento A.

Note que x e xA E Fw, logo 1r A = O. Considerando a solução simétrica a solução dada

na Figura 4.33, onde fazemos x 2 = x 3 = 1 ao invés de x 1 = x 4 = 1, pode-se mostrar que

1rB = 0.


Note que x ex E Fw ex ex E Fw. Logo 1ri =O Vi E {C, C', D', F, H, H', J, J', I, I'}. Como os segmentos De D', F e F' são simétricos, então 7rD = 7rp =O.


Como x ex E Fw e x ex" E Fw, conclui-se que 7rE = 7rE' = 7rK = 7rK' = O.

4.3. Resultados para o Poliedro do Problema RG-P .5l

A'

H' I'

C' o• I

A c s D

H 8

p

J P' r

Figura 4.34: Solução com vetor de incidência x. Removendo qualquer segmento rotulado com uma letra, exceto os segmentos A, A', C, C', D, F', obtém-se uma solução com vetor de incidência x. Agora ao remover conjuntamente os segmentos A, C, H ou A', C', H' de x obtém-se uma solução com vetor característico X*.

6 Ir::

7 B A

B' r

A'

Figura 4.35: Solução com vetor de incidência x. Removendo o segmento K (K') obtémse o vetor de incidência xK (xK'), ou removendo conjuntamente os segmentos A, E, K (A', E', K') obtém-se o vetor x*.


Caso 4: Observe as soluções na figura 4.36.

l

o• H'

o

6 8

• L

lt' L'

4

(a) (b)

Figura 4.36: (a) Solução com vetor de incidência x. Removendo os segmentos G' e H' de x obtém-se uma solução com vetor de incidência x*. (b) Solução com vetor característico x. Removendo os segmentos K' e L' de x obtém-se uma solução com vetor de incidência x*.

Note que x e x* E Fw ex ex* E Fw, logo 7ra• = 1ru = O. Como G e G', L e L' são simétricos conclui-se que 1ra = 7rL = O.

Pelo Lema 4.1 temos que 7ri =O para todo segmento i externo ao retângulo suporte

de I:~=l Xi ~ 2. Resumindo: 1r1 = 1r2 e 1r3 = 1r4 (caso 1); 1r1 +1r3 = 7rs+7rs = 1r6+1r1 = 1r2+1r6 = 7ro (casos

1,2,3 e 4) e, portanto, 1r1 = 1r2 = 7rr; 1r1 + 7rr = 7ro e, portanto, 1r1 = 1r2 = 7r6 = 7rr = 7ro/2 (Figura 4.37.a); 1r1 = 1r5 (caso 1 e Figura 4.37.b); 1r3 = 1r4 = 7rg (caso 2 e Figura 4.37.b);

1r3 = 1r4 = 1r5 = 1r8 (caso 2 e Figura 4.37.b); 1r1 = 7rg (casos 1, 2 e relação 1r4 = 7rs) e,

portanto, 7ri = 7ro/2 Vi E {1, ... , 8} e 1ri =O Vi E GI(P) \ {1, ... , 8}. Assim podemos concluir que existe um a E IR+ tal que

ViE{1, ... ,8} para i= O V i E GI(P) \ {1, ... , 8}

o


'

7

,.... 3 - -

(a) (b)


Capítulo 5

Modelando o RG-P como um Set Partitioning Problem

Neste capítulo apresentamos uma outra formulação para o problema RG-P através de uma

redução deste ao Set Partitioning Problem. Embora esta formulação nos leve a um número maior de variáveis, veremos que os limites inferiores fornecidos por ela são garantidamente pelo menos tão bons quanto aqueles obtidos com a formulação do capítulo anterior. Além

disso, no próximo capítulo veremos que é possível fazer-se uso desta formulação na prática

através de um algoritmo de geração de colunas.

5.1 Set Partitioning Problem (SPP)

Seja H= {1, ... ,m},K = {K1 , ... ,Kn}, onde Kj C H,j E J subconjunto J* Ç J define uma partição de H se

j, f E J*, j -j. f ====> Kj n Ke = 0

{1, ... ,n}. Um

(5.1)

(5.2)

Considere Cj > O um custo associado a cada Kj E K. O custo total da partição

é EjeJ• Cj. O problema Set Partitioning consiste em encontrar uma partição de custo mínimo. Usando programação linear inteira 0-1 podemos modelá-lo como

n

mmzmzze L: CjYj j=l

n

Sujeito a L: aijYj = 1, i= 1, ... , m j=l

54

5.2. Modelando o Problema RG-P como um SPP .).)

onde

Yi = {

Yi E {0,1}, j = 1, ... ,n

1 se Kj está na partição O caso contrário

{ 1 se i E Kj

a;j = O caso contrário

5.2 Modelando o Problema RG-P como um SPP

Antes de passarmos à modelagem do RG-P como um SPP, considere a seguinte definição.

Definição 5.1 Seja I = (R, P) uma instância de RG-P e GI(P) a grade induzida cor

respondente a I. Cada retângulo da partição retangular induzida por G I( P) em R é dito

ser um retângulo canônico.

Um exemplo desta definição pode ser visto na Figura 5.1. Note que o número de retângulos canônicos é O(IPI 2

).

Agora para modelarmos o problema RG-P como um Set Partitioning precisamos definir os conjuntos H; K e os valores de Yi e aij· Para isto, considere a instância I= (R, P) do problema RG-P. Define-se:

• H= {1, ... , m }, m é o número de retângulos canônicos em R, K = {R1 , ... , Rq}, é o conjunto de todos os retângulos sem pontos terminais no interior e que têm como lados segmentos de GI(P) ejou parte da borda de R. Note que pelo Teorema 2.5 temos que q = O(IPI 4

) (veja Figura 5.l.c).

• O custo Cj associado a cada retângulo Rj E K é definido como o perímetro ponderado de Rj. Este perímetro ponderado é calculado da seguinte maneira: se Rj tem um lado l que está na borda do retângulo R, então l tem peso igual a 2, senão l tem peso 1 (veja Figura 5.2).

• Os valores de y j e a;j são dados por:

Yi = { 1 se o retângulo Rj está na partição O caso contrário

5.2. .\[ode/ando o Problema RG-P como um SPP

se o retângulo canônico i está contido no retângulo j caso contrário

.j6

ou seja, queremos que a área de cada retângulo canônico seja coberta por um e somente um retângulo Rj.

Não é difícil ver que o programa linear inteiro para o SPP definido como acima é urna formulação correta para o RG-P, ou seja, todo vetor 0-1 satisfazendo às restrições do SPP são vetores característicos de partições retangulares de R e vice-versa. Note que existe urna e somente urna restrição para cada retângulo canônico. Portanto a formulação através do SPP tem O(IPI 2

) restrições e O(IPI 4) variáveis.

2,.----.------, I I I I I

1 ------·------

o

o

1

(a)

1

1

1

1

2

1 1

o 1 1

(b)

2 ,....-----,

2

2 o

E

1

(c)

2

2

2 ....-----.

o 2

F

1 2 o 2

Figura 5.1: (a) Uma instância I= (R, P) do problema RG-P. (b) Retângulos canônicos em R. (c) Retângulos definidos em R, sem pontos terminais no interior, que contêm no mínimo um retângulo canônico (p.ex. o retângulo E contém os retângulos canônicos A e B).

Denotaremos por Fseg a formulação baseada em segmentos de GI(P) (capítulo 4) e por FRet a formulação baseada em retângulos (redução do RG-P ao SPP).

5.2. Modelando o Problema RG-P como um SPP 57

2 ,....---,.-----,

1 ------·------'

o 1 2

Figura 5.2: Urna instância I= (R,P) (0,0,2,2,{1,1}) do problema RG-P. Considere Ri com vértices (0, 0), (1, 0), (1, 1), (0, 1). Como Rj tem os lados [(0, 0), (1, O)] e [(0, 0), (0, 1)] que estão na borda de R, então estes lados terão peso 2 no cálculo do perímetro ponderado, isto é, Cj = 2 * c[(O, 0), (1, O)]+ c[(1, 0), (1, 1)] + c[(1, 1), (0, 1)] + 2 * c[(O, 1), (0, 0)], onde c[(t, u), (v, x)] representa o comprimento do segmento [(t, u), (v, x)]. Para o retângulo Ri tem-se que c1 = 6.

O Teorema a seguir estabelece a relação entre as soluções ótimas inteiras de Fseg e

FRet·

Teorema 5.1 Considere uma instância I = (R, P) do problema RG-P. Seja x* uma

solução ótima inteira de valor Z* obtida por Fseg ao resolver a instância I. A nalogamente1

seja y* uma solução ótima inteira de valor W* obtida por FRet ao resolver a mesma

instância. Então W* = 2Z* + 2Per(RL onde Per(R) é o perímetro do retângulo R.

Prova:

Seja f um segmento de reta que pertence ao lado de um retângulo em y*. Se f E G I ( P), então este segmento é contado duas vezes em y*, isto é, existe um outro retângulo em y*

que tem este mesmo segmento em um dos seus lados. Agora se f rf. GI(P), ou seja, f está na borda de R, então pela forma como foram definidos os pesos das variáveis na função objetivo, f contribuirá para W* com o dobro do seu comprimento. Mas neste caso, este comprimento não é contabilizado em Fseg· Portanto, W* = 2Z* + 2Per(R). o

Provaremos abaixo que o valor do limitante inferior obtido pela relaxação linear de FRet é sempre maior ou igual do que aquele obtido pela relaxação linear de Fseg·

Teorema 5.2 Seja w· o valor da relaxação linear de FRet e Z* o valor da relaxação

linear de Fseg para uma instância I = (R, P) do RG-P. Então W* 2:: 2Z* + 2Per(R).

Além disso 1 as formulações não são equivalentes.

Prova: Para provar que W* 2:: 2Z* + 2Per(R) é suficiente mostrar que: dada urna solução

qualquer y, que satisfaz às restrições de FRet, y pode ser transformada numa solução x,

5.2. Modelando o Problema RG-P como um SPP .)8 •

que satisfaz às restrições de Fseg . .Mostrando que esta transformação existe, fica claro que o custo de x tem que ser maior ou igual a Z*, caso contrário teremos encontrado uma

solução, no caso x, que satisfaz às restrições de Fseg e tem custo menor do que z·, que é um absurdo, pois Z* foi assumido ser um limitante inferior para Fseg·

Vamos mostrar que o vetor de incidência y pode ser transformado para o vetor de

incidência x que satisfaz às restrições de Fse9 , isto é, x satisfaz às inequações das classes I, II e para cada variável X 8 , onde sé um segmento de GI(P), X 8 ~O e X 8 :S: 1.

Seja fs o conjunto dos retângulos em y que têm um segmentos E GI(P) como parte

de um dos seus lados. Note que X 8 = ~ Lker. Yk, pois cada segmento de GI(P) que é parte de um lado de um retângulo em y é contado duas vezes.

Caso 1: Inequação Xs ~O V sE GI(P).

Como Xs é dado por ! Lker. Yk, então Xs ~O sE GI(P).

Caso 2: Inequação Xs :::; 1 V sE GI(P).

Todo segmentos de GI(P) é lado de exatamente dois retângulos canônicos R! e R;. Como LJ=t aR~,jYj = 1 e LJ=l aR~.jYj = 1 (restrições do modelo do set partitioning) tem-se que

1 1 q q

Xs = 2 L Yk :S: 2(?: aR;,jYj + ?= aR~,jYj) :S: 1. ker. J=l J=l

O menor ou igual na última relação se justifica porque alguns retângulos que cobrem R! e R; não têm o segmentos como parte de seus lados.

Caso 3: Inequação Xi(l) + Xi( 2) ~ 1 para todo ponto terminal i.

Observe a Figura 5.3.

R.4 1

R.l

4 2

i

3 R.3 R.2

Figura 5.3: Retângulo com os segmentos incidentes em um ponto terminal i. Os retângulos R 1

, R2, R3 e R4 são retângulos canônicos.

Usaremos a notação Li,j para representar o somatório das variáveis definidas em y,

associadas aos retângulos sem pontos terminais no seu interior, que cobrem simultaneamente os retângulos Ri e Rj.

.5.2. Modelando o Problema RG-P como um SPP .)9

Vamos calcular os valores de Xi(l) e x;(2). Observe a Figura 5.3 para entender as relações abaixo.

1 Xi(l) = 2CL:+ I:+ I:+ L)

1,1 1,2 3,4 4,4

1 Xi(2) = 2(2:::+ I:+ I:+ L)

1,1 1,4 2,2 2,3

Xi(1) + Xi(2) = 1 +L ~ 1, 1,1

pois 2:1,1 ~ O. Note que os termos entre parênteses na penúltima relação são restrições do modelo do set partitioning.

Caso 4: Inequação Xi( 1) + Xi(2) - Xi(3) ~ O para todo ponto de Steiner i.

Observe a Figura 5.4.

a• 1 at

4 2

,i I I

a3 :3 a2 I I I

Figura 5.4: Retângulo com os segmentos incidentes em um ponto de Steiner z. Os retângulos R1

, R2, R3 e R4 são retângulos canônicos.

Seja Cio conjunto dos retângulos cobrindo Ri, mas não cobrindo pelo menos um Ri, j E {1,2,3,4} \{i}.

Note que I:jeCi Yi = a ~ 1 para i = 1, ... , 4; a ~ 1 pois I:jeCi Yi é uma parte de I:jeCi;; Yi = 1 (restrição do modelo do set partitioning, onde C~ representa o co~junto de todos os retângulos sem pontos terminais no interior que cobrem o retângulo R').

Observe que podemos expressar Lkecm Yk para algum mE {1, 2, 3, 4} como uma soma de I:i,j para i e j E {1,2,3,4}. Por exemplo,

L Yi = L+ L+ L = a ~ 1 ieC3 2,3 3,3 3,4

L Yi =L+ L+ L= a~ 1 jEC4 1,4 3,4 4,4

5.2. Modelando o Problema RG-P corno um SPP 60

Agora vamos calcular o valor de Xi(l) + X;( 2) - X;(3 ). ~ote que

1 Xi(1) = 2(L+ L:+ L:+ L)

1,1 1,2 3,4 4,4

1 Xi(2) = 2(L +L+ L+ L)

1,1 1,4 2,2 2,3

1 -Xi(3) = -2(L+ L:+ L:+ L)

1,2 2,2 3,3 3,4

então

Xi(1) + Xi(2) - Xj(3) = L+ L ;::: o. 1,1 2,3

Agora provaremos que Fseg e FRet não são equivalentes. Para isto é suficiente mostrar

uma instância do RG-P, cujo valor da relaxação linear de Fseg é menor do que o valor da relaxação linear de FRet· A Figura 5.5 mostra uma instância onde isto ocorre. D

Os resultados apresentados neste capítulo e no capítulo 4 são estendidos no capítulo 7 para os problemas da Tabela 2.1.

.5.:2. :Hodelando o Problt'ma RG-P como um SPP

: ::::::::t:::::t~~~J:::::::::::::::::t:::::: ........ J ..... J .... J ................ J ...... .

! ! ! !

... LLJ ..... L. I I I I

(a)

' '

' ······-----.. ·-·-~ ' ' ' ' ' ' ' ' ' ' ' ' · ------r----~-----r ' '

J -----.b.-----C>--·--9-: ---+---f

(b) (c)

Figura 5.5: (a) Uma instância do problema RG-P e sua grade induzida. (b) Uma solução ótima fracionária resultante da relaxação linear de Fseg· (c) Uma solução ótima inteira obtida da relaxação linear de FRet· Em (b) os valores das variáveis associadas aos segmentos pontilhados tem valor 0.5. Em (b) e (c) os valores das variáveis associadas aos segmentos de reta "cheios" tem valor 1. Os custos das soluções em (b) e (c) são 14.5 e 15, respectivamente.

Capítulo 6

Resultados Computacionais

Para as formulações de segmentos (capítulo 4) e de retângulos (capítulo 5) implementamos um algoritmo branch-and-cut e um algoritmo branch-and-price, respectivamente. As implementações foram feitas na linguagem de programação C e o código de programação linear usado foi o CPLEX (versão 3.0) [5]. Os testes computacionais foram feitos numa SUN SPARC 1000.

A implementação do algoritmo branch-and-cut foi baseada na descrição apresentada por Jünger, Reinelt e Thienel (1994) [16]. Na implementação do branch-and-price utilizamos o software MINTO ( Mixed INTeger Optimizer) [28]. MINTO é um software que resolve programas lineares inteiro misto através de um algoritmo branch-and-bound usando relaxações lineares. Ele também provê um ambiente para desenvolvimento de rotinas de pré-processamento, heurísticas primais, geração de restrições e geração de colunas. Através destas rotinas o usuário "customiza" o código do MINTO para as particularidades do seu problema.

Nas seções 6.1 e 6.2 são apresentadas decisões de implementação para os algoritmos branch-and-cut e branch-and-price, e na seção 6.3 apresentamos os resultados computacionais para estes algoritmos e para os algoritmos de aproximação GZ85, GRZ93 e DPS86.

6.1 Algoritmo Branch-and- Cut

Nesta seção descrevemos a política de separação, seleção do próximo nodo a ser explorado, a regra de branching e como detectamos tailing-off para o algoritmo branch-and-cut.

Por desconhecimento de argumentos geométricos que permitissem tornar mais compacta a formulação, não foi possível implementar qualquer tipo de pré-processamento. Foi implementada uma heurística primai, mas devido à sua ineficiência em gerar boas soluções inteiras e por consumir razoável tempo de cpu, esta não foi incluída no código do branch-and-cut.

62

6. L. Algoritmo Branch-and-Cut •

Na implementação do algoritmo branch-and-cut incorporamos um procedimento que verifica se é possível fixar variáveis a partir da informação dos seus custos reduzidos. Devido ao upper bound que fornecemos ao branch-and-cut ser razoavelmente ruim, este procedimento não surtiu o efeito desejado.

Para as instâncias testadas a formulação inicial é composta somente das classes de ine

quações I e li (ver capítulo 4). Na fase de cutting planes verificamos se alguma inequação das classes III, IV, V e VI é violada pela solução corrente.

6.1.1 Política de Separação

Em virtude do número de inequações das classes III, IV, V e VI ser da ordem de n,

decidimos resolver exatamente o problema de separação para estas classes. Resolvido o

problema de separação, todas as inequações violadas (caso exista alguma) são incluídas na formulação do nodo que está sendo explorado.

6.1.2 Seleção do No do

A estratégia para escolher o nodo a ser explorado foi a best bound, isto é, escolhemos o nodo com menor valor de função objetivo. Usando esta estratégia a árvore de branch-and

cut é explorada mais uniformemente e, portanto, aumenta a chance de se encontrar boas soluções inteiras. Entretanto, a lista de nodos não explorados pode ser muito grande. A vantagem desta estratégia é que pode-se evitar enumerar porções desnecessárias da árvore de branch-and-cut através do processo de poda por bounds.

6.1.3 Regra de Branching

Adotamos a estratégia de branching tradicional, isto é, escolhe-se uma variável fracionária

Xi que tem valor mais próximo de 0.5 e geramos dois novos subproblemas, um com Xi =O

e outro com Xi = 1. Testamos uma outra regra de branching, onde a variável fracionária escolhida é aquela

com valor mais próximo de 1. Esta estratégia mostrou-se muito ruim, ou seja, o número

denodos da árvore de branch-and-cut é significativamente maior do que o da árvore obtida usando a estratégia anterior.

6.1.4 Deteção de Tailing-off

Tailing-off é um fenômeno que pode ocorrer durante a fase de cutting-planes em um algoritmo branch-and-cut, quando mesmo incluindo inequações violadas ao problema, o

6.2. Algoritmo Branch-and-Price 64

ganho no valor da função objetivo é muito pequeno. Alguns autores sugerem que ao invés

de continuar resolvendo o problema de separação é melhor partir para a fase de branching.

A fim de detectar a ocorrência de tailing-off, em cada nodo da árvore de enumeração

do algoritmo branch-and-cut verificamos: se a mudança total no valor da relaxação linear

durante as 10 últimas iterações é menor do que 0.01 porcento (0.0001 vezes o valor da relaxação linear corrente), então forçamos um branch.

6.2 Algoritmo Branch-and-Price

A implementação de um algoritmo branch-and-price envolve muitas questões, como por

exemplo: como inicializar o algoritmo de geração de colunas (conjunto inicial de colunas),

como resolver o subproblema de pricing (algoritmo exato versus algoritmo aproximado),

qual estratégia de seleção de colunas adotar (gerar múltiplas ou uma única coluna a cada

iteração do algoritmo de geração de colunas), como implementar branching eficientemente

etc. A eficiência da implementação de um branch-and-price está estreitamente relacio

nada às decisões tomadas para estas questões. François Vanderbeck (31] em sua tese de

doutorado relata como estes aspectos influenciam na eficiência de um branch-and-price.

Nesta seção apresentamos as nossas decisões de implementação para o algoritmo

branch-and-price. Chamaremos de master LP a formulação de retângulos, sem as res

trições de integralidade.

6.2.1 Conjunto Inicial de Colunas

O algoritmo de geração de colunas precisa ser inicializado com uma solução viável do

master LP. Para prover este conjunto inicial de colunas (variáveis) usamos o algoritmo

de aproximação de corte guilhotina ótima (seção 2.5), ou seja, a partir dos segmentos

obtidos pelo algoritmo DPS86 identificamos os retângulos na partição guilhotina ótima.

Lembre-se que a cada retângulo, canônico ou não, associamos uma variável (coluna) do problema master LP. Além destas colunas obtidas a partir do algoritmo DPS86, incluímos também no conjunto inicial de colunas as colunas associadas aos retângulos canônicos.

Este conjunto inicial de colunas é normalmente denominado, na literatura, como res

tricted master LP.

6.2.2 Subproblema de Pricing

Dado que inicializamos o algoritmo de geração de colunas com um conjunto inicial de

colunas (solução viável para o master LP), precisamos checar se existe alguma variável

que não está na formulação corrente e que tem custo reduzido negativo, ou seja, precisamos

6.2. Algoritmo Bmnch-and-Prict {).j

resolver o problema de pricing. Caso exista uma variável não básica yP com custo reduzido negativo, salvo degenerecência, a introdução desta variável na base do restricted master

LP melhora a solução corrente. Caso contrário a base corrente é ótima.

Quando o CPLEX otimiza um problema primai ele produz tanto a solução primai

quanto a solução dual. Assim após otimizar o restricted master LP, os valores das variáveis

duais são coletados e podem ser usados para resolver o problema de pricing. A razão para "exigirmos" que o algoritmo de geração de colunas comece com uma solução viável para o

master LP, é justamente para que tenhamos informação dual apropriada para passarmos para o subproblema de pricing.

Sejam 1r E JRm, onde m é o número de retângulos canônicos, as variáveis duais e cP

o coeficiente da variável Yp na função objetivo. Se a condição de otimalidade se mantém, isto é, o custo reduzido mínimo é não negativo, ou seja,

m

minPE{l, ... ,q}{S,- 2:.::: Jriaip} ~O, i=l

então o problema master LP foi resolvido. Note que pelo Teorema 2.5 temos que q =

O(IPI 4).

Para o problema RG-P o problema de pricing pode ser resolvido exatamente em tempo

O(n4 ), isto é, como o número de colunas na formulação baseada em retângulos é da ordem de n4

, resolver o problema de pricing para o RG-P se reduz ao problema de identificar a

coluna com menor custo reduzido negativo. Neste trabalho não pudemos investigar mais

profundamente o problema de pricing. Uma questão interessante seria investigar se existe um algoritmo para encontrar a variável com menor custo reduzido cuja complexidade seja O(n4-~) para algum E: > O. Ou seja, se é possível encontrar a variável com menor custo reduzido através de um algoritmo assintoticamente melhor do que aquele que faz

enumeração de todas as variáveis. Embora o problema de pricing para o RG-P possa ser resolvido em tempo polinomial,

resolvê-lo exatamente a cada iteração do algoritmo de geração de colunas consome uma quantidade razoável de tempo. A seguir discutiremos como usar esse algoritmo da melhor

forma.

6.2.3 Estratégia de Seleção de Colunas

Quanto à seleção de colunas, precisamos decidir se a cada iteração do algoritmo de geração

de colunas, adicionaremos ao restricted master LP uma única coluna ou múltiplas colunas.

François Vanderbeck [31] relata que, caso o subproblema de pricing possa ser resolvido bastante eficientemente, então adicionar ao restricted master LP a coluna com menor custo reduzido é superior à estratégia de adicionar múltiplas colunas, a cada iteração do algoritmo de geração de colunas. Entretanto, quando resolver o subproblema de pricing é

6.:2. Algoritmo Brnnch-arul-Price 66

computacionalmente "caro", a estratégia de adicionar múltiplas colunas é a que funciona melhor.

A fim de verificar se o argumento acima é também válido para o problema RG-P,

decidimos testar as duas estratégias para o branch-and-price que implementamos.

6.2.4 Regra de Branching

A estratégia de branching que adotamos foi sugerida por Ryan e Foster (1981) [26]. O motivo de não usarmos a regra de branching tradicional é devido ao fato que esta gera

uma separação desbalanceada dos subproblemas. O espaço de soluções do subproblema com Yi = 1 (Yi é a variável fracionária com valor mais próximo de 0.5) é muito restritivo. Já no espaço de soluções para o subproblema com Yi = O somente uma coluna é excluída,

fazendo com que este subproblema não seja muito mais restritivo do que o seu nodo predecessor.

Ryan e Foster [26] sugerem uma estratégia de branching para problemas do tipo set

partitioning baseada na seguinte proposição.

Proposição 6.1 Se A é uma matriz 0-1 e uma solução básica para A,\ = 1 é fracionária,

isto é, no mínimo um dos componentes de ,\ é fracionário, então existem duas restrições

r e s do master LP tal que

0<

Usando-se o resultado da proposição anterior gera-se o par de restrições de branching

e

ou seja, os retângulos canônicos r e s têm que ser cobertos por colunas diferentes ( branch

da esquerda) e ambos devem ser cobertos pela mesma coluna ( branch da direita). Como o número de pares de restrições do master LP é O(m2

), então o algoritmo de branch-and-price termina após um número finito de branches. Note também que pela Proposição 6.1 se não for identificado um par de restrições de branching, então a solução

para o master LP é uma solução inteira.

Vanderbeck [31] generaliza a Proposição 6.1 para o caso quando o lado direito das equações do problema set partitioning são inteiros positivos quaisquer.

6 . .'3. Testes Computacionais 61

6.3 Testes Computacionais

Nesta seção discutimos os experimentos computacionais realizados neste trabalho. Ini

cialmente, fazemos uma descrição da forma como geramos as instâncias de teste. Em seguida, fazemos uma comparação dos resultados obtidos por diferentes algoritmos de

aproximação sugeridos na literatura. Finalmente, apresentamos os resultados obtidos pe

los algoritmos branch-and-cut e branch-and-price propostos neste trabalho para resolução

exata do RG-P e nos dedicamos à análise dos resultados obtidos.

6.3.1 Instâncias

Consideramos duas categorias de instâncias. Na primeira, o conjunto P é um conjunto

co-retilinear e na segunda P é um conjunto não co-retilinear. Consideramos, ainda, os pontos no conjunto P estarem no interior de retângulos com dimensões 20 por 20 e 50 por

50. Foram geradas no total 35 instâncias, sendo 25 delas com pontos não co-retilineares.

A justificativa para esta decisão é devido ao fato de termos percebido, experimental

mente, que instâncias com o conjunto P não co-retilinear parecem ser mais difíceis do que instâncias com P co-retilinear. Por simplicidade, todos os pontos em P tem coordenadas inteiras, isto é, para todo ponto p = (x,y) E P, x e y são números inteiros positivos.

Para gerar os pontos em P usamos um gerador de números pseudo aleatórios com distribuição uniforme.

6.3.2 Resultados para os Algoritmos GZ85, GRZ93 e DPS86

Conforme descrito nos objetivos deste trabalho, esta seção apresenta uma comparação

entre alguns dos algoritmos de aproximação para o RG-P existentes na literatura. Os resultados obtidos encontram-se nas Tabelas de 6.1 a 6.3, onde a coluna IPI representa a

cardinalidade do conjunto P e as colunas Valor e Tempo representam, respectivamente, valor da solução obtida pelo algoritmo e o tempo de cpu para obtê-la.

Para todas as instância testadas, os algoritmos GZ85 e GRZ93 geraram suas soluções em tempos inferiores a 1 segundo. Embora o algoritmo GZ85 tenha limite de aproximação

maior do que o do algoritmo GRZ93, o GZ85 sempre gerou soluções com valores menores do que o GRZ93. Acreditamos que isto se deve ao fato do algoritmo GZ85 só introduzir segmentos, para a partição, que passam por pontos terminais. Enquanto os segmentos introduzidos pelo GRZ93 não necessariamente passam por pontos terminais. Observamos também que quando consideramos pontos não co-retilineares o algoritmo GZ85 gera

soluções com valores bastante próximos dos valores de partições guilhotina ótima. Mas para instâncias com P co-retilinear o algoritmo GZ85 parece não "conservar" esta propri

edade, por exemplo observe a instância com IPI = 200.

6.3. Testes Computa.cionais 68

E sabido que o algoritmo DPS86 sempre gera soluções com valores no mínimo tão bons quanto os valores encontrados por GZ85 e GRZ93, isto é, estes três algoritmos geram partições guilhotina, mas somente DPS86 é garantidamente gera partições guilhotina ótima. Devido a isto, usaremos os valores das soluções geradas pelo DPS86 como upper

bound no valor de uma solução ótima, quando testando os algoritmos exatos nas seções 6.3.3 e 6.3.4.

Instância Alg. GZ85 Alg. GRZ93 Alg. DPS86 IPI Valor Valor Valor Tempo 20 137 142 112 2s 35 183 221 154 2s 50 223 251 196 3s 80 273 301 229 9s 100 300 325 259 8s 120 326 351 285 12s 150 367 392 307 lOs 170 399 409 324 9s 190 402 412 337 7s 200 419 433 341 13s

Tabela 6.1: Instâncias com pontos co-retilineares para um retângulo 20 x 20.

Instância Alg. GZ85 Alg. GRZ93 Alg. DPS86

IPI Valor Valor Valor Tempo 15 120 134 120 < ls 16 124 126 124 < ls 17 125 147 122 ls 18 134 144 134 ls 19 140 168 140 3s

Tabela 6.2: Instâncias com pontos não co-retilineares para um retângulo 20 x 20.

6.3.3 Resultados para o Branch-and-Cut

Nesta seção discutimos os resultados obtidos pelos algoritmos branch-and-bound e branch

and-cut usando a formulação apresentada no capítulo 4. As colunas Restr e V ar, Ótimo

6.3. Testes Computaciunai::> 69

Instância Alg. GZ85 Alg. GRZ93 Alg. DPS86 IPI Valor Valor Valor Tempo 20 343 429 341 3s 21 364 479 358 5s 22 365 429 365 1s 23 395 527 392 3s 24 400 527 398 8s 25 399 511 397 8s 26 423 573 421 3s 27 4?-~v 549 424 9s 28 440 493 437 6s 29 438 530 435 12s 30 437 517 435 lls 31 457 579 449 15s 32 490 585 484 17s 33 484 626 482 18s 34 478 628 475 17s 35 487 623 486 21s 36 492 621 491 24s 37 495 551 493 22s 38 519 665 505 35s 39 529 609 526 38s

Tabela 6.3: Instâncias com pontos não co-retilineares para um retângulo 50 x 50.

6 . .'J. Teóites Cornputaciona.is 70

e LVodos nas Tabelas de 6.4 a 6.11 representam, respectivamente, número de restrições e de variáveis na formulação, valor de uma solução ótima e número de nodos na árvore de enumeraçao.

Nas Tabelas deste capítulo estamos usando o símbolo (I) ao lado do valor da solução

obtida pela relaxação linear da formulação, para dizer que esta é uma solução ótima inteira.

Para as instâncias com o retângulo R tendo as dimensões 20 por 20, averiguamos qual das seguintes abordagens funciona melhor: (a) resolver a instância usando um algoritmo branch-and-bound a partir da formulação base (classes de inequações I e li), (b) usar o

algoritmo branch-and-bound tendo como formulação as classes I, II, III, IV, V e VI, ou seja, todas as inequações que conhecemos para o RG-P, (c) usar o algoritmo branch-and

cut com as classes III, IV, V e VI sendo separadas quando são necessárias, ou seja, quando são violadas pela solução corrente em um nodo da árvore de branch-and-cut.

Comparando os resultados das Tabelas 6.4, 6.5 e 6.6 (6.7, 6.8 e 6.9) notamos que a

abordagem (b) funciona melhor. Note que há uma redução drástica no tempo de cpu e no número de nodos da árvore de branch-and-bound. Isto evidencia que as classes III, IV e V parecem ser bastante úteis na descrição do poliedro Pn. Esta conclusão é reforçada

pela comparação entre as Tabelas 6.4 e 6.5, 6.7 e 6.8, 6.10 e 6.11. Perceba que a inclusão das inequações das classes IV e V para as instâncias maiores (Tabelas 6.10 e 6.11) implica uma melhora do lower bound da relaxação linear, de cerca de 10%, enquanto que esta mesma melhoria estava na faixa de 2 a 4% para instâncias menores (Tabelas 6.4 e 6.5, 6.7

e 6.8). Comparando as abordagens (a) e (b) para a instância com IPI = 200 (Tabelas 6.4 e 6.5) a abordagem (b) é 238 vezes mais rápida do que a abordagem (a) e o número de

nodos da árvore de branch-and-bound da primeira é 1477 vezes maior. Para as instâncias com pontos não co-retilineares não foi possível um ganho de tempo da mesma magnitude,

mesmo assim a instância maior (IPI = 19) foi resolvida 7 vezes mais rápido. Claramente existe uma diferença entre a dificuldade de resolver instâncias com pontos co-retilineares e instâncias com pontos não co-retilineares.

Note que a classe VI é muito rara, ou seja, nas 35 instâncias testadas a configuração de pontos desta classe nunca ocorreu.

Vale ressaltar que em todas as instâncias testadas o algoritmo de aproximação não foi capaz de obter soluções ótimas. Embora o limite de aproximação do algoritmo DPS86 seja de 1.75, note que em média os valores das soluções obtidas por este distam de 10%

dos valores de soluções ótimas. Tentamos testar estas mesmas três abordagens quando considerando o retângulo com

dimensões 50 por 50 e com P não co-retilinear. Ao contrário das instâncias com R tendo dimensões 20 por 20, não foi possível resolver o problema, pois suas relaxações lineares consumiam uma quantidade razoável de tempo de cpu. Para se ter uma idéia, executamos

6.:). Testes Computi:Lcionais 71

o branch-and-cut para a instância com /P/ = 20 e este após 20 horas de tempo de cpu ainda não havia encontrado uma solução inteira e estava consumindo mais de 100 megabytes de memória. Devido a estes números decidimos não ':atacar" estas instâncias nem com o branch-and-bound nem com o branch-and-cut restringindo-nos a resolver somente as suas relaxações lineares. Ao comparar os resultados das Tabelas 6.10 e 6.11, percebe-se que com a inclusão das classes IV e V diretamente na formulação, o bound fornecido pela relaxação linear é substancialmente melhor do que aquele obtido quando temos a formulação consistindo somente das classes I e II.

Pudemos também observar, experimentalmente, que o que torna uma instância "difícil" de resolver não é a cardinalidade de P, mas sim a disposição geométrica dos pontos no interior de R. Mais precisamente, percebemos que instâncias com P não co-retilinear parecem ser mais difíceis do que instâncias como P co-retilinear. Note que instâncias com P não co-retilinear são instâncias que definem o problema RG-NLP (ver Tabela 2.1). Isto parece reforçar a conjectura (capítulo 2) de que, também para este tipo de instância, o problema de decisão do RG-P pertence à classe de problemas NP-completos.

Instância Alg. DPS86 Relaxação Branch-and-Bound

/P/ Valor Tempo Restr V ar Valor Tempo Otimo Nodos Tempo 20 112 2s 1376 391 101.71 7s 108 176 2m27s 35 154 2s 2036 577 140.87 lOs 145 99 lml3s 50 196 3s 2536 721 172.58 25s 176 62 lm40s 80 229 9s 2568 760 207(I) 12s 207 1 12s 100 259 8s 2488 760 236.89 16s 239 50 5ls 120 285 12s 2408 760 257.75 13s 264 3011 13ml9s 150 307 lOs 2288 760 280.25 12s 283 120 lmOOs 170 324 9s 2208 760 300.09 lOs 303 173 57s 190 337 7s 2128 760 305.44 8s 312 44716 lh35ml4s 200 341 13s 2088 760 314.50 9s 321 36927 lh23m24s

Tabela 6.4: Instâncias com pontos co-retilineares para um retângulo 20 x 20. Formulação apenas com as classes de inequações I e II.

6.3.4 Resultados para o Branch-and-Price

Nesta seção discutimos os resultados obtidos pelo algoritmo branch-and-price baseado na formulação apresentada no capítulo 5.

Nas Tabelas de 6.12 a 6.16 as colunas LB, Ótimo, Nados, Tempo, Colsln, Restr e Gols representam, respectivamente, o valor da relaxação linear obtido pelo algoritmo de

6.3. Testes Computacionais 72

Instância Relaxação Branch-and-Bound

IPI Valor Tempo Nodos Tempo Inequações 20 10:3.92 5s 38 50s 46(IV) 35 142.22 15s 43 1m04s 91(IV)I1(V) 50 174.17 21s 9 31s 5(III) I 111 (IV) I 1 (V) 80 - - - - -

100 238.00 15s 2 15s 17(III)I146(IV)I4(V) 120 261.34 14s 95 1m 50s 32(III) I 128(IV) I2(V) 150 282.09 19s 2 19s 49(III)I117(IV)I3(V) 170 301.57 13s 17 17s 78(III) I79(IV) I 4(V) 190 309.72 7s 126 43s 83(III)I69(IV) 200 318.67 16s 25 21s 108(III) I65(IV) I2(V)

Tabela 6.5: Instâncias com pontos co-retilineares para um retângulo 20 x 20. Incluindo todas as inequações das classes I, II, III, IV, V e VI na formulação.

Instância Branch-and-Cut

IPI Nodos PLs Cortes Tempo 20 106 64 26(IV) 1m08s 35 98 58 24(IV) 1m04s 50 26 24 4(III) I38(IV) 11 (V) 47s 80 1 1 - 12s 100 4 5 13(III)I8(IV) 12s 120 268 156 25(III)I32(IV) 3m55s 150 14 12 21(III)I6(IV) 17s 170 148 81 47(III)I8(IV) 1m18s 190 1034 536 54(III)I11(IV) 8m07s 200 94 59 56(III)I6(IV) 1m01s

Tabela 6.6: Instâncias com pontos co-retilineares para um retângulo 20 x 20. Formulação apenas com as classes de inequações I e II. As classes III, IV, V e VI são incluídas na formulação somente quando são violadas em um nodo da árvore de branch-and-cut.

6 . .3. Testes Computacionais

Instância Alg. DPS86 Relaxação Branch-and-Bound

/P/ Valor Tempo Restr V ar Valor Tempo Otimo Nodos Tempo 15 120 < ls 1740 480 103.85 8s 110 120 lm52s 16 124 < ls 1984 544 100.90 13s 113 1722 37m00s 17 122 ls 2244 612 107.69 19s 119 4193 lh44m24s 18 134 ls 2520 684 108.41 2ls 124 4002 lh58ml2s 19 140 3s 2812 760 115.11 38s 127 8795 7hl4m35s

Tabela 6. 7: Instâncias com pontos não co-retilineares para um retângulo 20 x 20. Formulação apenas com as classes de inequações I e II.

Instância Relaxação Branch-and-Bound

/P/ Valor Tempo :\"o dos Tempo Inequações 15 106.38 lOs 39 59s 52(IV) 16 106.55 14s 434 13ml7s 52( IV) I 1 (V) 17 111.74 18s 769 23m48s 56(IV) 18 114.05 20s 3600 lh55m48s 57(IV) 19 119.63 49s 804 55m57s 66(IV)

Tabela 6.8: Instâncias com pontos não co-retilineares para um retângulo 20 x 20. Incluindo todas as inequações das classes I, II, IV, V e VI na formulação. A configuração de pontos da classe III não ocorre em instâncias com P não co-retilinear.

Instância Branch-and-Cut

/P/ Nodos PLs Cortes Tempo 15 102 60 38(IV) 2m04s 16 1070 605 45(IV)/l(V) 4lm48s 17 1702 979 52(IV) lh18m54s 18 7340 4189 52(IV) 6h48m52s 19 1550 791 60(IV) 2h42m48s

Tabela 6.9: Instâncias com pontos não co-retilineares para um retângulo 20 x 20. Formulação apenas com as classes de inequações I e II. As classes IV, V e VI são incluídas na formulação somente quando são violadas em um nodo da árvore de branch-and-cut.

6.3. Testes Computacionais ..

Instância Alg. DPS86 Relaxação

IPI Valor Tempo Restr V ar Valor Tempo 20 341 3s 3120 840 271.91 34s 21 358

,.. 3444 924 279.90 35s os

22 365 1s 3784 1012 283.36 54s 23 392 3s 4140 1104 292.53 lml2s 24 398 8s 4512 1200 312.37 1m12s 25 397 8s 4900 1300 305.50 2m07s 26 421 3s 5304 1404 317.17 2m15s 27 424 9s 5724 1512 314.38 2m55s 28 437 6s 6160 1624 327.14 3m00s 29 435 12s 6612 1740 320.07 3m26s 30 435 11s 7080 1860 326.87 4m48s 31 449 15s 7564 1984 347.55 5m25s 32 484 17s 8064 2112 314.50 6m27s 33 482 18s 8580 2244 338.30 7m30s 34 475 17s 9112 2380 346.35 9m05s 35 486 21s 9660 2520 344.88 13m30s 36 491 24s 10224 2664 347.97 15m47s 37 493 22s 10804 2812 338.50 15m19s 38 505 35s 11400 2964 376.86 17m28s 39 526 38s 12012 3120 368.86 18m28s

Tabela 6.10: Instâncias com pontos não co-retilineares para um retângulo 50 x 50. Formulação apenas com as classes de inequações I e II.

6.:J. Testes Computacionais

Instância Relaxação

IPI Valor Tempo Inequações 20 282.01 32s 66(IV) 21 294.64 50s 71(IV) 22 298.4 7 48s 74(IV)/1(V) 23 305.67 1m13s 82(IV) 24 327.63 1m24s 87(IV) 25 320.85 2m10s 88(IV) 26 334.53 2m36s 94(IV) 27 332.55 2m58s 100(IV) 28 342.61 3m20s 102(IV) 29 339.58 3m33s 106(IV) 30 344.90 4m57s 107(IV) 31 364.97 5m30s 114(IV) 32 335.95 6m44s 114(IV) 33 360.50 10m31s 120(IV) 34 369.14 9m20s 124(IV) 35 369.06 13m48s 124(IV) 36 371.48 13m00s 132(IV) 37 359.27 17m13s 132(IV) 38 404.54 17m33s 140(IV) 39 393.29 23m57s 146(IV)

Tabela 6.11: Instâncias com pontos não co-retilineares para um retângulo 50 x 50. Incluindo todas as inequações das classes IV, V e VI na formulação.

6 .. ). Tesff's Computacionais 16

geração de colunas no nodo raiz da árvore do branch-and-price, o valor de uma solução ótima, o número de nodos na árvore de enumeração do branch-and-price, o tempo de cpu gasto pelo algoritmo para provar a otimalidade de uma solução, número de colunas no master restricted LP no final da execução do branch-and-price, número de restrições e

número de variáveis no master LP. Usamos as colunas C'olsln e C'ols para contrastar o número de colunas que foram realmente necessárias para resolver uma instância e o número

de colunas do modelo master LP (formulação completa do modelo do set partitioning).

Nas Tabelas 6.12 e 6.13, 6.14 e 6.15 investigamos as estratégias de introduzir múltiplas colunas ou uma única coluna ao restricted master LP em cada iteração do algoritmo de

geração de colunas. Note que incluir múltiplas colunas ao restricted master LP em cada

iteração do algoritmo de geração de colunas funciona melhor, em relação ao tempo de cpu, do que inserir a coluna de menor custo reduzido. Mas na segunda estratégia são usadas bem menos colunas. Se conhecêssemos um algoritmo com complexidade de tempo menor do O(n4

) para resolver o problema de pricing, provavelmente poderíamos resolver

instâncias bem maiores do que as instâncias aqui apresentadas. Tentamos resolver uma

instância com 40 pontos não co-retilineares com R sendo 50 por 50, mas não conseguimos devido a quantidade de memória que era necessária.

Note que o limite inferior (LB) dado pela relaxação linear da formulação do set par

titioning é significativamente melhor do que o limite inferior fornecido pela formulação

apresentada no capítulo 4. Percebemos, novamente, que instâncias com P não co-retilinear parecem ser mais

difíceis do que instâncias com P co-retilinear. Para quase todas as instâncias conseguimos encontrar uma solução ótima inteira usando somente o algoritmo de geração de colunas no

nodo raiz da árvore do branch-and-price, ou seja, resolvendo a relaxação linear do master

LP. Note também que o número de colunas no restricted master LP no final da execução do branch-and-price é significamente menor do que o número de colunas no master LP.

Perceba que todas as instâncias com R tendo dimensões 20 por 20 e usando a estratégia de introduzir múltiplas colunas ao restricted master LP em cada iteração do algoritmo

de geração de colunas, são resolvidas em menos de 10 minutos de tempo de cpu. Em contraste, para resolver algumas instâncias com R sendo 50 por 50 e P não co-retilinear são necessárias algumas horas de tempo de cpu.

Das 35 instâncias que foram resolvidas pelo branch-and-price apenas em 7 a solução da relaxação linear não foi inteira. Destas 7 instâncias, 4 já têm o mesmo valor de uma

solução ótima. Em duas o valor da relaxação linear quando arredondado para cima já é

o valor de uma solução inteira (lembre-se que todos os custos das variáveis são inteiros). No que se refere à qualidade dos limitantes inferiores podemos dizer que o algoritmo

branch-and-cut com a formulação por segmentos é inferior ao algoritmo branch-and-price

com a formulação por retângulos, por outro lado, esta inferioridade já não é tão evidente

6.:$. Testes Computacionais 77

quando se comparam os tempos de computação. Assim, para instâncias co-retilineares, a comparação dos tempos das Tabelas 6.6 e 6.12 aponta para uma leve superioridade do algoritmo branch-and-cut. Já para instâncias com pontos não co-retilineares, as Tabelas 6.9 e 6.14 dão vantagem ao algoritmo branch-and-príce sendo que, para IPI = 18, este último foi 8.5 vezes mais rápido do que o branch-and-cut.

Note que somente com o branch-and-príce é que conseguimos resolver otimamente, em menos de 20 horas de tempo de cpu, as intâncias com R tendo dimensões 50 por 50 e P não co-retilinear.

Um fato interessante quanto às instâncias com P não co-retilinear é que, para todas as instâncias aqui testadas, o número de variáveis com valor 1 numa solução ótima inteira é sempre dado por IPI+ 1. Com isto surge a seguinte questão: é verdade que para instâncias com P não co-retilinear o número de retângulos numa partição ótima é sempre IPI + 1 ? Caso isto seja verdade, podemos usar este fato para construir um algoritmo de tempo polinomial para resolver estas instâncias ? Havendo um tal algoritmo, então RG-NLP

pertence à P e, supondo P =J. JVP, a conjectura atualmente existente na literatura [12] de que o RG-NLP é NP-completo seria falsa. Lembre-se que para este problema sabemos apenas que ele pertence a NP (veja Tabela 2.1).

Instância Branch-and-Price Master LP

IPI LB Otimo Nodos Tempo Colsln Restr Cols 20 108(1) 108 1 30s 1956 210 5196 35 145(1) 145 1 1m22s 2740 306 8116 50 176(1) 176 1 3m18s 3611 380 11004 80 207(1) 207 1 2m43s 3658 400 10157 100 239(1) 239 1 2m47s 3387 400 9591 120 264(1) 264 1 2m27s 3535 400 9269 150 283(1) 283 1 2m28s 3579 400 8809 170 303(1) 303 1 2m14s 3498 400 8578 190 312(1) 312 1 2m35s 3494 400 8529 200 321(1) 321 1 2m23s 3501 400 8385

Tabela 6.12: Instâncias com pontos co-retilineares para um retângulo 20 x 20. Resultados para estratégia de seleção com adição de no máximo 100 colunas ao restrícted master LP, em cada iteração do algoritmo de geração de colunas.

6.:]. Testes Computacionais 78

Instância Branch-and-Price

IPI LB 0.""odos Tempo Colsin 20 108(I) 1 17m30s 585 35 145(I) 1 54m42s 846 50 176(I) 1 2h04m59s 1137 80 207(I) 1 1h53m54s 1105 100 239(I) 1 1h52m40s 1127 120 264(I) 1 2h00m00s 1199 1.50 283(I) 1 1h44m34s 1140 170 303(I) 1 1h49m26s 1169 190 312(I) 1 1h45m39s 1152 200 321 46 2h35m05s 1455

Tabela 6.13: Instâncias com pontos co-retilineares para um retângulo 20 x 20. Resultados para estratégia de seleção com adição da coluna com custo reduzido mínimo ao restricted master LP.

Instância Branch-and-Price Master LP

IPI LB Otimo Nodos Tempo Colsin Restr Cols 15 110(I) 110 1 1m12s 2319 256 7262 16 113(I) 113 1 1m50s 2943 289 9292 17 117.67 119 27 8m04s 4131 324 11131 18 124(I) 124 1 4m47s 3860 380 13319 19 127(I) 127 1 6m.S0s 4469 400 15994

Tabela 6.14: Instâncias com pontos não co-retilineares para um retângulo 20 x 20. Resultados para estratégia de seleção com adição de no máximo 100 colunas ao restricted master LP, em cada iteração do algoritmo de geração de colunas.

6.:3. Testes C'omput;tcionais 79

Instância Branch-and-Price

IPI LB r\ odos Tempo Colsin 1.5 110(1) 1 35m38s 730 16 113(I) 1 1h05m17s 864 17 117.67 27 1h51m24s 1080 18 124(I) 1 2h21m12s 1080 19 127(1) 1 3h35m54s 1247

Tabela 6.15: Instâncias com pontos não co-retilineares para um retângulo 20 x 20. Resultados para estratégia de seleção com adição da coluna com custo reduzido mínimo ao restricted master LP.

Instância Branch-and-Price !vfaster LP

IPI LB Otimo Nados Tempo Colsln Restr Cols 20 311(I) 311 1 8m27s 4888 441 18731 21 323(I) 323 1 12m03s 5426 484 22214 22 331 331 2 17m47s 6095 529 26286 23 326(1) 326 1 21m47s 6513 576 28434 24 367(1) 367 1 32m09s 7492 625 32855 25 356(I) 356 1 44m59s 8284 676 37952 26 371(I) 371 1 1h02m38s 9006 729 43508 27 370(I) 370 1 1h24m36s 10115 784 47767 28 378(I) 378 1 1h52m35s 10590 841 54646 29 387(1) 387 1 2h31m17s 11360 900 62133 30 387 387 2 3h46m47s 20039 961 69612 31 410(1) 410 1 1h44m06s 20139 1024 76269 32 410(I) 410 1 2h12m45s 21735 1089 90257 33 423 423 3 7h18m57s 24298 1156 94713 34 418(1) 418 1 3h30m37s 24764 1225 104149 35 434.50 435 3 5h28m10s 28556 1296 116590 36 439.50 440 3 9h31m04s 28472 1369 123787 37 439(1) 439 1 7h38m26s 32082 1444 149378 38 457 457 2 17h44m47s 32983 1521 143874 39 462(I) 462 1 8h15m14s 34167 1600 157432

Tabela 6.16: Instâncias com pontos não co-retilineares para um retângulo 50 x 50. Resultados para estratégia de seleção com adição de no máximo 500 colunas ao restricted master LP, em cada iteração do algoritmo de geração de colunas.

Capítulo 7

Generalizações e Conclusões

Neste capítulo generalizamos os resultados apresentados nos capítulos 4 e 5 para atacar

outros problemas de decomposição de polígonos retilineares, e na seção 7.2 apresentamos as conclusões deste trabalho.

7.1 Generalizações

Antes de apresentrar como se generaliza os resultados dos capítulos 4 e 5 considere a seguinte definição.

Definição 7.1 Seja F um polígono retilínea r. O interior de F é a área entre a borda

externa de F e as bordas internas de F (bordas dos buracos no interior de F). Associado

a cada vértice de F existe um ângulo interno que é1 salvo degeneração1 de 90 graus ou de

210 graus. Um vértice com ângulo interno de 210 graus é chamado de vértice côncavo (veja Figura 7.1.b).

Para generalizar os resultados dos capítulos 4 e 5 é suficiente considerar cada vértice côncavo de um polígono retilinear F, como um ponto terminal no interior de F, ou seja,

pelo menos um dos dois segmentos da grade induzida de F, que são incidentes em cada vértice côncavo deve pertencer a uma partição retangular. A Figura 7.2 mostra a grade

induzida do polígono retilinear na Figura 7 .La. Desta forma tanto a formulação de segmentos (capítulo 4) quanto a de retângulos

(capítulo 5) podem ser usadas para resolver qualquer um dos problemas da Tabela 2.1. Existe uma série de outros problemas de particionamento de polígonos retilineares

([22]) onde suas instâncias são exatamente iguais às instâncias dos problemas apresentados na Tabela 2.1, mas as funções objetivo destes problemas minimizam o número de retângulos numa partição retangular. Claramente a formulação do capítulo 5 pode ser

adaptada para resolver também estes problemas.

80

/.1. Generalizações 81

(a) (b)

Figura 7.1: (a) Polígono retilinear com um buraco no seu interior. Em (b) cada vértice côncavo do polígono em (a) está indicado por um círculo.

--- <:>- ---- -Q-- --9- Q--- ------~ I I I I : I I I I 1

-- <:>- 9------ <:>--- ---1 I I I

--<:>-9---------.....1 1 I I 1 I I

--- <:>- .----'----e' -9- ---- --

Figura 7.2: Polígono retilinear e sua grade induzida. Os pontos terminais são representados por círculos "cheios" e os pontos de Steiner por círculos vazios.

7.2. Conclusões 82

Existe ainda um outro problema de decomposição de polígonos retilineares, cujas

instâncias são semelhantes às instâncias do problema RP-RPP, onde se deseja encontrar o número mínimo de retângulos que cobrem o polígono retilinear em retângulos ([22]),

ou seja, cada retângulo canônico da instância do problema RP-RPP deve ser coberto

por pelo menos um retângulo da partição retangular. Este problema pode ser facilmente modelado como um set covering problem. Fazendo poucas modificações na implementação

do branch-and-price que propomos podemos também resolver este problema.

7.2 Conclusões

Os resultados obtidos nos testes computacionais do capítulo anterior mostraram a viabilidade de se resolver de forma exata, através do uso de técnicas de programação linear inteira, instâncias de médio porte do RG-P quando o conjunto P é co-retilinear. Já

quando Pé não co-retilinear, as instâncias que podem ser resolvidas até a otimalidade são consideravelmente menores. Estes resultados parecem reforçar a conjectura existente na literatura de que a versão de decisão do problema RG-NLP é um problema JVP-completo.

Para chegar a estas conclusões, apresentamos duas formulações distintas do RG-P como um programa linear inteiro. Para a primeira formulação, baseada nos segmentos da

grade induzida, fazemos um estudo do poliedro associado ao problema, tendo encontrado várias classes de inequações definidoras de facets do mesmo. A utilidade computacional destas facets foi confirmada nos experimentos que realizamos. A segunda formulação, baseada no modelo do set partitioning, com variáveis associadas a retângulos mostrou

se superior à formulação anterior quando se considera o valor dos limitantes inferiores

fornecidos pelas relaxações lineares. No que se refere ao tempo de computação, novamente percebe-se a importância da existência ou não de co-retilinearidade. O algoritmo branch

and-cut baseado na primeira formulação é mais rápido que o algoritmo branch-and-price

baseado na segunda formulação, quando a instância apresenta co-retilinearidade. Esta

situação é invertida quando a instância não tem pontos co-retilineares. Como mostramos na seção anterior os resultados obtidos neste trabalho são aplicáveis

não somente ao problema RG-P, mas sim a uma variedade de problemas de decomposição

(particionamento ou cobrimento) de polígonos retilineares. Os testes computacionais evidenciaram que as classes de inequações I, II, III, IV e

V na formulação de segmentos são bastante úteis na descrição do poliedro do problema RG-P. Reconhecemos que para o branch-and-cut se tornar competitivo é preciso investir

mais tempo no estudo poliédrico, à procura de novas inequações válidas para Pn. Mais precisamente, deve-se procurar inequações válidas baseadas em instâncias onde P é não

co- retilinear. Os resultados computacionais revelaram dois interessantes problemas combinatórios.

1.'2. Conclusões 8:3

O primeiro se refere à resolução do subproblema de pricing, ou seja, é possível encontrar

a variável de mínimo custo reduzido em tempo inferior a O(n 4 ) ? O segundo problema consiste em responder a seguinte questão: é verdade que para toda instância do RG-P

com P não co-retilinear, o número de retângulos numa partição retangular ótima é sempre

IPI+ 1? Como uma das extensões deste trabalho sugerimos uma continuação do estudo polié

drico de Pn. e um estudo dos dois problemas combinatórios acima. Como observado no capítulo anterior parece que a dificuldade de se resolver uma

instância do RG-P está estritamente relacionada ao "grau de co-retilinearidade" dos pon

tos em P, isto é, instâncias com este grau igual a zero ( P é não co-retilinear) parecem ser mais difíceis de resolver do que instâncias com P co-retilinear. Abaixo sugerimos duas

medidas que tentam capturar o grau de co-retilinearidade de uma instância do RG-P. As medidas propostas por nós não são necessariamente os melhores indicadores da

dificuldade de se resolver uma dada instância do RG-P. Contudo, este pequeno estudo

que realizamos é, ao nosso conhecimento, uma primeira tentativa de se determinar a

priori a dificuldade de se tratar urna instância dada do RG-P e ter um critério um pouco mais consistente de avaliá-la que não seja a bivalência entre "co-retilinear" e "não co

retilinear". Isto porque urna instância co-retilinear com 200 pontos pode ter todos os 200 pontos na mesma reta horizontal ou 198 pontos não co-retilineares e 2 outros que são

co-retilineares entre si mas não com os demais. O critério atual não distingue entre estas duas instâncias mas, é muito provável que a segunda instância seja mais difícil de resolver

do que a primeira. A primeira medida que propomos é baseada em se calcular a sorna do número de vezes

que cada ponto em P é co-retilinear com cada outro ponto de P, e depois dividir esta

sorna pelo número máximo possível de pares de pontos co-retilineares de P (n * (n -1)/2). O grau de co-retilinearidade usando esta medida varia de O a 1. O limite superior (1) ocorre quando todos os pontos de P estão sobre urna mesma reta vertical ou horizontal. Um incoveniente com esta medida é que é aparentemente difícil gerar instâncias do RG-P

com um dado grau de co-retilinearidade. A segunda medida é baseada na seguinte idéia: determina-se o mínimo entre o número

de abscissas e ordenadas diferentes dos pontos em P, e divide-se este valor mínimo por n. A intuição por trás desta medida está relacionada ao fato de que, quando o conjunto Pé não co-retilinear, tem-se os pontos de P dispostos em exatamente n retas horizontais

e n retas verticais, e assim esta instância tem grau de co-retilinearidade igual a 1. Note que o grau de co-retilinearidade usando esta medida varia de 1/n a 1. O limite inferior (1/n) ocorre quando todos os pontos de P encontram-se sobre urna mesma reta vertical

ou horizontal. Uma direção futura seria investigar se estas duas medidas capturam a dificuldade de

7.2. Conclu:;Ões

se resolver instâncias do RG-P. Quanto aos algoritmos de aproximação GZ85, GRZ93 e DPS86 os resultados compu

tacionais mostraram que, embora o algoritmo GZ85 tenha limite de aproximação maior do que o do algoritmo GRZ93, o primeiro sempre gerou soluções melhores. Verificou-se

também que, para as instâncias de teste, o algoritmo DPS86 nunca gerou uma solução ótima, mas em média os valores de suas soluções estavam a 10% dos valores de soluções

ótimas e, portanto, bem abaixo da razão de performance de pior caso que é de 75%.

Apêndice A

Descrição do Algoritmo DPS86

Função PontosNointerior(xi,xf,yi,yf,Coordena.da( ],N,Coord(]) Inicio

Fim

1. Seja N o tamanho do vetor Coordenada;

2. Se (xf-xi=l OU yf-yi=l)

então retorne(O);

3. i=O;

4. Para j=O até N-1 faça

Se (Coordenada[i].x > xi E Coordenada[i].x < xf E Coordenada[i].y > yi E Coordenada[i].y < yf)

então

Início

Coord(i].x=Coordena.da[i].x;

Coord(i].y=Coordena.da[i].y;

incremente i;

Fim

5. retorne (i);

85

Procedimento Guilhotina(g( ],xi,xf,yi.yf,Coordenada( ],:\ ,Coord[]) Início

1. n=PontosN olnterior( xi,xf,yi,yf,Coordenada,N, Coord);

2. Se (n=O) então g(xi,xf,yi,yf].valorcorte=O;

3. Para k=O até n-1 faça

Início

x=Coord(k] .x;y=Coord[k] .y;

Guilhotina(g,xi ,x ,yi ,yf, Coordenada,N, Coord);

Guilhotina(g,x,xf,yi,yf,Coordenada,N,Coord);

gv=g(xi,xf,yi,yf].valorcorte + (yf-yi);

Guilhotina(g,xi ,xf,yi ,y, Coordenada,N, Coord);

Guilhotina(g,xi,xf,y,yf,Coordenada,N,Coord);

gh=g(xi,xf,yi,yf].valorcorte + (xf-xi)

Se (gv < gh E gv < g(xi,xf,yi,yf].valorcorte)

então

Início

g(xi,xf,yi,yf].valorcorte=gv;

g(xi,xf,yi,yf).sentido= "Vertical";

g(xi,xf,yi,yf] .xy=x;

Fim

Senão Se (gh < g(xi,xf,yi,yf].valorcorte)

então

Início

g(xi,xf,yi,yf]. valorcorte=gh;

g(xi,xf,yi,yf] .sentido= "Horizontal";

g(xi,xf,yi,yf].xy=y;

Fim

Fim Para

Fim Guilhotina

86

...

Procedimento LrnprimePa.rtiçãoGuilliotina(g[ ],xi,xf,yi,yf,Coordenada[ ],N,Coord[]) Início

l. n= PontosN o Interior( xi,xf,yi ,yf,Coordenada,N ,Coord);

2. Se (n #O) então

Início

Se (g[xi,xf,yi,yf].sentido = "Vertical")

então

Início

x=g[xi,xf,yi,yf] .xy;

Imprime P artiçãoGuilhotina( g,xi, x,yi,yf,Coordenada, N, Coord);

Imprime P art içãoG uilhotina(g ,x ,xf,yi,yf,Coordenada,N, Coord);

print( "[" ,g[xi,xf,yi,yf].xy,yi,g[xi,xf,yi,yf].xy,yf, "]" );

Fim

Senão

Inicio

y=g(xi,xf,yi,yf].xy;

Imprime P a.rtiçãoGuilliotina(g ,xi,xf,yi ,y, Coordenada,N, Coord);

lmprimeP a.rtiçãoGuilhotina(g,xi,xf,y,yf, Coordenada,N, Coord);

print( "[" ,xi,g[xi,xf,yi,yf] .xy,xf,g[xi,xf,yi,yf] .xy, "]");

Fim

Fim

Fimimprime

Programa Principal Inicio

l. Ler instãncia do problema RG-P (Coordenada,N,L,A);

2. Guilhotina(g,O,L,O,A,Coordenada,N ,Coord);

3. LrnprimePartiçãoGuilhotina(g,O,L,O,A,Coordenada,N,Coord);

Fim

87

No algoritmo acima N, L e A representam a cardinalidade do conjunto P de pontos, largura e altura do retângulo R respectivamente. Inicialmente g[xi, xf, yi, yf] = M para cada retângulo sem pontos terminais no interior definido por xi, xf, yi, yf e sendo M um número inteiro positivo razoavelmente grande. O valor de uma partição guilhotina ótima é armazenado em g[O, L, O, A].valorcorte.

Bibliografia

[1] C. Barnhart, E. L. Johnson, G. L. Nemhauser, M. vV. P. Savelsbergh, and P. Vance.

Branch-and-Price: Column Generation for Solving Huge Integer Programs. Operati

ons Research, 1996.

[2] C. E. Ferreira e Y. Wakabayashi. Combinatória Poliédrica e Planos-de-Corte Faciais.

X Escola de Computação, 1996.

[3] B. Chazelle and D. Dobkin. Decomposing a Polygon into its Convex Parts. In Proceedings of th 11th ACi\1 Symposium on Theory of Computing, 1979.

[4] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. lntroduction to Algorithms. MIT

Press, 1990.

[5] CPLEX Optimization, Inc. Using the CPLEX Callable Library. Manual, 1994.

[6] P. J. de Rezende e J. Stolfi. Fundamentos de Geometria Computacional. IX Escola de Computação, 1994.

[7] C. C. de Souza. The Graph Equípartition Problem: Optimal Solutíons, Extensions

and Applications. PhD thesis, Université Catholique de Louvain, 1993.

[8] D. Z. Du, L. Q. Pan, and M. T. Shing. Minimum Edge Length Guillotine Rectangular Partition. Technical report, Mathematical Sciences Research Institute, University of

California, Jan. 1986.

[9] M. R. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan. Triangulating a Sirnple Polygon. lnformatíon Processing Letters, 7( 4), 1978.

[10] T. F. Gonzalez, M. Razzazi, M. T. Shing, and S. Q. Zheng. On Optimal Guillotine Partitions Approximating Optimal d-Box Partitions. Computational Geometry, 4:1-

11, 1994.

88

BfBLfOGRAF'fA 89

[11] T. F. Gonzalez, M. Razzazi, and S. Q. Zheng. An Efficient Divide-and-Conquer Approximation Algorithm for Partitioning into d-boxes. International Journal of

Computational Geometry and Applications, 3( 4):281-287, 1993.

[12] T. F. Gonzalez and S. Q. Zheng. Bounds for Partitioning Rectilinear Polygons. Proc.

Symp. Computacional Geometry, pages 281-287, June 1985.

[13] T. F. Gonzalez and S. Q. Zheng. Improved Bounds for Rectangular and Guillotine

Partitions. J. Symbolic Computation, 7:591-610, 1989.

[14] T. F. Gonzalez and S. Q. Zheng. Approximation Algorithms for Partitioning a Rectangle with Interior Points. Algorithmica, 5:11-42, 1990.

[15] J. N. Hooker. Testing Heuristics: vVe Have It All vVrong. Technical report, Graduate School of Industrial Administration, Carnegie Mellon University, May 1995.

[16] M. Jünger, G. Reinelt, and S. Thienel. Practical Problem Solviií.g with Cutting Plane Algorithms in Combinatorial Optimization. Technical report, Institut für Informatik, Universitat zu Koln, 1994.

[17] C. Levcopoulos. Fast Heuristics for Minimum Length Rectangular Partitions of Polygons. Proceedings of the 2nd Computational Geometry Conference, June 1986.

[18] A. Lingas, R. Pinter, R. Rivest, and A. Shamir. Minimum Edge Length Partitioning of Rectlinear Polygons. In Proceedings of the 20th Annual Allerton Conference Communication, Control, and Computing. University of Illinois, 1982.

[19] E. Lodi, F. Luccio, C. Mugnai, L. Pagli, and J. W. Lipski. On Two-Dimensional Data Organization II. Fundamenta Informaticae, 2(3), 1979.

[20] M. Minoux. Mathematical Programming: Theory and Algorithms. Wiley-Interscience,

1986.

[21] G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial Optimization. John vViley and Sons, New York, 1988.

[22] J. O'Rourke and K. J. Supowit. Some NP-Hard Polygon Decomposition. IEEE Transactions on Information Theory, 1983.

[23] M. vV. Padberg and M. Grotschel. Polyhedral Computations. John Wiley and Sons,

1985.

(24] M. vV. Padberg and G. Rinaldi. Optmization of a 532-City Traveling Salesman Problem by Branch and Cut. Operations Research Lettres, 6:1-8, 1987.

BIBLIOGRAFIA 90

[25] F. P. Preparata and M. I. Shamos. Computational Geometry: An lntroduction.

Spring- Verlag, 1988.

[26] D. M. Ryan and B. A. Foster. An Integer Programming Approach to Scheduling. A.

Wren (ed.) Computer Scheduling of Public Transport Urban Passenger Vehicle and

Crew Scheduling} North-Holland} Amsterdam, pages 269-280, 1981.

[27] J. R. Sack. An O(nlogn) Algorithm for Decomposing Simple Rectilinear Polygons

into Convex Quadrilaterals. In Proceedings of the 20th Annual Allerton Conference

Communication} Control} and Computing. U niversity of Illinois, 1982.

[28] M. W. P. Savelsbergh and G. L. Nemhauser. Functional Description of MINTO, a Mixed INTeger Optimizer. Manual version 2.3, 1996.

(29] A. Schrijver. Theory of Linear and Interger Programming. John vViley and Sons, Chichester, 1986.

[30] H. A. Taha. Operations Research - An lntroduction - Fourth Edition. Macmillan

Publishing Company, 1987.

[31] F. Vanderbeck. Decomposition and Column Generation for Integer Programs. PhD thesis, Universite Catholique de Louvain, 1994.

Documents

Partição Retangular Mínima de um Retângulo com Pontos no …repositorio.unicamp.br/bitstream/REPOSIP/275993/1/... · 2018. 7. 22. · UNICAMI> CM-00102277-4 FICHA CATALOGRÁFICA