Hierarchical Rectangle Packing Solved by Multi-Level Recursive Logic-based Benders Decomposition

이 논문은 회로 레이아웃 및 물류 분야의 응용을 배경으로, 블록 차원을 동적으로 정밀하게 조정하며 기존의 단일 구조 공식 및 기존의 상향식(Bottom-Up) 베이스라인 모델보다 해의 품질과 확장성 측면에서 크게 뛰어난 성능을 보이는 새로운 다층 로직 기반 벤더스 분해(Logic-based Benders Decomposition) 방법을 제안함으로써 2차원 계층적 직사각형 패킹 문제를 다룬다.

핵심

핵심 개념: 상자 안의 상자 채우기

당신이 거대한 컨테이너를 포장하려는 물류 관리자라고 상상해 보세요. 하지만 이 컨테이너는 일반적인 컨테이너가 아닙니다. 큰 컨테이너 안에는 그냥 물건들이 들어있는 것이 아니라, 이미 포장된 상자들이 있고, 그 상자들 안에는 또 더 작은 포장된 상자들이 들어 있습니다.

이것이 바로 **계층적 직사각형 패킹 문제(Hierarchical Rectangle Packing Problem)**입니다. 러시아 인형(마트료시카)과 비슷하지만, 인형 대신 직사각형(회로 부품이나 운송용 상자 등)이 있으며, 이들은 서로 겹치지 않으면서 완벽하게 맞물려 들어가야 합니다.

목표는 간단합니다: 최종적인 가장 바깥쪽 컨테이너를 최대한 작게 만드는 것입니다.

문제점: 왜 이렇게 어려운가?

일반적인 패킹 문제에서는 물건을 상자에 던져 넣고 어떻게든 맞추기만 하면 됩니다. 하지만 여기서는 규칙이 재귀적(recursive)입니다:

1. "블록" 규칙: 만약 "모듈 A"(하위 상자)가 있다면, 모듈 A를 사용할 때마다 그것은 반드시 동일한 크기와 모양이어야 합니다. 특정 위치에 맞추기 위해 모듈 A를 늘리거나 줄일 수 없습니다.
2. 계층 구조: 모듈 A가 얼마나 커야 하는지 알기 위해서는, 먼저 모듈 A 안에 무엇이 들어있는지에 대한 퍼즐을 풀어야 합니다. 만약 모듈 A 안에 "모듈 B"가 들어있다면, 모듈 B의 퍼즐을 먼저 풀어야 합니다.

저자들은 만약 이 모든 것을 한꺼번에 해결하려고 한다면(마치 창고 전체를 하나의 거대한 두뇌 퍼즐로 풀려고 하는 것처럼), 컴퓨터가 과부하에 걸린다고 설명합니다. 이는 1,000피스짜리 퍼즐을 풀면서 동시에 그 퍼즐 조각들 안에 숨겨진 50개의 작은 퍼즐들을 동시에 풀어야 하는 것과 같습니다.

기존 방식: "추측하고 확인하기" 방법 (Bottom-Up)

이 논문이 나오기 전, 이 문제를 해결하는 표준적인 방법은 바텀업(Bottom-Up) 방식이었습니다.

• 작동 방식: 가장 아래 단계(가장 작은 아이템들)에서 시작합니다. 이들을 작은 상자에 담습니다. 그다음 그 작은 상자를 중간 크기의 상자에 담습니다. 이 과정을 위로 올라가며 계속 반복합니다.
• 결함: 아직 큰 상자가 어떤 모습일지 모르기 때문에, 계속 추측해야 합니다. 예를 들어, 작은 상자를 아주 길고 좁은 모양으로 포장했을 수도 있습니다. 하지만 상위 단계에 도달했을 때, 큰 상자는 짧고 넓은 모양이 필요하다는 것을 깨닫게 될 수도 있습니다.
• 해결책: 좋은 형태를 놓치지 않기 위해, 기존 방식은 모든 작은 상자에 대해 수많은 다양한 버전(예: 25가지의 서로 다른 모양)을 생성하려고 시도합니다. 이는 마치 자동차 트렁크에 맞을지 몰라서 여행 가방을 25가지 방식으로 짐을 싸보는 것과 같으며, 이는 엄청난 시간과 컴퓨터 자원을 낭비합니다.

