Pseudo-Boolean Optimization20PHOENIX/Relat%F3rios%20T%E9... · de limites das ariávveis, ... Como o número de termos de uma restrição pseudo-booleana é dependente do ... amosV

Pseudo-Boolean Optimization

Anexo

1 Denição

Uma função pseudo-booleana fPB é uma função que mapeia n variáveis binárias à um

número real.

fPB : 0, 1n → Rb 7→ x

tal que, ∀x ∈ R

fPB(b1, b2, ..., bn) =

n∑i=1

xibi +

n∑i=1

n∑j=i

xijbibj +

n∑i=1

n∑j=i

n∑k=j

xijkbibjbk + ...

Uma restrição pseudo-booleana RPB é uma relação que associa uma função pseudo-

booleana à um número real.

RPB ≡∑i

xi∏j

bij y

onde é uma relação <, ≤, =, ≥ ou >.

Dada uma fórmula f sendo uma conjunção de restrições pseudo-booleanas e uma

função objetivo pseudo-booleana g, no problema de Otimização Pseudo-Booleana tem-se

que decidir se f é satisfatível e identicar a valoração que minimiza g.

min g

Sujeito a:

f

tal que f =∧

iRPBi.

Para construir uma restrição pseudo-booleana a partir de uma função pseudo-booleana

qualquer, devemos simplicá-la algebricamente utilizando as propriedades distributiva e

associativa. Tal formato de restrição facilita a implementação de resolvedores pseudo-

booleanos e ajudam na análise da quantidade de termos da restrição.

1

2 Modelagem

Para modelar um problema de otimização qualquer como um problema de Otimização

Pseudo-Booleana, temos que construir a fórmula f e a função objetivo g a partir do

domínio estabelecido. Para isso, primeiramente discretizamos as variáveis do problema

original, obtendo domínios nitos para cada uma delas.

Seja Λ o conjunto de variáveis do modelo original. Discretizamos toda variávelXi ∈ Λobtendo D(Xi) tal que |D(Xi)| < ∞. Para cada elemento xj ∈ D(Xi) denimos uma

variável binária bij e então, para cada restrição do modelo original, adicionamos ao modelo

pseudo-booleano uma restrição equivalente realizando a substituíção:

Xi =∑

xj∈D(Xi)

xjbij

onde bij representa a escolha do valor xj para a variável Xi, tal que j = 1 .. |D(Xi)| <∞, para toda variável Xi do modelo original.

Além disso, para cada variável Xi temos que adicionar ao modelo a restrição

|D(Xi)|∑j=1

bij = 1

garantindo unicidade na escolha do valor de Xi.

Essa substituição modica o domínio das restrições, transformando-as em restrições

pseudo-booleanas. A não ser pela simplicação ocasionada na discretização das variáveis,

o modelo gerado é equivalente ao modelo original, pois simplesmente enumeramos todas

as possibilidades de atribuições às variáveis na fórmula, de maneira explícita. Essa enu-

meração aumenta o tamanho da restrição conforme a não-linearidade da função original.

Devido à restrição de unicidade temos as seguintes propriedades:

X1 =∑

xi∈D(X1)

xib1,i

X1 + X2 =∑

x1,i∈D(X1)

x1,ib1,i +∑

x2,i∈D(X2)

x2,ib2,i

X1X2 = (∑

x1,i∈D(X1)

x1,ib1,i)(∑

x2,i∈D(X2)

x2,ib2,i) =∑

x1,i∈D(X1)

∑x2,i∈D(X2)

x1,ix2,ib1,ib2,i

X21 = (

∑x1,i∈D(X1)

x1,ib1,i)(∑

x1,i∈D(X1)

x1,ib1,i) =∑

x1,i∈D(X1)

x21,ib1,i

n∏i=1

Xaii =

n∏i=1

(∑

xj∈D(Xi)

xaij bik) =∑

x1,i∈D(X1)

∑x2,i∈D(X2)

...∑

xn,i∈D(Xn)

n∏j=1

xajj,ibj,i

Portanto, para uma restrição não-linear da forma Xa11 Xa2

2 ...Xann teremos uma restri-

ção pseudo-booleana com |D(X1)||D(X2)|...|D(Xn)| termos.

2

3 Discretização

Para cada variável X ∈ Λ denimos um tamanho de grão ∆(X), um valor de referência

X0 e um comprimento de intervalo de discretização Γ(X) e montamos D(X) da forma:

D(X) = X0 ± i.∆(X) | i = 0 .. Γ(X)

Para melhorar a solução da otimização matemática, denimos X0 como o valor en-

