[PYTHON] Combinatorial optimization-typical problem-combinatorial auction problem

Typical problem and execution method

Combination auction problem

$ 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.

Execution method

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

data

Supplement

--By adding a small random number to the amount of money, it also functions as a lottery.

Recommended Posts

Combinatorial optimization-typical problem-combinatorial auction problem
Combinatorial optimization-typical problem-knapsack problem
Combinatorial optimization-typical problem-n-dimensional packing problem
Combinatorial optimization-Typical problem-Stable matching problem
Combinatorial optimization-typical problem-generalized allocation problem
Combinatorial optimization-typical problem-bin packing problem
Combinatorial optimization-typical problem-maximum matching problem
Combinatorial optimization-Typical problem-Secondary allocation problem
Combinatorial optimization-typical problem-shortest path problem
Combinatorial optimization-typical problem-maximum flow problem
Combinatorial optimization-typical problem-set cover problem
Combinatorial optimization-typical problem-weight matching problem
Combinatorial optimization-Typical problem-Facility placement problem
Combinatorial optimization-typical problem-job shop problem
Combinatorial optimization-typical problem-maximum cut problem
Combinatorial optimization-typical problem-traveling salesman problem
Combinatorial optimization-typical problem-work scheduling problem
Combinatorial optimization-Typical problem-Minimum spanning tree problem
Combinatorial optimization-Typical problem-Maximum stable set problem
Combinatorial optimization-typical problem-Chinese postal delivery problem
Combinatorial optimization-Typical problem-Transportation route (delivery optimization) problem
Combinatorial optimization-minimum cut problem
Combinatorial optimization-Typical problem-Facility placement problem with no capacity constraints
Combinatorial optimization-typical problems and execution methods