Branch and Bound·탐색 트리·최적값 인증

좋은 해를 찾는 것과 최적임을 증명하는 것

신경망이 좋은 자원 배정을 추천했다고 해서 다른 모든 배정이 더 나쁘다는 증명이 생기지는 않습니다. Branch and Bound는 실제 가능한 해와 아직 살펴볼 후보들의 상한을 함께 관리합니다. 탐색 트리는 어디를 확인했고, 무엇을 근거로 제외했으며, 아직 어느 정도의 개선 가능성이 남았는지를 보여주는 기록이 됩니다.

실습에서는 무게가 2,3,4인 세 물건 중 일부를 선택하여 가치를 최대화합니다.

$$\max_{x\in\{0,1\}^3}v_0x_0+v_1x_1+v_2x_2, \qquad 2x_0+3x_1+4x_2\le C.$$

가치와 용량은 각각 0부터 9까지의 정수입니다. 아무것도 선택하지 않는 해는 항상 가능합니다. 따라서 자식 노드 하나가 불가능하다는 사실과 전체 문제가 불가능하다는 사실을 혼동하면 안 됩니다. 이 실험의 목표는 최적값과 그 값을 만드는 해 하나이며, 동률인 모든 최적해의 열거가 아닙니다.

실제 해는 하한이고 완화는 상한이다

현재 확보한 정수 해를 incumbent라고 부릅니다. 이 해가 용량을 지키고 가치가 L이면 최적값 OPT는 적어도 L입니다. 초기 해는 root LP의 좌표를 내림하여 만듭니다. 좌표가 1인 물건은 남기고 분수인 물건은 버리므로 양의 무게를 가진 이 예제에서는 용량을 위반하지 않습니다. 다만 좋은 해라는 보장은 없습니다.

각 노드는 일부 변수를 이미 0이나 1로 고정한 부분 문제입니다. 고정 조건을 유지하면서 나머지만 [0,1]로 완화하면 원래 정수 후보를 포함하는 더 큰 집합이 됩니다.

$$F_N\subseteq R_N \quad\Longrightarrow\quad \max_{x\in F_N}v^Tx\le\max_{x\in R_N}v^Tx=U_N.$$

따라서 LP의 최대값은 해당 노드의 상한입니다. 최대화와 최소화의 방향을 주의하세요. 최소화에서는 가능한 해가 상한을 주고 완화가 하한을 줍니다. 완화 점의 높은 가치를 그대로 정수 해의 가치로 보고하면 안 됩니다.

이 작은 LP를 정확하게 계산하기

먼저 1로 고정된 물건의 무게를 용량에서 뺍니다. 이미 음수가 되면 해당 노드는 불가능합니다. 그렇지 않으면 자유 변수 중 가치가 양수인 물건을 가치/무게 비율이 큰 순서대로 채웁니다. 밀도가 낮은 물건이 공간을 차지하는데 더 높은 물건이 덜 채워져 있다면, 같은 무게만큼 높은 쪽으로 옮겨 가치를 줄이지 않을 수 있습니다. 이런 교환을 반복하면 fractional knapsack 해를 얻고, 분수 변수는 많아야 하나입니다.

가치가 0인 자유 물건은 선택하지 않아도 LP 최적값이 변하지 않습니다. 이는 LP 해 하나를 고르는 규칙이며 해가 유일하다는 뜻은 아닙니다. 밀도는 나눗셈의 반올림 대신 교차 곱으로 비교하고 동률이면 작은 물건 번호를 먼저 사용합니다.

무게가 2,3,4이고 용량과 가치가 정수이므로 좌표와 목적값은 모두 1/12 단위로 표현할 수 있습니다. 내부 계산은 이 단위의 정수를 사용합니다. 화면의 반올림된 소수끼리 비교하여 가지를 잘라내지 않습니다.

분기·정수 종료·불가능·상한 가지치기

선택한 LP 해가 정수이면 그 해가 해당 노드의 정수 최적해입니다. 분수이면 그 변수를 0과 1로 고정한 두 자식으로 나눕니다. 모든 정수 후보는 정확히 한 자식에 속하므로 후보를 빠뜨리지 않습니다. 실습은 0 자식을 먼저 처리하는 결정적인 깊이 우선 탐색을 사용합니다.

노드를 처리할 때 먼저 LP를 내림한 후보로 incumbent를 개선할 수 있는지 검사합니다. 그 다음 분수 노드의 상한이 현재 하한 이하이면 제외합니다.

$$U_N\le L\quad\Longrightarrow\quad \text{이 노드에는 현재보다 더 좋은 정수 해가 없다.}$$

등호에서도 최적값과 해 하나를 구하는 데는 안전하지만 다른 동률 해를 놓칠 수 있습니다. 아예 해가 없는 불가능 노드와는 다릅니다. 트리의 open은 대기, split은 분기, int는 정수 LP, bound는 상한으로 제외, none은 불가능을 뜻합니다. 노드 표의 종료 당시 하한은 그때 확보한 값이며 나중에 발견한 더 좋은 값으로 덮어쓰지 않습니다.

대기 목록으로 전체 인증을 만들기

대기 중인 frontier 노드들은 아직 종료하거나 안전하게 제외하지 않은 정수 후보를 덮습니다. 각 상한과 현재 해를 비교하면 전체 문제에 대한 경계를 얻습니다.

