분기 및 경계

분기 및 경계(BB, B&B 또는 BnB)는 수학적 최적화뿐만 아니라 이산 및 조합 최적화 문제에 대한 알고리즘 설계 패러다임입니다.분기 및 경계 알고리즘은 상태 공간 검색을 통한 후보 솔루션의 체계적 열거로 구성됩니다. 후보 솔루션 집합은 루트에 전체 집합이 있는 루트 트리를 형성하는 것으로 간주됩니다.알고리즘은 솔루션 세트의 하위 집합을 나타내는 이 트리의 분기를 탐색합니다.브랜치의 후보 솔루션을 열거하기 전에 브랜치는 최적 솔루션의 상한 및 하한을 기준으로 체크되며 알고리즘에 의해 지금까지 발견된 최적 솔루션보다 더 나은 솔루션을 생성할 수 없는 경우 폐기됩니다.

알고리즘은 검색 공간의 영역/지점의 하한 및 상한을 효율적으로 추정해야 합니다.사용 가능한 경계가 없는 경우 알고리즘은 완전한 검색으로 퇴보합니다.

이 방법은 1960년 브리티시 페트롤리엄이 후원한 런던 정경대학에서 이산 프로그래밍을 ^[1][2]위해 연구를 수행하던 중 Ailsa Land와 Alison Doig에 의해 처음 제안되었으며, NP-하드 최적화 ^[3]문제를 해결하기 위해 가장 일반적으로 사용되는 도구가 되었다."가지와 경계"라는 이름은 Little et al.의 여행 세일즈맨 ^[4][5]문제에 관한 연구에서 처음 나왔습니다.분기 및 바인딩 방식은 깊이 우선 검색과 같이 깊이 들어가지 않습니다. 첫 번째 방향은 너비 우선 검색(BFS)과 유사한 트리의 가로 방향 이동입니다.

개요

분기 및 경계 알고리즘의 목적은 허용 가능한 S 집합 또는 후보 해법 중에서 목적 함수라고 불리는 실수치 함수 f(x)의 값을 최대화 또는 최소화하는 값 x를 찾는 것이다.집합 S를 서치 공간 또는 피지블 영역이라고 합니다.이 섹션의 나머지 부분에서는 f(x)의 최소화가 바람직하다고 가정한다. 이 가정은 g(x) = -f(x)의 최소값을 구함으로써 f(x)의 최대값을 구할 수 있기 때문에 일반성의 손실 없이 이루어진다.B&B 알고리즘은 다음 두 가지 원칙에 따라 동작합니다.

• 검색 공간을 작은 공간으로 반복적으로 분할한 다음 이러한 작은 공간에서 f(x)를 최소화합니다. 분할을 분기라고 합니다.
• 브런치만 해도 후보 솔루션을 무리하게 열거하여 모두 테스트하는 셈이 됩니다.B&B 알고리즘은, brute-force 검색의 퍼포먼스를 향상시키기 위해서, 검출하려고 하는 최소의 경계를 추적해, 이러한 경계를 사용해 서치 공간을 「프루닝」해, 최적인 솔루션을 포함하지 않는 것을 증명할 수 있는 후보 솔루션을 배제합니다.

이러한 원칙을 특정 최적화 문제에 대한 구체적인 알고리즘으로 바꾸려면 후보 솔루션 세트를 나타내는 데이터 구조가 필요합니다.이러한 표현을 문제의 예라고 부릅니다.인스턴스 I의 후보 솔루션 집합을 S로_I 나타냅니다.인스턴스 표현에는 다음 3가지 조작이 필요합니다.

