Desigualdades Definidoras de Facetas

No último post da série sobre combinatória poliédrica, apresentei o algoritmo de Branch and Cut. Um aspecto essencial no desempenho desse algoritmo é o quanto uma desigualdade é capaz de aproximar uma formulação da envoltória convexa. Vimos que as desigualdades definidoras de facetas são as mais eficientes na prática.

Hoje vou discutir um pouco sobre métodos para determinar se uma dada desigualdade define faceta para a envoltória convexa. Para tal, precisamos revisar alguns conceitos de álgebra linear.

Álgebra Linear

Independência linear: o conjunto de vetores  é linearmente independente se

(1)

então, para todo i = 1, …, n

Para . Em outras palavras, não existe um vetor que possa ser escrito como combinação linear de outro.

Independência (linear) afim: o conjunto de vetores  é afim independente se

(2)

e (3)

então, para todo i = 1, …, n

Para . Aqui temos a restrição adicional de que a soma dos coeficientes deve ser 0. Observe que se o vetor nulo estiver no conjunto de vetores, esse nunca será linearmente independente, pois se a igualdade em (1) valesse, qualquer coeficiente não-nulo multiplicando o vetor nulo manteria a igualdade. Porém, a adição da desigualdade (3), garante nesse caso que o coeficiente do vetor nulo seja 0. Essa notação é interessante para não termos que tratar o vetor nulo como um caso especial ao fazer algumas contas.

Vamos apresentar a seguir dois possíveis métodos que podem ser utilizados para decidir se uma dada desigualdade define faceta de um poliedro.

Método Direto

Existe um teorema que diz que a dimensão de um poliedro é igual ao maior número de pontos afim independentes pertencentes a ele, menos um. Assim, se encontramos k soluções afim independentes do nosso problema, sabemos que ele tem dimensão maior ou igual a k-1. Se o modelo tem n variáveis e o poliedro tem dimensão n, dizemos que ele possui dimensão cheia. É muito mais difícil trabalhar com poliedros de dimensão menor que n, portanto, para fins de explicação, vamos assumir daqui pra frente que o poliedro tem dimensão cheia.

Uma face qualquer de um poliedro, é também um poliedro, só que com dimensão menor. Logo, para determinar a dimensão de uma face basta enumerar pontos afim independentes que pertençam a essa face.

Como vimos, a dimensão da faceta é uma a menos do que a dimensão do poliedro. Para determinar se uma desigualdade define faceta, precisamos calcular a dimensão da insterseção da mesma com o poliedro. Para isso, devemos encontrar pontos do poliedro, que satisfaçam essa desigualdade na igualdade e que ainda sejam afim independentes entre si. Se a dimensão dessa interseção for uma a menos do que a do poliedro, tal desigualdade define uma faceta do poliedro.

Método Indireto

Encontrar pontos afim independentes pode não ser uma tarefa simples. Uma alternativa consiste em usar um método indireto.

Dada uma desigualdade válida da forma , queremos decidir se a mesma define uma faceta do poliedro P. Considere a interseção dessa desigualdade com o poliedro P, representada por . Considere os pontos x em P que satisfazem e portanto satisfazem .

Cada uma dessas igualdades formará uma linha de um sistema linear onde as variáveis são os coeficientes . Se esse sistema tiver solução única, pode-se mostrar que a desigualdade define uma faceta e que é equivalente a , ou seja .

O método indireto procura resolver esse sistema linear por partes, escolhendo pontos de P que satisfazem (e por consequência ) com o objetivo de mostrar que os coeficientes são iguais a . Se formos capazes de definir todos os coeficientes a partir desses pontos, a desigualdade define uma faceta de P. A conveniência é que não precisamos determinar se os pontos são afim independentes, pois isso é considerado implicitamente ao resolvermos o sistema linear. Além disso, como sabemos o valor esperado para os coeficientes , fica mais fácil procurar pontos que levem a essa conclusão.

Os pontos p e q definem a reta . O ponto s sozinho não consegue definir unicamente a reta .

A intuição geométrica do método pode ser vista na figura acima. Os pontos da interseção de com P são ‘p’ e ‘r’. Como a única reta (solução única) que passa por esses dois pontos é , a equação da interseção é equivalente a . Essa interseção é uma faceta de P. Já para a reta , o único ponto de sua interseção com P é o ponto s. Observe que existem infinitas retas que podem passar por ‘s’, como por exemplo a própria , mas também . Ou seja, o sistema linear correspondente não tem solução única e como podemos ver, a interseção não é uma faceta de P.

Exemplo

Para dar um exemplo do método indireto, vou usar o problema do conjunto independente. Dado um grafo não direcionado, queremos encontrar o maior conjunto de vértices de forma que nenhum deles seja vizinho entre si. Para isso, definimos uma variável binária  que vale 1 se o vértice v está no conjunto independente e 0 caso contrário. O modelo é bem simples,

(4) 

(5) 


Grafo com conjunto independente máximo marcado em laranja.

Esse modelo é bem fraco, no sentido de que na prática o valor da relaxação linear está bem distante da solução inteira ótima (poucas podas no Branch and Bound). Uma desigualdade bastante eficaz é a da clique maximal. Seja M uma clique maximal, ou seja, um conjunto de vértices tal que todos são adjacentes entre si e tal que não exista outro vértice fora de M, vizinho a todos os vértices de M. Considere a seguinte desigualdade

(6)

Ela é válida para nosso problema pois nenhum conjunto independente pode conter mais de um vértice de qualquer clique. Vamos verificar se ela define uma faceta. Suponha então que a interseção de (6) com a envoltória convexa do problema do conjunto independente seja da forma

(7)

A ideia é encontrar pontos válidos para o problema e que satisfaçam (6) na igualdade, pois assim sabemos que esses pontos satisfazem (7). Vamos chamar de o coeficiente de associado ao vértice v.

Dado um v na clique M, podemos fazer e o resto 0, que ele será um conjunto independente válido e satisfaz (6) na igualdade. Substituindo esse x em (7), temos que

(8)

Agora, dado um vértice u fora de M, temos a propriedade de que existe algum vértice em M não adjacente a u (do contrário poderíamos incluir u em M e esta não seria maximal, uma contradição). Seja então v* tal vértice em M. O ponto x, com e o resto 0, é um conjunto independente válido uma vez que u e v* não são adjacentes. Como este ponto satisfaz (7) na igualdade, temos que . Mas, por (8), chegamos que

(9)

Substituindo por pela igualdade (8), temos que cada coeficiente da desigualdade (7) é igual ao coeficiente da desigualdade (6) multiplicado por , concluindo que (7) define uma faceta.

Dá para substituir as desigualdades (5) do modelo por desigualdade (6), desde que todas as arestas (u, v) estejam na desigualdade de pelo menos uma clique maximal. Felizmente, existe um algoritmo polinomial para encontrar uma cobertura de arestas por cliques maximais [2].

Exemplo de uma cobertura por cliques maximais (arestas podem ser cobertas por mais de uma clique).

Referências

[1] Disciplina de Programação linear inteira com o prof. Cid.
[2] Nemhauser, G.L. and Sigismondi, G.A – Strong cutting plane/branch-and-bound algorithm for node packing

Os comentários estão fechados.

%d bloggers like this: