PIOC Cobertura 2015

Problema de Cobertura

Problema de cobertura:
Dada uma matriz de zeros e uns e um custo associado a cada coluna, pretende-se determinar o subconjunto de colunas custo mínimo que cubram todas as linhas, isto é, tal que, para cada linha, existe pelo menos um um numa das colunas seleccionadas.

Teorema:
O problema de cobertura é NP-difícil.

Cobertura

Optimização Combinatória

1/6

Problema de Cobertura

Formulação
Conjuntos:
N = {1, . . . , n}− conjunto das colunas.
M = {1, . . . , m}− conjunto das linhas.
Ni = {j ∈ N : aij = 1}, i ∈ M.
Mj = {i ∈ M : aij = 1}, j ∈ N.
Parâmetros:
1

cj custo da coluna j, j ∈ N.

2

aij = 1 se coluna j cobre a linha i e aij = 0 no caso contrário i ∈ M, j ∈ N.

Variáveis: xj =

1, se é seleccionada a coluna j; j∈J 0, caso contrário;
Cobertura

Optimização Combinatória

2/6

Problema de Cobertura

Formulação

min

cj xj j∈N aij xj ≥ 1, ∀i ∈ M

s.a : j∈N xj ∈ {0, 1}, j ∈ N
Substituindo

j∈N

aij xj ≥ 1, ∀i ∈ M por aij xj = 1, ∀i ∈ M j∈N obtemos o problema da partição.
Cobertura

Optimização Combinatória

3/6

Problema de Cobertura

Reduções:
1

Se existe i ∈ M tal que Ni = ∅ então o problema é impossível.

2

Se i ∈ M é tal que Ni = {j(i)} (i é coberta apenas por uma coluna) então j(i) está na solução.

3

(Dominância entre linhas) Sejam i, ℓ ∈ M tal que Ni ⊆ Nℓ então a linha ℓ pode ser eliminada.

4

(Dominância entre colunas) Sejam k, j1 , . . . , js ∈ N tais que s Mk ⊆

s

Mt e ck ≥ t=1 ct então a coluna k pode ser removida. t=1 5

(Dominância entre colunas simples) Sejam k, j ∈ N tais que
Mk ⊆ Mj e ck ≥ cj então a coluna k pode ser removida.

6

(Dominância fraca entre colunas) Seja di = minj∈Ni cj e k ∈ N tal que ck ≥ di então a coluna k pode ser removida. i∈Mk Cobertura

Optimização Combinatória

4/6

Problema de Cobertura

Algoritmo Greedy
Inicializar R ← M, S ← ∅, t ← 1
Enquanto R = ∅ fazer
Seja i ∗ ∈ R tal que | Ni ∗ |= mini∈R | Ni |
Escolher j(t) tal que f (cj(t) , kj(t) ) = min{f (cj , kj ) : j ∈ Ni ∗ ∧ kj > 0}
onde