Problema da Mochila Bianca de Almeida Dantas

Marcio Osshiro

Objetivos

• Apresentar o problema da mochila e suas variantes.

• Mostrar alternativas de solução para a variante 0-1.

• Mostrar o funcionamento de um código MPI para o problema.

• Abordagem utilizando CUDA.

Aplicação

• Logística

• Criptografia

• Engenharia Naval

• Gerenciamento de Projetos

• Finanças

• Entre outras

• Suponha que um gerente de uma empresa possua no seu orçamento c reais para investir em projetos dentro do seu departamento. Após uma pesquisa realizada por sua equipe, o gerente recebe um relatório com n diferentes projetos que trariam reduções de custo ou aumento de produtividade ao departamento como um todo. Associado a cada projeto j existe um retorno de pj reais e um custo para sua realização de cj reais. O gerente pode encontrar uma distribuição ótima de seu orçamento resolvendo um problema da mochila binária

Variações

• Problema da Mochila Limitada

• Problema da Mochila Ilimitada (UKP)

• Problema da Soma de Subconjuntos

• Problema da Mochila 0-1

• Problema da Mochila Limitada

Dados um conjunto N de n objetos com valores positivos pj, pesos wj, cada um tendo

bj cópias, e uma mochila de capacidade inteira e positiva c, determine um vetor (x1,

x2, ..., xn), 0 ≤ xj ≤ bj ∈N, que satisfaça as condições:

• Problema da Mochila Ilimitada

Dados um conjunto N de n objetos com valores positivos pj, pesos wj, e uma mochila

de capacidade inteira e positiva c, determine um vetor (x1, x2, ..., xn), xj ∈N, que

satisfaça as condições:

Este problema é uma generalização do Problema da Mochila Limitada no qual bj = ∞, ∀j ∈ N

• Problema da Soma de Sub-conjuntos

Dados um conjunto N de n objetos com pesos wj , e uma mochila de capacidade

inteira e positiva c, determine um vetor (x1 ,x2 , ..., xn),xj ∈{0, 1}, que satisfaça as

condições:

Este problema é um caso particular do 0-1KP em que wj = pj, ∀j ∈ N.

• Problema da Mochila 0-1:

▫ Dados um conjunto N de n objetos com valores

positivos pj, pesos wj e uma mochila de capacidade

