パーティション $N$ アイテムに $K$ 元のアイテムのグループを保持しながら、同じサイズのパーティション
あるとしましょう $N$ 入ってくるアイテム $M$グループ。しましょう$c_i \in \{1, ..., M\}$ ために $i=1, ..., N$ アイテムのグループメンバーシップを表す $i$。アイテムのより粗いパーティションを見つけたい$K$ 新しいグループ、ここで $K < M$、2つの制約があります：
- 同じグループ内のアイテムは同じパーティションに割り当てる必要があり、
- 新しいグループのサイズは、可能な限り均等にする必要があります。
私の最初の考えは、これを非線形整数計画として定式化することです。 $y_{ij} = 1$ アイテムの場合 $i$ パーティションに割り当てられています $j$それ以外の場合はゼロです。次に、一連の制約があります。
- $\sum_{j=1}^K y_{ij} = 1$ ために $i=1,..., N$ （各アイテムは正確に1つのパーティションに割り当てる必要があります）
- $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ユーザー向けの標準的な選択肢はありますか？（コードサンプルは大歓迎です！）
いくつかの追加の背景：私は本質的に、グループアウトを除外する相互検証のためのより（計算上）効率的なアプローチを探しています。現在の標準では、一度に1つのグループを除外することで、$M$ モデル、ここで $M$かなり高くなる可能性があります。実際には、$K=5$ または $K=10$統計的な目的には十分であり、同じグループの全員が同じフォールドに入り、フォールドがほぼ同じサイズである限り、交差検定には必要なプロパティがあります。だからフィッティング$M >> 10$ 多くのグループがある場合のモデルは、多くの場合、非効率的で不要です。
回答
1つのアプローチは、グループをジョブと見なすことです。各ジョブの期間は、グループ内のアイテムの数に等しくなります。次に、これらのジョブをにスケジュールします$K$ 同一のマシン、メイクスパンを最小化、つまり最小化 $\max_j N_j$。LPTヒューリスティックは高速で、$(2-1/K)$-概算。
最初の質問：IPモデルでは、アイテムとパーティションの組み合わせごとにバイナリ変数は必要ありません。グループを一緒に保持するという要件を考えると、グループとパーティションの組み合わせごとにバイナリが必要です。君の$y_{ij}=y_{\ell j}$制約により、ソルバーの事前解決関数はモデルをこのサイズに縮小しますが、より小さな定式化から始めることもできます。また、問題を2次にするのではなく、線形である最小パーティションサイズと最大パーティションサイズの差を最小限に抑えると思います。これは必ずしも「特に簡単」に解決できるモデルを生成するわけではありませんが、問題の次元とIPソルバー（および忍耐力）によっては、十分に簡単な場合があります。
2番目の質問：IPモデルとIPソルバーを使用して問題を正確に解決できます。かなりうまくいくかもしれない速いヒューリスティックは、$K$ 空のパーティションで、グループをサイズの降順で並べ替えてから、各グループを現在最小のパーティションに割り当てます。
3番目の質問：JuliaまたはPythonについて話すことはできません（Python用のIPソルバーをいくつか知っていますが）が、RIでは、モデルの作成にOMPRパッケージ（LP / IP用のDSL）を使用する傾向があります。OMPRは、モデルを解決するためにROIに依存します。また、OMPRとROIの両方で、ソルバー固有のプラグインをロードする必要があります（もちろん、対応するソルバーをインストールする必要があります）。
OMPRとROIをそれぞれのCPLEXプラグインで使用してRノートブックをハッキングしました。のランダムテスト問題について$N=5700$、 $M=130$ そして $K=10$、私が説明したヒューリスティックは、通常、パーティションサイズのスプレッドが5（567から572の範囲のサイズ）であり、IPモデルはそれぞれ570のパーティションが10個あります（スプレッド= 0）。ヒューリスティックは（小さな）ほんの一瞬でした。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秒未満で完了しました。