How can I solve this algorithmic task in Python?

Question

I am trying to solve this task:

There are three datasets: first data on offices in cities: each city has a certain number of offices and each office has its own capacity of employees. Second, data on teams and open positions in these teams. Third, data on candidates for positions, showing their id, city and position.

We have to allocate applicants across teams and offices in such a way as to maximize the number of employees of one team located in one office together. At the same time, we have to minimize number of cases when there are less than two employees of a certain team in a certain office.

Example:

Input:

city_data:

    city          office_id           capacity
 New York           A                     3
 New York           B                     2
 New York           C                     6
 Boston             D                     2
 Boston             E                     5

team_data:

team_id         position
alpha            Manager
alpha            Manager
alpha            Engineer
alpha            Engineer
alpha            Engineer
alpha            Engineer
alpha            Designer
beta             Engineer
beta             Engineer
beta             Engineer
gamma            Designer
gamma            Engineer

employees_data:

employee_id               city                  position
1                        New York              Manager
2                        New York              Manager
3                        New York              Engineer
4                        New York              Engineer
5                        New York              Engineer
6                        New York              Engineer
7                        New York              Engineer
8                        New York              Designer
9                        New York              Designer
10                       Boston                Engineer
11                       Boston                Engineer
12                       Boston                Engineer

Possible output:

team_id      employee_id          position           city            office_id
alpha            1                Manager         New York              C
alpha            2                Manager         New York              C
alpha            3                Engineer         New York             C
alpha            4                Engineer         New York             C
alpha            5                Engineer         New York             C
alpha            6                Engineer         New York             B
alpha            8                Designer         New York             B
beta             10               Engineer         Boston               E
beta             11               Engineer         Boston               E
beta             12               Engineer         Boston               E
gamma            9                 Designer        New York             A
gamma            7                 Engineer        New York             A

I tried to solve this way:

1. Sort the employee_data in decreasing order of the count of employees for each position and city.
2. For each city and position, assign the employee_id to the team_id and office_id with the maximum capacity until it reaches the capacity limit.
3. Repeat the step 2 until all employees are assigned to the team_id and office_id.

And wrote this code:

from collections import defaultdict
def allocate_employees(city_data, team_data, employee_data):
    city_office_capacity = defaultdict(dict)
    for city, office, capacity in city_data:
        city_office_capacity[city][office] = capacity
team_positions = defaultdict(list)
for team, position in team_data:
    team_positions[team].append(position)

employee_allocations = []
for employee, city, position in employee_data:
    max_capacity = 0
    max_office = None
    for office, capacity in city_office_capacity[city].items():
        if capacity > max_capacity:
            max_capacity = capacity
            max_office = office
    city_office_capacity[city][max_office] -= 1
    for team, positions in team_positions.items():
        if position in positions:
            employee_allocations.append((team, employee, position, city, max_office))
            break
return employee_allocations


city_data = [("New York", "A", 3),
             ("New York", "B", 2),
             ("New York", "C", 6),
             ("Boston", "D", 2),
             ("Boston", "E", 5)]
team_data = [("alpha", "Manager"),
             ("alpha", "Manager"),
             ("alpha", "Engineer"),
             ("alpha", "Engineer"),
             ("alpha", "Engineer"),
             ("alpha", "Engineer"),
             ("alpha", "Designer"),
             ("beta", "Engineer"),
             ("beta", "Engineer"),
             ("beta", "Engineer"),
             ("gamma", "Designer"),
             ("gamma", "Engineer")]
employee_data = [(1, "New York", "Manager"),
                 (2, "New York", "Manager"),
                 (3, "New York", "Engineer"),
                 (4, "New York", "Engineer"),
                 (5, "New York", "Engineer"),
                 (6, "New York", "Engineer"),
                 (7, "New York", "Engineer"),
                 (8, "New York", "Designer"),
                 (9, "New York", "Designer"),
                 (10, "Boston", "Engineer"),
                 (11, "Boston", "Engineer"),
                 (12, "Boston", "Engineer")]
allocate_employees(city_data, team_data, employee_data)

But I get the wrong output:

