from ortools.linear_solver.pywraplp import Solver

# cost[c][j] = cost for CPU c to run job j
cost = [[90, 76, 75, 70],
        [35, 85, 55, 65],
        [125, 95, 90, 105],
        [45, 110, 95, 115],
        [60, 105, 80, 75],
        [45, 65, 110, 95]]

clusters = [
    [0, 2, 4],
    [1, 3, 5]
]

num_cpus = len(cost)
num_jobs = len(cost[0])

solver = Solver('mip_debug', Solver.CBC_MIXED_INTEGER_PROGRAMMING)

# x[c, j] if CPU c gets job j
x = {}
for c in range(num_cpus):
    for j in range(num_jobs):
        x[c, j] = solver.IntVar(0, 1, f'cpu {c} gets job {j}')

# Each cpu gets at most one job
for c in range(num_cpus):
    solver.Add(
        sum(x[c, j] for j in range(num_jobs)) == 1
    )

# Each job gets exactly one CPU
for j in range(num_jobs):
    solver.Add(
        sum(x[c, j] for c in range(num_cpus)) == 1
    )

# Each cluster gets at most two jobs
for cluster in clusters:
    solver.Add(
        sum(x[c, j] for c in cluster for j in range(num_jobs)) <= 2
    )

total_cost = sum(x[c, j] * cost[c][j] for c in range(num_cpus) for j in range(num_jobs))
solver.Minimize(total_cost)

if solver.Solve() == Solver.OPTIMAL:
    print([v for v in x.values() if v.solution_value() == 1])
    print('Min cost:', total_cost.solution_value())
else:
    print('No solution!')