A Group-Based Resource Allocation Model for the Fractional Knapsack Problem

기술 요약: 분할 배낭 문제(Fractional Knapsack Problem)를 위한 그룹 기반 자원 할당 모델

문제 정의
본 논문은 $n$개의 아이템으로 구성된 유계 분할 배낭 문제(bounded fractional knapsack problem)를 다룬다. 각 아이템은 가치 $v_i$, 비용 $w_i$, 그리고 용량 제한 $u_i \in [0, 1]$를 가지며, 총 예산 $C$의 제약을 받는다. 목표는 $\sum w_i z_i \le C$ 및 $0 \le z_i \le u_i$를 만족하면서 총 가치 $\sum v_i z_i$를 최대화하는 것이다.

표준 해법인 단직(Dantzig)의 탐욕적 규칙(greedy rule)은 효율성 비율 $\rho_i = v_i/w_i$에 따라 아이템을 정렬하고 예산을 내림차순으로 할당한다. 이 방식은 최적이지만, 두 가지 결정적인 문제를 가진다:

1. 불연속성(Discontinuity): 최적 해의 매핑은 리프시츠 연속(Lipschitz continuous)이 아니다. 비용 데이터에 아주 작은 섭동(perturbation)만 발생해도, 예산이 거의 동일한 비율을 가진 두 아이템 사이에서 소진될 경우 할당량이 가용 집합의 극점(extreme vertices) 사이를 급격히 건너뛰게 된다.
2. 가짜 순위(Spurious Ranking): 솔루션은 측정 노이즈와 구별할 수 없을 정도로 미세한 비율 차이에 매우 민감하며, 이는 실제 데이터의 변화를 반영하지 못하는 불안정한 할당으로 이어진다.

방법론
이러한 불안정성을 완화하기 위해, 저자는 2단계 그룹 기반 할당 알고리즘을 제안한다.

1. 지표 그룹화(Metric Grouping): 속성 공간 $(A, d)$를 기반으로 아이템을 그룹으로 분할한다. 속성 거리 $d(a_i, a_j)$가 허용 반경 $\delta$ 이내인 아이템 $i$와 $j$는 하나의 그룹으로 묶인다. 각 그룹 $G_k$ 내의 아이템들은 대표 속성 $b_{a_k}$를 공유하며, 이에 따른 대표 가치 $b_{v_k}$, 대표 비용 $b_{w_k}$, 대표 비율 $b_{\rho_k}$를 갖는다.
2. 1단계 (그룹 간 할당): 그룹들을 대표 비율 $b_{\rho_k}$에 따라 내림차순으로 정렬한다. 예산이 소진될 때까지 순차적으로 그룹에 예산 몫을 할당한다. 예산이 소진되는 지점의 그룹을 "경계 그룹($\Gamma$)"으로 지정한다. 앞선 모든 그룹은 전액 펀딩되며, 뒤따르는 모든 그룹은 0을 받는다.
3. 2단계 (그룹 내 할당): 경계 그룹 $\Gamma$에 대해, 할당된 예산 몫을 추가적인 순위 결정 없이 내부 멤버들에게 배분한다. 이 배분은 "그룹 내 규칙"(타당성, 예산 클리어런스, 균등 보호)을 따르며, 수학적으로는 "워터 필링(water-filling)" 메커니즘과 동일하다. 구체적으로, $\sum_{i \in \Gamma} w_i \min(u_i, \zeta) = c^*$를 만족하는 할당 수준 $\zeta$를 찾는다 (여기서 $c^*$는 잔여 예산이다). $\Gamma$ 내의 모든 아이템은 $\min(u_i, \zeta)$만큼을 할당받는다.

주요 기여 및 이론적 보장

• 안정성 (리프시츠 연속성): 정확한 탐욕적 해법과 달리, 그룹화된 할당은 인접한 그룹 간의 분리 마진 내에서 비용 섭동에 대해 리프시츠 연속성을 가진다. 연속성 계수는 $K/w_{\min}$으로 제한되며, 여기서 $K$는 최대 그룹 크기이다. 이는 할당이 노이즈로 인해 급격하게 변하지 않음을 보장한다.
• 손실 경계 (Loss Bounds):
  • 그룹 내 손실: 그룹 내 손실은 그룹의 용량 $U_G$와 상대적 비용 변동 $(w_+ - w_-)/(w_+ + w_-)$에 비례하는 항, 그리고 가치 변동을 위한 항에 의해 제한된다. 이 경계는 타이트(tight)함이 입증되었다.
  • 전역 손실: 그룹화가 "순서 호환적(order-compatible)"인 경우(즉, 그룹의 비율 구간이 서로 분리되어 있고 엄격히 감소하는 경우), 총 손실 $E(C)$는 전적으로 경계 그룹 $\Gamma$ 내에 국한된다. 상대적 손실은 $O(K/n)$의 척도를 가지며, 이는 그룹 크기 $K$가 유계일 때 아이템 수 $n$이 증가함에 따라 오차가 감소함을 의미한다.
  • 비순서 호환적 경우: 그룹 비율 구간이 최대 $\omega$만큼 겹치는 경우, 오차 경계에 $\omega C$라는 가산 항이 도입된다.
• 복잡도: 알고-리즘은 $O(n + m \log m + |\Gamma| \log |\Gamma|)$ 시간 내에 할당을 계산한다 (여기서 $m$은 그룹의 수이다). 만약 선형 시간 선택(linear-time selection)을 통해 경계 그룹을 식별하면 복잡도는 $O(n + m \log m)$으로 낮아진다. 대표 비율이 이미 정렬되어 있다면 $O(n)$을 달성한다.

실험 결과
저자는 무작위로 생성된 인스턴스에 대해 단직의 탐욕적 규칙과 제안된 방법을 비교 평가하였다.

• 인스턴스 크기($n$) 대비 손실: 고정된 허용 오차 $\delta$에 대해, $n$이 매우 작을 때(그룹이 단일 원소인 경우) 상대적 손실은 0이다. $n$이 커짐에 따라 손실은 상승하다가 일정한 고원(plateau) 상태(실험상 약 6%)에서 안정화된다. 이는 손실이 $\delta$에 의존하지만, 대규모 인스턴스에서는 $n$과는 독립적이라는 이론적 예측을 확인시켜 준다.
• 허용 오차($\delta$) 대비 손실: 손실은 $\delta$에 따라 다항식 형태로 증가한다. $\delta$가 매우 작으면 손실은 무시할 수 있는 수준이며 사실상 정확한 최적해와 일치한다. $\delta$가 증가함에 따라 손실도 증가하며, 그룹화가 단일 그룹으로 붕괴되는 지점에 도달하면 손실은 포화 상태가 된다.
• 실행 시간: 그룹화된 방법은 단직의 규칙과 유사한 경험적 성장률을 보인다. 작은 인스턴스에서는 그룹화 및 정렬로 인한 상수 오버헤드가 발생하지만, 대규모 $n$($10^6$까지)에 대해서는 실행 시간이 거의 구별되지 않으며, 그룹화된 방법이 최대 2배 정도 느릴 뿐이다.

의의 및 주장
본 논문은 그룹 기반 할당 모델이 최적성과 안정성 사이의 실용적인 절충안을 제공한다고 주장한다. 속성 차이가 임계값 $\delta$ 미만인 아이템들의 순위를 매기기를 거부함으로써, 이 방법은 측정 노이즈에 대한 정확한 해법의 가짜 민감성을 제거한다. 저자는 이 접근 방식이 다음을 수행한다고 단언한다:

1. 가용 영역과 목적 함수를 보존하면서, 그룹 내부의 할당 규칙만을 제한한다.
2. 정확한 해법에는 없는 유한한 섭동 몫(리프시츠 상수)을 제공한다.
3. 표준 탐욕적 접근법과 대등한 계산 효율성을 유지하여, 데이터 정밀도가 제한적인 대규모 응용 분야에서도 활용 가능하다.

이 연구는 수학적 프로그래밍의 다면체 민감도 분석(polyhedral sensitivity analysis)과 집계 기술(aggregation techniques) 사이의 가교 역할을 하며, 시스템적 안정성을 얻기 위해 약간의 최적성 손실을 감수하는 "공정성의 대가(price of fairness)"를 제시한다.