새로운 방식: "스마트 협상가" (LBBD)

저자들은 **논리 기반 벤더스 분해(Logic-based Benders Decomposition, LBBD)**라고 불리는 새로운 방법을 제안합니다. 이것은 단계 사이에서 말을 주고받는 스마트 협상가 또는 프로젝트 매니저와 같습니다.

무작정 추측하는 대신, 이 방법은 다음과 같이 작동합니다:

1. 계획 (Top-Down): "매니저"(상위 레벨)가 말합니다. "내 생각에 이 하위 상자는 가로 10인치, 세로 5인치여야 할 것 같아."
2. 확인 (Bottom-Up): "작업자"(하위 상자 레벨)가 그 정확한 치수에 맞춰 아이템들을 포장해 봅니다.
   • 시나리오 A: "좋아요! 다 들어갑니다." -> 매니저는 그 크기를 유지합니다.
   • 시나리오 B: "안 됩니다. 다 넣을 수 없어요. 높이가 더 높아야 합니다." -> 작업자는 매니저에게 **컷(Cut)**을 보냅니다.
3. 컷(Cut): 이것이 마법 같은 부분입니다. 작업자는 단순히 "안 된다"라고만 하지 않습니다. 그들은 "가로를 10인치로 하고 싶다면, 세로는 최소 8인치는 되어야 합니다"라고 말합니다. 이는 매니저의 선택지 목록에서 불가능한 조합들을 모두 제거해 버립니다.

그러면 매니저는 이 새로운 규칙에 근거하여 새로운 계획을 세웁니다. 그들은 모두에게 적합한 완벽한 크기를 찾을 때까지 계속 협상합니다.

왜 더 나은가?

• 낭비 없는 추측: 기존 방식(Bottom-Up)은 상자의 모양 하나를 만들기 위해 25가지 형태를 만드는 데 시간을 허비했습니다. 새로운 방식(LBBD)은 아래 단계의 피드백을 바탕으로 실제로 가능한 모양만을 탐색합니다.
• 더 똑똑한 결정: 이 방식은 규칙을 동적으로 정교화합니다. 끝까지 기다렸다가 모양이 틀렸다는 것을 깨닫는 것이 아니라, 실수로부터 즉시 배웁니다.

결과

저자들은 복잡한 전자 회로와 유사한 합성 문제(최대 7단계의 계층 구조)를 통해 이를 테스트했습니다.

• 승자: 새로운 "스마트 협상가"(LBBD) 방식은 기존의 "추측하고 확인하기" 방식보다 일관되게 더 작고 효율적인 컨테이너를 찾아냈습니다.
• 트레이드오프(Trade-off): 완벽하지는 않습니다. 저자들은 가장 거대한 문제의 경우 이 방법도 여전히 시간이 오래 걸린다는 점을 인정했지만, 모든 것을 한꺼번에 풀거나 무작정 추측하는 것보다는 훨씬 빠르고 더 나은 결과를 만들어냅니다.

요약

집을 짓는다고 상상해 보세요.

• 기존 방식: 모든 방을 가능한 모든 모양으로 만든 다음, 그것들을 집으로 조립하려고 시도합니다. 만약 집이 맞지 않으면, 방들을 다시 만들고 다시 시도합니다.
• 새로운 방식: 방 제작자들에게 "가로 10, 세로 10인 주방이 필요해"라고 말합니다. 그들이 만들어 봅니다. 만약 안 된다면, 그들은 "이 재료로는 10x10 주방을 만들 수 없습니다. 10x12가 필요합니다"라고 말합니다. 당신은 설계도를 업데이트합니다. 그들은 10x12를 만듭니다. 집 전체가 완벽하게 들어맞을 때까지 이 과정을 반복합니다.

이 논문은 복잡하게 중첩된 상자를 채울 때, 무작정 추측하고 확인하는 기존 방식보다 이러한 "협상" 접근 방식이 훨씬 더 똑똑한 방법임을 증명합니다.

기술 요약

기술 요약: 다층 재귀적 로직 기반 벤더스 분해를 이용한 계층적 직사각형 패킹 문제 해결

