Combinatorial optimization-typical problem-set cover problem
Typical problem and execution method
Set cover problem
$ N $ subsets of the set $ M = \ {1, \ dots, m \} $ $ S_j (\ subseteq M), j \ in N = \ {1, \ dots, n \} Suppose a cost of $ c_j $ is given to $. Find the cover $ X (\ subseteq N) $ of $ M $ that minimizes the sum of costs. The coating may have the same elements in the subset.
Execution method
usage
Signature: set_covering(n, cand, is_partition=False)
Docstring:
Set cover problem
input
n:Element count
cand: (weight,Subset)Candidate list
output
Number list of selected candidate list
python
#CSV data
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])
result
[0, 1, 2]
python
# 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 |
python
#Sample data
from ortoolpy import set_covering
set_covering(4, [(1, ('a', 'b')), (1, ('a', 'c')), (1, ('a', 'd')), (3, ('b', 'c'))])
result
[0, 1, 2]
data
Recommended Posts