contrado para a variável X na solução ótima e para utilizar o PBO como uma alternativa

à otimização não-linear, denimos X0 = 0.No processo de discretização das variáveis também levamos em conta as restrições

de limites das variáveis, dispensando a representação destas no modelo pseudo-booleano.

Para aplicar tais restrições na contrução dos domínios, utilizamos o seguinte algoritmo:

Discretiza(X)

t1← Γ(X)t2← Γ(X)Enquanto (X0 − t1·∆(X)) < XMIN

t1← t1− 1Fim Enquanto

I(X)← X0 − t1·∆(X)Enquanto (X0 + t2·∆(X)) > XMAX

t2← t2− 1Fim Enquanto

T (X)← t1 + t2 + 1Devolva (I(X),∆(X), T (X))

Na implementação, utilizamos os valores I(X), ∆(X) e T (X), respectivamente, valor

mínimo do domínio de X, tamanho de grão e tamanho do conjunto D(X). Assim,

contruímos o domínio tal que

D(X) = I(X) + i.∆(X) | i = 0 .. T (X)− 1

Como o número de termos de uma restrição pseudo-booleana é dependente do ta-

manho dos domínios de suas variáveis e cresce polinomialmente, então é direto que o

valor T (X) é o mais impactante na geração da fórmula. No entanto, também é T (X),em conjunto com ∆(X), que denirá o espaço de busca e a possibilidade de encontrar a

solução ótima.

4 Janela de Termelétricas

4.1 Janelas de Tamanho 2

A variável GTj,t é a geração da termelétrica j no período t e seu domínio D(GTj,t) é

construído de forma que 0 ∈ D(GTj,t) e a variável binária b(j,t),0 representa a escolha

3

do valor 0 para GTj,t, isto é, representa o desligamento da usina j.Seja xj,t ∈ 0, 1 a variável que representa ligar a termelétrica j no período t,

t = 1 .. T , é direto que xj,t = ¬b(j,t),0.

Seja yj,t ∈ 0, 1 a variável que representa acionar a janela t para a termo j, isto é,

ligar a usina j nos períodos t e t + 1.

yj,t =

0 se t = 0

xj,txj,t+1 se 0 < t < Txj,t se t = T

A janela T é composta apenas pelo período T , assim, permitimos terminar o plano com

janela de funcionamento não completa. Para qualquer outro período, não existe janela

válida.

Ou, equivalentemente, para todo 0 ≤ t ≤ T

yj,t = xj,txj,t+1

onde xj,0 = 0 e xj,T+1 = 1

Para modelar a janela de térmicas, basta adicionar a seguinte restrição:

• Para 0 < t < T , se a janela t não foi acionada (¬yj,t), então a usina não pode

ser ligada em nenhum período daquela janela (xj,t + xj,t+1), exceto se o período

pertence a outra janela acionada (−yj,t−1 − yj,t+1):

¬yj,t(xj,t + xj,t+1 − yj,t−1 − yj,t+1) = 0

Isto é

¬(xj,txj,t+1)(xj,t + xj,t+1 − (xj,t−1xj,t)− (xj,t+1xj,t+2)) = 0

(¬xj,t + ¬xj,t+1)(xj,t + xj,t+1 − xj,t−1xj,t − xj,t+1xj,t+2) = 0

¬xj,txj,t+1 − ¬xj,txj,t+1xj,t+2 + xj,t¬xj,t+1 − xj,t−1xj,t¬xj,t+1 = 0

Assim, para todo 0 < t < T

xj,t¬xj,t+1 + ¬xj,txj,t+1 − xj,t−1xj,t¬xj,t+1 − ¬xj,txj,t+1xj,t+2 = 0

Da mesma forma, para a janela de manutenção das térmicas denimos a variável

zj,t ∈ 0, 1 que representa acionar a janela de manutenção t para a termo j, isto é,

desligar a termo j nos períodos t e t + 1.

zj,t =

¬xj,t+1 se t = 0

¬xj,t¬xj,t+1 se 0 < t < T¬xj,t se t = T

4

Diferente da janela de funcionamento, aqui denimos a janela 0 para representar que

é válido deixar a termo desligada no primeiro período e ligar logo no segundo, pois todas

as usinas começam desligadas.

Ou, equivalentemente, para todo 0 ≤ t ≤ T

zj,t = ¬xj,t¬xj,t+1

onde ¬xj,0 = 1 e ¬xj,T+1 = 1

E assim:

• Para 0 < t < T , se a janela t não foi acionada (¬zj,t), então a termelétrica não