[('alpha', 1, 'Manager', 'New York', 'C'),
 ('alpha', 2, 'Manager', 'New York', 'C'),
 ('alpha', 3, 'Engineer', 'New York', 'C'),
 ('alpha', 4, 'Engineer', 'New York', 'A'),
 ('alpha', 5, 'Engineer', 'New York', 'C'),
 ('alpha', 6, 'Engineer', 'New York', 'A'),
 ('alpha', 7, 'Engineer', 'New York', 'B'),
 ('alpha', 8, 'Designer', 'New York', 'C'),
 ('alpha', 9, 'Designer', 'New York', 'A'),
 ('alpha', 10, 'Engineer', 'Boston', 'E'),
 ('alpha', 11, 'Engineer', 'Boston', 'E'),
 ('alpha', 12, 'Engineer', 'Boston', 'E')]

I tried a greedy algorithm here, but maybe integer programming will do better, for example?

Answer 1

Here is solution with a MIP, based on a multicommodity flow formulation. A commodity is a "city-position" couple. Consider the following multipartite network with 5 layers:

1. the candidate layer with nodes $V_1=\{\text{NewYork-Manager}, \text{NewYork-Engineer}, \text{NewYork-Designer}, \text{Boston-Engineer}\}$
2. the position layer with nodes $V_2=\{\text{Manager}, \text{Engineer}, \text{Designer}\}$
3. the team layer with nodes $V_3=\{\alpha, \beta, \gamma\}$
4. the office layer with nodes $V_4=\{\text{A},\text{B},\text{C},\text{D},\text{E}\}$
5. the city layer with nodes $V_5=\{\text{NewYork},\text{Boston}\}$

Each from one layer to another are add to the graph based on the data. The network is illustrated below (with obvious abreviations or labels):

What does not appear in the graph is the fact that some edges are not allowed for some commodities. For example, between nodes $\alpha$ (or $a$ in the illustration) and $\textit{A}$, there is no existing edge for commodity $\text{BO-Eng}$, because such a commodity can only cross node $\text{BO}$ in the cities layer. Below is the network induced by the arcs of commodity $\text{BO-Eng}$ (green) and $\text{NY-Man}$ (red):

Once the network is setup, the model is straightforward: define integer variables $x_{ij}^c \in \mathbb{N}^+$ which denote the number of commodities of type $c$ on arc $(i,j)$. The following constraints must hold:

• Flow conservation: $$ \sum_{i} x_{ij}^c = \sum_{i} x_{ij}^c \quad \forall c, \forall j\neq s,t \tag{1} $$
• Office capacities: $$ \sum_{c} x_{ij}^c \le Q_{ij}\quad \forall (i,j)\in V_4 \times V_5 \tag{2} $$
• Teams requirements: $$ \sum_{c} x_{ij}^c = R_{ij}\quad \forall (i,j)\in V_2 \times V_3 \tag{3} $$
• Given amount of candidates/commodities: $$ x_{sc}^c = N_c \quad \forall c \tag{4} $$

The above is the core model. Now to maximize members of a given team in a given office, introduce binary variable $y_{ij}$ that takes value $1$ if and only if arc $(i,j)\in V_4\times V_5$ is used. The problem is to minimize $\sum_{(i,j)} y_{ij}$ subject to constraints $(1)-(4)$, with the additional constraint $x_{ij}^c\le M y_{ij}$ to link $x$ and $y$ variables. And to ensure no member of a team is by himself in an office, add $$ \sum_c x_{ij}^c \ge 2 y_{ij} \quad \forall (i,j) \in V_3 \times V_4 $$

When I run the model, I get the following solution:

NY,Eng
=======
Eng a 4.0
Eng g 1.0
a C 4.0
g B 1.0
B NY 1.0
C NY 4.0
NY,Man
Man a 2.0
a A 2.0
A NY 2.0
NY,Des
Des a 1.0
Des g 1.0
a C 1.0
g B 1.0
B NY 1.0
C NY 1.0
BO,Eng
Eng b 3.0
b E 3.0
E BO 3.0

Or in terms of teams:

Team  a
======
office A -> 2.0 employees
office C -> 5.0 employees
Team  b
office E -> 3.0 employees
Team  g
office B -> 2.0 employees

Answer 2

you can try with integer programming but we can see if this combinatorics works
In the code put\

from collections import defaultdict
def allocate_employees(city_data, team_data, employee_data):
    city_office_capacity = defaultdict(dict)
    for city, office, capacity in city_data:
        city_office_capacity[city][office] = capacity
