Branching Strategies

Branch and Bound(분기한정법)은 조합 최적화 문제를 해결하기 위한 알고리즘 패러다임으로, 가능한 해결책의 공간을 체계적으로 탐색하여 최적의 해를 찾는 방법이다.
이 알고리즘의 핵심 요소 중 하나가 바로 ‘분기 전략(Branching Strategies)‘이다.
분기 전략은 문제 공간을 어떻게 분할하고 탐색할 것인지를 결정하며, 이는 알고리즘의 효율성과 성능에 직접적인 영향을 미친다.

문제 구조를 이해하고 적절한 분기 전략을 선택하는 것은 효율적인 알고리즘 구현을 위해 필수적이다. 변수 기반, 제약 기반, 문제 특화 분기 등 다양한 전략을 이해하고, 문제의 특성에 맞게 적용하거나 조합하는 능력이 중요하다.

또한, 분기 변수 선택 전략(최대 분수부, 의사 비용, 강한 분기 등)을 활용하여 더 효과적인 탐색이 가능하다.
분기 전략은 탐색 전략 및 하한 계산과 밀접하게 연관되어 있으므로, 이들을 종합적으로 고려하여 최적의 Branch and Bound 알고리즘을 설계하는 것이 중요하다.

최신 연구에서는 머신러닝과 병렬 컴퓨팅을 활용한 분기 전략이 발전하고 있어, 더 복잡하고 대규모 문제에도 효과적으로 적용할 수 있는 가능성을 보여주고 있다.

분기 전략의 기본 개념

분기 전략은 현재 부분 문제를 더 작은 하위 문제로 분할하는 방식을 정의한다. 이 과정에서 해결책 공간은 상호 배타적인 부분 공간으로 나뉘며, 이들을 모두 합치면 원래의 해결책 공간을 완전히 포함한다.
좋은 분기 전략은 다음과 같은 특성을 가져야 한다:

완전성(Completeness): 모든 가능한 해결책이 적어도 하나의 하위 문제에 포함되어야 한다.
배타성(Exclusivity): 하위 문제들은 가능한 한 겹치지 않아야 한다.
균형성(Balance): 하위 문제들이 비슷한 크기와 복잡도를 가지면 탐색이 더 효율적이다.
제약 증가(Constraint Increase): 각 하위 문제는 추가적인 제약 조건을 포함하여 해결책 공간을 효과적으로 축소해야 한다.

주요 분기 전략 유형

변수 기반 분기(Variable-based Branching)

가장 널리 사용되는 분기 전략 중 하나로, 결정 변수를 기준으로 문제 공간을 분할한다.

정수 변수 분기(Integer Variable Branching)

정수 계획법(Integer Programming) 문제에서 자주 사용되며, 비정수 값을 가진 변수를 선택하여 그 값보다 작거나 같은 경우와 크거나 같은 경우로 분기한다.

예를 들어, 변수 x가 현재 해에서 값 3.7을 가진다면:

왼쪽 가지: x ≤ 3 추가
오른쪽 가지: x ≥ 4 추가

1
2
3
4
5
                  현재 해: x = 3.7
                     /        \
               x ≤ 3          x ≥ 4
              /                  \
새로운 제약으로 문제 해결     새로운 제약으로 문제 해결

이진 변수 분기(Binary Variable Branching)

변수가 0 또는 1의 값만 가질 수 있는 경우, 각 분기는 변수를 0 또는 1로 고정한다.

1
2
3
4
5
                  현재 노드
                  /      \
              x = 0      x = 1
              /            \
 x=0으로 고정한 하위 문제  x=1로 고정한 하위 문제

제약 기반 분기(Constraint-based Branching)

문제의 제약 조건을 기준으로 분기하는 전략.

2제약 추가 분기(Constraint Addition Branching)

새로운 제약 조건을 추가하여 문제 공간을 분할한다.
이 방식은 특히 그래프 기반 문제나 스케줄링 문제에서 유용하다.

예를 들어, 작업 스케줄링 문제에서:

1
2
3
4
5
                현재 상태: 작업 A와 B의 순서 미정
                     /                  \
              작업 A가 B보다 먼저    작업 B가 A보다 먼저
                  /                        \
  A를 B보다 먼저 수행하는 제약 추가  B를 A보다 먼저 수행하는 제약 추가

문제 분할 분기(Problem Decomposition Branching)

문제를 서로 다른 하위 문제로 분해하는 방식.
각 하위 문제는 원래 문제의 다른 측면을 다룬다.