• 지점(I)은 각각 S의 하위_I 집합을 나타내는 두 개 이상의 인스턴스를 생성합니다(일반적으로 알고리즘이 동일한 후보 솔루션을 두 번 방문하는 것을 방지하기 위해 하위 집합이 분리되지만, 이는 필수가 아닙니다).단, S 중의_I 최적용액은 적어도 1개의 서브셋에 포함되어야 한다.)^[6]
• bound(I)는 I로 표현되는 공간의 후보 솔루션 값에 대한 하한, 즉 S의_I 모든 x에 대해 bound(I) f f(x)를 계산합니다.
• 솔루션(I)은 내가 단일 후보 솔루션을 나타내는지 여부를 결정합니다. (선택적으로 그렇지 않은 경우 운영은 S 중에서 실현_I 가능한 솔루션을 반환하도록 선택할 수 있습니다.)^[6] 솔루션(I)이 솔루션을 반환하는 경우 f(solution(I)는 실현 가능한 솔루션의 전체 공간에 걸쳐 최적의 목적 값에 대한 상한을 제공합니다.

이러한 연산을 사용하여 B&B 알고리즘은 분기 연산에 의해 형성된 인스턴스의 트리를 통해 하향식 재귀 검색을 수행합니다.인스턴스 I을 방문하면 바인딩(I)이 현재 상한보다 크거나 같은지 확인합니다.그렇다면 검색에서 안전하게 삭제되고 재귀가 정지될 수 있습니다.이 플루닝 스텝은 일반적으로 지금까지 조사된 모든 인스턴스 중 확인된 최소 상한을 기록하는 글로벌 변수를 유지함으로써 구현됩니다.

범용 버전

다음은 임의의 목적 함수 ^[3]f를 최소화하기 위한 범용 분기 및 바운드 알고리즘의 골격이다.이것으로부터 실제의 알고리즘을 취득하려면 , 검색 트리의 노드상에서 f의 하한을 계산하는 경계 함수 경계와 문제 고유의 분기 규칙이 필요합니다.따라서 여기서 설명하는 범용 알고리즘은 고차 함수입니다.

1. 휴리스틱을 사용하여 최적화 문제에 대한 솔루션_h x를 찾습니다.값 B = f(x_h)를 저장합니다.(사용할 수 있는 휴리스틱이 없는 경우 B를 무한대로 설정합니다.)B는 지금까지 발견된 최고의 솔루션을 나타내며 후보 솔루션의 상한으로 사용됩니다.
2. 큐를 초기화하여 문제의 변수가 할당되지 않은 상태에서 부분 해결책을 유지합니다.
3. 큐가 비워질 때까지 루프합니다.
   1. 큐에서 노드N을 삭제합니다.
   2. N이 단일 후보 솔루션 x를 나타내고 f(x) < B일 경우 x가 지금까지의 솔루션 중 가장 좋습니다.기록하고 B ← f(x)로 설정합니다.
   3. 그렇지 않으면 N으로 분기하여 새 노드_i N을 생성합니다.각각에 대해서:
      1. bound(N_i) > B일 경우 아무것도 하지 마십시오.이 노드의 하한은 문제의 상한보다 크기 때문에 최적의 해결책으로 이어지지 않고 폐기할 수 있습니다.
      2. 그렇지 않으면 큐에 N을_i 저장합니다.

몇 가지 다른 큐 데이터 구조를 사용할 수 있습니다.이 FIFO 큐 기반 구현에서는 폭 우선 검색이 이루어집니다.스택(LIFO 큐)은 깊이 우선 알고리즘을 생성합니다.best-first branch 및 bound 알고리즘은 노드를 ^[3]하한으로 정렬하는 priority 큐를 사용하여 얻을 수 있습니다.이를 전제로 한 최선의 검색 알고리즘의 예로는 Dijkstra 알고리즘과 그 하위 A* 검색을 들 수 있습니다.깊이 우선 변종은 초기 솔루션을 생성하는 데 사용할 수 있는 좋은 휴리스틱이 없을 때 권장된다. 왜냐하면 이 변종은 전체 솔루션을 빠르게 생성하기 때문에 ^[7]상한을 초과하기 때문이다.

유사 코드

위의 C++ 유사 코드의 실장은 다음과 같습니다.

// 브랜치 및 바운드의 C++와 유사한 구현, // 목적 함수 f를 최소화하는 것으로 가정합니다. 조합 솔루션 branch_and_bound_module(     조합상의 문제 문제,      목적 기능 목적_기능 /*f*/,     경계 기능 lower_bound_function /*바운드*/)  {     // 위의 스텝1     이중으로 하다 문제_상한_한계 = 표준::numeric_displaces< >이중으로 하다>::무궁무한; // = B     조합 솔루션 경험적 접근 = 경험적 접근(문제); // x_h     문제_상한_한계 = 목적_기능(경험적 접근); // B = f(x_h)     조합 솔루션 현재_개요 = 경험적 접근;     // 위의 스텝2     큐잉< >후보 솔루션트리> candidate_module(후보자)_module(후보자);     // 문제 고유의 큐 초기화     candidate_module(후보자)_module(후보자) = poople_internates(문제);     하는 동안에 (!candidate_module(후보자)_module(후보자).빈()) { // 위의 스텝3         // 스텝 3.1         후보 솔루션트리 노드 = candidate_module(후보자)_module(후보자).팝();         // "node"는 위의 N을 나타냅니다.         한다면 (노드.표현_single_disples()) { // 스텝 3.2             한다면 (목적_기능(노드.후보()) < > 문제_상한_한계) {                 현재_개요 = 노드.후보();                 문제_상한_한계 = 목적_기능(현재_개요);             }             //그렇지 않으면 노드가 단일 후보이며 최적이지 않습니다.         }         또 다른 { // 스텝 3.3: 노드는 후보 솔루션의 분기를 나타냅니다.             // "child_branch"는 위의 N_i를 나타냅니다.             위해서 (자동& & 차일드 : 노드.candidate_module(후보자)_module(후보자)) {                 한다면 (lower_bound_function(차일드) <=> 문제_상한_한계) {                     candidate_module(후보자)_module(후보자).큐잉(차일드); // 스텝 3.3.2                 }                 //그렇지 않으면 bound(N_i)> B로 브랜치를 플루닝합니다.스텝 3.3.1             }         }     }     돌아가다 현재_개요; } 

위의 의사 코드에서 기능은heuristic_solve그리고.populate_candidates서브루틴으로 호출된 경우 문제에 적용할 수 있도록 제공해야 합니다.함수 f(objective_function및 바인드(lower_bound_function)는 기술된 함수 객체로 취급되며 C++ 프로그래밍 언어의 람다 표현식, 함수 포인터 및 기타 유형의 호출 가능한 객체에 대응합니다.

개선점

x$${\$displaystyle \mathbf {x}$가 R ${\displaystyle {}^{}}$\$displaystyle \mathbb {R}$^{$n$의 벡터일 $경우{\displaystyle \mathbf{}}$ 분기 알고리즘 및 바운드 알고리즘을 구간 분석^[8] 및 계약자 기술과 결합하여 글로벌 최소 ^[9][10]인클로저를 제공할 수 있습니다.

적용들

이 접근방식은 다수의 NP-하드 문제에 사용됩니다.

• 정수 프로그래밍
• 비선형 프로그래밍
• 출장 세일즈맨 문제(TSP)^[4][11]
• 2차 할당 문제(QAP)
• 최대 만족도 문제(MAX-SAT)
• 가장 가까운 이웃^[12] 찾기 (후쿠나가 케이노스케 지음)
• 플로우 숍 스케줄링
• 절삭재고문제
• 계산 계통학
• 반전 설정
• 모수 추정
• 0/1 배낭 문제
• 커버 설정 문제
• 기계^[13][14] 학습 기능 선택
• 컴퓨터^{[15]: 267–276} 비전에서의 구조화된 예측
• 중국어 우체국 문제를 포함한 아크 라우팅 문제

분기 및 경계는 다양한 휴리스틱의 기초가 될 수도 있습니다.예를 들어, 상한과 하한 사이의 간격이 특정 임계값보다 작아지면 분기를 중지할 수 있습니다.이 방법은 솔루션이 "실용적인 목적에 충분히 적합"하여 필요한 계산을 크게 줄일 수 있는 경우에 사용됩니다.이러한 유형의 솔루션은 사용된 비용 함수가 노이즈가 있거나 통계적 추정의 결과이기 때문에 정확하게 알려져 있지 않고 오히려 특정 ^{[citation needed]}확률을 갖는 값의 범위 내에 있는 것으로만 알려져 있을 때 특히 적용할 수 있다.

다른 알고리즘과의 관계

Nau 등은 A*, B* 및 알파 베타 검색 알고리즘을 ^[16]가정한 분기 및 바운드의 일반화를 제시한다.

최적화 예시

분기 및 경계를 사용하여 이 문제를 해결할 수 있습니다.

Z ${\displaystyle =}$ ${\displaystyle 5}$ ${\displaystyle {x\mathrm{}}_{}}$1 + ${\displaystyle 6}$ ${\displaystyle {}_{}}$ ({$displaystyle$ Z$=5x_{1}+6x_{2})$ $최대화$

${\displaystyle x_{1}+x_{2}\leq 50}$

${\displaystyle 4x_{1}+7x_{2}\leq 280}$

${\displaystyle x_{1}x_{2}\geq 0}$

${\displaystyle {x\mathrm{}}_{}}$ 1$(\$ $및$ x $(\$는 정수입니다.

첫 번째 단계는 정수 제약을 완화하는 것입니다.직선을 형성하는 첫 번째 방정식에는 [${\displaystyle \begin{array}{c}{}_{}\\ {}_{}\end{array}}$ x $=$ [${\displaystyle \begin{array}{}50\\ \mathrm{}\end{array}}$ 0$]$ {$style {bmatrix}\\x_{1}\\x_${2}\end {bmatrix}=$syslog {bmatrix}50\0$$\end {bmatrix$과 [$] 스타일의$두 개의 극단점이 $있다$$.{\displaystyle }$h 벡터 포인트${\displaystyle }$[$]{$ {$bmatrix}$${\displaystyle }$및$$ [${\displaystyle \begin{array}{}70\\ \mathrm{}\end{array}}$0$]{displaystyle$ {$bmatrix}70\\\end$ {$bmatrix$

두 줄

세 번째 포인트는 [${\displaystyle \begin{array}{}0\\ \mathrm{}\end{array}}$0$]({$입니다$.{\displaystyle }$이것은 볼록한 선체 영역이기 때문에 해답은 영역의 꼭지점 중 하나에 있습니다.이 교차로는 [${\displaystyle \begin{array}{c}70/\\ 380\mathrm{}/\end{array}}$3$]($표시 스타일 {$bmatrix}70/3\80/3\end{$bmatrix$\})$ 또는 [$23$.333 26$.$333$\\26.667\$end${bmatrix})$을 사용하여 찾을 수 있습니다.다른 엔드포인트를 테스트하려면 지역 위로 회선을 스위프합니다.이 값이 실수에 대한 최대치임을 알 수 있습니다.

최대 소수 부분을 가진 변수를 선택합니다.${\displaystyle {이\mathrm{}}_{}}$ $경우{\displaystyle {}_{}}$ x 2$(\$는 분기 및 바운드 방식의 파라미터가 됩니다.${\displaystyle {x\mathrm{}}_{}}$ 2${\displaystyle {}_{}26}$ 26$({$${\displaystyle \mathrm{style}}$ $x_$${2}\leq$ 26$)$으로 분기하여 276 $@{\displaystyle 26}$ 24$,$ 26${\displaystyle }${\ { $displaystyle \langle$ 24$,26 \rangle$을 얻습니다.정수 솔루션에 도달하여 다른 $분기{\displaystyle {}_{}}$ x ${\displaystyle {2\mathrm{}}_{}75}$ 27$$75 27$$75 27 $75$ 27 $75 27$ 、 275${\displaystyle 75}$ ${\displaystyle 2275\mathrm{、}}$${\displaystyle {소수점}_{}}$에서는 x 1$({$에서 x $({displaystyle x_$${1$$}\leq$$22$)로$$ $분기$하고 274.571 @${\displaystyle 22}$ 22${\displaystyle ,}$ ${\$ { $displaystyle 22$$,27.4286\rangle$ $\}$을 찾습니다.다른 ${\displaystyle {브랜치x\mathrm{}}_{}}$ 1${\displaystyle {}_{}23}$ 23$$q 23 、 23$ge 。$${\displaystyle {따라서\mathrm{}}_{}}$ x 1${\displaystyle {}_{}24}$ 24 $(\$ $displaystyle x_{1}\ longmapsto 24$）${\displaystyle {및}_{}}$ x ${\$ 26 (\ $displaystyle x_{$2}\ $longmapsto$ 26$$)의 $최대값$은 276 입니다.

「 」를 참조해 주세요.

• 역추적
• 분기 앤 컷 정수 선형 프로그램을 해결하는 데 광범위하게 사용되는 분기 앤 바운드와 절단 평면 메서드 간의 하이브리드입니다.
• 알파 베타 가지치기

레퍼런스

외부 링크

• LiPS – 선형, 정수 및 목표 프로그래밍 문제를 해결하기 위한 사용하기 쉬운 무료 GUI 프로그램.
• Cbc – (Coin-or branch and cut)는 C++로 작성된 오픈소스 혼합 정수 프로그래밍 솔버입니다.