pode ser desligada em nenhum período daquela janela (¬xj,t + ¬xj,t+1), exceto se

o período pertence a outra janela acionada (−zj,t−1 − zj,t+1):

¬zj,t(¬xj,t + ¬xj,t+1 − zj,t−1 − zj,t+1) = 0

Isto é

¬(¬xj,t¬xj,t+1)(¬xj,t + ¬xj,t+1 − (¬xj,t−1¬xj,t)− (¬xj,t+1¬xj,t+2)) = 0

(xj,t + xj,t+1)(¬xj,t + ¬xj,t+1 − ¬xj,t−1¬xj,t − ¬xj,t+1¬xj,t+2) = 0

xj,t¬xj,t+1 − xj,t¬xj,t+1¬xj,t+2 + xj,t+1¬xj,t − xj,t+1¬xj,t−1¬xj,t = 0

Assim, para todo 0 < t < T

xj,t¬xj,t+1 + ¬xj,txj,t+1 − ¬xj,t−1¬xj,txj,t+1 − xj,t¬xj,t+1¬xj,t+2 = 0

4.1.1 Exemplo

Vamos calcular para uma termo e apenas 4 períodos, cujas variáveis que representam seu

acionamento em cada período são x1, x2, x3 e x4.

Dessa forma temos as seguintes restrições:

• janela de funcionamento:

x1¬x2 + ¬x1x2 − x0x1¬x2 − ¬x1x2x3 = 0

x2¬x3 + ¬x2x3 − x1x2¬x3 − ¬x2x3x4 = 0

x3¬x4 + ¬x3x4 − x2x3¬x4 − ¬x3x4x5 = 0

Como, para essas restrições, x0 = 0 e x5 = 1, temos:

x1¬x2 + ¬x1x2 − ¬x1x2x3 = 0

x2¬x3 + ¬x2x3 − x1x2¬x3 − ¬x2x3x4 = 0

x3¬x4 + ¬x3x4 − x2x3¬x4 − ¬x3x4 = 0

5

• janela de manutenção:

x1¬x2 + ¬x1x2 − ¬x0¬x1x2 − x1¬x2¬x3 = 0

x2¬x3 + ¬x2x3 − ¬x1¬x2x3 − x2¬x3¬x4 = 0

x3¬x4 + ¬x3x4 − ¬x2¬x3x4 − x3¬x4¬x5 = 0

Como, para essas restrições, ¬x0 = 1 e ¬x5 = 1, temos:

x1¬x2 + ¬x1x2 − ¬x1x2 − x1¬x2¬x3 = 0

x2¬x3 + ¬x2x3 − ¬x1¬x2x3 − x2¬x3¬x4 = 0

x3¬x4 + ¬x3x4 − ¬x2¬x3x4 − x3¬x4 = 0

x1 x2 x3 x4 x1¬x2 ¬x1x2 ¬x1x2x3 x1¬x2 + ¬x1x2 − ¬x1x2x3

0 0 0 0 0 0 0 0

0 0 0 1 0 0 0 0

0 0 1 0 0 0 0 0

0 0 1 1 0 0 0 0

0 1 0 0 0 1 0 1

0 1 0 1 0 1 0 1

0 1 1 0 0 1 1 0

0 1 1 1 0 1 1 0

1 0 0 0 1 0 0 1

1 0 0 1 1 0 0 1

1 0 1 0 1 0 0 1

1 0 1 1 1 0 0 1

1 1 0 0 0 0 0 0

1 1 0 1 0 0 0 0

1 1 1 0 0 0 0 0

1 1 1 1 0 0 0 0

Descartamos as linhas que correspondem às valorações que não satisfazem a restrição.

6

x1 x2 x3 x4 x2¬x3 ¬x2x3 x1x2¬x3 ¬x2x3x4 x2¬x3 + ¬x2x3 − x1x2¬x3 − ¬x2x3x4

0 0 0 0 0 0 0 0 0

0 0 0 1 0 0 0 0 0

0 0 1 0 0 1 0 0 1

0 0 1 1 0 1 0 1 0

0 1 1 0 0 0 0 0 0

0 1 1 1 0 0 0 0 0

1 1 0 0 1 0 1 0 0

1 1 0 1 1 0 1 0 0

1 1 1 0 0 0 0 0 0

1 1 1 1 0 0 0 0 0

x1 x2 x3 x4 x3¬x4 ¬x3x4 x2x3¬x4 ¬x3x4 x3¬x4 + ¬x3x4 − x2x3¬x4 − ¬x3x4

