조합 최적화 - 일반적인 문제 - 집합 코팅 문제

일반적인 문제와 실행 방법

집합 코팅 문제

집합 $M=\{1,\dots,m\}$의 $n$개의 하위 집합 $S_j(\subseteq M), j\in N=\{1,\dots,n\}$ 비용 $ c_j $가 주어진다고 가정합니다. 비용의 총합이 최소가 되는 $M$의 피복 $X(\subseteq N)$를 찾아라. 코팅은 부분 집합에 동일한 요소를 가질 수 있습니다.

실행 방법

usage

Signature: set_covering(n, cand, is_partition=False)
Docstring:
集合被覆問題
入力
    n: 要素数
    cand: (重み, 部分集合)の候補リスト
出力
    選択された候補リストの番号リスト

파이썬

# CSVデータ
import pandas as pd
from ortoolpy import set_covering
ss = pd.read_csv('data/subset.csv')
g = ss.groupby('id')
set_covering(len(g), [(r.weight.iloc[0], r.element.tolist()) for _, r in g])

결과

[0, 1, 2]

파이썬

# pandas.DataFrame
from ortoolpy.optimization import SetCovering
SetCovering('data/subset.csv')

id
weight
element




0
0
1.0
a


1
0
NaN
b


2
1
1.0
a


3
1
NaN
c


4
2
1.0
a


5
2
NaN
d



파이썬

# サンプルデータ
from ortoolpy import set_covering
set_covering(4, [(1, ('a', 'b')), (1, ('a', 'c')), (1, ('a', 'd')), (3, ('b', 'c'))])

결과

[0, 1, 2]

데이터

data/subset.csv