[PYTHON] 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]

set.gif

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

Combinatorial optimization-typical problem-set cover problem
Combinatorial optimization-Typical problem-Vertex cover problem
Combinatorial optimization-typical problem-knapsack problem
Combinatorial optimization-typical problem-n-dimensional packing problem
Combinatorial optimization-Typical problem-Stable matching problem
Combinatorial optimization-typical problem-generalized allocation problem
Combinatorial optimization-typical problem-bin packing problem
Combinatorial optimization-Typical problem-Secondary allocation problem
Combinatorial optimization-typical problem-combinatorial auction problem
Combinatorial optimization-typical problem-maximum flow problem
Combinatorial optimization-typical problem-weight matching problem
Combinatorial optimization-Typical problem-Facility placement problem
Combinatorial optimization-typical problem-job shop problem
Combinatorial optimization-typical problem-maximum cut problem
Combinatorial optimization-typical problem-traveling salesman problem
Combinatorial optimization-typical problem-work scheduling problem
Combinatorial optimization-Typical problem-Minimum spanning tree problem
Combinatorial optimization-Typical problem-Maximum stable set problem
Combinatorial optimization-typical problem-minimum cost flow problem
Combinatorial optimization-Typical problem-Transportation route (delivery optimization) problem
Combinatorial optimization-minimum cut problem
Combinatorial optimization-typical problems and execution methods