0 0 0 0 0 0 0 0 0

0 0 0 1 0 1 0 1 0

0 0 1 1 0 0 0 0 0

0 1 1 0 1 0 1 0 0

0 1 1 1 0 0 0 0 0

1 1 0 0 0 0 0 0 0

1 1 0 1 0 1 0 1 0

1 1 1 0 1 0 1 0 0

1 1 1 1 0 0 0 0 0

x1 x2 x3 x4 x1¬x2 ¬x1x2 ¬x1x2 x1¬x2¬x3 x1¬x2 + ¬x1x2 − ¬x1x2 − x1¬x2¬x3

0 0 0 0 0 0 0 0 0

0 0 0 1 0 0 0 0 0

0 0 1 1 0 0 0 0 0

0 1 1 0 0 1 1 0 0

0 1 1 1 0 1 1 0 0

1 1 0 0 0 0 0 0 0

1 1 0 1 0 0 0 0 0

1 1 1 0 0 0 0 0 0

1 1 1 1 0 0 0 0 0

7

x1 x2 x3 x4 x2¬x3 ¬x2x3 ¬x1¬x2x3 x2¬x3¬x4 x2¬x3 + ¬x2x3 − ¬x1¬x2x3 − x2¬x3¬x4

0 0 0 0 0 0 0 0 0

0 0 0 1 0 0 0 0 0

0 0 1 1 0 1 1 0 0

0 1 1 0 0 0 0 0 0

0 1 1 1 0 0 0 0 0

1 1 0 0 1 0 0 1 0

1 1 0 1 1 0 0 0 1

1 1 1 0 0 0 0 0 0

1 1 1 1 0 0 0 0 0

x1 x2 x3 x4 x3¬x4 ¬x3x4 ¬x2¬x3x4 x3¬x4 x3¬x4 + ¬x3x4 − ¬x2¬x3x4 − x3¬x4

0 0 0 0 0 0 0 0 0

0 0 0 1 0 1 1 0 0

0 0 1 1 0 0 0 0 0

0 1 1 0 1 0 0 1 0

0 1 1 1 0 0 0 0 0

1 1 0 0 0 0 0 0 0

1 1 1 0 1 0 0 1 0

1 1 1 1 0 0 0 0 0

Dessa forma, dadas todas as valorações possíveis, apenas as linhas destacadas serão

válidas:

x1 x2 x3 x4

0 0 0 0

0 0 0 1

0 0 1 0

0 0 1 1

0 1 0 0

0 1 0 1

0 1 1 0

0 1 1 1

1 0 0 0

1 0 0 1

1 0 1 0

1 0 1 1

1 1 0 0

1 1 0 1

1 1 1 0

1 1 1 1

8

4.2 Janelas de tamanho 3

Analogamente, basta redenirmos as variáveis y e z para que contemplem três perídos:

yj,t =

0 se t ≤ 0

xj,txj,t+1xj,t+2 se 0 < t < T − 1xj,txj,t+1 se t = T − 1

xj,t se t = T1 se t > T

Ou, equivalentemente,

yj,t = xj,txj,t+1xj,t+2

onde ∀u ≤ 0, xj,u = 0 e ∀v > T, xj,v = 1.

zj,t =

1 se t < −1¬xj,t+2 se t = −1

¬xj,t+1¬xj,t+2 se t = 0¬xj,t¬xj,t+1¬xj,t+2 se 0 < t < T − 1

¬xj,t¬xj,t+1 se t = T − 1¬xj,t se t = T

1 se t > T

Ou, equivalentemente,

zj,t = ¬xj,t¬xj,t+1¬xj,t+2

onde ∀u ≤ 0, xj,u = 0 e ∀v > T, xj,v = 0.

Assim como na janela de tamanho dois, adicionamos dois tipos de restrições, repre-

sentando que se uma janela não foi acionada, então nenhuma termo daquele período

pode ser acionada, exceto se essa termo pertence às janelas vizinhas (nesse caso duas

termos serão pertencentes) ou às janelas vizinhas das vizinhas (apenas uma termo será

pertencente). No entanto, como pode haver sobreposição de períodos (o que não ocorre

para janelas de tamanho 2), obtemos uma inequação.


¬yj,t(xj,t + xj,t+1 + xj,t+2 − 2yj,t−1 − yj,t−2 − 2yj,t+1 − yj,t+2) ≤ 0


¬zj,t(¬xj,t + ¬xj,t+1 + ¬xj,t+2 − 2zj,t−1 − zj,t−2 − 2zj,t+1 − zj,t+2) ≤ 0