inteira e positiva c, determine um vetor (x1, x2, ..., xn

que encontre:

𝑚𝑎𝑥 𝑝𝑗𝑥𝑗

𝑛

𝑗=1

Respeitando as condições 𝑤𝑗𝑥𝑗 ≤ 𝑐𝑛𝑗=1

e 𝑥𝑗 ∈ 0, 1 , 𝑗 = 1,… , 𝑛

Pesquisas em busca de soluções Problema

da Mochila

Soluções Exatas

Aproximação Heurística

Branch and

Bound

Programação Dinâmica

Algoritmos Genéticos

Est

ud

os

Problema da Mochila

• Dados:

▫ uma mochila de compartimento único e com uma capacidade máxima.

▫ conjunto de itens, cada qual com um peso e um valor associados.

• Quais itens podem ser carregados na mochila sem exceder sua capacidade e maximizando o valor a ser carregado?

• Dois tipos:

▫ Mochila 0-1: itens indivisíveis. Resolvido com programação dinâmica.

▫ Mochila fracionária: itens podem ser divididos. Resolvido com uma estratégia gulosa.

Programação Dinâmica

• Utilizada quando o problema pode ser definido recursivamente em termos de soluções para subproblemas menores (subestrutura ótima).

• Deve-se encontrar e armazenar soluções para os subproblemas e, então, utilizá-las na solução de problemas maiores.

• Mais eficiente do que soluções que utilizam estratégias de força-bruta.

• Ideias básicas:

▫ Subestrutura ótima: a solução ótima para o problema é construída a partir de soluções ótimas para os subproblemas.

▫ Subproblemas “overlapping”: poucos subproblemas com muitas instâncias recorrentes de cada.

▫ Construção de uma tabela com as “subsoluções” usada para solucionar os problemas maiores.

Problema da Mochila 0-1 • Também conhecido como problema da mochila

booleana. • Dado um valor inteiro W e os conjuntos: ▫ S = {1, 2, 3, ..., n} ▫ W = {w1, w2, w3, ..., wn} ▫ V = {v1, v2, v3, ..., vn}

• onde W é a capacidade da mochila, S é um conjunto de objetos, W é o conjunto dos pesos de tais objetos e V é o conjunto de seus valores. Devemos encontrar quais os itens de S devem ser colocados na mochila visando maximizar o valor carregado, sem exceder a capacidade da mochila.

• Problema NP-completo. • Pode ser resolvido em O(nW) => solução

pseudo-polinomial. • Alternativas para solução exata: ▫ Força-bruta. ▫ Programação dinâmica (DP): melhor

comportamento quando os parâmetros são correlacionados.

▫ Branch-and-bound (B&B): mais eficiente quando os valores de w e v são indepentemente gerados.

Algoritmo Força-Bruta

• Forma direta e ingênua para resolver o problema.

• Todas as combinações possíveis de itens são geradas. A combinação com o maior valor e que caiba na mochila será a solução ótima.

• Com n itens => 2n possíveis combinações.

• Complexidade: 0(2n) Algoritmo exponencial.

Muito caro!!!!

Tentando definir um subproblema

• Podemos considerar um subproblema definido como:

▫ Sk = conjunto de itens numerados de 1 a k, onde 1<=k<=n.

• É possível encontrar a solução final Sn em termos dos subproblemas Sk?

A resposta é não....

Objeto 1 2 3 4 5

Peso 2 3 4 5 9

Valor 3 4 5 8 10

S4 = {1, 2, 3, 4} => Peso total: 14 e Valor: 20 S5 = {1, 3, 4, 5} => Peso total: 20 e Valor: 26

S4 não faz parte da solução de S5

• Devemos considerar outro parâmetro: o peso de cada conjunto de subitens.

• O subproblema consiste em computar f(r, c):

▫ f(r, c) = f(r-1, c), se wr > W

f(r, c) = max{f(r-1, c), f(r-1, c-wr) + vr}

• A melhor solução Sr com peso c é:

▫ a melhor solução Sr-1 com peso c, ou

▫ a melhor solução Sr-1 com peso c-wr mais o valor do item r

Fórmula Recursiva com Subproblemas

{

Algoritmo de Gilmore e Gomory

• Primeiro algoritmo a usar DP para resolver o problema da mochila 0-1.

• Seja f(r, c) a solução ótima considerando o conjunto de objetos [1, r] e o peso c., com 1<=r<=n e 0<=c<=W. A solução ótima para o problema será f(n, W).

• A relação de recorrência para solução:

▫ f(r, c) = max{f(r-1, c), f(r-1, c-wr) + vr}

• Tempo: O(nW)

para c de 0 ate W faca F[0,w] = 0 fimpara para r de 1 ate n faca F[i,0] = 0 fimpara para r de 1 ate n faca para c de 0 ate W faca se (wi <= W) entao// item i can be part of the solution se (F[r-1,c-wi] + vr > F[r-1,c]) entao F[r,c] = F[r-1,c-wi] + vr senao F[r,c] = F[r-1,c] fimse else F[r,c] = F[r-1,c] // wi > W fimse fimpara fimpara

Exemplo

• Sejam uma mochila de capacidade 10 e 5 objetos com seus pesos e valores representados na seguinte tabela:

Objeto 1 2 3 4 5

Peso 8 3 6 4 2

Valor 100 60 70 15 15

0 1 2 3 4 5 6 7 8 9 10

0

1(8)

2(3)

3(6)

4(4)

5(2)

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0

2(3) 0

3(6) 0

4(4) 0

5(2) 0

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0 0

2(3) 0

3(6) 0

4(4) 0

5(2) 0

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0 0 0 0 0 0 0 0

2(3) 0

3(6) 0

4(4) 0

5(2) 0

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0 0 0 0 0 0 0 0 100

2(3) 0

3(6) 0

4(4) 0

5(2) 0

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0 0 0 0 0 0 0 0 100 100 100

2(3) 0

3(6) 0

4(4) 0

5(2) 0

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0 0 0 0 0 0 0 0 100 100 100

2(3) 0 0 0 60

3(6) 0

4(4) 0

5(2) 0

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0 0 0 0 0 0 0 0 100 100 100

2(3) 0 0 0 60 60 60 60 60

3(6) 0

4(4) 0

5(2) 0

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0 0 0 0 0 0 0 0 100 100 100

2(3) 0 0 0 60 60 60 60 60 100 100 100

3(6) 0

4(4) 0

5(2) 0

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0 0 0 0 0 0 0 0 100 100 100

2(3) 0 0 0 60 60 60 60 60 100 100 100

3(6) 0 0 0 60 60 60

4(4) 0

5(2) 0

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0 0 0 0 0 0 0 0 100 100 100

2(3) 0 0 0 60 60 60 60 60 100 100 100

3(6) 0 0 0 60 60 60 70 70

4(4) 0

5(2) 0

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0 0 0 0 0 0 0 0 100 100 100

2(3) 0 0 0 60 60 60 60 60 100 100 100

3(6) 0 0 0 60 60 60 70 70 100

4(4) 0

5(2) 0

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0 0 0 0 0 0 0 0 100 100 100

2(3) 0 0 0 60 60 60 60 60 100 100 100

3(6) 0 0 0 60 60 60 70 70 100 130 130

4(4) 0

5(2) 0

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0 0 0 0 0 0 0 0 100 100 100

2(3) 0 0 0 60 60 60 60 60 100 100 100

3(6) 0 0 0 60 60 60 70 70 100 130 130

4(4) 0 0 0 60

5(2) 0

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0 0 0 0 0 0 0 0 100 100 100

2(3) 0 0 0 60 60 60 60 60 100 100 100

3(6) 0 0 0 60 60 60 70 70 100 130 130

4(4) 0 0 0 60 60 60 70

5(2) 0

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0 0 0 0 0 0 0 0 100 100 100

2(3) 0 0 0 60 60 60 60 60 100 100 100

3(6) 0 0 0 60 60 60 70 70 100 130 130

4(4) 0 0 0 60 60 60 70 75

5(2) 0

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0 0 0 0 0 0 0 0 100 100 100

2(3) 0 0 0 60 60 60 60 60 100 100 100

3(6) 0 0 0 60 60 60 70 70 100 130 130

4(4) 0 0 0 60 60 60 70 75 100 130 130

5(2) 0

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0 0 0 0 0 0 0 0 100 100 100

2(3) 0 0 0 60 60 60 60 60 100 100 100

3(6) 0 0 0 60 60 60 70 70 100 130 130

4(4) 0 0 0 60 60 60 70 75 100 130 130

5(2) 0 0 15

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0 0 0 0 0 0 0 0 100 100 100

2(3) 0 0 0 60 60 60 60 60 100 100 100

3(6) 0 0 0 60 60 60 70 70 100 130 130

4(4) 0 0 0 60 60 60 70 75 100 130 130

5(2) 0 0 15 60 60

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0 0 0 0 0 0 0 0 100 100 100

2(3) 0 0 0 60 60 60 60 60 100 100 100

3(6) 0 0 0 60 60 60 70 70 100 130 130

4(4) 0 0 0 60 60 60 70 75 100 130 130

5(2) 0 0 15 60 60 75 75

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0 0 0 0 0 0 0 0 100 100 100

2(3) 0 0 0 60 60 60 60 60 100 100 100

3(6) 0 0 0 60 60 60 70 70 100 130 130

4(4) 0 0 0 60 60 60 70 75 100 130 130

5(2) 0 0 15 60 60 75 75 75

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0 0 0 0 0 0 0 0 100 100 100

2(3) 0 0 0 60 60 60 60 60 100 100 100

3(6) 0 0 0 60 60 60 70 70 100 130 130

4(4) 0 0 0 60 60 60 70 75 100 130 130

5(2) 0 0 15 60 60 75 75 75 100

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0 0 0 0 0 0 0 0 100 100 100

2(3) 0 0 0 60 60 60 60 60 100 100 100

3(6) 0 0 0 60 60 60 70 70 100 130 130

4(4) 0 0 0 60 60 60 70 75 100 130 130

5(2) 0 0 15 60 60 75 75 75 100 130

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0 0 0 0 0 0

1(8) 0 0 0 0 0 0 0 0 100 100 100

2(3) 0 0 0 60 60 60 60 60 100 100 100

3(6) 0 0 0 60 60 60 70 70 100 130 130

4(4) 0 0 0 60 60 60 70 75 100 130 130

5(2) 0 0 15 60 60 75 75 75 100 130 130

Algoritmo Wavefront

• Algoritmo paralelo utilizando programação dinâmica.

• Segue o modelo de programação BSP/CGM. • Considerando n itens, capacidade W e p

processadores: ▫ O(p) rodadas de comunicação ▫ O(W n/p) de computação

• O vetor de pesos é replicado para todos os processadores.

• O vetor v é dividido em p partes.

Figura 11 – Divisão da matriz em faixas para cada processador.

• Comunicação wavefront ou sistólica.

• Cada processador se comunica com, no máximo, dois processadores.

• Problema: Processador Pi precisa de informação do processador Pi-1 para calcular sua primeira coluna.

• Solução: Particionar as submatrizes dos processadores em blocos.

Figura 12 – Particionamento em blocos de m/p linhas.

• Problema: Baixo nível de paralelismo.

Figura 13 – Particionamento usando α = ½.

Código MPI

Referências

• Cáceres, E.N.; Nishibe, C. 0-1 Knapsack Problem: BSP/CGM Algorithm and Implementation. Proc of the 17th IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS 2005), pp. 331-335, 2005.

• http://www.cse.unl.edu/~goddard/Courses/CSCE310J