기술 요약: 최대 다양성 그룹화 문제(Maximally Diverse Grouping Problem)를 위한 (혼합-)정수 선형 계획법 정식화 분석

문제 정의

최대 다양성 그룹화 문제(MDGP)는 전형적인 NP-난해(NP-hard) 조합 최적화 문제이다. 아이템 집합 $I$와 그룹 집합 $G$가 주어졌을 때, 목적은 각 아이템을 정확히 하나의 그룹에 할당하여 그룹 내 총 다양성을 최대화하는 것이다. 아이템 쌍 $(i, j)$의 다양성은 파라미터 $d_{ij} \geq 0$에 의해 정의된다. 총 다양성은 동일한 그룹에 할당된 아이템들의 모든 쌍별 다양성의 합이다. 이 문제는 각 그룹 $g \in G$에 대한 하한 $l_g$와 상한 $u_g$로 정의된 그룹당 아이템 수 제약 조건을 따른다.

MDGP의 응용 분야로는 학생들을 그룹 또는 강의에 배정하거나, 프로젝트 팀을 구성하고, 리뷰어 그룹을 생성하며, 기말고사를 스케줄링하는 것 등이 있다. 문헌에서는 휴리스틱 접근 방식이 흔히 사용되지만, 엄밀해(exact solution) 방법은 역사적으로 작은 규모의 문제 인스턴스에 국한되어 왔다.

방법론 및 모델 정식화

본 논문은 네 가지 서로 다른 (혼합-)정수 선형 계획법(MILP) 정식화를 분석하고 비교한다:

1. 표준 정식화 (Weitz and Lakshminarayanan, 1998):

   • 변수: 아이템 $i$가 그룹 $g$에 할당되었는지 나타내는 이진 변수 $x_{ig}$. 아이템 $i$와 $j$가 모두 그룹 $g$에 있는지 나타내는 보조 이진 변수 $y_{ijg}$.
   • 메커니즘: 목적 함수는 제약 조건 $y_{ijg} \leq x_{ig}$ 및 $y_{ijg} \leq x_{jg}$를 사용하여 선형화된다.
   • 약점: 선형 계획법(LP) 완화(relaxation)가 약하다. 완화 과정에서 아이템들이 모든 그룹에 분수 형태로 할당될 수 있어($x_{ig} = 1/|G|$), 목적 함수 값이 가능한 모든 $d_{ij}$ 쌍의 합이 되어, 실행 가능한 정수 해에 도달할 수 없는 상한값을 형성한다.

2. Papenberg and Klau 정식화 (2021):

   • 변수: 아이템 $i$와 $j$가 (어느 그룹인지는 명시하지 않고) 동일한 그룹에 할당되었는지 나타내는 이진 변수 $z_{ij}$.
   • 메커니즘: 일관성을 보장하기 위한 추이성 제약 조건(예: $-z_{ij} + z_{ik} + z_{jk} \leq 1$)과 모든 아이템이 정확히 $|I|/|G| - 1$개의 다른 아이템과 그룹을 이루도록 하는 제약 조건을 사용한다.
   • 강점: 아이템-아이템 할당($z_{ij}$)에 대해 분기(branching)가 일어나며, 이는 목적 함수에 직접적인 영향을 미친다. LP 완화는 훨씬 더 강력한데, 이는 제약 조건이 아이템당 쌍의 수를 그룹 크기로 제한하기 때문이다.
   • 한계: 원래 동일한 크기의 그룹만을 위해 설계되었다.

3. 결합 정식화 (Combined Formulation):

   • 메커니즘: $z_{ij} = \sum_{g \in G} y_{ijg}$를 통해 표준 정식화와 Papenberg and Klau 방식을 결합한다.
   • 기여: 표준 모델에 추이성 제약 조건을 추가하고 다양한 크기의 그룹에 맞게 그룹 크기 제약 조건을 조정한다. 본 논문은 동일한 크기의 그룹에 대해 이 정식화가 적어도 Papenberg and Klau 정식화만큼 강력한 LP 완화를 가짐을 증명한다.

