LoginSignup
6

More than 5 years have passed since last update.

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

Last updated at Posted at 2017-08-03

典型問題と実行方法

組合せオークション問題

$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

データ

補足

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
6