1

PARTIÇÃOPARTIÇÃO DEDE

BENDERSBENDERS

Secundino Soares FilhoUnicamp

2

INTRODUÇÃOINTRODUÇÃO

Método para otimização de problemas mistos e de grande dimensão

Minimizar yfcx Yyx ,0

s.a. byFAx

x variáveis reais

y variáveis “cri-cri” (zero – um, inteira, etc)

1

3

Idéia

Particionar (decompor)

(1)(1)em dois problemas independentes

x y

INTRODUÇÃOINTRODUÇÃO

4

Hipótese: (1) tem solução ótima finita

PROJEÇÂO: Vamos projetar (1) sobre as variáveis Y

MIN

0

..

x

byFAxascxmínimoyf 2

Yy

O mínimo é dado pelo PL:(MIN)

0

..

x

yFbAxascx

3PRIMAL

5

Note que para algum é possível que (3) seja infactívelYy

Vamos procurar uma condição em que (3) seja sempre factível

Vamos tomar o dual de (3). Seja a variável dualu

(MAX)

0

..

u

cuAas

yFbu 4SUBPROBLEMA

6

Devido a hipótese (1), esta forma dual do subproblema é sempre factível, como garante a teoria da Dualidade em Programação Linear:

O primal (dual) é factível se o seu dual (primal) tem solução ótima finitaO primal (dual) é factível se o seu dual (primal) tem solução ótima finita

dual (MAX) primal (MIN)

ótimo

7

Sejam os pontos extremos e

os raios extremos de

puuu ,,, 21 0, ucuA qppp uuu ,,, 21

Então, como RESULTADO da teoria de dualidade, o primal (3) é factívelse o dual (4) tem solução ótima finita, ou seja, se

qppjyFbu j ,,1,0 5

A condição (5) assegura que o dual (4) é sempre finitoo primal (3) é sempre factível

8

EXEMPLOEXEMPLO

1ru2ru

2yFb

1u

2u

1yFb

0

u

cuA

1ru

2ru

9

qppjyFbu j ,,1,0

Pelo TEOREMA FUNDAMENTAL DA DUALIDADE (1), o dual (4) e oprimal (3) têm solução ótimas iguais

Então

MIN

0

..

x

byFAxascxmínimoyf 2

Yy

A restrição

garante solução ótima finita para o dual (4).

10

MIN

yFbuMAXyf j

pj1

6Yy

Sujeito a:

qppjyFbu j ,,1,0

é equivalente a

11

O problema (6) é equivalente a

MIN yf

7;Yy

Sujeito a:

pjyFbu j ,,1,

qppjyFbu j ,,1,0

Pois o MÁXIMO é o menor limite superior. Note que (7) é equivalente a (1)

12

RESOLUÇÃO DE (7)RESOLUÇÃO DE (7)

(7) tem um grande número de restrições que não são conhecidas a priori

IDÉIA: Usar RELAXAÇÃO. Ou seja, construir um problemamestre relaxado com somente algumas restrições, eaplicar a estratégia da RELAXAÇÃO.

PROBLEMA MESTRE RELAXADO

MIN yf

8;Yy

s.a.

pJjyFbu Pj ,,1,

qppJjyFbu Rj ,,1,0

13

Seja uma solução ótima de (8). Dois casos são possíveis: KKy ,

1) Se satisfaz todas as restrições de (7), então

é solução ótima de (7), e portanto

KKy , KKy ,

** xeyy K solução de

(MIN)

0

.. *

x

yFbAxas

cx

são a solução ótima de (1).

14

2) Se viola alguma restrição de (7), então a solução

não é ótima.

KKy ,

Violação:

extremoraiouyFbu

extremopontouyFbu

jKj

jKKj

ou

,0

,

15

A restrição mais violada é aquela que

qpj

yFbu Kj

1 9

(MAX)

(9) é equivalente a (4)

(MAX)

0

..

u

cuAas

KyFbu 4SUBPROBLEMA

16

Seja uma solução ótima finita do subproblema (4). Então, a

restrição mais violada a ser acrescentada ao programa mestre é:

yFbu K*

Ku*

Caso (4) seja ilimitado, a restrição mais violada é do tipo raio extremo

0ˆ yFbuK

Com sendo um raio extremo de (4).Ku

17

CONCLUSÃO: O sub-problema serve para testar a

factibilidade/otimalidade de uma proposta

do problema mestre. KKy ,

18

ESQUEMA DA DECOMPOSIÇÃOESQUEMA DA DECOMPOSIÇÃO

PROBLEMA

NA VARIÁVEL yPROBLEMA

MESTRE

SUB-PROBLEMAPROBLEMA

NA VARIÁVEL u

Ky* KK uouu ˆ*

Testa as propostasdo mestre

Gera propostas de y

19

ESQUEMA DA DECOMPOSIÇÃOESQUEMA DA DECOMPOSIÇÃO

ALGORITMO

• Note que a resolução de um problema mestre relaxado (8) fornece

um valor ótimo que é um limitante inferior (LI) do

problema original (1). Por quê? (Note que a seqüência

é monótona não decrescente).

** yf RR yf **

• Note que o valor ótimo fornecido pela resolução de um subproblema