문제 정의
본 논문은 아날로그 집적 회로 레이아웃, 시설 설계 및 물류 분야의 응용을 배경으로 하는 2차원 계층적 직사각형 패킹 문제(2DHRP)를 다룬다. 컨테이너의 차원이 고정된 클래식한 스트립 또는 빈 패킹과 달리, 2DHRP는 컨테이너 자체가 최적화 문제의 결과물로서 차원이 미리 정의되지 않은 "블록 유형"인 재귀적 구조를 가진다.

이 문제는 가중치 유향 트리(weighted directed out-tree)로 모델링된다. 루트는 최상위 블록 유형을 나타내며, 이는 개별 직사각형들과 하위 블록 유형들의 발생 사례들을 포함해야 한다. 결정적으로, 특정 블록 유형의 모든 발생 사례는 동일하게 패킹되어야 하며 동일한 차원(너비와 높이)을 공유해야 하는데, 이는 표준화된 부품(예: 회로 설계에서의 부품)의 재사용을 반영한다. 목적 함수는 최상위 블록 유형의 크기, 즉 면적의 대리 지표인 반둘레(half-perimeter, $W + H$)를 최소화하는 것이며, 모든 계층 수준에서 겹침 방지 제약 조건과 경계 제한을 준수해야 한다.

방법론
저자들은 대규모 인스턴스의 계산 복잡성을 처리하기 위해 혼합 정수 선형 계획법(MILP)과 제약 프로그래밍(CP)을 사용하는 엄밀한 정식화와 두 가지 분해 휴리스틱을 제안한다.

1. 엄밀한 모델 (Exact Models):

   • MILP: 비중첩(non-overlapping)을 강제하기 위해 "big-M" 제약 조건을 포함한 상대적 위치 기반 정식화를 사용한다. 또한 사이클을 제거하기 위한 위상적 순서 제약과 사전 정의된 직사각형 변체(variant) 선택을 위한 이진 변수를 포함한다.
   • CP: 위치와 차원을 모델링하기 위해 구간 변수(interval variables)를 사용하며, 변체 선택을 위한 alternative 제약과 자원 소비에 대한 경계값을 조여주는 cumulative 제약(pulse 함수를 통한)을 활용한다.

2. 기초 분해 (Bottom-Up):
   본 논문은 리프(leaf) 블록 유형을 먼저 해결하는 표준적인 Bottom-Up 방식을 구현한다. 상위 레벨로부터의 정보 부족을 완화하기 위해, 이 방법은 각 블록 유형에 대해 여러 개의 패킹 변체(서로 다른 너비/높이 조합)를 생성한다. 이러한 변체들은 상위 블록 유형을 해결할 때 고정된 차원을 가진 직사각형으로서 취급된다. 시간 할당은 각 블록 유형 내의 객체 수에 비례하여 이루어진다.

3. 제안된 방법: 재귀적 로직 기반 벤더스 분해 (LBBD):
   핵심 기여는 사전 생성된 변체에 의존하는 대신 차원 제약을 동적으로 정교화하는 다층 재귀적 LBBD 방식이다.

   • 마스터 문제 (Master Problem): 각 레벨에서 마스터 문제는 현재 블록 유형의 차원을 최적화한다. 명시적인 하위 차원 대신, 거친 근사치(면적 하한값)와 "컷(cut)" 세트를 사용한다.
   • 서브 문제 (Subproblems): 마스터 문제의 후보 해(PLAN)가 발견되면, 제안된 차원이 타당한지 검증하기 위해 하위 블록 서브 문제가 호출된다.
   • 컷 (Cuts): 만약 하위 서브 문제가 제안된 차원 내에서 패킹될 수 없다면, 마스터 문제의 탐색 공간에서 해당 특정 차원 쌍(또는 영역)을 제거하는 컷이 생성된다.
   • 휴리스틱-LBBD: 실질적인 실행 시간을 보장하기 위해, 엄밀한 LBBD는 휴리스틱 버전으로 적응되었다. 이 버전은 서브 문제 해결에 시간 제한을 두고, 빠른 해를 찾기 위해 "제한된 마스터 문제"를 사용하며, "미세 조정(fine-tuning)" 단계를 채택한다. 미세 조정 단계는 고정된 높이에 대해 너비를 최소화하려고 시도하고, 높이를 약간 줄여 탐색 공간을 공격적으로 가지치기함으로써 더 강력한 컷을 생성한다.