team_positions = defaultdict(list)
for team, position in team_data:
    team_positions[team].append(position)

employee_allocations = []    
for employee, city, position in employee_data:
            max_capacity =0;
            max_office = None              
            for office, capacity in city_office_capacity[city].items():
                if capacity > max_capacity:
                    max_capacity = capacity
                    max_office = office

                    for team, positions in team_positions.items():    
                       if position in positions:
                           employee_allocations.append((team, employee, position, city, max_office))
                           #team_positions[team].pop(position)
                           team_positions[team].remove(position)
                           city_office_capacity[city][max_office] -= 1
                           break
                    break       
return employee_allocations

If you choose to go for MIP, here is suggested solution: Sets:
Roles: $ R_r$ Teams: $ T_t$: Role $ R_{rt}$
Office $ O_o$: Capacity $ Cap_o$, City $ Ct_o$
City: $Ct_c$
Employees: $ E_e$: City $Ct_e$: Role $ \tau_{r,e} =1$ if employee has that role r, else 0\

Derived sets:
ET: $ \{(e,t): R_e \in R_t \}$
EO: $\{(e,o): Ct_e \in Ct_o \}$
ETOC = ET$\times$EO Vars:
$ x_{e,t,o} = 1$ if assigned, else 0. No need for city as office-id itself will determine the city
$ z_{to}$ binary: to track of cases where less than 2 employees are assigned per team per ofice

Max $\sum_{eto} x_{eto} - \sum_o\sum_tz_{to}$
s.t.
$ \sum_t \sum_{e\in EO} x_{e,t,o} \le Cap_o \ \ \forall o \in O$
$R_{r,t} \le \sum_o\sum_{e\in ET} \tau_{r,e}x_{e,t,o} \ \ \forall r \in R \ \forall t \in T$: $\tau$ just represents set membership (if employee E if of the role ,R) Can be replaced with set membership logic like EO & ET.

$(2+e) - \sum_e x_{eto} \le 3z_{t,o} $
$\sum_e x_{eto}-(2+e) \le 3(z_{t,o}-1) \ \ \forall t \in T \ \ \forall o \in O$

Using Gurobipy, solves in 0.02 secs, 1 node

#Combos
ETOClist = []
for employee in employee_data:
  for team in team_data:
    if employee[2] == team[1]:
      #tp = employee[0],team[0], employee[2]
      #ETlist.append(tp)
      for office in city_data:
        if employee[1] == office[0]:
          ta = office[1], employee[0],team[0], employee[2]
          ETOClist.append(ta)
ETOCSet = set(ETOClist)
ETOC = tuplelist(ETOCSet)
#EO = tuplelist(ETlist)
TOlist = []
for team in team_data:
  for office in city_data:
    tp = team[0],office[1]
    TOlist.append(tp)
TOSet = set(TOlist)
TO = tuplelist(TOSet)
#Dict from citydata
office,city,cap = multidict({office:[city,capa] for city,office,capa in city_data})
req = {('Manager','alpha'):2,('Engineer','alpha'):4,('Designer','alpha'):1,
       ('Engineer', 'beta'): 3, ('Designer', 'gamma'): 1, ('Engineer', 'gamma'): 1 }
model = Model('Assign')
x = model.addVars(ETOC,vtype='b',name='x')
z = model.addVars(TO,vtype='b',name='z')
M = 100
#Constraints
C1 = model.addConstrs((x.sum(o,'','','') <= cap[o] for o in office),'Capacity')
C2= model.addConstrs((req[r,t] <= x.sum('','*',t,r) for r,t in req),'Req')
#Ensure no employee is assigned to a team unless role is there. redundant
#C3= model.addConstrs((x.sum('','',t,r) <= Mreq[r,t] for r,t in req),'Optional')
C4 = model.addConstrs(2.01 - x.sum(o,'',t,'') <= 3z[t,o] for t,o in TO)
C5 = model.addConstrs(x.sum(o,'',t,'') - 2.01 <= 3(z[t,o]-1) for t,o in TO)
#Prioritizing objectives: P1, P2
P1, P2 = 3,1
obj = P1x.sum() - P2z.sum()
model.setObjective(obj, GRB.MAXIMIZE)
model.optimize()
model.printAttr('x')

Answer 3

