Kommunedelplanen Akershus grense- Vinterbro Bakgrunn for Statens vegvesens

Grafo de Conflitos 13 Minimize: x1 + x2+ x3+ x4 Sujeito a: x₁+ x2+ x3 ≥ 2 (2.8) − 2x1+ 3x2+ 4x3+ 5x4 ≤ 4 (2.9) x₁, . . . , x₄ ∈ {0, 1}

A Figura 2.2 mostra um grafo de conflitos para o Programa Bin´ario P. Arestas representam conflitos entre vari´aveis e/ou complementos de vari´aveis.

x

1

x

2

x

3

x

2

x

1

x

3

x

4

x

4

Figura 2.2: Um grafo de conflitos para P.

A constru¸c˜ao do grafo inicia inserindo as arestas triviais, entre vari´aveis e seus com- plementos (linhas pontilhadas). Em seguida ´e analisada a restri¸c˜ao da equa¸c˜ao 2.8. ´E necess´ario convertˆe-la para o formato padr˜ao utilizado (P_j∈Na_ijx_j ≤ bi), resultando na

seguinte restri¸c˜ao:

−x1− x2− x3 ≤ −2 (2.10)

Como os coeficientes s˜ao iguais n˜ao ´e necess´ario executar um algoritmo de ordena¸c˜ao. A pr´oxima etapa ´e calcular os limites inferiores para o LHS dessa restri¸c˜ao. Para cada par de vari´aveis consecutivas, o valor de Lxˆj=1, xˆj+1=1

2.10 ser´a sempre menor ou igual a -2

(RHS). Portanto, nenhum conflito de ativa¸c˜ao de vari´aveis ´e detectado nessa restri¸c˜ao. Essa verifica¸c˜ao poderia ser feita apenas calculando o limite inferior para os dois maiores

14 Grafo de Conflitos

coeficientes. Nesse caso, como todos s˜ao iguais, qualquer par pode ser escolhido, por exemplo x2 e x3, calculando L

x2=1, x3=1

2.10 e verificando que o valor ´e igual a -3, menor

do que o lado direito da restri¸c˜ao. O pr´oximo passo ´e investigar cliques que envolvam complementos de vari´aveis. Calculando Lxˆj=0, xˆj+1=0

2.10 para o primeiro par de vari´aveis

subsequentes (x1 e x2) obtem-se o valor -1, que ´e maior do que o RHS. Dessa forma,

´e detectado um clique que envolve todos os complementos de vari´aveis dessa restri¸c˜ao. Assim, cada par de conflitos desse clique ´e inserido no grafo.

A an´alise prossegue para a restri¸c˜ao da equa¸c˜ao 2.9. Essa restri¸c˜ao est´a ordenada em ordem crescente, podendo iniciar a busca por cliques com vari´aveis ativas. Calculando Lxˆj=1, xˆj+1=1

2.9 para cada par de vari´aveis consecutivas, ´e poss´ıvel detectar um clique en-

volvendo a ativa¸c˜ao das vari´aveis x2 at´e x4 (Lx2.92=1, x3=1 = 5). Cada par de conflitos ´e

ent˜ao inserido no grafo. Em seguida, cliques envolvendo complementos de vari´aveis s˜ao testados. Para isso, ´e necess´ario ordenar os coeficientes em ordem decrescente (sendo necess´ario apenas percorrer a restri¸c˜ao em ordem inversa). ´E poss´ıvel detectar a ine- xistˆencia de cliques envolvendo complementos de vari´aveis calculando Lxˆj=0, xˆj+1=0

2.8 para

as duas vari´aveis de menor coeficiente (x1 e x2). Para essas vari´aveis, o valor do limite

Cap´ıtulo 3

Planos de Corte

Uma aplica¸c˜ao prim´aria para grafos de conflitos ´e a gera¸c˜ao de desigualdades v´alidas (cortes) derivadas de um empacotamento de n´os (SPP) (Padberg, 1973) para refor¸car a relaxa¸c˜ao da programa¸c˜ao linear. Diversos trabalhos apresentam a gera¸c˜ao e aplica¸c˜ao de desigualdades v´alidas aplicadas a problemas modelados por PI. Entre eles, Atamt¨urk et al. (2000) utilizaram o grafo de conflitos constru´ıdo por probing, e estendido por meio de heur´ısticas baseadas em factibilidade e otimalidade, para gerar desigualdades de clique. Experimentos computacionais demonstraram que a melhoria do limite in- ferior contribuiu para aprimorar o desempenho do resolvedor MINTO 3.0 (Nemhauser et al., 1994). Analogamente, Hoffman e Padberg (1993) utilizaram grafos de conflitos para gerar desigualdades v´alidas para problemas de escalonamento de tripula¸c˜oes a´ereas, considerando desigualdades de cliques, ciclos ´ımpares e anti-holes. Achterberg (2007) apresentou heur´ısticas compostas de t´ecnicas SAT para resolvedores de Programa¸c˜ao Inteira Mista, gerando desigualdades v´alidas a partir da an´alise de solu¸c˜oes infact´ıveis e de informa¸c˜oes associadas ao branching. A mesma ideia foi desenvolvida em paralelo por Sandholm e Shields (2006).

As classes mais comuns de cortes para SPP s˜ao os cortes de clique e de ciclos ´ımpares (odd holes). Uma desigualdade de clique para um conjunto C de vari´aveis conflitantes pode ser definido como:

X

j∈C

x_j ≤ 1 (3.1)

16 Planos de Corte

Uma desigualdade de ciclo ´ımpar envolvendo um conjunto C de vari´aveis conflitantes pode ser definida como:

X

j∈C

x_j ≤ ⌊|C|