1
2
3
4
5
                    전체 문제
                /      |       \
        하위 문제 1  하위 문제 2  하위 문제 3
       (지역 1에서  (지역 2에서  (지역 3에서
        고객 배정)    고객 배정)    고객 배정)

특수 문제별 분기 전략(Problem-specific Branching Strategies)

경로 기반 분기(Path-based Branching)

외판원 문제(TSP)나 경로 찾기 문제에서, 특정 경로의 포함 여부에 따라 분기.

1
2
3
4
5
             현재 상태: 부분 경로 [1->2->3]
                  /                \
      간선 (3,4) 포함              간선 (3,4) 제외
         /                           \
 경로 [1->2->3->4]           다른 간선 (3,x) 중 하나 선택

아이템 기반 분기(Item-based Branching)

배낭 문제(Knapsack Problem)와 같은 아이템 선택 문제에서, 특정 아이템의 포함 여부에 따라 분기.

1
2
3
4
5
           현재 상태: 아이템 1, 2 선택됨
                /            \
       아이템 3 포함       아이템 3 제외
            /                  \
 아이템 1,2,3 선택      아이템 1,2만 선택

분기 변수 선택 전략(Branching Variable Selection Strategies)

어떤 변수에 대해 분기할 것인지를 결정하는 전략도 중요하다.

최대 분수부 전략(Most Fractional Variable)

정수 계획법에서, 현재 해에서 가장 0.5에 가까운 비정수 값(즉, 정수값에서 가장 멀리 떨어진 값)을 가진 변수를 선택한다. 이는 가장 “모호한” 변수를 먼저 결정하여 빠르게 해결책 공간을 축소하려는 전략이다.

의사 비용 전략(Pseudo-cost Branching)

각 변수에 대해 과거 분기 경험에 기반한 “의사 비용"을 계산하고, 가장 높은 의사 비용을 가진 변수를 선택한다.
이 전략은 각 변수에 대한 분기가 목적 함수에 미치는 영향을 추정한다.

강한 분기 전략(Strong Branching)

여러 후보 변수에 대해 실제로 분기를 시뮬레이션하고, 가장 큰 하한(bound) 증가를 가져오는 변수를 선택한다.
계산 비용이 높지만 더 효과적인 분기 결정을 내릴 수 있다.

신뢰성 분기 전략(Reliability Branching)

강한 분기와 의사 비용 분기의 하이브리드 방식으로, 충분한 정보가 있는 변수에 대해서는 의사 비용을 사용하고, 그렇지 않은 경우 강한 분기를 적용한다.

실제 구현에서의 분기 전략

정수 계획법(Integer Programming)을 위한 분기 전략

정수 계획법 문제를 해결하는 Branch and Bound 구현 예제.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def branch_and_bound_IP(problem, branching_strategy="most_fractional"):
    # 초기화: 루트 노드 생성
    root = create_root_node(problem)
    queue = [root]
    best_solution = None
    best_value = float('inf')  # 최소화 문제 가정
    
    while queue:
        # 현재 노드 선택 (보통 가장 유망한 노드)
        current = select_node(queue)
        queue.remove(current)
        
        # 선형 완화 문제 해결
        solve_relaxation(current)
        
        # 가지치기(pruning) 조건 확인
        if is_pruned(current, best_value):
            continue
        
        # 정수 해인지 확인
        if is_integer_solution(current.solution):
            # 더 좋은 해결책을 찾았으면 업데이트
            if current.value < best_value:
                best_solution = current.solution
                best_value = current.value
        else:
            # 분기할 변수 선택
            if branching_strategy == "most_fractional":
                branch_var = select_most_fractional_variable(current.solution)
            elif branching_strategy == "pseudo_cost":
                branch_var = select_by_pseudo_cost(current, problem)
            # 다른 전략들…
            
            # 두 개의 하위 문제 생성 (x ≤ floor(val) 및 x ≥ ceil(val))
            left_bound = math.floor(current.solution[branch_var])
            right_bound = math.ceil(current.solution[branch_var])
            
            left_child = create_child_node(current, branch_var, "<=", left_bound)
            right_child = create_child_node(current, branch_var, ">=", right_bound)
            
            # 큐에 추가
            queue.append(left_child)
            queue.append(right_child)
    
    return best_solution, best_value

TSP(외판원 문제)를 위한 분기 전략

