Programming Pearls: Parte 2

Esse post é o segundo da série sobre o estudo do Programming Pearls. O primeiro post, onde falei sobre as colunas 1 a 5, pode ser encontrado aqui. Hoje vou falar sobre as colunas 6 a 10, que englobam o assunto de desempenho dos programas.

Coluna 6: Algorithm Design Techniques

Na primeira coluna sobre o assunto, o livro descreve um caso real onde a otimização do programa diminuiu o tempo de execução do programa em 400 vezes. Essa otimização foi feita em diversos níveis:

Algoritmos e estruturas de dados — Investir um tempo para desenvolver algoritmos e escolher as estruturas de dados corretas pode reduzir a complexidade. Em geral é onde se consegue a maior redução no tempo.

Ajuste de algoritmos — Dependendo do problema, o uso de heurísticas para evitar processamento desnecessário pode ser interessante. A complexidade não mudará, mas na prática podemos ganhar um pouco de tempo. (Hey, minha área de pesquisa está aqui!)

Ajuste de código — Quando não se consegue mais melhorias com os níveis anteriores, pode-se apelar para truques de implementação. Aqui vale tudo: escrever o código em assembly, fazer uso de particularidades do sistema, paralelizar código, etc. O problema é que se perde em legibilidade de código e é um caminho sem volta.

Se seu código otimizado ainda deverá sofrer manutenção, pode ficar bastante difícil programar. Já dizia o mestre:

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil

Donald Knuth

Ou seja, só desça para esse nível se seu código estiver funcional e não for sofrer maiores alterações.

Hardware — Após passar por todos os níveis, se quiser ganhar mais eficiência, uma ideia é investir em equipamentos mais sofisticados. Sistemas multi-core, clusters, GPU’s estão na moda. Não é preciso dizer que essa é a opção mais cara de se implementar.

Coluna 7: Back of the Envelope

Nas primeiras aulas de desenho técnico, lembro-me que o professor não deixava usar régua e compasso. A justificativa era que precisávamos aprender a improvisar rascunhos em situações em que não tivéssemos tais instrumentos à mão. Acredito que seja esse o espírito da coluna 7: estimar valores e custos.

Algumas regras para certos tipos de estimativas são apresentadas nessa coluna.

[1] Quantos segundos aproximadamente tem um ano? Faça a conta 3600*24*30*12, ou use o mnemônico: “pi segundos é um nano centenário” , para concluir que 1 ano ~= 3,14*10e7 s

[2] Removendo os 9 — Essa regra parte da propriedade de que o resto da divisão de um número N por 9, é igual ao resto da divisão da soma dos dígitos de N. Por indução, podemos repetir o argumento até que a soma contenha um dígito apenas, ficando fácil determinar o resto da divisão de N por 9.

Exemplo: N = 23718. A soma dos dígitos dá 21. A soma dos dígitos de 21 dá 3. Logo, 23718 % 9 = 3.

Mas a regra consiste em usar essa propriedade para determinar se uma soma está errada. Lembrando que o módulo da soma deve ser igual à soma dos módulos dos termos somados, vejamos o exemplo extraído do livro: 3142 + 2718 + 1123 = 6973. Temos que 3142 % 9 = 1, 2718 % 9 = 0 e 1123 % 9 = 7. A soma dá 8, mas 6973 % 9 = 7, então a soma deve estar errada.

[3] Regra do 72 — Essa regra vem de contabilidade e diz que se J é o rendimento de uma aplicação e T é o tempo em que o dinheiro ficou investido, então quando J*T = 72, o montante dobra. Por exemplo, se investimos R$1000 com rendimento de 6% ao ano, a regra diz que T = 12. Fazendo a conta para juros compostos, teremos 1000*(1 + .06)^12 = 2012.20.

[4] Lei de Little — diz “O número médio de objetos em um sistema é o produto do fluxo médio em que os objetos deixam o sistema e o tempo médio em que os objetos permanecem no sistema.”

Curiosamente eu já tinha usado essa regra para fazer uma estimativa sem saber que ela existia. Lembrando de um episódio do Chaves em que o prof. Girafales dizia “Cada vez que você respira, morre um chinês”, fiquei curioso para saber quantas pessoas morrem por segundo na China.

