Lifted Cover Inequalities

Nesse post falarei sobre as desigualdades de cobertura erguidas (em uma horrorosa tradução livre de lifted cover inequalities). A minha ideia inicial era comentar sobre cortes automáticos que resolvedores como o XPRESS inserem no programa para apertar o modelo. Há dois tipos de desigualdades usadas como cortes: as de cobertura erguidas e aquelas resultantes do procedimento de Chvátal-Gomory.

Como esse segundo método faz uso direto do tableau do simplex, antes eu gostaria de escrever um post revisando o primal simplex e o dual simplex. Por isso, ater-me-ei às coberturas erguidas.

Essas desigualdades surgiram a partir do problema da mochila binária. Vamos relembrar o problema: dado um conjunto de n itens — cada qual com um peso e valor — e uma mochila de capacidade b, queremos escolher um subconjunto de itens cuja soma dos pesos respeite à capacidade da mochila e cuja soma dos valores seja máxima.

Vamos supor que os valores dos itens sejam dados por e os pesos por (para facilitar, suponha que os itens estão ordenados em ordem não crescente de peso, ou seja ). Para cada item i, definimos a variável binária que vale 1 se vamos colocar o item na mochila e 0 caso contrário. O modelo de programação linear inteira é dado por:

Sujeito a:

(1)

(2)

Definições

Definimos qualquer subconjunto de itens que cabem na mochila como conjunto independente. Assim, se S é um conjunto independente, temos que

Se, por outro lado, o subconjunto não cabe na mochila, denominamo-no uma cobertura.

Adicionalmente, uma cobertura é dita minimal se a remoção de qualquer item do subconjunto torna-o independente. Dada uma cobertura C, uma desigualdade de cobertura é definida como:

Ela é claramente válida pois por definição incluir todos os itens de uma cobertura violará a capacidade da mochila.

Cobertura Estendida

Podemos estender essa desigualdade da seguinte forma: Seja j o item mais pesado dessa cobertura. Se colocarmos um item mais pesado que j, ainda assim não podemos ter mais do que |C|-1 itens. Aplicando esse argumento várias vezes, podemos inserir todos os itens j’ < j (que são mais pesados que j por causa da ordenação inicial) na cobertura, para deixar a desigualdade mais apertada. Definimos então a cobertura estendida E(C) como sendo a cobertura C mais os itens mais pesados que o item j. A desigualdade abaixo é então válida:

Lifting das Desigualdades de Cobertura

Uma outra maneira de melhorar uma desigualdade de cobertura é através de lifting, que consiste em aumentar os coeficientes das variáveis do lado esquerdo de uma desigualdade na forma (<=), desde que ela continue viável. Obviamente só conseguimos fazer lifting em desigualdades que não representam facetas, uma vez que a desigualdade que sofreu lifting domina a original.

As desigualdades de cobertura estendida é uma forma de lifting, pois estamos aumentando de 0 para 1 o coeficiente dos itens mais pesados que j. Porém, usando um método diferente (porém mais caro), podemos conseguir aumentar os coeficientes para valores maiores do que 1. Vamos considerar um exemplo de mochila, extraído de [1]:

Uma desigualdade de cobertura válida é

(3)

A cobertura estendida consiste em incluir os itens e , os itens mais pesados que , resultado na desigualdade de cobertura estendida: .

Ao invés de aumentar o valor de para 1 em (3), vamos usar uma variável , levando a

(4)

A pergunta é: qual o maior valor que pode assumir, desde que (4) se mantenha válida? Para isso, temos que encontrar o valor de considerando todas as possibilidades e escolher o menor. Primeiro, se então é ilimitado, o que não ajuda muito. Vamos considerar então que . Com isso, podemos reduzir o problema:

Agora queremos encontrar o maior valor de em (4) que respeite a desigualdade. Para isso, devemos considerar o pior caso, ou seja, em que a soma dos outros termos é máxima,

