##組合せオークション問題
$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 |
##データ
補足
- 金額に微小な乱数を足すことにより、抽選としても機能する。