Sem ter acesso a qualquer referência, decidi fazer a estimativa. Eu tinha uma noção da população (número médio de pessoas no sistema) e chutei 1.5bi. Também chutei que a expectativa de vida lá é 70 anos (tempo que permanecem no sistema). Supus que a distribuição de pessoas por idade era uniforme, então pessoas com “0 anos”, devem corresponder a cerca de 1.5bi/70 =~ 20.000.000 por ano, o que dá 0.7 de recém-nascidos por segundo. Como a população da China está aumentando, o número de mortes deve ser menor do que nascimentos, mas como não tinha como usar essa informação, supus que eram iguais.

Não lembro qual foi minha estimativa para o tempo que levamos para respirar, mas aparentemente a média é 5 segundos. Isso siginifica que cada vez que o Chaves respira morrem 3.5 chineses. Não bateu exatamente com a afirmação do professor, mas como a estimativa ficou na mesma ordem de grandeza parece razoável.

Coluna 8: Algorithm Design Techniques

Nessa coluna o autor apresenta o clássico problema da subsequência de soma máxima. Dado um vetor de n elementos, por exemplo números inteiros, deseja-se encontrar i < j tal que a soma dos elementos de i a j, inclusive, seja máxima.

É mostrada uma abordagem inicial O(n^3), que vai reduzindo para O(n^2), O(n log n) por divisão e conquista, até chegar no famoso algoritmo baseado em programação dinâmica O(n).

Coluna 9: Code Tuning

People who play with bits should expect to get bitten

Jurg Nievergelt

Aqui são apresentados alguns truques para otimizar código. Os exemplos citados incluem:

— Evitar operações de divisão e módulo quando há uma alternativa simples;

— Substituir funções por macros (ou usar o modificador inline do C++);

Porém, usar macros pode ser perigoso. Considere o código abaixo:

#define max(a, b) ((a) > (b) ? (a) : (b))

int arrmax(int *x, int n){
    if (n == 1) return x[0];
    else return max(x[n-1], arrmax(x, n-1));
}

Qual a complexidade desse código? E se substituirmos a macro por uma função?

— Usar loop unrolling, embora eu não tenha conseguido implementar um código onde tal estratégia tenha diminuído o tempo de execução.

Coluna 10: Squeezing Space

Com a disponibilidade de memória na casa dos giga bytes, não faz mais tanto sentido escovar código para reduzir consumo de memória, exceto para sistemas embarcados. Nessa coluna o autor descreve algumas técnicas para a redução do consumo de memória, tais como

— Estruturas de dados esparsos – como matrizes esparsas

— Compressão de dados – usando informação sobre o intervalo de valores que seu dado possa assumir, dá para escolher um tipo de dado mais adequado. Por exemplo, usar char ao invés de int.

— Garbage Collection – algumas linguagens como Java têm essa funcionalidade embutida. Em linguagens que não oferecem esse mecanismo como C++, existe a alternativa de se usar smart pointers.

Python como alternativa a Bash Script

Sempre que precisava automatizar alguma tarefa no linux, apelava para scripts bash. O problema é que escrevo scripts com pouca frequência e somada à sintaxe peculiar dos comandos bash, sempre preciso consultar referências e acabo perdendo bastante tempo.

Pra piorar, algumas tarefas como processamento de strings são complicadas de fazer em bash script e então normalmente usam-se ferramentas auxiliares como sed e awk. A sintaxe delas é bem concisa e elegante, mas acho difícil dominá-las usando-as tão pouco.

Foi por isso que decidi investir um tempo pesquisando modos de substituir bash script por python.

No meu ponto de vista, há um tradeoff entre usar bash script e python. O primeiro faz comunicação direta com o sistema operacional, sendo trivial executar programas, redirecionar entrada/saída ou manipular diretórios, mas é complicado para se fazer processamentos em geral. Já python é o oposto: é bem simples de se programar mas para comunicar com o sistema operacional é necessário usar API’s.

Módulo os

Algumas tarefas de manipulação de diretórios ficam relativamente simples usando o módulo os. Comandos como mkdir, chmod, chown têm suas versões homônimas nesse módulo. Outras comuns mas com nomes ligeiramente diferentes são

* ls — os.listdir(path) — retorna uma lista com os nomes dos arquivos no diretório apontado por path.

* pwd — os.getcwd() — retorna o nome do diretório corrente.

Além dessas, temos também algumas de manipulação de caminhos no módulo os.path. As que eu mais usei até agora,

* os.path.join — Sintaxe: os.path.join(path1[, path2[, …]])

Recebe um conjunto de strings e as concatena em ordem para formar um caminho. Exemplo:

print os.path.join('/home', 'joao/', 'musica')

Vai imprimir

/home/joao/musica

Nota: como está dito no manual, se alguma das strings representar um caminho absoluto, ele ignora todas as strings anteriores. No linux o caminho absoluto é iniciado por /. Por exemplo:

print os.path.join('/home', 'joao/', '/musica')

Vai imprimir

/musica

* os.path.exists — Sintaxe: os.path.exists(path)

Esse comando retorna True se o caminho path existe e False caso contrário.

Nota: esse comando não diferencia arquivos e diretórios. Assim, se existir o diretório foo/ mas você estiver procurando um arquivo chamado foo, o comando mencionado vai retornar True mesmo que o arquivo não exista. Para obter o comportamento esperado, deve-se usar o comando os.path.isfile (ou os.path.isdir na situação oposta).

Módulo subprocess

A criação de processos dentro de scripts python ficava no módulo os, mas está depreciada desde a versão 2.6. Essa tarefa agora está implementada no módulo subprocess.

O principal componente desse módulo é a classe Popen, que recebe vários parâmetros. O primeiro deles é uma lista contendo o nome do programa a ser executado e os argumentos. Depois tem diversos outros, mas os que achei mais importantes são stdin, stderr, stdout.

Exemplo 1 — Executando um processo com argumentos

Imagine um programa chamado ./print que imprime o primeiro e o segundo parâmetro que ele receber. Em C++ pode ser algo como:

#include <iostream>
int main (int argc, char **argv){
    std::cout << argv[1] << " -- " << argv[2] << "\n"; 
}

No bash, se quisermos enviar um argumento para o programa ./print que contenha espaço, devemos pô-lo entre aspas. Por exemplo,

./print "ola mundo" "tudo bem?"

Vai imprimir: ola mundo -- tudo bem?

A vantagem de se usar uma lista de strings é que podemos especificar qual é argumento é qual. Podemos fazer assim:

import subprocess
p = subprocess.Popen(['./print', 'ola mundo',
                      'tudo bem?'])
p.wait()

Exemplo 2 — Processando stdout

No exemplo anterior, a string será impressa na saída padrão (stdout), mas o código python não terá acesso a ela. Se quisermos processar a string impressa por ./print, podemos redirecionar a saída usando pipes, como no bash.

Para fazer isso, usa-se a variável especial subprocess.PIPE. Por exemplo:

import subprocess
import sys
p = subprocess.Popen(['./print', 'oi', 'mundo'],
                     stdout=subprocess.PIPE)
saida = p.communicate()
sys.stdout.write(saida[0].upper())

Nesse caso, o método communicate() serve para fazer a comunicação com o processo. Ele retorna uma lista de dois elementos [stdout, stderr] e também pode receber como argumento a string que será redirecionada para o stdin do processo. No exemplo, só estamos redirecionando o stdout para o objeto, então saida[1] = None, enquanto que saida[0] contém a linha impressa por ./print. Estamos convertendo tudo para caixa alta, então o programa acima imprime:

OI -- MUNDO

Exemplo 3 — Usando stdin e stderr

Para completar, um exemplo onde usamos o stdin e o stdout. Seja ./read um programa que lê um inteiro da entrada padrão e imprima na saída de erro esse número multiplicado por 2, como o código C++ a seguir:

#include <iostream>
int main(){
    int n;
    std::cin >> n;
    std::cerr << 2*n << '\n';
}

Queremos executar esse programa, enviar um número na entrada padrão dele e ler da saída de erro. Podemos fazer isso com o seguinte código:

import subprocess
import sys
p = subprocess.Popen(['./read'],
                     stdin=subprocess.PIPE,
                     stderr=subprocess.PIPE)
sys.stdout.write(p.communicate('2')[1])

Nesse caso redirecionamos o stdin e o stderr. Conforme eu havia dito, o método communicate recebe como parâmetro os dados que serão enviados para a entrada padrão do processo. Além disso, o conteúdo da saída de erro é o segundo elemento da lista retornada.

Exemplo 4 — Redirecionamento para arquivo

Em bash script é comum redirecionarmos saída para arquivos com o operador ‘>’. Para fazer isso usando subprocess, temos que abrir o arquivo explicitamente com open e passar o objeto retornado como parâmetro para o stdout do Popen. Exemplo:

import subprocess
f = open('tmp.txt', 'w')
subprocess.call(['ls'], stdout=f)
f.close()

É comum redirecionarmos o stderr para o /dev/null para que ele não seja impresso no terminal. Se quisermos fazer isso com subprocess, basta abrir o arquivo '/dev/null' e passar o objeto para stderr.

Funções auxiliares

Adicionalmente há algumas funções para simplificar a tarefa dependendo das suas necessidades.

subprocess.call — executa um comando, espera o processo terminar e devolve o código retornado pelo processo. Seria adequado para o Exemplo 1.

subprocess.check_output — Executa um comando e retorna uma string com o conteúdo da saída padrão — só está disponível a partir da versão 2.7. Seria adequado para o Exemplo 2.

Nota: Em geral, eu adiciono permissão de execução para meus scripts bash, por exemplo script.sh, e o executo como ./script.sh. Porém, usando subprocess, tem que executá-lo usando o /bin/bash:

p = subprocess.Popen(['/bin/bash', 'script.sh'])

Conclusão

Com esses módulos mencionados, tenho conseguido me virar usando python como script. Agora só uso bash scripting mesmo quando preciso executar uma lista de comandos sem ter que fazer processamento algum.

Referências

[1] 15.1 – Miscellaneous operating system interfaces
[2] 17.1 – Subprocess management
[3] Stackoverflow — How do I check if a file exists using Python?

Topcoder: SRM 495

O post era pra ter saído na Sexta, mas acabou atrasando :/ Bom, hoje vou comentar sobre os problemas não resolvidos durante o SRM 495. Consegui fazer o fácil de 300 pontos, mas demorei bastante tempo e tive que ressubmeter. Aí meu rating acabou caindo.

Carrot Boxes

Descrição. Há N caixas numeradas de 0 a N-1. Todas as caixas, exceto uma, possuem uma cenoura. Deseja-se descobrir a caixa vazia sem abri-la.

Algumas caixas possuem informações sobre o conteúdo de outras caixas e essa informações são conhecidas a priori. É dado um vetor<string> information, onde o j-ésimo caractere da i-ésima string é ‘Y’ se abrir a i-ésima vai revelar se a j-ésima caixa contém ou não uma cenoura, ou ‘N’ caso contrário.

Retornar a maior probabilidade para descobrir a caixa vazia sem ter que abri-la. (Texto original)

O autor do editorial descreveu a solução desse problema de forma tão bem detalhada e exemplificada que nem vale a pena explicar do meu jeito. Implementei a solução descrita em C++. Uma coisa que achei legal da solução é que se você pode se dar ao luxo de rodar um Floyd-Warshall O(n^3), depois fica bem simples determinar componentes fortemente conexas.

Strange Elevator

Descrição resumida. Considere um prédio de H andares e um elevador formado por N compartimentos (não necessariamente consecutivos). Quando parado, cada parte fica em um andar distinto e quando o elevador se move, todas as partes movem junto. Cada andar deve ser coberto por exatamente um compartimento do elevador. (Texto original)

Podemos representar um elevador pelos andares em que cada compartimento está, quando o compartimento mais baixo está no primeiro andar (denotado aqui por nível 0). Por exemplo, se H = 6 e N = 3, os elevadores (0, 2, 4) e (1, 3, 5) são respectivamente:

O problema pede para, dados N e H, encontrar quantos elevadores válidos podem ser formados. Para H = 6 e N = 3, há duas possibilidades, (0, 2, 4) e (0, 1, 2). Observe que (0, 2, 3) não é válido, pois o elevador, ao subir um andar, irá para os andares (1, 3, 4) e o andar 3 terá sido coberto por dois compartimentos diferentes.

Solução. Está bem detalhada no editorial, então vou tentar resumir aqui.

Proposição 1: Definimos como bloco um conjunto contínuo de compartimentos. Em um dado elevador, todos os blocos têm mesmo tamanho L.

Proposição 2: O espaço de separação entre dois blocos consecutivos é múltiplo de L.

A ideia básica das provas das duas proposições acima é que se elas não forem verdade, então necessariamente algum andar será coberto por mais de um compartimento ou algum andar não será coberto.

Problemas de contagem geralmente envolvem algum tipo de programação dinâmica (exceto quando existe uma fórmula fechada). De fato, a solução apresentada divide a matriz de PD em duas partes: C1(H, N) e Cn(H, N) a primeira corresponde ao número de elevadores válidos para um prédio de H andares e N caixas quando os blocos têm tamanho L = 1, enquanto a segunda quando os blocos têm tamanho L > 1.