2 ⌋ (3.2)

´

E importante notar que, quando um v´ertice xj representar o complemento de uma

vari´avel, os termos xj das equa¸c˜oes 3.1 e 3.2 devem ser substitu´ıdos por 1 − xj.

Na pr´atica, os cortes de clique apresentam um papel mais importante (Borndorfer, 1998) do que os cortes de ciclo ´ımpar. O impacto de tais cortes foi avaliado em alguns problemas dif´ıceis de timetabling (Avella e Vasil’ev, 2005; Burke et al., 2012). A con- tribui¸c˜ao para a melhoria do limite inferior de problemas de PI obtida pela inser¸c˜ao de desigualdades de ciclo ´ımpar ´e pequena (Borndorfer, 1998; M´endez-D´ıaz e Zabala, 2008). Entretanto, sua inclus˜ao em procedimentos branch-and-cut ´e pouco custosa, uma vez essas desigualdades podem ser separadas em tempo polinomial usando algoritmos de caminhos m´ınimos (Grotschel et al., 1993; Rebennack, 2009).

3.1

Separa¸c˜ao de Cortes de Clique

O algoritmo aqui proposto para gera¸c˜ao de cortes considera uma rotina de separa¸c˜ao de cliques agressiva: o objetivo n˜ao ´e encontrar a desigualdade de clique mais violada, mas

todas as desigualdades de clique violadas. Alguns trabalhos indicam que essa ´e a melhor

estrat´egia. Por exemplo, no trabalho de Burke et al. (2012) os resultados computacionais motivaram a inclus˜ao de cortes n˜ao maximamente violados, encontrados durante a busca do clique mais violado em um algoritmo de branch-and-bound. O resultado ´e consistente com relatos de aplica¸c˜oes de outros cortes em diferentes modelos, tais como cortes de Chv`atal-Gomory (Fischetti e Lodi, 2007). A op¸c˜ao de inserir um grande n´umero de desi- gualdades violadas ao mesmo tempo ´e tamb´em respons´avel para refor¸car a importˆancia dos cortes de Gomory (Cornu´ejols, 2007).

A rotina de separa¸c˜ao de cliques tem dois principais componentes:

1. um m´odulo para separar todos os cliques violados, considerando o subgrafo de conflitos induzido pelas vari´aveis com valores fracion´arios na relaxa¸c˜ao linear;

Planos de Corte 17

2. um m´odulo de lifting, que estende os cliques gerados pelo m´odulo anterior consi- derando o grafo de conflitos completo.

O m´odulo de separa¸c˜ao de cliques foi implementado usando uma vers˜ao melhorada do algoritmo Bron-Kerbosch (Bron e Kerbosch, 1973). Essa vers˜ao implementa uma regra de pivoteamento otimizada (Brito e Santos, 2011) para acelerar a descoberta de cliques maximais com altos pesos. Tal regra atribui prioridade maior para visitar primeiramente n´os com alto grau modificado, isto ´e, soma do grau do n´o e de seus vizinhos, e com pesos maiores. Embora esse algoritmo tenha um desempenho exponencial em seu pior caso, a regra de pivoteamento heur´ıstica se torna apropriada n˜ao somente para execu¸c˜ao no contexto de enumera¸c˜ao mas tamb´em para execu¸c˜ao com tempos restritos, j´a que os cliques mais violados tendem a ser descobertos primeiro. Apesar disso, nos experimen- tos realizados, todas as desigualdades de cliques violadas puderam ser enumeradas em fra¸c˜oes de segundos usando essa abordagem. Vale ressaltar que mesmo se apenas um subconjunto de cliques for inserido durante a execu¸c˜ao de um algoritmo de branch-and-

cut, a melhor solu¸c˜ao n˜ao seria perdida, apenas resultaria em uma convergˆencia mais

lenta.

Ap´os gerar um clique, o m´odulo de lifting ´e executado. Trata-se de um m´etodo guloso que seleciona a cada itera¸c˜ao a vari´avel com menor custo reduzido e verifica se ela pode ser inserida no clique, ou seja, se ela tem conflito com todas outras contidas no clique atual. Para isso, ´e considerado o grafo de conflitos completo, incluindo vari´aveis com valores inteiros na relaxa¸c˜ao linear.

A importˆancia da realiza¸c˜ao do lifting em desigualdades de clique pode ser explicada com o grafo de conflitos da Figura 3.1. V´ertices dentro da ´area cinza indicam vari´aveis com valores n˜ao-nulos na solu¸c˜ao fracion´aria. Nesta solu¸c˜ao, somente os n´os x2, x3 e

x₄ poderiam contribuir para definir a desigualdade de clique m´aximo violada. Apesar disso, relaxa¸c˜oes lineares subsequentes poderiam incluir trˆes diferentes cliques K3 (cli-

ques envolvendo trˆes v´ertices) alternando a vari´avel inativa. Se a desigualdade do clique K₄ fosse inserida durante a separa¸c˜ao da primeira solu¸c˜ao fracion´aria, re-otimiza¸c˜oes adicionais da programa¸c˜ao linear poderiam ser evitadas. Al´em disso, uma matriz de restri¸c˜oes menos densa seria obtida com a inser¸c˜ao inicial dessas restri¸c˜oes dominantes.

18 Planos de Corte x 2 x 3 x4 x 1

Figura 3.1: Exemplo de um grafo K3 em que o lifting poderia ser aplicado,

transformado-o em um K4.

In document Samspillet mellom Statens vegvesen og kommunene i planlegging av hovedveger: Basert på case-studier av kommunedelplan E6 Ringebu sør-Frya og kommunedelplan E18 Akershus grense- Vinterbro. (sider 161-165)