Combinatorial optimization-typical problem-generalized allocation problem

Typical problem and execution method

Generalization allocation problem

$ n $ jobs $ J = \ {1,2, \ dots, n \} $ and $ m $ agents $ I = \ {1,2, \ dots, m \} $ On the other hand, the cost of allocating work $ j \ in J $ to agent $ i \ in I $ $ c_ {ij} $, resource requirement $ a_ {ij} (\ ge 0) $, and each agent The available resource amount $ b_i (\ ge 0) $ of $ i \ in I $ is given. Each job must be assigned to one of the agents, and the total resource requirements for the jobs assigned to each agent must not exceed the available resources of that agent. At this time, find the allocation that minimizes the total cost.

Execution method

usage


Signature: gap(cst, req, cap)
Docstring:
Generalization allocation problem
Solve the minimum cost allocation
input
    cst:Table of costs by agent and job
    req:Request amount table for each agent and job
    cap:List of agent capacities
output
Agent number list for each job

python


from ortoolpy import gap
gap([[2, 2, 2], [1, 1, 1]], [[1, 1, 1], [1, 1, 1]], [2, 1])

result


[0, 0, 1]

python


# pandas.DataFrame
from ortoolpy.optimization import Gap
Gap('data/gap.csv', [2,1])
agent job cost req
0 0 0 2 1
1 0 1 2 1
5 1 2 1 1

data

Recommended Posts

Combinatorial optimization-typical problem-generalized allocation problem
Combinatorial optimization-Typical problem-Secondary allocation problem
Combinatorial optimization-typical problem-knapsack problem
Combinatorial optimization-Typical problem-Vertex cover problem
Combinatorial optimization-Typical problem-Stable matching problem
Combinatorial optimization-typical problem-bin packing problem
Combinatorial optimization-typical problem-maximum matching problem
Combinatorial optimization-typical problem-shortest path problem
Combinatorial optimization-typical problem-combinatorial auction 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-minimum cost flow 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