:O método [ http[w: //en.wikipedia.org/wiki/Branch_and_boundBranch and bound| Branch and Bound ]] abordado por [[Logística/Referências#refbPEVD|Sandia national laboratories]] (1997) e [[Logística/Referências#refbPEVE|Dorronsoro]] (2007) é uma técnica [[w:Algoritmo|algoritmica]], que permite encontrar uma solução óptima de problemas de [[w:Otimização combinatória|optimização]], tem vindo a ser utilizado nos últimos anos na resolução de CPEV simétrico e assimétrico (ACPEV). Mantendo a melhor solução encontrada até até então, ou seja, se a nova solução encontrada for pior que a anterior é abandonada. Por exemplo Imaginando que se pretende fazer uma viagem Lisboa-Porto, em que pela A1 o percurso seriam cerca de 300Km. A próxima solução a procurar terá de ser inferior, caso contrário é abandonada; pois o objectivo é minimizar a distância. ▼
*'''Pode também ter aplicação noutras áreas como:''' ▼** [[w:Problema da mochila| Problema da mochila]],
** [[w:Programação linear| Programação linear]],
** Programação não-linear,
** [[w:Problema do caixeiro viajante| Problema do caixeiro viajante]],
** Problema de atribuição quadrático,
** [[w:Problema de satisfatibilidade booleana| Problema de satisfatibilidade máxima]],
** [[w:Algoritmo do vizinho mais próximo| Busca do vizinho mais próximo]],
** Problema do corte de stock,
*'''Respectivamente em Inglês:'''
**[[w:Knapsack problem|<i>Knapsack problem</i>]]
**[[w:Linear programming| <i>Integer programming</i>]]
**[[w:Nonlinear programming| <i>Nonlinear programming</i>]]
**[[w:Travelling salesman problem| <i>Traveling salesman problem</i>]] (TSP)
**[[w:Quadratic assignment problem| <i>Quadratic assignment problem</i>]] (QAP)
**[[w:Maximum satisfiability problem| <i>Maximum satisfiability problem</i>]] (MAX-SAT)
**[[w:Nearest neighbor search| <i>Nearest neighbor search</i>]] (NNS)
**[[w:Cutting stock problem| <i>Cutting stock problem</i>]]
▲:O método [http://en.wikipedia.org/wiki/Branch_and_bound Branch and Bound] abordado por [[Logística/Referências#refbPEVD|Sandia national laboratories]] (1997) e [[Logística/Referências#refbPEVE|Dorronsoro]] (2007) é uma técnica [[w:Algoritmo|algoritmica]], que permite encontrar uma solução óptima de problemas de [[w:Otimização combinatória|optimização]], tem vindo a ser utilizado nos últimos anos na resolução de CPEV simétrico e assimétrico (ACPEV). Mantendo a melhor solução encontrada até até então, ou seja, se a nova solução encontrada for pior que a anterior é abandonada. Por exemplo Imaginando que se pretende fazer uma viagem Lisboa-Porto, em que pela A1 o percurso seriam cerca de 300Km. A próxima solução a procurar terá de ser inferior, caso contrário é abandonada; pois o objectivo é minimizar a distância.
▲*'''Pode também ter aplicação noutras áreas como:'''
** [http://pt.wikipedia.org/wiki/Problema_da_mochila Problema da mochila], [http://en.wikipedia.org/wiki/Knapsack_problem <i>Knapsack problem</i>] (em Inglês)
** [http://pt.wikipedia.org/wiki/Programa%C3%A7%C3%A3o_linear Programação linear], [http://en.wikipedia.org/wiki/Linear_programming <i>Integer programming</i>] (em Inglês)
** Progrmação não-linear, [http://en.wikipedia.org/wiki/Nonlinear_programming <i>Nonlinear programming</i>] (em Inglês)
** [http://pt.wikipedia.org/wiki/Problema_do_caixeiro_viajante Problema do caixeiro viajante], [http://en.wikipedia.org/wiki/Traveling_salesman_problem <i>Traveling salesman problem</i>] (TSP) (em Inglês)
** Problema de atribuição quadrático, [http://en.wikipedia.org/wiki/Quadratic_assignment_problem <i>Quadratic assignment problem</i>] (QAP) (em Inglês)
** [http://pt.wikipedia.org/wiki/Problema_de_satisfatibilidade_booleana Problema de satisfatibilidade máxima], [http://en.wikipedia.org/wiki/Maximum_satisfiability_problem <i>Maximum satisfiability problem</i>] (MAX-SAT) (em Inglês)
** [http://pt.wikipedia.org/wiki/Algoritmo_do_vizinho_mais_pr%C3%B3ximo Busca do vizinho mais próximo], [http://en.wikipedia.org/wiki/Nearest_neighbor_search <i>Nearest neighbor search</i>] (NNS) (em Inglês)
** Problema do corte de stock, [http://en.wikipedia.org/wiki/Cutting_stock_problem <i>Cutting stock problem</i>] (em Inglês)
:Todavia para amostras com maior dimensão, mais complexas ou até para encontrar uma solução mais rapidamente ([[Logística/Referências#refbPEVE|Dorronsoro]] (2007) refere, a utilização de outros métodos mais eficazes como por exemplo [http[w://pt.wikipedia.org/wiki/Heur%C3%ADstica_%28computa%C3%A7%C3%A3o%29Heurística (computação)| heurísticos]]. Pois o problema cria árvores muito extensas, o que não torna fácil a sua resolução.
:Abordado inicialmente por A. H. Land e A. G. Doig em 1960, pioneiros nesta temática no artigo [http://www.jstor.org/pss/1910129 <i>"An automatic method of solving discrete programs problems"</i>] no jornal <i>Econometrica</i>, onde apresentaram um algoritmo númericonumérico simples para programação discreta (que continha variáveis discretas, bem como contínuas). Todavia num trabalho em paralelo Murty, Karel e Little (1962), focavam-se num tipo específico de programação discreta.([[Logística/Referências#refbPEVF|Brusco, 2005 , p.4 a 6]])
:Por forma, o método [http://www.jstor.org/pss/171617?cookieSet=1 <i>K-Tree</i>] proposto por Fisher um dos mais utilizados, no que se refere a aproximação exacta (na resolução especifica de CPEV).
:Conseguiu resolver um problema com 71 clientes; contudo existem problemas com amostras menores, que ainda não têm solução, devido a algumas restrições inerentes. ([[Logística/Referências#refbPEVE|Dorronsoro, 2007]]).
:Recentemente como referido, Fisher introduziu o método [http://www.jstor.org/pss/171617?cookieSet=1 <i>K-Tree</i>], que utiliza um processo diferente de [http[w://en.wikipedia.org/wiki/Branch_and_bound Branch and Bound]]. Propondo uma partição, por via da fixação da borda de incidência de subconjuntos seleccionados de clientes agrupados. As limitações laterais são dualizadas para obter uma [http[w://pt.wikipedia.org/wiki/Otimiza%C3%A7%C3%A3o_combinat%C3%B3riaOtimização combinatória| relaxação lagrangeana ]] ([http[w://en.wikipedia.org/wiki/Lagrangian_relaxationLagrangian relaxation| <i>Lagrangian relaxation</i> ]] em Inglês), que é a limitação minimamínima do problema [http://www.jstor.org/pss/171617?cookieSet=1 <i>K-Tree</i>]. ([[Logística/Referências#refbPEVB|Toth eet al. Vigo, 20012002]]).
:Assim Fisher refere que inicialmente analiza-sedeve ser analisada toda a amostra de soluções <math>\ S</math>. De seguida efectua-se à relaxação do problema, no processamento ou na fase de limitação. Com esta acção estamos a admitir soluções que não se encontram, no espaço de soluções possíveis.
:A solução dessa relaxação produz um limite inferior ao valor de uma solução óptima. Se a solução de relaxação pertencer a <math>\ S</math> ou tenha um custo igual <math>\ \hat s </math> (onde <math>\ \hat s \in S </math>), então a nova solução ou <math>\ \hat s </math> é óptima.
:Caso contrário de acordo com [[Logística/Referências#refbPEVE|Dorronsoro]] (2007)]] , identifica-mos <math>\ n</math> sub-sistemas de <math>\ S ( S_{1} ,..., S_{n} ) </math>, tal que <math>\ U_{i=1}^n S_{i}=S</math>. Estes sub-sistemas são denominados, sub-problemas que ao serem processados, dão origem a quatro resultados possíveis.
*Se for encontrada uma solução melhor que <math>\ \hat s </math>, substitui-se pela nova solução e continua-se.
| 