두 접근 방식, 하나의 문제: 자원 제약 프로젝트 스케줄링(RCPSP)을 위한 Branch-and-Bound와 A* 비교

Branch-and-Bound (B&B)와 $A^*$는 각각 운영 연구(Operations Research)와 인공지능(Artificial Intelligence)에서 유래한 인기 있는 정확 탐색 방법이다. 두 방법이 근본적인 검색 원리를 공유함에도 불구하고, 탐색 공간을 탐색하는 방식의 차이는 상당히 다른 계산 성능을 초래할 수 있다.

우리는 자원 제약 프로젝트 스케줄링 문제(Resource-Constrained Project Scheduling Problem, RCPSP)를 예시적인 문제 설정으로 사용하여 이러한 차이점들을 조사한다. 먼저 혼합 정수 선형 프로그래밍(mixed-integer linear programming), 상태-행동(state-action), 그리고 시간 기반 Petri-net 표현 간의 관계를 확립한다.

B&B와 $A^*$는 수많은 알고리즘적 개선이 가능하므로, 우리는 비교적 기본적인 구현에 초점을 맞춘다. 이는 최첨단 솔버의 성능을 비교하기보다는 방법론 간의 근본적인 차이를 검토할 수 있게 한다. 동일한 하한(lower bound)과 최고 우선순위 노드 선택(best-first node selection)을 사용하여, 특히 서로 다른 스케줄링 결정 순서를 통해 도달하는 동등 상태(equivalent states) 식별에 초점을 맞춰 검색 메커니즘의 영향을 분리하여 분석한다.

벤치마크 RCPSP 인스턴스 480개에 대한 실험 결과, 그래프 기반 $A^$가 고려된 B&B 변형보다 상당히 우수한 성능을 보였다. 추가적인 가지치기 규칙(pruning rules)을 적용했을 때, $A^$는 동일한 시간 및 메모리 제한 하에서 best-first B&B의 445개 인스턴스와 비교하여 모든 480개 인스턴스에 대해 최적성을 입증했다. 깊이 우선 B&B(Depth-first B&B)는 메모리를 적게 사용하며, 검색이 시간 제한 내에 완료되지 않더라도 실현 가능한 해답을 찾을 수 있다. 더 강력한 선형 프로그래밍 완화(linear programming relaxations)는 탐색 공간을 줄이지만 상당한 계산 오버헤드를 유발한다.

우리의 연구 결과는 중복 상태 감지(duplicate-state detection)의 중요성을 강조하며, 검색 접근 방식 간의 계산적 트레이드오프를 명확히 한다. 이러한 통찰력은 연구자들이 적절한 방법을 선택하고, 한 접근 방식의 효과적인 메커니즘을 다른 접근 방식에 통합할 기회를 식별하는 데 도움을 줄 수 있다.