Isto é

9


¬xj,txj,t+1 + ¬xj,txj,t+2 − 2¬xj,txj,t+1xj,t+2xj,t+3 − ¬xj,txj,t+2xj,t+3xj,t+4

+ xj,t¬xj,t+1 + ¬xj,t+1xj,t+2 − xj,t−2xj,t−1xj,t¬xj,t+1 − ¬xj,t+1xj,t+2xj,t+3xj,t+4

+xj,t¬xj,t+2 +xj,t+1¬xj,t+2−2xj,t−1xj,txj,t+1¬xj,t+2−xj,t−2xj,t−1xj,t¬xj,t+2 ≤ 0


xj,t¬xj,t+1 + xj,t¬xj,t+2 − 2xj,t¬xj,t+1¬xj,t+2¬xj,t+3 − xj,t¬xj,t+2¬xj,t+3¬xj,t+4

+¬xj,txj,t+1+xj,t+1¬xj,t+2−¬xj,t−2¬xj,t−1¬xj,txj,t+1−xj,t+1¬xj,t+2¬xj,t+3¬xj,t+4

+¬xj,txj,t+2+¬xj,t+1xj,t+2−2¬xj,t−1¬xj,t¬xj,t+1xj,t+2−¬xj,t−2¬xj,t−1¬xj,txj,t+2 ≤ 0

Para todo 0 < t < T .

4.2.1 Exemplo

Para apenas uma termelétrica, num intervalo de 8 períodos e janelas de acionamento e

de manutenção de tamanho 3, dentre todas as valoração possíveis, apenas as destacadas

são válidas segundo as restrições denidas.

10

x1 x2 x3 x4 x5 x6 x7 x8

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 1

0 0 0 0 0 0 1 0

0 0 0 0 0 0 1 1

0 0 0 0 0 1 0 0

0 0 0 0 0 1 0 1

0 0 0 0 0 1 1 0

0 0 0 0 0 1 1 1

0 0 0 0 1 0 0 0

0 0 0 0 1 0 0 1

0 0 0 0 1 0 1 0

0 0 0 0 1 0 1 1

0 0 0 0 1 1 0 0

0 0 0 0 1 1 0 1

0 0 0 0 1 1 1 0

0 0 0 0 1 1 1 1

0 0 0 1 0 0 0 0

0 0 0 1 0 0 0 1

0 0 0 1 0 0 1 0

0 0 0 1 0 0 1 1

0 0 0 1 0 1 0 0

0 0 0 1 0 1 0 1

0 0 0 1 0 1 1 0

0 0 0 1 0 1 1 1

0 0 0 1 1 0 0 0

0 0 0 1 1 0 0 1

0 0 0 1 1 0 1 0

0 0 0 1 1 0 1 1

0 0 0 1 1 1 0 0

0 0 0 1 1 1 0 1

0 0 0 1 1 1 1 0

0 0 0 1 1 1 1 1

11

x1 x2 x3 x4 x5 x6 x7 x8

0 0 1 0 0 0 0 0

0 0 1 0 0 0 0 1

0 0 1 0 0 0 1 0

0 0 1 0 0 0 1 1

0 0 1 0 0 1 0 0

0 0 1 0 0 1 0 1

0 0 1 0 0 1 1 0

0 0 1 0 0 1 1 1

0 0 1 0 1 0 0 0

0 0 1 0 1 0 0 1

0 0 1 0 1 0 1 0

0 0 1 0 1 0 1 1

0 0 1 0 1 1 0 0

0 0 1 0 1 1 0 1

0 0 1 0 1 1 1 0

0 0 1 0 1 1 1 1

0 0 1 1 0 0 0 0

0 0 1 1 0 0 0 1

0 0 1 1 0 0 1 0

0 0 1 1 0 0 1 1

0 0 1 1 0 1 0 0

0 0 1 1 0 1 0 1

0 0 1 1 0 1 1 0

0 0 1 1 0 1 1 1

0 0 1 1 1 0 0 0

0 0 1 1 1 0 0 1

0 0 1 1 1 0 1 0

0 0 1 1 1 0 1 1

0 0 1 1 1 1 0 0

0 0 1 1 1 1 0 1

0 0 1 1 1 1 1 0

0 0 1 1 1 1 1 1

12

x1 x2 x3 x4 x5 x6 x7 x8

0 1 0 0 0 0 0 0

0 1 0 0 0 0 0 1

0 1 0 0 0 0 1 0

0 1 0 0 0 0 1 1

0 1 0 0 0 1 0 0