4. 적응형 Papenberg and Klau 정식화 (다양한 그룹 크기용):

   • 메커니즘: "더미 아이템(dummy item)"을 도입하여 다양한 그룹 크기($l_g \neq u_g$)를 처리할 수 있도록 Papenberg and Klau 모델을 확장한다. 아이템들은 더미 아이템(그룹을 나타냄)에 할당된다($z_{i, \text{dummy}}$).
   • 변수: 더미 아이템을 포함한 모든 아이템에 추이성 제약 조건이 적용된다. 각 실제 아이템이 정확히 하나의 더미 그룹에 할당되도록 보장하는 제약 조건과, 각 더미 주변의 클러스터 크기가 $l_g$와 $u_g$를 준수하도록 하는 제약 조건이 포함된다.

주요 기여

• 비교 분석: 아이템-그룹 할당 정식화와 아이템-아이템 할당 정식화에 대한 이론적 및 경험적 비교를 제공한다.
• 이론적 통찰: 아이템-그룹 할당 변수($x_{ig}$)보다 아이템-아이템 할당 변수($z_{ij}$)에 대해 분기하는 것이 더 우월함을 입증한다. 이는 $z_{ij}$가 목적 함수 값을 직접적으로 제한하고 더 타이트한 LP 완화를 제공하기 때문이다.
• 새로운 정식화: 일반적인 그룹 크기 제약을 처리하기 위해 두 가지 새로운 정식화를 제시하여, 더 강력한 아이템-아이템 할당 로직의 적용 가능성을 확장한다.
• 대칭성 깨기 (Symmetry Breaking): 표준 정식화에 대한 대칭성 깨기 제약 조건을 논의하고 일반적인 경우로 전이시킨다.

계산 결과

CPLEX 12.9를 사용하여 1030개의 아이템과 210개의 그룹으로 구성된 인스턴스에 대해 포괄적인 계산 연구를 수행하였다. 동일한 크기의 그룹과 다양한 크기의 그룹 시나리오가 모두 테스트되었다.

• LP 완화 품질: Papenberg and Klau 정식화와 그 변형들은 표준 정식화에 비해 일관되게 훨씬 더 타이트한 상한(작은 갭)을 생성했다. 표준 정식화의 LP 완화 갭은 종종 100%를 넘었으나, 아이템-아이템 정식화는 훨씬 낮은 수준을 유지했다.
• 해결 성능:
  • 동일 크기 그룹: Papenberg and Klau 정식화는 거의 모든 인스턴스를 표준 정식화보다 빠르게 최적해로 해결했다.
  • 다양한 그룹 크기: 적응형 Papenberg and Klau 정식화(섹션 3.4)가 가장 우수한 성능을 보였으며, 1800초의 시간 제한 내에 최대 30개 아이템의 인스턴스를 최적해로 해결하거나 작은 갭을 달성했다.
  • 표준 정식화: 상당한 어려움을 겪었으며, 종종 갭을 좁히지 못하거나 15개 이상의 아이템을 가진 인스턴스를 시간 제한 내에 해결하는 데 실패했다.
  • 결합 정식화: 이론적으로는 강력하지만, $x_{ig}$ 변수에 대해 분기할 때 표준 정식화보다 실질적인 성능 향상을 보이지 못했다. 이는 추이성 제약 조건만으로는 아이템-그룹 분기 전략의 취약성을 극복하기에 불충분함을 시사한다.

의의 및 주장

본 논문은 새로운 정식화의 우수한 성능을 이끄는 주요 동력이 **분기 전략(branching strategy)**이라고 주장한다. 아이템-그룹 할당이 아닌 아이템-아이템 할당에 대해 분기함으로써, 솔버는 추이성 제약 조건이 제공하는 더 강력한 LP 완화 덕분에 탐색 공간을 더 효과적으로 가지치기(pruning)할 수 있다.

연구는 MDGP, 특히 다양한 그룹 크기가 설정된 환경에서 적응형 Papenberg and Klau 정식화가 현재 사용 가능한 가장 효과적인 엄밀해 접근 방식이라고 결론짓는다. 이는 수십 년 된 표준 정식화의 한계를 극복하고 아이템-아이템 할당 로직의 이점을 일반적인 그룹 제약 조건으로 성공적으로 확장한다. 저자들은 적응형 정식화가 가장 우수한 성능을 보이지만, 다양한 그룹 크기를 가진 인스턴스는 솔루션 공간의 유연성 증가로 인해 동일 크기 인스턴스보다 해결하기가 여전히 더 어렵다고 언급했다.