Explicação de ramificação e limite

Eu tenho um teste sobre o algoritmo de ramificação e limite . Entendo teoricamente como esse algoritmo funciona, mas não consegui encontrar exemplos que ilustrem como esse algoritmo pode ser implementado praticamente.

Encontrei alguns exemplos como este, mas ainda estou confuso. Também procurei o problema do vendedor ambulante e não consegui entender.

O que eu preciso é de alguns problemas e como esses problemas podem ser resolvidos usando branch e bound.

Vamos aplicar o Branch and Bound ao Knapsack , espero que isso torne o conceito claro para você.

Temos itens, rotulados de a . é o valor do ésimo item e seu peso. Tentamos encaixá-los em uma mochila que pode conter até peso no total, e tentamos maximizar a soma dos valores do item que colocamos na mochila.1 n v i i w i$n$$1$$n$$v_i$$i$$w_i$$T$

A abordagem comum de retorno é a nossa base. Primeiro colocamos no pacote e depois resolvemos o problema para os itens restantes com recursão. Em seguida, removemos a do pacote e resolvemos o problema para os itens restantes novamente e retornamos a melhor configuração que encontramos. n - 1 v 1 n - $v_1$$n-1$$v_1$$n-1$

Esse retorno é a parte 'Ramificação' de Ramificação e limite. Você ramifica (no caso da mochila) dois casos: 'item faz parte da solução' e 'item não faz parte da solução'. Você pode visualizar isso como uma árvore binária, onde o filho esquerdo é um caso e o filho direito é o outro caso. Essa árvore é a árvore de pesquisa (ou espaço de pesquisa ): sua profundidade é e, portanto, possui nós. O algoritmo, portanto, tem um tempo de execução exponencial no número de itens.i n O ( 2 N$i$$i$$n$$O(2^n)$

Agora chegamos à parte 'Limite': tentamos encontrar critérios para que possamos dizer 'essa configuração nunca funciona, então é melhor não nos incomodarmos em computar isso'. Um exemplo desse critério é 'o peso dos itens que já colocamos na mochila excede ': se adicionamos, digamos, os primeiros itens à mochila e, portanto, ela já está cheia, não há não adianta tentar colocar os itens até na mochila também, mas também não adianta tentar ajustar qualquer subconjunto de até na mochila, pois ela já está cheia, então economizamos cerca de casos. Outro exemplo é 'n / 2 $T$$n/2$n n / 2 + 1 n 2 n /$n/2+1$$n$$n/2+1$$n$$2^{n/2}$mesmo se eu colocar todos os itens restantes, o valor dos itens que eu coloquei não excederá a melhor configuração que encontrei até agora '.

Esses critérios essencialmente cortam partes da árvore de pesquisa: em algum nó, você diz, por exemplo, 'a subárvore esquerda não me dará uma configuração melhor, porque X', então você esquece essa subárvore e não a explora. Uma subárvore de profundidade que você cortou dessa maneira economiza nós, que podem aumentar bastante a velocidade se você tiver sorte.O ( 2 d$d$$O(2^d)$

Observe que isso se chama ' Limite ' porque geralmente envolve algum tipo de limite inferior ou superior: para o critério ' mesmo que eu coloque todos os itens restantes, o valor dos itens que eu coloquei não excederá a melhor configuração Eu descobri até agora ', o valor da sua melhor configuração até agora é um limite inferior para a melhor configuração; portanto, qualquer coisa que nunca ultrapasse esse limite inferior está fadada ao fracasso.

Você pode tornar a parte 'Limite' a mais complexa possível. Por exemplo, problemas de programação inteira geralmente são resolvidos usando relaxações: você relaxa seu programa para um programa linear, que pode ser resolvido em tempo polinomial, e então pode jogar fora muitos casos de suas variáveis ​​binárias que nunca funcionarão de qualquer maneira. Em seguida, você ramifica nas opções restantes.

Observe que Branch and Bound geralmente apenas aumentam a velocidade na prática, mas não na teoria: é difícil dizer exatamente quanto da árvore de pesquisa é cortada usando suas heurísticas. Isso é testemunhado pelo número de heurísticas diferentes usadas na prática em tais problemas. Se você não tiver sorte, a árvore de pesquisa restante permanece enorme, mesmo com muitos limites.

Considere a programação , a tarefa de atribuir tarefas com determinadas durações e prazos às máquinas. Assumimos tempo discreto. Muitos desses problemas são NP (O) -hard.

Em particular, esta resposta falará sobre , que é o cronograma$1 \mid r_i \mid L_\max$

• em uma máquina
• problemas com datas de lançamento e nós
• minimizar o atraso máximo , que é a diferença máxima entre o prazo final e o tempo de conclusão em todos os trabalhos.$L_\max$

A versão de decisão deste problema é NP-difícil; isso pode ser visto pela redução de 3PARTITION .

É interessante notar que , se permitirmos a preempção , que é a troca de trabalhos ativos, o problema pode ser resolvido em tempo quadrático pela heurística da Data de vencimento mais antiga (nas datas de vencimento modificadas). É fácil ver que a solução ideal dessa variante não pode ser pior do que a solução ideal do problema original.

Agora, para aplicar Branch & Bound a esse problema, precisamos corrigir alguns parâmetros:

• Calculamos limites inferiores, permitindo a preempção e usando o EDD.
• Ramificamos fixando todos os trabalhos não programados como o próximo.
• Primeiro vamos à criança com o limite inferior menor.

Você precisa fazer isso para todas as aplicações do B&B.

Para um exemplo concreto, considere esta instância de :$1 \mid r_i \mid L_\max$

$\qquad \displaystyle \begin{array}{c|cccc} i & 1 & 2 & 3 & 4 \\ \hline p_i & 4 & 2 & 6 & 5 \\ r_i & 0 & 1 & 3 & 5 \\ d_i & 8 & 12 & 11 & 10 \end{array}$

com os tempos de processamento dos trabalhos, as datas de lançamento e as datas de vencimento.$p_i$$r_i$$d_i$

Executando o B&B conforme especificado acima, isso acontece:

_{Este GIF não faz loop. Recarregue -o em uma nova guia para ver desde o início.}
^{[ fonte ] [ versão estática ]}

Observe que dos 41 nós, apenas quatro são visitados adequadamente e apenas dez são computados limites inferiores.