I second the integer programming suggestion. But greedy is worth a shot.

I don't have time to give a full implementation, but here is the basic idea.

for all teams from biggest to smallest
    if you can put them entirely colocated in one city
        can you do it without leaving just one employee out?
            put them in the smallest such available city.
for all cities from least open spaces to most:
    how many is the most that can be assigned from one team?
        can you do it without leaving only one out (city or team)?
            do that from the smallest team you can.
        if that is more than 2:
            assign one less than that from the smallest team you can
               (leave one out from the most commonly needed role)
        else:
            assign as many as you can anyways
    repeat until the city is assigned

Answer 4

I put together a solution for the provided data, not sure if my stuff is very scalable, with large datasets. My line of thinking with the data you provided was:

1.) add all employees to a dataframe 2.) assign largest teams to largest cities containing employees 3.) assign city teams to city rooms based on the size of team/room with the condition a room must always have 2 members from a team.

my assign employees to rooms was definitely a hack and slash, conditionals could be reworked or improved on. Regardless the code below will give you the desired output for the datasets you provided.

import pandas as pd
import math
city_data = [("New York", "A", 3), 
             ("New York", "B", 2), 
             ("New York", "C", 6), 
             ("Boston", "D", 2), 
             ("Boston", "E", 5)]
team_data = [("alpha", "Manager"), 
             ("alpha", "Manager"), 
             ("alpha", "Engineer"), 
             ("alpha", "Engineer"), 
             ("alpha", "Engineer"), 
             ("alpha", "Engineer"), 
             ("alpha", "Designer"), 
             ("beta", "Engineer"), 
             ("beta", "Engineer"), 
             ("beta", "Engineer"), 
             ("gamma", "Designer"), 
             ("gamma", "Engineer")]
employee_data = [(1, "New York", "Manager"), 
                 (2, "New York", "Manager"), 
                 (3, "New York", "Engineer"), 
                 (4, "New York", "Engineer"), 
                 (5, "New York", "Engineer"), 
                 (6, "New York", "Engineer"), 
                 (7, "New York", "Engineer"), 
                 (8, "New York", "Designer"), 
                 (9, "New York", "Designer"), 
                 (10, "Boston", "Engineer"), 
                 (11, "Boston", "Engineer"), 
                 (12, "Boston", "Engineer")]
df = pd.DataFrame({
    "team_id" : [],
    "employee_id" : [],
    "position" : [],
    "city" : [],
    "office_id": []
})
def add_employee(employee, df):
    new_employee = pd.DataFrame({
        "team_id" : [''],
        "employee_id" : [employee[0]],
        "position" : [employee[2]],
        "city" : [employee[1]],
        "office_id": [''],
    })
    return pd.concat([df, new_employee], ignore_index=True)
def add_team(team_id, employee_id, df):
    df.loc[df['employee_id'] == employee_id, 'team_id'] = team_id
def assign_employee_to_team(team_data, df):
    current_team= ""
for item in team_data:      
    team = item[0]
    position = item[1]      

    if team != current_team:
        current_team = team
        location = list(get_largest_available_employees_location(team_data, df).keys())[0]

    if location is None:
        employee = df.loc[(df['team_id'] == '') & (df['position'] == position), 'employee_id'].iloc[0]
    else:   
        employee = df.loc[(df['team_id'] == '') & (df['position'] == position) & (df['city'] == location), 'employee_id'].iloc[0]

    add_team(team, employee, df)


def get_largest_available_employees_location(team_data, df):
        return df.loc[df['team_id'] == '', 'city'].value_counts().to_dict()
def add_all_employees(df):
    for employee in employee_data:
        df = add_employee(employee, df)
    return df
def assign_room(employee, room, df):
    df.loc[(df['office_id'] == '') & (df['employee_id'] == employee), 'office_id'] = room
def update_employee_rooms(people_to_add, team_name, city, room_id, df):
    for person in range(people_to_add):
        employee = df.loc[(df['office_id'] == '') & (df['team_id'] == team_name) & (df['city'] == city), 'employee_id'].iloc[0]
        assign_room(employee,room_id,df)
def get_total_team_count_per_city(df):
    return df.value_counts(['team_id', 'city'])
def assign_employee_to_room(city_data, df):
    rooms = sorted(city_data, key=lambda tup: (tup[0], tup[2]), reverse=True)
    teams = get_total_team_count_per_city(df)
    carry_over = 0