0 1 0 0 0 1 0 1

0 1 0 0 0 1 1 0

0 1 0 0 0 1 1 1

0 1 0 0 1 0 0 0

0 1 0 0 1 0 0 1

0 1 0 0 1 0 1 0

0 1 0 0 1 0 1 1

0 1 0 0 1 1 0 0

0 1 0 0 1 1 0 1

0 1 0 0 1 1 1 0

0 1 0 0 1 1 1 1

0 1 0 1 0 0 0 0

0 1 0 1 0 0 0 1

0 1 0 1 0 0 1 0

0 1 0 1 0 0 1 1

0 1 0 1 0 1 0 0

0 1 0 1 0 1 0 1

0 1 0 1 0 1 1 0

0 1 0 1 0 1 1 1

0 1 0 1 1 0 0 0

0 1 0 1 1 0 0 1

0 1 0 1 1 0 1 0

0 1 0 1 1 0 1 1

0 1 0 1 1 1 0 0

0 1 0 1 1 1 0 1

0 1 0 1 1 1 1 0

0 1 0 1 1 1 1 1

13

x1 x2 x3 x4 x5 x6 x7 x8

0 1 1 0 0 0 0 0

0 1 1 0 0 0 0 1

0 1 1 0 0 0 1 0

0 1 1 0 0 0 1 1

0 1 1 0 0 1 0 0

0 1 1 0 0 1 0 1

0 1 1 0 0 1 1 0

0 1 1 0 0 1 1 1

0 1 1 0 1 0 0 0

0 1 1 0 1 0 0 1

0 1 1 0 1 0 1 0

0 1 1 0 1 0 1 1

0 1 1 0 1 1 0 0

0 1 1 0 1 1 0 1

0 1 1 0 1 1 1 0

0 1 1 0 1 1 1 1

0 1 1 1 0 0 0 0

0 1 1 1 0 0 0 1

0 1 1 1 0 0 1 0

0 1 1 1 0 0 1 1

0 1 1 1 0 1 0 0

0 1 1 1 0 1 0 1

0 1 1 1 0 1 1 0

0 1 1 1 0 1 1 1

0 1 1 1 1 0 0 0

0 1 1 1 1 0 0 1

0 1 1 1 1 0 1 0

0 1 1 1 1 0 1 1

0 1 1 1 1 1 0 0

0 1 1 1 1 1 0 1

0 1 1 1 1 1 1 0

0 1 1 1 1 1 1 1

14

x1 x2 x3 x4 x5 x6 x7 x8

1 0 0 0 0 0 0 0

1 0 0 0 0 0 0 1

1 0 0 0 0 0 1 0

1 0 0 0 0 0 1 1

1 0 0 0 0 1 0 0

1 0 0 0 0 1 0 1

1 0 0 0 0 1 1 0

1 0 0 0 0 1 1 1

1 0 0 0 1 0 0 0

1 0 0 0 1 0 0 1

1 0 0 0 1 0 1 0

1 0 0 0 1 0 1 1

1 0 0 0 1 1 0 0

1 0 0 0 1 1 0 1

1 0 0 0 1 1 1 0

1 0 0 0 1 1 1 1

1 0 0 1 0 0 0 0

1 0 0 1 0 0 0 1

1 0 0 1 0 0 1 0

1 0 0 1 0 0 1 1

1 0 0 1 0 1 0 0

1 0 0 1 0 1 0 1

1 0 0 1 0 1 1 0

1 0 0 1 0 1 1 1

1 0 0 1 1 0 0 0

1 0 0 1 1 0 0 1

1 0 0 1 1 0 1 0

1 0 0 1 1 0 1 1

1 0 0 1 1 1 0 0

1 0 0 1 1 1 0 1

1 0 0 1 1 1 1 0

1 0 0 1 1 1 1 1

15

x1 x2 x3 x4 x5 x6 x7 x8

1 0 1 0 0 0 0 0

1 0 1 0 0 0 0 1

1 0 1 0 0 0 1 0

1 0 1 0 0 0 1 1

1 0 1 0 0 1 0 0

1 0 1 0 0 1 0 1

1 0 1 0 0 1 1 0

1 0 1 0 0 1 1 1

1 0 1 0 1 0 0 0

1 0 1 0 1 0 0 1

1 0 1 0 1 0 1 0

1 0 1 0 1 0 1 1

1 0 1 0 1 1 0 0

1 0 1 0 1 1 0 1

1 0 1 0 1 1 1 0

1 0 1 0 1 1 1 1

1 0 1 1 0 0 0 0