$$L\le\mathrm{OPT}\le U=\max\bigl(\{L\}\cup\{U_N:N\text{은 대기 중인 가능한 노드}\}\bigr).$$

불가능한 노드는 상한에 기여하지 않습니다. 대기 목록이 비면 U=L입니다. 이 실습의 인증 표시는 정확히 U=L인 경우를 사용합니다. 목적값이 정수라는 사실로 상한을 내리는 등 가능한 모든 추가 강화 규칙을 구현한 것은 아닙니다. 정확한 탐색이 진행되는 동안 하한은 감소하지 않고 전체 상한은 증가하지 않습니다.

LP 상한은 노드를 생성할 때 계산하므로 생성 노드 수는 경계 평가 수입니다. 처리한 노드 수와는 다르며 둘 다 실제 실행 시간이 아닙니다. 초기 incumbent는 root에서 만들지만 이후 후보는 해당 노드를 처리할 때만 사용합니다. 이전 단계에 미래의 정수 해를 미리 가져오지 않습니다. 인증 간극이 0이 된 뒤에도 종료 이유를 살펴볼 수 있도록 예시 이력은 남은 목록을 처리합니다. 따라서 최적값 인증과 목록 처리 완료를 별도 표시합니다.

손계산 예제: 열려 있는 간극에서 종료까지

가치를 (3,4,5), 용량을 4로 놓습니다. root LP는 (1,2/3,0)이며 가치가 17/3입니다. 내림한 (1,0,0)의 가치는 3입니다. root를 한 번 처리하면 분수인 x1을 기준으로 두 자식이 생기고 각 상한은 11/2입니다. 처리 단계 1에서 전체 간극은 11/2−3=5/2이며, 처음 root의 간극 8/3과 구분해야 합니다.

처리 단계 4에서는 (0,0,1)의 가치 5를 발견하지만 대기 노드가 허용하는 상한은 아직 11/2입니다. 실제 처리 9회 뒤 전체 상한과 하한이 5로 일치하며 대기 목록도 빕니다. N6은 x0=x1=1로 고정되어 무게 5가 용량 4를 초과하는 불가능 노드입니다. 이를 조회하면 주황 LP 배정은 없고, 전체 문제의 가능한 파란 정수 해는 계속 보입니다. 전체 해가 선택한 노드의 고정 조건을 만족할 필요는 없습니다.

손계산 예제: 동률 가지를 제외해도 되는 이유

가치를 (1,1,2), 용량을 7로 바꿉니다. 초기 정수 해 (1,0,1)의 가치는 3이고 root 상한은 10/3입니다. x1으로 분기하면 두 자식의 상한은 모두 3입니다. N2는 x1=1이며 LP 배정은 (1,1,1/2), 가치 3입니다. 내림 후보는 현재 해보다 나쁘고 LP 상한도 현재 값 3보다 클 수 없어 bound로 제외합니다.

하지만 이 가지에는 (0,1,1)이라는 다른 정수 해가 있고 그 가치도 3입니다. 가지치기는 최적값과 이미 확보한 해를 유지하는 데 안전할 뿐 유일성이나 모든 동률 해의 수집을 보장하지 않습니다. 요청한 최적화 목표가 해 전체의 열거라면 등호 처리 규칙도 다시 설계해야 합니다.

연습 문제와 해설

문제: 가치 (3,4,5), 용량 1, 처리 단계 3에서 인증 간극이 0이면서 대기 노드가 남아 있을 수 있을까요?

해설: 어떤 물건도 단독으로 넣을 수 없으므로 빈 배정의 가치 0이 최적입니다. 0 자식을 따라 세 번 분기하면 모두 0인 배정만 남기고, 1 자식들은 고정 무게 때문에 이미 불가능하다고 판단됩니다. 대기 노드가 네 개 남았어도 그 중 가능한 노드의 상한은 0이어서 L=U=0입니다. 생성한 일곱 노드를 모두 처리하면 대기 목록도 비지만 해의 값은 바뀌지 않습니다. 이것은 상한에 의한 증명이지 많은 노드를 방문해야만 정확하다는 주장이 아닙니다.

추가 문제: 원래 가치에서 용량을 5로 바꾸세요. 해설: root LP가 이미 (1,1,0)의 정수이며 가치 7입니다. 분기 없이 최적값을 인증합니다. 실제 이력보다 큰 처리 횟수나 아직 없는 노드 번호를 요청하면 마지막으로 존재하는 상태로 제한하여 미래 결과를 만들어내지 않습니다.

AI 연구에 연결하기

학습한 branching 정책이나 후보 생성기는 탐색 순서와 속도를 개선할 수 있습니다. 그러나 안전한 인증을 유지하려면 상한 계산과 제외 논리가 여전히 옳아야 합니다. 학습 모델의 예측 점수가 자동으로 인증된 경계가 되는 것은 아닙니다. 이 실험은 작은 문제에서 그 논리를 분리해 확인하며 산업용 solver나 일반 비선형 문제의 성능을 주장하지 않습니다. 큰 문제에서는 최악의 경우 지수적으로 많은 노드와 훨씬 비싼 완화 풀이가 필요할 수 있습니다.

Stanford의 Boyd·Mattingley Branch and Bound 강의 노트는 일반적인 경계·분할 구조와 Boolean-convex 문제를 설명합니다. 해당 자료는 주로 최소화 관례를 사용합니다. 여기의 최대화 예제, 1/12 단위 계산, 단계별 진단은 교재를 위해 직접 구성했습니다.