Aula 15: Desigualdades V£Œlidas - Otimiza£§££o Linear e Planos de Corte de Gomory Pergunta: No caso

  • View
    1

  • Download
    0

Embed Size (px)

Text of Aula 15: Desigualdades V£Œlidas - Otimiza£§££o Linear e Planos de...

  • Aula 15: Desigualdades Válidas Otimização Linear e Inteira

    Túlio A. M. Toffolo http://www.toffolo.com.br

    BCC464/PCC174 –2018/2 Departamento de Computação –UFOP

    http://www.toffolo.com.br

  • Previously...

    Branch-and-bound

    Exercícios

    Hoje:

    Branch-and-bound em Programação Inteira

    Desigualdades Válidas

    Cortes Combinatórios

    Exercícios

    2 / 23 Túlio Toffolo – Otimização Linear e Inteira – Aula 15: Desigualdades Válidas

  • Aula de Hoje

    1 Branch-and-Bound em Programação Inteira

    2 Desigualdades Válidas

    3 Cortes Combinatórios

    4 Exercícios

    3 / 23 Túlio Toffolo – Otimização Linear e Inteira – Aula 15: Desigualdades Válidas

  • Aula de Hoje

    1 Branch-and-Bound em Programação Inteira

    2 Desigualdades Válidas

    3 Cortes Combinatórios

    4 Exercícios

    3 / 23 Túlio Toffolo – Otimização Linear e Inteira – Aula 15: Desigualdades Válidas

  • Branch-and-bound: Problema da Mochila

    5 :X , -1/4,113=1

    10,75/9 5 :×z=1

    X. = 1 Xy =O

    5 : × , -1,113=45 5×3=1 , 114=1/2

    six'=' 1×4=1 10,6/10 10,5 / 9 si×3= '

    3=1 ×3=0 ×4=1 ×y=O

    X 5 :X } -45,114=1 § : xa.it/3,Xz=1

    inviavel yosinfueeiarjo 10,2/7si×a=110,33/9 si×3= '

    5:X , --X4=1 13=1 113=0

    ×2=1* poda ×2=O por limit

    inviavel 7 sinfueeirjo 9,4/4 g sdueaointeira

    5 :X4=1 5 :Xa=1 , .×s=

    5 :×z=1

    S :Xa=1

    item vi wi di 1 7 4 1,75 2 4 3 1,33 3 9 5 1,80 4 3 2 1,50

    4 / 23 Túlio Toffolo – Otimização Linear e Inteira – Aula 15: Desigualdades Válidas

  • Branch-and-Bound

    max. z = 5x1 + 4x2

    s.a. x1 + x2 ≤ 5 10x1 + 6x2 ≤ 45 x1, x2 ≥ 0

    1

    2

    3

    4

    5

    1 2 3 4 5

    x 2

    x 1

    x1 ≤ 3 OU x1 ≥ 4

    5 / 23 Túlio Toffolo – Otimização Linear e Inteira – Aula 15: Desigualdades Válidas

  • Branch-and-Bound

    max. z = 5x1 + 4x2

    s.a. x1 + x2 ≤ 5 10x1 + 6x2 ≤ 45 x1, x2 ≥ 0

    1

    2

    3

    4

    5

    1 2 3 4 5

    x 2

    x 1

    x1 ≤ 3 OU x1 ≥ 4

    5 / 23 Túlio Toffolo – Otimização Linear e Inteira – Aula 15: Desigualdades Válidas

  • Branch-and-Bound em Programação Inteira

    Notação utilizada:

    P0 : problema original L : lista de subproblemas: problemas criados a partir de P0 com limites

    inteiros para variáveis

    P̄ : relaxação linear de um problema P , ou seja o problema P sem as restrições de integralidade

    z∗ : custo da melhor solução inteira encontrada até o momento

    z̃ : limite dual (limite inferior no caso de minimização): obtido, por exemplo, pela resolução de P̄

    x̃ : vetor de solução da última resolução de P̄

    6 / 23 Túlio Toffolo – Otimização Linear e Inteira – Aula 15: Desigualdades Válidas

  • Inicialização: L← P0, z∗ ←∞

    Seleção de sub-problema: se L = ∅ então fim senão selecione um problema P ∈ L e faça L← L\{P}

    Relaxação linear: z̃ ← custo ótimo de P̄ se problema P̄ é inviável ou z̃ ≥ z∗ então

    vá para seleção de sub-problema

    Teste de integralidade: se solução ótima de P̄ não tem variáveis com valores fracionários então

    se z̃ < z∗ então z∗ ← z̃ vá para seleção de sub-problema

    Ramificação: xj ← uma variável inteira com valor fracionário na solução ótima de P̄ P ′ ← problema P com uma restrição adicional: xj ≤ bx̃jc P ′′ ← problema P com uma restrição adicional: xj ≥ dx̃je L← L ∪ {P ′, P ′′} vá para seleção de sub-problema

    7 / 23 Túlio Toffolo – Otimização Linear e Inteira – Aula 15: Desigualdades Válidas

  • Aula de Hoje

    1 Branch-and-Bound em Programação Inteira

    2 Desigualdades Válidas

    3 Cortes Combinatórios

    4 Exercícios

    8 / 23 Túlio Toffolo – Otimização Linear e Inteira – Aula 15: Desigualdades Válidas

  • A Formulação Ideal Maximize:

    6x1 + 5x2

    Sujeito a: 15x1 + 7x2 ≤ 49 2x1 + 4x2 ≤ 17 x1, x2 ∈ Z+

    Substituir por ... 2x1 + 2x2 ≤ 8

    6x1 + 3x2 ≤ 18 x1, x2 ∈ R+

    Formulação ideal

    envoltória convexa dos pontos inteiros válidos

    1

    2

    3

    4

    1 2 3 4

    9 / 23 Túlio Toffolo – Otimização Linear e Inteira – Aula 15: Desigualdades Válidas

  • A Formulação Ideal

    Maximize: 6x1 + 5x2

    Sujeito a: 2x1 + 2x2 ≤ 8 6x1 + 3x2 ≤ 18 x1, x2 ∈ R+

    Formulação ideal

    envoltória convexa dos pontos inteiros válidos

    1

    2

    3

    4

    1 2 3 4

    9 / 23 Túlio Toffolo – Otimização Linear e Inteira – Aula 15: Desigualdades Válidas

  • A Formulação Ideal

    Maximize: 6x1 + 5x2

    Sujeito a: 2x1 + 2x2 ≤ 8 6x1 + 3x2 ≤ 18 x1, x2 ∈ R+

    Formulação ideal

    envoltória convexa dos pontos inteiros válidos

    1

    2

    3

    4

    1 2 3 4

    9 / 23 Túlio Toffolo – Otimização Linear e Inteira – Aula 15: Desigualdades Válidas

  • Planos de Corte

    Maximize: 6x1 + 5x2

    Sujeito a: 15x1 + 7x2 ≤ 49 2x1 + 4x2 ≤ 17 x1, x2 ∈ Z+

    1

    2

    3

    4

    1 2 3 4

    Como colocar uma restrição adicional que invalide a solução fracionária corrente (sem cortar soluções inteiras válidas)?

    10 / 23 Túlio Toffolo – Otimização Linear e Inteira – Aula 15: Desigualdades Válidas

  • Exemplo de corte

    Considere a restrição: 2x1 + 4x2 ≤ 17 (satisfeita por x1 = 1, 7 e x2 = 3, 4).

    Vamos gerar outra restrição dividindo a primeira por 2: x1 + 2x2 ≤ 8, 5

    Note que do lado esquerdo temos apenas coeficientes inteiros e o valor das variáveis também deve ser inteiro. Portanto: x1 + 2x2 ≤ 8

    A restrição acima denomina-se Desigualdade Válida ou Corte. Note que um corte não invalida nenhuma solução inteira válida.

    11 / 23 Túlio Toffolo – Otimização Linear e Inteira – Aula 15: Desigualdades Válidas

  • Cortando

    1

    2

    3

    4

    1 2 3 4

    Solução Inicial: x1 = 1, 67 x2 = 3, 4 z = 27, 11

    Com o corte: x1 = 1, 8 x2 = 3, 1 z = 26, 4

    12 / 23 Túlio Toffolo – Otimização Linear e Inteira – Aula 15: Desigualdades Válidas

  • Cortando

    1

    2

    3

    4

    1 2 3 4

    Solução Inicial: x1 = 1, 67 x2 = 3, 4 z = 27, 11

    Com o corte: x1 = 1, 8 x2 = 3, 1 z = 26, 4

    12 / 23 Túlio Toffolo – Otimização Linear e Inteira – Aula 15: Desigualdades Válidas

  • Planos de Corte

    Inserção de Cortes

    Formulação resultante mais forte (mais próxima da formulação ideal).

    Limite dual possivelmente melhor: aproximando-se do ótimo do programa inteiro.

    Problema de Separação

    O problema de encontrar uma desigualdade válida não satisfeita pela solução fracionária é chamado de Problema de Separação.

    13 / 23 Túlio Toffolo – Otimização Linear e Inteira – Aula 15: Desigualdades Válidas

  • Planos de Corte de Gomory

    Pergunta:

    No caso de se obter uma solução fracionária, sempre pode-se encontrar um corte que a invalide?

    Gomory, R.E. Outline of an algorithm for integer solutions to linear programs. Bull. Amer. Math. Soc., 64(5), pp. 275-278, 1958.

    14 / 23 Túlio Toffolo – Otimização Linear e Inteira – Aula 15: Desigualdades Válidas

  • Aula de Hoje

    1 Branch-and-Bound em Programação Inteira

    2 Desigualdades Válidas

    3 Cortes Combinatórios

    4 Exercícios

    15 / 23 Túlio Toffolo – Otimização Linear e Inteira – Aula 15: Desigualdades Válidas

  • Cortes da Mochila

    Considere que variáveis binárias xj aparecem numa restrição do tipo:∑ j∈N

    ajxj ≤ b (aj ≥ 0 para todo j ∈ N)

    Um Conjunto C ⊆ N é uma Cobertura (Cover) se:∑ j∈C

    ajxj > b

    O que define o seguinte Corte de Cover :∑ j∈C

    xj ≤ |C| − 1

    16 / 23 Túlio Toffolo – Otimização Linear e Inteira – Aula 15: Desigualdades Válidas

  • Cortes de Cover

    Exemplo

    Considere a seguinte restrição sobre as variáveis binárias xj :

    11x1 + 6x2 + 6x3 + 5x4 + 5x5 + 4x6 + x7 ≤ 19

    Alguns cortes de cover:

    x1 + x2 + x3 ≤ 2 x1 + x2 + x6 ≤ 2 x1 + x5 + x6 ≤ 2

    x3 + x4 + x5 + x6 ≤ 3

    Os cortes acima são cortes de cover minimais, no sentido que qualquer variável retirada da restrição descaracteriza a cobertura.

    17 / 23 Túlio Toffolo – Otimização Linear e Inteira – Aula 15: Desigualdades Válidas

  • Cortes de Cover : separação

    Considere a solução fracionária x∗.

    Desigualdades violadas de Cover podem ser geradas resolvendo-se o problema DP:

    DP =

     σ(x∗) = min

    ∑ j∈N

    (1− x∗j )zj

    s.a. ∑ j∈N

    ajzj > b

    zj ∈ {0, 1} ∀j ∈ N

    Uma desigualdade válida violada de cover é descoberta quando