1 0 1 1 0 0 0 1

1 0 1 1 0 0 1 0

1 0 1 1 0 0 1 1

1 0 1 1 0 1 0 0

1 0 1 1 0 1 0 1

1 0 1 1 0 1 1 0

1 0 1 1 0 1 1 1

1 0 1 1 1 0 0 0

1 0 1 1 1 0 0 1

1 0 1 1 1 0 1 0

1 0 1 1 1 0 1 1

1 0 1 1 1 1 0 0

1 0 1 1 1 1 0 1

1 0 1 1 1 1 1 0

1 0 1 1 1 1 1 1

16

x1 x2 x3 x4 x5 x6 x7 x8

1 1 0 0 0 0 0 0

1 1 0 0 0 0 0 1

1 1 0 0 0 0 1 0

1 1 0 0 0 0 1 1

1 1 0 0 0 1 0 0

1 1 0 0 0 1 0 1

1 1 0 0 0 1 1 0

1 1 0 0 0 1 1 1

1 1 0 0 1 0 0 0

1 1 0 0 1 0 0 1

1 1 0 0 1 0 1 0

1 1 0 0 1 0 1 1

1 1 0 0 1 1 0 0

1 1 0 0 1 1 0 1

1 1 0 0 1 1 1 0

1 1 0 0 1 1 1 1

1 1 0 1 0 0 0 0

1 1 0 1 0 0 0 1

1 1 0 1 0 0 1 0

1 1 0 1 0 0 1 1

1 1 0 1 0 1 0 0

1 1 0 1 0 1 0 1

1 1 0 1 0 1 1 0

1 1 0 1 0 1 1 1

1 1 0 1 1 0 0 0

1 1 0 1 1 0 0 1

1 1 0 1 1 0 1 0

1 1 0 1 1 0 1 1

1 1 0 1 1 1 0 0

1 1 0 1 1 1 0 1

1 1 0 1 1 1 1 0

1 1 0 1 1 1 1 1

17

x1 x2 x3 x4 x5 x6 x7 x8

1 1 1 0 0 0 0 0

1 1 1 0 0 0 0 1

1 1 1 0 0 0 1 0

1 1 1 0 0 0 1 1

1 1 1 0 0 1 0 0

1 1 1 0 0 1 0 1

1 1 1 0 0 1 1 0

1 1 1 0 0 1 1 1

1 1 1 0 1 0 0 0

1 1 1 0 1 0 0 1

1 1 1 0 1 0 1 0

1 1 1 0 1 0 1 1

1 1 1 0 1 1 0 0

1 1 1 0 1 1 0 1

1 1 1 0 1 1 1 0

1 1 1 0 1 1 1 1

1 1 1 1 0 0 0 0

1 1 1 1 0 0 0 1

1 1 1 1 0 0 1 0

1 1 1 1 0 0 1 1

1 1 1 1 0 1 0 0

1 1 1 1 0 1 0 1

1 1 1 1 0 1 1 0

1 1 1 1 0 1 1 1

1 1 1 1 1 0 0 0

1 1 1 1 1 0 0 1

1 1 1 1 1 0 1 0

1 1 1 1 1 0 1 1

1 1 1 1 1 1 0 0

1 1 1 1 1 1 0 1

1 1 1 1 1 1 1 0

1 1 1 1 1 1 1 1

5 Modelagem Proposta

Denidas essas propriedades, geramos um modelo pseudo-booleano baseado na mode-

lagem matemática capaz de representar o problema de maneira similar, num contexto

booleano, utilizando-se de todo o maquinário para resoluções de problemas de satisfati-

bilidade de funções booleanas. Devido à discretização das variáveis, transformamos as

restrições de igualdade em inequações, obtendo o erro mínimo de aproximação na otimi-

zação pela função objetivo, que tenta maximizar os recursos disponíveis para minimizar

18

o custo de geração elétrica.

1. Modelo com prolinômios aproximados por uma função linear:

minT∑t=1

(J∑

j=1

[ctj,0 + ctj,1.S(GTj,t) + ctj,2.S(GTj,t)2]+

S∑s=1

[cds,0 + cds,1.S(DEFs,t) + cds,2.S(DEFs,t)2])

Sujeito a:

S(Vi,t)−S(Vi,t−1)−∑l∈Ji

(S(QCl,t) + S(QV Tl,t))+S(QCi,t)+S(QV Ti,t) ≤ Yi,t+∆i,t

S(DEFs,t) +∑j∈Ts

[S(GTj,t)] +∑n∈Ωs

