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

  • 0
    Like
  • 0
    Comment

    典型問題と実行方法

    組合せオークション問題

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

    実行方法

    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

    データ

    補足

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