Slide - Branch-and-bound - 2023-2

4 Programacao Inteira » Referencias: =» Notas de aulas do Prof. Silvio Alexandre de Araujo http://www.dcce.ibilce.unesp.br/~saraujo/ Material da Professora Gladys Castillo do Departamento de Matematica da Universidade de Aveiro (http://www.mat.ua.pt/io/) Métodos de Solução: Branch-and-Bound • O método Branch-and-Bound (B&B) baseia-se na idéia de desenvolver uma enumeração inteligente das soluções candidatas à solução ótima inteira de um problema. • Apenas uma fração das soluções factíveis é realmente examinada. • O termo branch refere-se ao fato de que o método efetua partições no espaço das soluções e o termo bound ressalta que a prova da otimalidade da solução utiliza-se de limites calculados ao longo da enumeração. Métodos de Solução: Branch-and-Bound inteiros x x x x x x a s x x max 2 1 2 1 2 1 2 1 , 0 , 13 4 7 . . 11 21 ≥ ≤ + + Exemplo Métodos de Solução: Branch-and-Bound • O exemplo anterior é um problema de programação linear inteira, pois as variáveis devem ser inteiras. • Na Figura (a) têm-se os pontos que representam as soluções factíveis do problema (todos os pontos inteiros que satisfazem as restrições). • O problema de programação linear (PPL) obtido ao desconsiderarmos as restrições de integralidade das variáveis inteiras é conhecido como a relaxação linear do PPI (ver Figura (b)). • Existem outros tipos de relaxação, como por exemplo a Relaxação Lagrangiana: relaxa-se algumas restrições, consideradas complicadas, incorporando uma penalidade na função objetivo; Métodos de Solução: Branch-and-Bound (b) (a) Ótimo = 33 Ótimo = 39 PPI PPL x2 inteiros x x x x x x a s x x max 2 1 2 1 2 1 2 1 , 0 , 13 4 7 . . 11 21 ≥ ≤ + + (X1=1.897) (x2=3, x1=0) Métodos de Solução: Branch-and-Bound • Como podemos observar a solução do PPL é sempre maior ou igual a solução do PPI, pois o problema relaxado é composto por todas as soluções inteiras e também as soluções reais do problema, logo é formado por um conjunto de soluções factíveis mais abrangente. • Assim temos que, para um problema de maximização , ou seja, a solução ótima da relaxação linear de um problema inteiro ( ) é sempre maior ou igual a solução ótima do problema inteiro ( ). * PPI * PPL Z Z ≥≥≥≥ * ZPPL * ZPPI Métodos de Solução: Branch-and-Bound (b) (a) Ótimo = 33 Ótimo = 39 Métodos de Solução: Branch-and-Bound • Princípio básico: se a solução do PPL relaxado corresponde a uma solução do PPI, pois possui todas as variáveis inteiras, então esta solução é a solução ótima do PPI. Prova: É fácil provar tal princípio, pois sabemos que para um problema de máximo, logo, , ou seja, é maior ou igual a uma solução qualquer do PPI ( ). Suponha que seja inteira, logo temos que, , portanto o valor máximo para o PPI será exatamente igual a . * PPI * PPL Z Z ≥≥≥≥ PPI * PPL Z Z ≥≥≥≥ * PPL Z PPI Z * ZPPL PPI INT * PPL Z Z Z ≥≥≥≥ ==== * ZPPL Métodos de Solução: Branch-and-Bound • Idéia Geral: relaxar o problema de programação inteira e dividir o problema relaxado em vários problemas até encontrar soluções inteiras ou não factíveis, o ótimo é a melhor solução encontrada. O algoritmo B&B é baseado na idéia de “dividir para conquistar”, ou seja, trabalhamos em problemas menores e mais fáceis de resolver em busca da solução ótima. Métodos de Solução: Branch-and-Bound • A divisão do problema é interrompida quando uma das condições a seguir é satisfeita. Essas condições são chamadas de testes de sondagem ou Poda do nó (TS). (TS1 ou poda por infactibilidade) O problema relaxado é infactível. (TS2 ou poda por otimalidade) A solução ótima do problema relaxado é inteira . (TS3 ou poda por qualidade) O valor de qualquer solução factível do problema relaxado é pior que o valor da melhor solução factível atual (solução incumbente). • Quando uma dessas três condições ocorre, o subproblema pode ser descartado (sondado ou podado), pois todas as suas soluções factíveis estão implicitamente enumeradas. Exemplo: Branch-and-Bound inteiros x x x x x x a s x x max 2 1 2 1 2 1 2 1 , 0 , 13 4 7 . . 11 21 ≥ ≤ + + (b) (a) Ótimo = 33 Ótimo = 39 Exemplo: Branch-and-Bound • Resolvendo o problema relaxado tem-se que: • Valor ótimo da solução: 39 • Valores das variáveis x1=1.86 e x2=0 • Logo o valor de x1 não é inteiro, então dividimos o problema em dois subproblemas: • um onde consideramos o valor de x1 ≥ 2 , que vamos chamar de subproblema A • outro consideramos x1 ≤ 1, chamado de subproblema B. Z=39 x1=1.86 x2=0 Exemplo: Branch-and-Bound Ótimo = 37.5 Infactível A B Suproblema A Subproblema B 0 , 2 13 4 7 . . 11 21 2 1 1 2 1 2 1 ≥ ≥ ≤ + + x x x x x a s x x max 0 , 1 13 4 7 . . 11 21 2 1 1 2 1 2 1 ≥ ≤ ≤ + + x x x x x a s x x max Exemplo: Branch-and-Bound • Não encontramos solução factível ao resolver o problema A, então aplicando o o critério para poda podemos eliminá-lo ((TS 1) O problema relaxado é infactível). • Resolvendo o subproblema B temos Z = 37.5, x1 =1 e x2 =1.5 • Agora x2 não é inteiro, logo particionamos o problema em dois considerando o subproblema C com a variável x2 ≤ 1 e o subproblema D com x2 ≥ 2. Z=39 x1=1.86 x2=0 Z=37.5 x1=1 x2=1.5 x1≥2 x1≤1 TS1 A B Exemplo: Branch-and-Bound Suproblema C Subproblema D 0 , 1 1 13 4 7 . . 11 21 2 1 2 1 2 1 2 1 ≥ ≤ ≤ ≤ + + x x x x x x a s x x max 0 , 2 1 13 4 7 . . 11 21 2 1 2 1 2 1 2 1 ≥ ≥ ≤ ≤ + + x x x x x x a s x x max Ótimo = 37 Ótimo = 32 C D Exemplo: Branch-and-Bound Z=39 x1=1.86 x2=0 Z=37.5 x1=1 x2=1.5 x1≥2 x1≤1 TS1 Z=37 x1=0.71 x2=2 x2≥2 x2≤1 A D C B Z=32 x1=1 x2=1 TS2 (TS2 - otimalidade) A solução ótima do problema relaxado é inteira. Exemplo: Branch-and-Bound • A solução do subproblema C é igual a 32, x1=1 e x2=1, as duas variáveis são inteiras, logo considerando o teste de sondagem (TS2) este problema pode ser sondado por otimalidade. • Resolvendo o subproblema D temos Z = 37, x1=0.71 e x2=2 • note que a variável x1 novamente não é inteira, então particionamos o subproblema gerando dois novos subproblemas como mostramos a seguir Exemplo: Branch-and-Bound Suproblema E Subproblema F 0 , 0 2 1 13 4 7 . . 11 21 2 1 1 2 1 2 1 2 1 ≥ ≤ ≥ ≤ ≤ + + x x x x x x x a s x x max 0 , 1 2 1 13 4 7 . . 11 21 2 1 1 2 1 2 1 2 1 ≥ ≥ ≥ ≤ ≤ + + x x x x x x x a s x x max Infactível Ótimo = 35,75 F E Exemplo: Branch-and-Bound Z=39 x1=1.86 x2=0 Z=37.5 x1=1 x2=1.5 x1≥2 x1≤1 TS1 Z=37 x1=0.71 x2=2 x2≥2 x2≤1 A D C B Z=32 x1=1 x2=1 TS2 x1≥1 x1≤0 F E Z=35.75 x1=0 x2=3.25 TS1 Exemplo: Branch-and-Bound • O problema F é infactível, logo podemos usar TS1 e eliminá-lo • O subproblema E tem solução igual a 35.75 e x1=0 e x2=3.25 Suproblema G Subproblema H 0 , 3 0 2 1 13 4 7 . . 11 21 2 1 2 1 2 1 2 1 2 1 ≥ ≤ ≤ ≥ ≤ ≤ + + x x x x x x x x a s x x max 0 , 4 0 2 1 13 4 7 . . 11 21 2 1 2 1 2 1 2 1 2 1 ≥ ≥ ≤ ≥ ≤ ≤ + + x x x x x x x x a s x x max Exemplo: Branch-and-Bound Z=39 x1=1.86 x2=0 Z=37.5 x1=1 x2=1.5 x1≥2 x1≤1 TS1 Z=37 x1=0.71 x2=2 x2≥2 x2≤1 A D C B Z=32 x1=1 x2=1 TS2 x1≥1 x1≤0 F E Z=35.75 x1=0 x2=3.25 TS1 x2≥4 x2≤3 H G solução ótima Z=33 x1=0 x2=3 TS1 TS2 Exemplo: Branch-and-Bound • Resolvendo o subproblema G obtemos Z = 33, x1=0 e x2=3 , logo a solução é inteira, portanto aplicando o TS2 este problema pode ser sondado. • O subproblema H não tem solução factível e também pode ser sondado por TS1. • Temos que nenhum nó pode ser ramificado, logo, a melhor solução inteira encontrada é dada pelo problema G e é a solução ótima do problema. • Na resolução do Exemplo através do método B&B podemos observar que muitas soluções não precisaram ser avaliadas explicitamente. Isso fica mais claro quando se resolve problemas maiores. Selecao de nos na arvore Branch-and-Bound (livro a Pesquisa Operacional — pagina 249-251) = Considere uma lista de nos ativos de uma arvore. Como escolher o proximo no a ser examinado? Existem duas regras alternativas: » @ Regras a priori (determinam previamente a ordem de escolha dos nos) =“ @ Regras adaptativas (determinam o no a partir de informacao dos nos ativos). Selecao de nos na arvore Branch-and-Bound (livro 4 Pesquisa Operacional — pagina 249-251) =» A regra a priori mais utilizada: busca em profundidade com backtracking (last-in, first-out — 0 ultimo no incluido na lista é o primeiro a ser examinado). =» Na busca em profundidade, se 0 no corrente nao é eliminado, o proximo no a ser examinado é um de seus filhos. =» Backtracking - quando um no é eliminado, retorna-se ao longo do caminho em direcao ao no raiz até encontrar o primeiro no que tem filho a ser examinado. Selecao de nos na arvore Branch-and-Bound (livro 4 | Pesquisa Operacional — pagina 249-251) =» A busca em profundidade tem duas vantagens: = i. a experiéncia mostra que é mais provavel encontrar solucdes factiveis em niveis mais profundo em relacao a raiz =» 2. areotimizacao do no filho, dada a solucao otima do no pai, pode ser feita utilizando um algoritmo chamado dual simplex. O tamanho Maximo dos nos ativos nao é muito grande. =» Desvantagem: nao usa informacao, tende a gerar uma arvore com muitos nos. Selecao de nos na arvore Branch-and-Bound (livro a Pesquisa Operacional — pagina 249-251) =» Regra adaptativa: escolher o no que tem o maior limitante superior (maximizacao). =» Vantagem: produz uma arvore com um numero menor de nos (em relacao a busca em profundidade) porém guarda muitos nos ativos o que pode inviabilizar a solucao de um problema pelo limite de memoria computacional. Seleção de nós na árvore Branch-and-Bound –Problema da Mochila Seleção de nós na árvore Branch-and-Bound –Problema da Mochila EVOLUÇÃO DA BUSCA PELO MAIOR LIMITE SUPERIOR PARA O PROBLEMA DA MOCHILA ( Podas -> Q-Qualidade, O-Otimalidade e I – Infactibilidade). Solução ótima x1=x2=x3=1, x4=x5=0, x6=x7=x8=1, x9=x10=0, Valor z=763 Seleção de nós na árvore Branch-and-Bound –Problema da Mochila EVOLUÇÃO DA BUSCA EM PROFUNDIDADE PARA O PROBLEMA DA MOCHILA . 4 ' Exercicio . =» Encontre a _ solucao otima para o problema de programacao inteira abaixo. Especifique qual 0 motivo de cada poda dos nos. A primeira relaxacao linear deve ser resolvida utilizando o algoritmo simplex (algoritmo). O primeiro filho que sera acrescentado com xi<= devera ser resolvido pelo simplex tabelas. Mex Z=x, +2x, Sujeito a: 2x,+2x, <6 X,+2x, <5 Ax +2x, <8 X,20, X20 e inteiras.