[S(INT(n,s),t)− S(INT(s,n),t)]+∑i∈Rs

[ki.S(QCi,t).(aΦi

2.(S(Vi,t−1) + S(Vi,t)) + bΦi−

aΘi .(S(QCi,t) + S(QV Ti,t))− bΘi − pci,t)] ≤ Ds,t

S(QCr,t) + S(QV Tr,t) ≥ QMINr,t

S′(Vr,t) = 1

S′(QCr,t) = 1

S′(QV Tr,t) = 1

S′(GTj,t) = 1

S′(DEFs,t) = 1

S′(INT(n,s),t) = 1

19







2. Modelo completo:

minT∑t=1

(J∑

j=1

[ctj,0 + ctj,1.S(GTj,t) + ctj,2.S(GTj,t)2]+

S∑s=1

[cds,0 + cds,1.S(DEFs,t) + cds,2.S(DEFs,t)2])

Sujeito a:

S(Vi,t)−S(Vi,t−1)−∑l∈Ji

(S(QCl,t) + S(QV Tl,t))+S(QCi,t)+S(QV Ti,t) ≤ Yi,t+∆i,t

20

S(DEFs,t) +∑j∈Ts

[S(GTj,t)] +∑n∈Ωs

[S(INT(n,s),t)− S(INT(s,n),t)]+∑i∈Rs

[ki.S(QCi,t).(cΦi,0 +cΦi,1

2.S(Vi,t) +

cΦi,1

2.S(Vi,t−1)+

cΦi,2

4.S(Vi,t)

2 +cΦi,2

2.S(Vi,t−1).S(Vi,t) +

cΦi,2

4.S(Vi,t−1)2+

cΦi,3

8.S(Vi,t)

3+3cΦi,3

8.S(Vi,t−1).S(Vi,t)

2+3cΦi,3

8.S(Vi,t−1)2.S(Vi,t)+

cΦi,3

8.S(Vi,t−1)3+

cΦi,4

16.S(Vi,t)

4 +cΦi,4

4.S(Vi,t−1).S(Vi,t)

3+

3cΦi,4

8.S(Vi,t−1)2.S(Vi,t)

2 +cΦi,4

4.S(Vi,t−1)3.S(Vi,t) +

cΦi,4

16.S(Vi,t−1)4−

cΘi,0 − cΘi,1.S(QCi,t)− cΘi,1.S(QV Ti,t)−cΘi,2.S(QCi,t)

2 − 2.cΘi,2.S(QCi,t).S(QV Ti,t)− cΘi,2.S(QV Ti,t)2−

cΘi,3.S(QCi,t)3−3.cΘi,3.S(QCi,t)

2.S(QV Ti,t)−3.cΘi,3.S(QCi,t).S(QV Ti,t)2−cΘi,3.S(QV Ti,t)

3−cΘi,4.S(QCi,t)

4 − 4.cΘi,4.S(QCi,t)3.S(QV Ti,t)− 6.cΘi,4.S(QCi,t)

2.S(QV Ti,t)2−

4.cΘi,4.S(QCi,t).S(QV Ti,t)3 − cΘi,4.S(QV Ti,t)

4 − pci,t)] ≤ Ds,t

S(QCr,t) + S(QV Tr,t) ≥ QMINr,t

S′(Vr,t) = 1

S′(QCr,t) = 1

S′(QV Tr,t) = 1

S′(GTj,t) = 1

S′(DEFs,t) = 1

S′(INT(n,s),t) = 1

21







onde, para toda variável X,

S(X) =∑

xi∈D(X)

xi.bi

S′(X) =∑

xi∈D(X)

bi

e para todo xj,t,xj,t = ¬bGTj,t,0

Esse modelo representa as variáveis originais V , QC, QV T , GT , DEF e INT e

possui N variáveis binárias e M restrições pseudo-booleanas, tais que

N =

T∑t=1

[

R∑r=1

(|D(Vr,t)|+ |D(QCr,t)|+ |D(QV Tr,t)|)+

J∑j=1

|D(GTj,t)|+S∑

s=1

|D(DEFs,t)|+S∑

n=1

S∑s=1

|D(INT(n,s),t)|]

M = T (5R + 3J + 2S + S2)

onde T , J , R e S são, respectivamente, o número de períodos, termelétricas, hidrelé-

tricas e subsistemas do sistema completo.

22

Documents

Pseudo-Boolean Optimization20PHOENIX/Relat%F3rios%20T%E9... · de limites das ariávveis, ... Como o número de termos de uma restrição pseudo-booleana é dependente do ... amosV