A sacada do problema consiste em definir a relação de recorrência. A primeira observação é um corolário das Proposições 1 e 2: Como os blocos têm tamanho L e os espaços têm tamanho múltiplos de L, então H deve ser múltiplo de L. Dado isso, podemos “escalar” o problema dividindo todas as dimensões por L. Ou seja, o número de elevadores válidos para H andares, N caixas e blocos de tamanho L, é o mesmo para H/L andares, N/L caixas e blocos unitários. Logo, podemos definir a recorrência de Cn(H, N) da seguinte forma:

(1)

Para definir a recorrência de C1(H, N) é mais complicado. Considere o vetor offbox que representa o offset dos compartimentos (boxes), ou seja, é o andar que cada compartimento ocupa quando o compartimento mais embaixo está no primeiro andar. Esse vetor tem tamanho N. Seja offlift o offset do elevador, ou seja, é o andar ocupado pelo compartimento mais embaixo. Esse vetor tem tamanho H/N que é o número de vezes que um elevador com N caixas pára.

Observe que se o elevador é válido, então para todo andar a, existe exatamente um par (i, j) tal que a = offbox[i] + offlift[j] e que esses dois vetores caracterizam unicamente um dado elevador. É fácil ver que se offbox e offlift representam um elevador válido para H andares e N caixas, trocando os papéis deles, vai gerar um elevador, denotado por dual, válido com H andares e H/N caixas.

Considere então um elevador com blocos de tamanho 1. Temos que offbox[0] = 0 e offbox[1] > 1, já que a primeira e a segunda caixa não podem estar contíguas. Além do mais, o primeiro compartimento é o único capaz de visitar o segundo andar, ou seja o elevador deve parar também no primeiro andar e offlift[1] = 1. Trocando os papeis dos vetores, temos offbox[0] = 0 e offbox[1] = 1, ou seja, é um elevedor com L > 1. Assim, todo elevador para H andares, com N caixas e L = 1, corresponde a um elevador para H andares, H/N caixas e L > 1.

Exemplo de configurações duais. O primeiro é offbox = {0, 2, 4} e offlift = {0, 1}. O segundo é offbox = {0, 1} e offlift = {0, 2, 4}.

Por outro lado, é fácil ver que todo elevador para H andares, H/N caixas e L > 1, corresponde a um elevador para H andares, N caixas e L = 1. Lembrando que cada um desses vetores caracteriza unicamente um elevador, não é difícil de acreditar que há uma bijeção entre essas duas configurações, o que equivale a afirmar que o número de elevadores válidos em cada uma delas é exatamente o mesmo, permitindo finalmente que escrevamos a recorrência de C1(H, N)

(2)

Como H e N sempre diminuem, as recorrências em (1) e (2) são suficientes para resolver o problema que é simplesmente C1(H, N) + Cn(H, N).

Ainda está faltando o caso base. Como H começa maior do que N e nunca diminuímos H mais do que N, fica claro que H não chegará em 1 antes de N. Logo, basta tratar o caso em que N = 1. Só há um possível elevador para N = 1 com blocos de tamanho 1 e claramente não existem elevadores com N = 1 para blocos de tamanho maior do que 1.

Outro cuidado que devemos tomar é que só existe solução se N dividir H, então precisamos fazer essa verificação antes de rodar o algoritmo.

Finalmente, um detalhe sobre a implementação. A princípio a complexidade parece ser O(HN*div(N)), onde div(N) são os divisores de N, que é essencialmente O(sqrt(N)). Porém, como H e N são da ordem de 1000000000 (10^9), essa abordagem parece impraticável.

Por outro lado, note que quando chamamos Cn(H, N), apenas os O(sqrt(N)) divisores de N serão chamados e serão divididos por pelo menos um fator de 2. Sinceramente, não sei calcular uma complexidade mais justa, mas olhando por cima, parece que não serão chamadas muitas combinações de H e N.

Além do mais, podemos otimizar o algoritmo usando memoização. No caso usual usaríamos os valores de H e N para indexar uma matriz. Aqui, entretanto, não é possível devido à magnitude dos valores. Supondo um número pequeno de combinações H e N, podemos usar um mapa usando como chave o par (H, N) (map<pair<int, int> > da STL).

Minha implementação em C++ está disponível aqui.

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