[PYTHON] Combinatorial optimization --Typical problem-- Partition of a set problem

Typical problem and execution method

Partition of a set 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 division $ X (\ subseteq N) $ of $ M $ that minimizes the sum of costs. The split must not have the same elements in the subset.

Execution method

usage

Signature: set_partition(n, cand)
Docstring:
Partition of a set 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_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])

result

[2, 3]

python

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

python

#Sample data
from ortoolpy import set_partition
set_partition(4, [(1, ('a', 'b')), (1, ('a', 'c')), (1, ('a', 'd')), (3, ('b', 'c'))])

result

[2, 3]

data

• data/subset.csv