TSP 문제에 대한 Branch and Bound 구현에서의 분기 전략.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def branch_and_bound_TSP(graph):
    # 초기화
    start_city = 0
    root = create_root_node(start_city, graph)
    queue = [root]
    best_tour = None
    best_length = float('inf')
    
    while queue:
        current = select_node(queue)  # 보통 하한이 가장 낮은 노드 선택
        queue.remove(current)
        
        # 현재 노드가 완전한 투어인 경우
        if is_complete_tour(current):
            if current.length < best_length:
                best_tour = current.path
                best_length = current.length
        # 가지치기(pruning)
        elif current.lower_bound < best_length:
            # 다음 방문할 도시 선택 및 분기
            unvisited = get_unvisited_cities(current, graph)
            
            for next_city in unvisited:
                # 각 미방문 도시에 대해 새 노드 생성
                child = create_child_node(current, next_city, graph)
                # 하한 계산
                calculate_lower_bound(child, graph)
                
                # 유망한 노드만 큐에 추가
                if child.lower_bound < best_length:
                    queue.append(child)
    
    return best_tour, best_length

효과적인 분기 전략의 특성과 권장사항

좋은 분기 전략의 특성
- 균형적 분할: 가능한 한 해결책 공간을 균등하게 분할하여 한쪽으로 치우친 탐색을 방지
- 빠른 계산: 분기 결정을 내리는 데 과도한 계산이 필요하지 않아야 함
- 효과적인 공간 감소: 각 분기 후 해결책 공간이 크게 감소해야 함
- 문제 특화: 문제의 구조와 특성을 활용하는 분기 전략이 일반적인 전략보다 효과적
실무 개발자를 위한 권장사항
1. 문제 구조 분석: 문제의 특성과 구조를 철저히 분석하여 가장 적합한 분기 전략 선택
2. 하이브리드 접근: 다양한 분기 전략을 조합하여 사용 (예: 트리의 상위 레벨에서는 강한 분기, 하위 레벨에서는 의사 비용 분기)
3. 실험적 비교: 여러 분기 전략을 실험적으로 비교하여 특정 문제 인스턴스에 가장 효과적인 전략 선택
4. 동적 전략 전환: 알고리즘 실행 중에 성능 지표에 따라 분기 전략을 동적으로 전환
5. 병렬화 고려: 독립적인 하위 문제들을 병렬로 처리하는 방안 검토

분기 전략과 다른 Branch and Bound 구성 요소와의 관계

분기 전략과 탐색 전략(Exploration Strategy)의 관계

분기 전략이 “어떻게 분할할 것인가"를 결정한다면, 탐색 전략은 “어떤 순서로 노드를 탐색할 것인가"를 결정한다.
이 두 전략의 조합이 알고리즘의 성능을 결정한다.

주요 탐색 전략:

깊이 우선 탐색(DFS): 메모리 효율적이지만 초기에 좋은 해를 찾지 못할 수 있음
너비 우선 탐색(BFS): 메모리 요구량이 크지만 균형적인 탐색 보장
최선 우선 탐색(Best-First): 하한(bound)이 가장 유망한 노드부터 탐색

분기 전략과 하한 계산(Bounding)의 관계

좋은 분기 전략은 하한 계산과 시너지 효과를 발휘한다.
효과적인 분기는 하위 문제의 하한을 빠르게 증가시켜 더 많은 가지치기를 가능하게 한다.

실제 응용 사례와 성능 분석

작업 스케줄링 문제

`1`	`n개의 작업을 m개의 기계에 할당하여 총 완료 시간을 최소화하는 문제`

분기 전략: 작업-기계 할당에 기반한 분기

1
2
3
4
5
                  현재 상태: 작업 1,2가 할당됨
                /       |       \
      작업 3->기계 1  작업 3->기계 2  작업 3->기계 3
        /              |              \
새로운 작업 할당…   새로운 작업 할당…   새로운 작업 할당…

성능 분석: 작업을 가장 임계적인 기계(현재 완료 시간이 가장 긴 기계)에 할당하는 분기를 먼저 평가하면, 더 빠르게 좋은 하한을 얻을 수 있다.

최대 독립 집합 문제

`1`	`그래프에서 서로 인접하지 않은 노드의 최대 집합을 찾는 문제`

분기 전략: 노드 포함/제외 기반 분기

1
2
3
4
5
              현재 상태: 노드 집합 S
                 /            \
        노드 v를 S에 포함     노드 v를 S에서 제외
             /                    \
   v의 이웃 노드들 모두 제외   다른 노드에 대해 결정 계속

성능 분석: 분기할 노드 v를 선택할 때, 가장 많은 이웃을 가진 노드를 선택하면 분기 효율이 높아진다. 이는 v를 포함하는 분기에서 많은 노드가 자동으로 제외되기 때문.