1#!/usr/bin/env python3 2# Copyright 2010-2021 Google LLC 3# Licensed under the Apache License, Version 2.0 (the "License"); 4# you may not use this file except in compliance with the License. 5# You may obtain a copy of the License at 6# 7# http://www.apache.org/licenses/LICENSE-2.0 8# 9# Unless required by applicable law or agreed to in writing, software 10# distributed under the License is distributed on an "AS IS" BASIS, 11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12# See the License for the specific language governing permissions and 13# limitations under the License. 14# [START program] 15"""Solve assignment problem for given group of workers.""" 16# [START import] 17from ortools.linear_solver import pywraplp 18# [END import] 19 20 21def main(): 22 # Data 23 # [START data] 24 costs = [ 25 [90, 76, 75, 70, 50, 74], 26 [35, 85, 55, 65, 48, 101], 27 [125, 95, 90, 105, 59, 120], 28 [45, 110, 95, 115, 104, 83], 29 [60, 105, 80, 75, 59, 62], 30 [45, 65, 110, 95, 47, 31], 31 [38, 51, 107, 41, 69, 99], 32 [47, 85, 57, 71, 92, 77], 33 [39, 63, 97, 49, 118, 56], 34 [47, 101, 71, 60, 88, 109], 35 [17, 39, 103, 64, 61, 92], 36 [101, 45, 83, 59, 92, 27], 37 ] 38 # [END data] 39 40 # Allowed groups of workers: 41 # [START allowed_groups] 42 group1 = [ # Subgroups of workers 0 - 3 43 [2, 3], 44 [1, 3], 45 [1, 2], 46 [0, 1], 47 [0, 2], 48 ] 49 50 group2 = [ # Subgroups of workers 4 - 7 51 [6, 7], 52 [5, 7], 53 [5, 6], 54 [4, 5], 55 [4, 7], 56 ] 57 58 group3 = [ # Subgroups of workers 8 - 11 59 [10, 11], 60 [9, 11], 61 [9, 10], 62 [8, 10], 63 [8, 11], 64 ] 65 66 allowed_groups = [] 67 for workers_g1 in group1: 68 for workers_g2 in group2: 69 for workers_g3 in group3: 70 allowed_groups.append(workers_g1 + workers_g2 + workers_g3) 71 # [END allowed_groups] 72 73 # [START solves] 74 min_val = 1e6 75 total_time = 0 76 for group in allowed_groups: 77 res = assignment(costs, group) 78 status_tmp = res[0] 79 solver_tmp = res[1] 80 x_tmp = res[2] 81 if status_tmp == pywraplp.Solver.OPTIMAL or status_tmp == pywraplp.Solver.FEASIBLE: 82 if solver_tmp.Objective().Value() < min_val: 83 min_val = solver_tmp.Objective().Value() 84 min_group = group 85 min_solver = solver_tmp 86 min_x = x_tmp 87 total_time += solver_tmp.WallTime() 88 # [END solves] 89 90 # Print best solution. 91 # [START print_solution] 92 if min_val < 1e6: 93 print(f'Total cost = {min_solver.Objective().Value()}\n') 94 num_tasks = len(costs[0]) 95 for worker in min_group: 96 for task in range(num_tasks): 97 if min_x[worker, task].solution_value() > 0.5: 98 print(f'Worker {worker} assigned to task {task}.' + 99 f' Cost = {costs[worker][task]}') 100 else: 101 print('No solution found.') 102 print(f'Time = {total_time} ms') 103 # [END print_solution] 104 105 106def assignment(costs, group): 107 """Solve the assignment problem for one allowed group combinaison.""" 108 num_tasks = len(costs[1]) 109 # Solver 110 # [START solver] 111 # Create the mip solver with the SCIP backend. 112 solver = pywraplp.Solver.CreateSolver('SCIP') 113 # [END solver] 114 115 # Variables 116 # [START variables] 117 # x[worker, task] is an array of 0-1 variables, which will be 1 118 # if the worker is assigned to the task. 119 x = {} 120 for worker in group: 121 for task in range(num_tasks): 122 x[worker, task] = solver.BoolVar(f'x[{worker},{task}]') 123 # [END variables] 124 125 # Constraints 126 # [START constraints] 127 # The total size of the tasks each worker takes on is at most total_size_max. 128 for worker in group: 129 solver.Add( 130 solver.Sum([x[worker, task] for task in range(num_tasks)]) <= 1) 131 132 # Each task is assigned to exactly one worker. 133 for task in range(num_tasks): 134 solver.Add(solver.Sum([x[worker, task] for worker in group]) == 1) 135 # [END constraints] 136 137 # Objective 138 # [START objective] 139 objective_terms = [] 140 for worker in group: 141 for task in range(num_tasks): 142 objective_terms.append(costs[worker][task] * x[worker, task]) 143 solver.Minimize(solver.Sum(objective_terms)) 144 # [END objective] 145 146 # Solve 147 # [START solve] 148 status = solver.Solve() 149 # [END solve] 150 151 return [status, solver, x] 152 153 154if __name__ == '__main__': 155 main() 156# [END program] 157