Python
数学
最適化
組合せ最適化

組合せ最適化 - 典型問題 - 組合せオークション問題

典型問題と実行方法

組合せオークション問題

$n$個の候補(集合$M=\{1,\dots,m\}$の部分集合$S_j(\subseteq M), j \in N=\{1,\dots,n\}$)に対して金額$c_j$が与えられているとする。金額の総和が最大となるように候補から選択せよ。
集合$M$の要素を重複して選んではいけない
集合被覆問題で目的関数が最大化で、制約条件の不等号が逆になったものと考えることもできる。

実行方法

usage
Signature: combinatorial_auction(n, cand, limit=-1)
Docstring:
組合せオークション問題
    要素を重複売却せず、購入者ごとの候補数上限を超えないように売却金額を最大化
入力
    n: 要素数
    cand: (金額, 部分集合, 購入者ID)の候補リスト。購入者IDはなくてもよい
    limit: 購入者ごとの候補数上限。-1なら無制限。購入者IDをキーにした辞書可
出力
    選択された候補リストの番号リスト
python
# サンプル
from ortoolpy import combinatorial_auction
cand = [
    ( 15, (0,2), 0),
    ( 10, (0,), 1),
    (  8, (1,), 1),
    ( 14, (1,2), 2),
]
combinatorial_auction(3, cand)
結果
[1, 3]
python
# pandas.DataFrame
from ortoolpy.optimization import CombinatorialAuction
CombinatorialAuction('data/auction.csv')
id price element buyer
2 1 10.0 a 1
4 3 14.0 b 1
5 3 NaN c 1
python
# pandas.DataFrame
from ortoolpy.optimization import CombinatorialAuction
CombinatorialAuction('data/auction.csv',limit=1)
id price element buyer
0 0 15.0 a 0
1 0 NaN c 0
3 2 8.0 b 2

データ

補足

  • 金額に微小な乱数を足すことにより、抽選としても機能する。