組合せ最適化 - 典型問題 - 集合分割問題

  • 2
    Like
  • 0
    Comment

典型問題と実行方法

集合分割問題

集合$M=\{1,\dots,m\}$の$n$個の部分集合$S_j(\subseteq M), j \in N=\{1,\dots,n\}$に対してコスト$c_j$が与えられているとする。コストの総和が最小となる$M$の分割$X(\subseteq N)$を求めよ。分割は、部分集合の中に同じ要素があってはいけない。

実行方法

usage
Signature: set_partition(n, cand)
Docstring:
集合分割問題
入力
    n: 要素数
    cand: (重み, 部分集合)の候補リスト
出力
    選択された候補リストの番号リスト
python
# CSVデータ
import pandas as pd
from ortoolpy import set_partition
ss = pd.read_csv('data/subset.csv')
g = ss.groupby('id')
set_partition(len(g), [(r.weight.iloc[0], r.element.tolist()) for _, r in g])
結果
[2, 3]

set.gif

python
# pandas.DataFrame
from ortoolpy.optimization import SetPartition
SetPartition('data/subset.csv')
id weight element
4 2 1.0 a
5 2 NaN d
6 3 3.0 b
7 3 NaN c
python
# サンプルデータ
from ortoolpy import set_partition
set_partition(4, [(1, ('a', 'b')), (1, ('a', 'c')), (1, ('a', 'd')), (3, ('b', 'c'))])
結果
[2, 3]

データ