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

典型問題と実行方法

組合せオークション問題

$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

データ

• data/auction.csv

補足

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