Typical problem and execution method
$ n $ Candidates (set $ M = \ {1, \ dots, m \} $ subset $ S_j (\ subseteq M), j \ in N = \ {1, \ dots, n \ } $) Is given the amount $ c_j $. Select from the candidates so that the total amount of money is maximized. Do not select duplicate elements of the set $ M $ It can also be considered that the objective function is maximized and the constraint inequality sign is reversed in Set Cover Problem.
usage
Signature: combinatorial_auction(n, cand, limit=-1)
Docstring:
Combination auction problem
Maximize the sale price so that the maximum number of candidates for each purchaser is not exceeded without duplicate selling of elements
input
n:Element count
cand: (Amount of money,Subset,Buyer ID)Candidate list. You do not have to have a purchaser ID
limit:Maximum number of candidates for each purchaser.-1 is unlimited. A dictionary using the purchaser ID as a key is possible
output
Number list of selected candidate list
python
#sample
from ortoolpy import combinatorial_auction
cand = [
( 15, (0,2), 0),
( 10, (0,), 1),
( 8, (1,), 1),
( 14, (1,2), 2),
]
combinatorial_auction(3, cand)
result
[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 |
--By adding a small random number to the amount of money, it also functions as a lottery.
Recommended Posts