주요 기여

• 공식 정의: 본 논문은 2DHRP를 평면 2D 패킹의 일반화로 공식 정의하여 계층적 최적화와의 관계를 확립하고, 엄밀한 MILP 및 CP 모델을 제공한다.
• 재귀적 분해: 정보가 상향식(Bottom-Up)으로만 흐르는 기존 방식과 달리, 차원 제약(Top-Down)과 타당성 컷(Bottom-Up)을 통해 정보를 양방향으로 전파하는 새로운 재귀적 LBBD 프레임워크를 도입한다. 이는 부모 블록이 하위 블록의 적절한 차원을 능동적으로 선택할 수 있게 함으로써, 단순히 사전 생성된 변체를 수동적으로 받아들이는 Bottom-Up 방식과 차별화된다.
• 계산 연구: 최대 7개 계층과 블록 유형당 최대 80개의 아이템을 포함하는 합성 인스턴스로 구성된 새로운 벤치마크 세트를 생성하였으며, 이는 집적 회로 설계와 관련된 시나리오를 포괄한다.

실험 결과
Gurobi(MILP)와 CP Optimizer(CP)를 사용하여 합성 인스턴스에 대한 실험을 수행하였다.

• 솔버 성능: 단일 레벨 인스턴스에서, CP 솔버(M-CP)가 시간 제한 내에 MILP 솔버(M-MILP)보다 솔루션 품질(반둘레 갭) 측면에서 일반적으로 우수한 성능을 보였다. 이에 따라 CP가 분해 방법의 백본(backbone)으로 선택되었다.
• 분해 비교:
  • 단일 모델 (Monolithic Models): M-MILP와 M-CP 모두 다층 인스턴스에서 어려움을 겪었으며, 분해 방법과 비교했을 때 시간 제한 내에 높은 품질의 해를 찾는 데 실패하는 경우가 많았다.
  • Bottom-Up vs. LBBD: 제안된 휴리스틱-LBBD는 2~7개 계층을 가진 모든 인스턴스에서 Bottom-Up 베이스라인(BUN)보다 일관되게 우수한 성능을 보였다.
  • 확장성: 계층 깊이가 깊어질수록 성능 격차가 커졌다. 가장 복잡한 인스턴스(7개 계층)의 경우, LBBD는 최상의 Bottom-Up 변체보다 평균 반둘레 갭이 약 2.5 퍼센트 포인트 더 낮았다.
  • 일관성: LBBD는 Bottom-Up 방식이 생성된 변체의 수에 따라 높은 분산을 보이는 것과 대조적으로, 더 일관된 결과(더 좁은 사분위 범위)를 보여주었다.
  • 미세 조정: 공격적인 컷 강화(예: 높이를 일정 비율로 감소)를 사용하는 LBBD 변형이 약간 더 나은 결과를 얻었으나, 그 차이는 미미했다.

의의 및 주장
본 논문은 제안된 재귀적 LBBD 방법이 솔루션 품질과 확장성 측면에서 기존의 단일 모델 및 전통적인 Bottom-Up 분해를 유의미하게 능가한다고 주장한다. 식별된 주요 장점은 반복적인 정교화를 통해 하위 블록에 필요한 차원을 "추론"할 수 있다는 점이며, 이를 통해 Bottom-Up 방식에서 발생하는 불필요한 변체 생성 및 최적화의 계산 낭비를 피할 수 있다.

저자들은 휴리스틱-LBBD가 (시간 제한 및 휴리스틱 컷으로 인해) 이론적인 최적성 보장은 포기하지만, 엄밀한 방법이 실패하는 복잡한 다층 산업 시나리오에서 실용적이고 효과적인 접근법을 제공한다고 언급한다. 이 방법은 솔버 독립적이며, 클러스터링을 통한 "가상 계층" 생성을 통해 3D 패킹으로 확장하거나 단일 레벨 문제에 적용될 가능성이 있으나, 후자는 테스트된 결과라기보다 잠재적인 일반화 가능성으로 제시되었다. 본 연구는 모듈형 및 재사용 가능한 부품 배치의 필요성을 다루는 집적 회로 설계, 시설 레이아웃 및 물류의 맥락에 위치한다.