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

Consider a new graph that duplicates this graph for each device, and create edges between the same programs. image

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