(5)

A soma máxima pode ser determinada resolvendo-se outro problema da mochila:

Sujeito a

A solução ótima desse problema é 1, o que significa que por (5), . Temos então a desigualdade

(6)

Repetindo esse procedimento para fazer um lifting em (6) aumentando o coeficiente de para , concluiremos que , levando a desigualdade

(7)

Que domina inclusive a desigualdade de cobertura estendida. Porém, isso tem seu preço: para estender uma desigualdade de cobertura só precisamos inserir os itens mais pesados, enquanto nesse último procedimento tivemos que resolver dois novos problemas da mochila. Ou seja, para resolver um problema NP-difícil precisamos resolver sub-problemas que também são NP-difíceis? Veremos…

Programação Dinâmica

Como se sabe, o problema da mochila pode ser resolvido através de um algoritmo clássico de programação dinâmica que possui complexidade pseudo-polinomial de O(nb). Basicamente define-se uma submochila m(i, j), que quer representa o maior valor que se consegue com uma mochila usando os i primeiros itens e com capacidade j. A recorrência é

Porém, é possível indexar o valor da mochila ao invés da capacidade. Nesse sentido definimos m'(i, v) como o menor peso que conseguimos usando os i primeiros itens e com valor v. A recorrência é semelhante:

Com a restrição de que os valores dos itens sejam inteiros. Para encontrar maior valor da mochila, basta percorrer a matriz m’ e determinar o maior v, tal que m'(n, v) <= b.

A complexidade desse segundo algoritmo é O(max_v n), onde max_v é o maior valor que a mochila pode ter (ou seja, um limite superior para o custo da função objetivo). No nosso caso, nossa função objetivo corresponde a um pedaço do lado esquerdo da desigualdade de cobertura. Como tal desigualdade é válida, sabemos que o lado esquerdo nunca ultrapassará |C|-1, logo max_v . Concluímos que os subproblemas da mochila podem ser resolvidos em .

Desigualdades de Cobertura para outros problemas

As desigualdades levantadas para coberturas podem ser usadas para outros problemas. Se temos um PLI na forma para i=1,…,m onde representa a i-ésima linha de A, então podemos particionar P em vários problemas da mochila na forma e encontrar desigualdades fortes para esses subproblemas.

Como temos que

A esperança é que as desigualdades fortes para os subproblemas (em especial as desigualdades de cobertura) sejam úteis para P na prática. Mais detalhes sobre essa técnica, ver em [1].

Bibliografia

[1] Crowder, H. and Johnson, E.L. and Padberg, M. – Solving large-scale zero-one linear programming problems

2 respostas a Lifted Cover Inequalities

  1. Juliano diz:

    Olá,
    nesse exemplo que eu estou lhe passando, se tentar levantar começando a adicionar (ALPHA . x1), teremos ALPHA=1, entretanto, a desigualdade levantada ( x1 + x3 + x4 + x6 <= 2 ) não é válida para X.
    ____________________________________________________
    PROBLEMA
    X={ x em B6 tal que 12×1 + 15×2 + 9×3 + 7×4 + 8×5 + 5×6 <= 19}
    Levantar a cobertura mínima x3 + x4 + x6 <= 2
    ____________________________________________________

    Pq isso ocorre?????

    Abraço!

  2. kunigami diz:

    Olá Juliano,

    Não entendi porque a desigualdade não é válida para X. Se isso for verdade, então existe uma combinação de x1, x3, x4 e x6 tal que x1 + x3 + x4 + x6 >= 3. Isso que dizer que você pode pegar três itens suja soma de coeficientes seja menor ou igual a 19. Porém, se você pegar os três itens com os menores coeficientes, que são x6 (coeficiente 5), x4 (coeficiente 7) e x3 (coeficiente 9), a soma já dá 21. Logo, podemos pegar no máximo 2 itens e a desigualdade é válida.

%d bloggers like this: