분할 $N$ 항목에 $K$ 원본 항목에 그룹을 유지하면서 동일한 크기의 파티션
거기에 있다고 가정하십시오 $N$ 들어오는 항목 $M$여러 떼. 허락하다$c_i \in \{1, ..., M\}$ ...에 대한 $i=1, ..., N$ 항목에 대한 그룹 구성원을 나타냅니다. $i$. 항목의 더 거친 파티션을 찾고 싶습니다.$K$ 새 그룹, 여기서 $K < M$, 두 가지 제약 조건 :
- 동일한 그룹의 항목은 동일한 파티션에 할당되어야합니다.
- 새 그룹 크기는 가능한 한 균등해야합니다.
내 초기 생각은 이것을 비선형 정수 프로그램으로 공식화하는 것입니다. $y_{ij} = 1$ if 항목 $i$ 파티션에 할당 됨 $j$그렇지 않으면 0입니다. 그런 다음 일련의 제약 조건이 있습니다.
- $\sum_{j=1}^K y_{ij} = 1$ ...에 대한 $i=1,..., N$ (각 항목은 정확히 하나의 파티션에 할당되어야합니다.)
- $y_{ij} = y_{\ell j}$ 모든 $j=1, ..., K$ 만약 $c_i = c_\ell$ (같은 그룹의 항목은 동일한 파티션에 할당되어야합니다.)
그런 다음 정의 할 수 있습니다. $N_j = \sum_{i=1}^N y_{ij}$ 최소화
$$\sum_{j=1}^K \left(N_j - \frac NK \right)^2.$$
그러나 여기서 특정 목표는 실제로 중요하지 않습니다. 한$N_j$ 에 가깝다 $N/K$ 모든 $j$, 나는 그것이 $\ell_2$ 또는 $\ell_1$ 그 라인을 따라 모호하게 감각이나 다른 것을.
내 질문 :
- 특히 쉬운 해결책으로이 문제에 대한 더 나은 공식이 있습니까?
- 이 문제를 정확히 해결하는 알고리즘은 무엇입니까? 욕심 많은 근사 솔루션을 얻을 수있는 방법이 있습니까?
- 내 솔루션을 얻기 위해 기존 최적화 소프트웨어를 활용해야한다고 생각합니다. Python / Julia / R 사용자를위한 표준 선택이 있습니까? (코드 샘플은 대단히 감사합니다!)
몇 가지 추가 배경 : 본질적으로 탈퇴 그룹-아웃 교차 검증에 대한보다 (계산적으로) 효율적인 접근 방식을 찾고 있습니다. 현재 표준은 한 번에 한 그룹 만 남겨 두는 것입니다.$M$ 모델, 어디서 $M$상당히 높을 수 있습니다. 실제로는$K=5$ 또는 $K=10$통계적 목적으로 충분하며 교차 검증은 동일한 그룹의 모든 사람이 동일한 접기에 들어가고 접기가 거의 동일한 크기 인 한 우리가 원하는 속성을 갖습니다. 그래서 피팅$M >> 10$ 그룹이 많을 때 모델은 종종 비효율적이고 불필요합니다.
답변
한 가지 접근 방식은 각 작업의 기간이 해당 그룹의 항목 수와 동일한 작업으로 그룹을 생각하는 것입니다. 이제 이러한 작업을$K$ 동일한 기계, makespan 최소화, 즉 최소화 $\max_j N_j$. LPT 휴리스틱은 빠르며$(2-1/K)$-근사.
첫 번째 질문 : IP 모델에서는 항목과 파티션의 각 조합에 대해 이진 변수가 필요하지 않습니다. 그룹이 함께 유지되어야한다는 요구 사항을 감안할 때 그룹과 파티션의 각 조합에 대해 바이너리가 필요합니다. 너의$y_{ij}=y_{\ell j}$제약 조건을 사용하면 솔버의 사전 해결 기능이 모델을이 크기로 축소 할 수 있지만 더 작은 공식으로 시작하는 것이 좋습니다. 또한 문제를 2 차로 만드는 것보다 최소 파티션 크기와 최대 파티션 크기의 차이를 최소화 할 것입니다. 이는 선형입니다. 이것은 반드시 풀기 "특히 쉬운"모델을 생성하지는 않지만, 문제의 차원과 IP 솔버 (및 인내심)에 따라 충분히 쉬울 수 있습니다.
두 번째 질문 : IP 모델과 IP 솔버를 사용하여 문제를 정확하게 해결할 수 있습니다. 합리적으로 잘 수행 할 수있는 빠른 휴리스틱은 다음으로 시작하는 것입니다.$K$ 파티션을 비우고 그룹을 내림차순으로 정렬 한 다음 각 그룹을 현재 가장 작은 파티션에 할당합니다.
세 번째 질문 : Julia 또는 Python에 대해 말할 수는 없지만 (Python 용 IP 솔버에 대해 알고 있지만) RI에서는 모델 작성을 위해 OMPR 패키지 (LP / IP 용 DSL)를 사용하는 경향이 있습니다. OMPR은 모델을 해결하기 위해 ROI에 의존하며, OMPR과 ROI는 모두 솔버 별 플러그인을로드해야합니다 (물론 해당 솔버를 설치해야 함).
각 CPLEX 플러그인과 함께 OMPR 및 ROI를 사용하여 R 노트북을 해킹했습니다. 무작위 테스트 문제에서$N=5700$, $M=130$ 과 $K=10$, 내가 설명한 휴리스틱은 일반적으로 5의 파티션 크기 분산 (567에서 572 범위의 크기)을 얻었으며 IP 모델은 각각 570 개의 파티션 10 개 (spread = 0)를 얻었습니다. 휴리스틱은 1 초도 걸리지 않았습니다. IP 모델을 빌드하고 CPLEX로 해결하는 데 약 9 초가 걸렸습니다.
항상 그렇듯이 마일리지는 다양합니다.
부록 : 문제 차원에 반올림 숫자를 사용하는 것이 상황을 더 좋게 만들 수 있다고 의심했기 때문에 $N=5723$, $M=137$ 과 $K=10$(모든 파티션 크기가 동일한 솔루션이 없음을 보장). IP 솔루션은 1 개의 스프레드를 관리했습니다 (일부 파티션에는 572 개 항목이 있고 일부에는 573 개 항목이있어 일반적으로 달성 할 수 있다고 생각하는 것보다 여전히 낫습니다). 휴리스틱 솔루션의 분산은 30 개입니다 (파티션 크기는 552에서 582까지).
부록 2 : Rob이 LPT 휴리스틱이라고 부르는 후에 쌍별 교환 휴리스틱을 추가했습니다. 예제에서$N=5723$등, 쌍별 스왑 휴리스틱은 스프레드를 30에서 2로 줄 였지만 최적은 아니지만 (최적은 1) 훨씬 더 가깝습니다. LPT와 마찬가지로 스와핑 휴리스틱은이 예제에서 1 초도 채 걸리지 않았습니다.