(4) para um fixo e adicionado do valor fornece um

limitante superior (LS) do problema original (1) (se for melhor que a

“incumbente” – melhor solução até o momento)

y yf

20

INÍCIOLS = LI = -

SELECIONE UM VALORINICIAL PARA y

GERE UMA NOVA RESTRIÇÃO PARA O PROBLEMA MESTRE:

— DE PONTO EXTREMO— DE RAIO EXTREMO

RESOLVA O SUBPROBLEMA (4) PARA OBTERMELHOROU LS? SE SIM, CORRIJA O VALOR DE LS

*u

RESOLVA UM PROBLEMAMESTRE PARA OBTER

NOVO LI

*y

LS=LI RESOLVA O SUBPROBLEMA

PARA E OBTENHA*y *x

FIMSIMNÃO

21

BIBLIOGRAFIABIBLIOGRAFIA

[1] Benders, J. F., “Partitionning Procedures for Solving Mixed-Variables Programming Problems”, Numerische Mathematik, 4, 238-252, 1962.

[2] Salkin, H. N., “Integer Programming”, Addison Wesley Publ. Co., 1975.

[3] Hu, T. C., “Integer Programming and Network Flows”, Addison Wesley Publ. Co., 1969.

[4] Geoffrion, A. M., “Generalized Benders Decomposition”, Journal of Optimization Theory and Application, 10, 237-260, 1972.

22

ED-15ED-15

Resolver o problema abaixo aplicando o método de Benders

Minimizar yxxw 232 21 s.a.

821 yxx0221 yxx0, 21 xx

5,4,3,2,1,0Sy

Solução:

Projetando P1 sobre a variável , temos:y

(P1)

23

ED-15ED-15

Minimizar 21 322 xxMinimizaryw s.a. yxx 821

yxx 221 0, 21 xx

Sy

Temos o seguinte sub-problema primal

Minimizar 21 32 xxz s.a.

yxx 821

yxx 221 0, 21 xx

(SPP)

(P2)

24

ED-15ED-15

O dual (SPP) é:Maximizar yyz 28 21

s.a.221 321 0, 21

(SPP)

1

22

1

4

3

1

2

3

1 2 3

)00(1 )30(2 )2125(3 )02(4

O politopo das restrições do dualé limitado e, portanto, não possuiraio extremo.

4 pontos extremos

25

ED-15ED-15

O problema P2 pode ser reescrito como:

Minimizar 21 282 yyMaxyw s.a.

221 321 0, 21

(P3)

Escrevendo o sub-problema em função dos pontos extremos do politopodo dual, temos:

21 282 yyzMaxywMin Sy

npp 1(P4)

np = número total de pontos extremos

26

ED-15ED-15

P4 é equivalente ao problema

Minimizar yT 2

s.a. pp yy 21 28,Sy

npp ,,2,1

Problema mestre

Supondo que não conhecemos os pontos extremos, vamos aplicara estratégia de relaxação:

Minimizar yT 2 s.a. pp yy 21 28,Sy

npJp p ,,2,1

27

ED-15ED-15

Inicialização:

LIeLS

Iteração 1:

Problema mestre 1: (irrestrito)

Minimizar yT 2 ,Sy

A solução é:

LIT

y

*

5*

28

ED-15ED-15

Sub-problema 1

Minimizar 21 32 xxz s.a.

321 xx1021 xx0, 21 xx

Resolvendo pelo método simplex:

)30(*

)100(*

30*

x

z

29

ED-15ED-15

Calculando o valor da função objetivo da solução:

LSLI

yx

LSLSw

yzyxxw

5ˆ),100(ˆ

20*

2010302232* ****2

*1

A restrição mais violada do problema mestre é:

yyy 63.20.8 (1)

Note que a solução viola (1) *,5* y

30

ED-15ED-15

Iteração 1:

Problema mestre 2:

Minimizar

,Sy

A solução é:

0

0

0*

0*

LI

LIT

y

yT 2

s.a. (1) y6

31

ED-15ED-15

Sub-problema 2

Minimizar 21 32 xxz s.a.

821 xx021 xx0, 21 xx

Resolvendo pelo método simplex:

)2125(*

)44(*

20*

x

z

32

ED-15ED-15

Calculando o valor da função objetivo da solução:

LSLI

LSw

yzw

*

20020*2**

A restrição mais violada do problema mestre é:

202

3

2

1.2

2

5.8 yyy (2)

Note novamente que a solução viola (2)0*,0* y

33

Iteração 3:

Problema mestre 3:

Minimizar

,Sy

A solução é:

12

12

18*

3*

LI

LIT

y

yT 2

s.a. (1) y6

ED-15ED-15

(2) 202

3y

34

ED-15ED-15

Sub-problema 3

Minimizar 21 32 xxz s.a.

521 xx621 xx0, 21 xx

Resolvendo pelo método simplex:

)30(*

)60(*

18*

x

z

35

Calculando o valor da função objetivo da solução:

FIMLSLI

y

x

LSLSw

yzw

3ˆ

)60(ˆ

12*

12618*2**

ED-15ED-15

A solução ótima é:

12

3

60

o

o

o

w

y

x