for team_info in teams.items():
    team_name = team_info[0][0]
    team_city = team_info[0][1]
    num_of_people = team_info[1]

    for index, item in enumerate(rooms):
        if num_of_people == 0:
            break

        city = item[0]
        room_id = item[1]
        max_size = item[2]

        if max_size == 'FULL':
            continue

        if team_city == city:
            if (math.floor(num_of_people/max_size)) >= 2:
                people_to_add = num_of_people - max_size
                update_employee_rooms(people_to_add, team_name, city, room_id, df)
                num_of_people = num_of_people - people_to_add
            else:
                if (num_of_people - (max_size-1)) < 0:
                    people_to_add = num_of_people
                elif (num_of_people - max_size) == 0:
                    people_to_add = num_of_people
                else:
                    people_to_add = (max_size-1)

                num_of_people = (num_of_people - people_to_add)
                update_employee_rooms(people_to_add, team_name, city, room_id, df)
                rooms[index] = (city, room_id, 'FULL')


df = add_all_employees(df)
assign_employee_to_team(team_data, df)
assign_employee_to_room(city_data, df)
print(df)

Answer 5

I used the library pulp (github) which is nice for linear programming and optimization. It allows to add additional constraints later on (see the # comments), the code is a bit longer and clunky (because I just noticed your question today) but it should do the job:

---

The data:

import pandas as pd
from pulp import *
Load the data
city_data = pd.DataFrame({
    'city': ['New York', 'New York', 'New York', 'Boston', 'Boston'],
    'office_id': ['A', 'B', 'C', 'D', 'E'],
    'capacity': [3, 2, 6, 2, 5]
})
team_data = pd.DataFrame({
    'team_id': ['alpha', 'alpha', 'alpha', 'alpha', 'alpha', 'alpha', 'alpha', 'beta', 'beta', 'beta', 'gamma', 'gamma'],
    'position': ['Manager', 'Manager', 'Engineer', 'Engineer', 'Engineer', 'Engineer', 'Designer', 'Engineer', 'Engineer', 'Engineer', 'Designer', 'Engineer']
})
employees_data = pd.DataFrame({
    'employee_id': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
    'city': ['New York', 'New York', 'New York', 'New York', 'New York', 'New York', 'New York', 'New York', 'New York', 'Boston', 'Boston', 'Boston'],
    'position': ['Manager', 'Manager', 'Engineer', 'Engineer', 'Engineer', 'Engineer', 'Engineer', 'Designer', 'Designer', 'Engineer', 'Engineer', 'Engineer']
})

---

The Code:

# Create a list of cities, offices and teams
cities = city_data['city'].unique()
offices = city_data['office_id'].unique()
teams = team_data['team_id'].unique()
Create a dictionary of office capacities
capacities = dict(zip(city_data['office_id'], city_data['capacity']))
Create a dictionary of employees by city and position
employees = {}
for city in cities:
    for position in team_data['position'].unique():
        employees[(city, position)] = employees_data[(employees_data['city'] == city) & (employees_data['position'] == position)]['employee_id'].tolist()
Create the LP problem
prob = LpProblem("Employee Allocation Problem", LpMaximize)
Create a binary variable for each employee, indicating whether they are assigned to a team
employee_vars = LpVariable.dicts("Employee", [(employee_id, team_id, office_id) for employee_id in employees_data['employee_id']
                                              for team_id in teams for office_id in offices],
                                 cat='Binary')
Create Auxiliary table
df_employee_vars = pd.DataFrame.from_dict(employee_vars, orient='index', columns=['Employee']).reset_index().rename(columns={'index': 'assignment'})  # , index=range(len(employee_vars))
df_employee_vars['employee_id'] = df_employee_vars['assignment'].str[0]
df_employee_vars['team'] = df_employee_vars['assignment'].str[1]
df_employee_vars['office'] = df_employee_vars['assignment'].str[2]
Objective 1: minimize number of offices
employees_in_office = (df_employee_vars['Employee']*df_employee_vars['office']).values
prob += lpSum(-len({y for x in employees_in_office for y in x.values()}))
Objective 2: maximize number of employees of same team in same office
vals = df_employee_vars.groupby(['team', 'office'])['Employee'].sum().values
prob += lpSum(np.mean(vals))
Constraint: each employee can only be assigned to one team and one office
for employee_id in employees_data['employee_id']:
    prob += lpSum([employee_vars[(employee_id, team_id, office_id)] for team_id in teams for office_id in offices]) == 1
Constraint: Each office has a capacity constraint
for office_id in offices:
    for team_id in teams:
        prob += lpSum([employee_vars[(employee_id, team_id, office_id)] for employee_id in employees_data['employee_id']]) <= capacities[office_id]
Constraint: Each office has a capacity constraint
for office_id in offices:
    employees_in_office = df_employee_vars[df_employee_vars['office'].eq(office_id)]['Employee'].values
    prob += lpSum(employees_in_office) <= capacities[office_id]
Constraint: Each team has a capacity constraint
team_capacities = team_data.groupby(['team_id'])['team_id'].count().to_dict()
for team_id, capacity in team_capacities.items():
    employees_in_team = df_employee_vars[df_employee_vars['team'].eq(team_id)]['Employee'].values
    prob += lpSum(employees_in_team) <= capacity
Solve
prob.solve()
Print the status of the solution
print("Status:", LpStatus[prob.status])
Print the optimal objective value
print("Objective value:", value(prob.objective))
Print the optimal variable values
for v in prob.variables():
    if v.varValue == 1:
        print(v.name, "=", v.varValue)

---

The Output:

INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.3 Mb (266494 bytes)
Writing MIP solution to 'C:\Users\...\AppData\Local\Temp\...-pulp.sol'...
Status: Optimal
Objective value: 5
Employee_(1,_'alpha',_'A') = 1
Employee_(10,_'alpha',_'A') = 1
Employee_(11,_'alpha',_'A') = 1
Employee_(12,_'gamma',_'E') = 1
Employee_(2,_'gamma',_'E') = 1
Employee_(3,_'alpha',_'B') = 1
Employee_(4,_'alpha',_'B') = 1
Employee_(5,_'alpha',_'C') = 1
Employee_(6,_'alpha',_'C') = 1
Employee_(7,_'beta',_'E') = 1
Employee_(8,_'beta',_'E') = 1
Employee_(9,_'beta',_'E') = 1

Answer 6

Here's my modified code:

from collections import defaultdict, Counter
def allocate_employees(city_data, team_data, employee_data):
    city_office_capacity = defaultdict(dict)
    for city, office, capacity in city_data:
        city_office_capacity[city][office] = capacity
team_position_count = defaultdict(Counter)
for team, position in team_data:
    team_position_count[team][position] += 1

employee_allocations = []
for employee, city, position in employee_data:
    max_capacity = 0
    max_office = None
    for office, capacity in city_office_capacity[city].items():
        if capacity > max_capacity:
            max_capacity = capacity
            max_office = office
    city_office_capacity[city][max_office] -= 1
    for team, position_count in team_position_count.items():
        if position_count[position] > 0:
            employee_allocations.append((team, employee, position, city, max_office))
            team_position_count[team][position] -= 1
            break
return employee_allocations


city_data = [
    ("New York", "A", 3),
    ("New York", "B", 2),
    ("New York", "C", 6),
    ("Boston", "D", 2),
    ("Boston", "E", 5),
]
team_data = [
    ("alpha", "Manager"),
    ("alpha", "Manager"),
    ("alpha", "Engineer"),
    ("alpha", "Engineer"),
    ("alpha", "Engineer"),
    ("alpha", "Engineer"),
    ("alpha", "Designer"),
    ("beta", "Engineer"),
    ("beta", "Engineer"),
    ("beta", "Engineer"),
    ("gamma", "Designer"),
    ("gamma", "Engineer"),
]
employee_data = [
    (1, "New York", "Manager"),
    (2, "New York", "Manager"),
    (3, "New York", "Engineer"),
    (4, "New York", "Engineer"),
    (5, "New York", "Engineer"),
    (6, "New York", "Engineer"),
    (7, "New York", "Engineer"),
    (8, "New York", "Designer"),
    (9, "New York", "Designer"),
    (10, "Boston", "Engineer"),
    (11, "Boston", "Engineer"),
    (12, "Boston", "Engineer"),
]
allocations = allocate_employees(city_data, team_data, employee_data)
for r in allocations:
    print(r)
```