Determine recorded programs by combinatorial optimization
Job assignment problem
Consider allocating multiple jobs to multiple resources. Certain work pairs cannot be assigned to the same resource. Maximize the sum of the values of selected jobs.
Here is a concrete example.
--There are some broadcast programs that you want to record. --There are some recordable devices. ――It is not possible to record programs with overlapping broadcast times on the same device. (Simultaneous recording prohibited) --Maximize the total value of recorded programs.
Way of thinking
Consider the following 5 programs. Suppose you have three recording devices.
| name | Start time | End time | value |
|---|---|---|---|
| A | 9:00 | 9:30 | 1 |
| B | 9:30 | 10:00 | 1 |
| C | 9:00 | 10:00 | 1 |
| D | 9:00 | 9:30 | 1 |
| E | 9:30 | 10:00 | 1 |
Consider a graph with a program as a node and simultaneous recording prohibited as an edge.
Consider a new graph that duplicates this graph for each device, and create edges between the same programs.
By solving the maximum stable set problem on this graph, it is possible to find a solution that "satisfies the simultaneous recording prohibition and records the same program only on one device", so which program should be recorded on which device? I know if it's good.
Try to solve with Python
python3
import networkx as nx
from itertools import combinations
from more_itertools import grouper
from ortoolpy import maximum_stable_set, Autodict
g = nx.Graph()
dc = Autodict()
for i in 'ABCDE':
for j in'123':
g.add_node(dc[i+j], weight=1)
for i, j in grouper(2, 'ACADBCBECDCE'):
for k in '123':
g.add_edge(dc[i+k], dc[j+k])
for i in 'ABCDE':
for j, k in combinations('123', 2):
g.add_edge(dc[i+j], dc[i+k])
print([dc.keys[i] for i in maximum_stable_set(g)[1]])
>>>
['A1', 'B3', 'C2', 'D3', 'E1']
You can see that you can record A and E on device 1, C on device 2, and B and D on device 3.
that's all
Recommended Posts