Group Preference Maximizer through Student Preferences on Paper Assigned to Groups - A narrow example of an assignment problem solution with constraints

module_assignment_solver.py

"""
I wrote this for a course I was in where we had a group of 6 that had to give
presentations over 3 modules (0, 1, and 2) with each module having 2 papers we
needed to present on.

As a group we decided to pair up so 2 people would generate the presentations
for a single module, working together to make slides for the 2 papers.

The question then comes how to pair people up so they are most satisfied with
their pairings (none of us are co-located because it's an online course). This
script solves this specific problem under these specific parameters.

This is a rough implementation of the Hungarian algorithm since fundamentally
this is an assignment problem. Based on people's preferences for which papers
they would want to present, a cost is computed based on group assignments which
are just permutations of the ordering of the student with the first 2 students
in the permutations being in the first group/module, next 2 in the second
group/module, and last 2 in the 3rd group/module.

Ratings can be re-used though I advised the group to start with 1 and increment
only by 1 to avoid scaling issues; someone could put all 0's except for their
preferred paper to force them into a specific group for example.

The output is simple text that describes the group assignments. Below is an
example from this implementation:

Best permutation: {0: 0, 2: 0, 3: 1, 5: 1, 1: 2, 4: 2}
Cost of best permutation: 1.4126984126984128
(0, 'Allen') assigned to module 0 with cost 0.14285714285714285
(2, 'Cheese') assigned to module 0 with cost 0.23809523809523808
(3, 'Daniel') assigned to module 1 with cost 0.3333333333333333
(5, 'Frank') assigned to module 1 with cost 0.3333333333333333
(1, 'Ben') assigned to module 2 with cost 0.14285714285714285
(4, 'Eric') assigned to module 2 with cost 0.2222222222222222

In this specific solution everyone ended up with a module assignment where
they had a paper that was at least rated 1 or 2 with 3 people getting
assigned to a group with their top choice paper(s).
"""
import itertools
import numpy as np

# Just our names in a list; easier to code with parallel arrays since the
# space is finite. Would want to do more advanced data structures for arbitrary
# numbers of students, groups, papers, etc.
name_index = [
    "Allen",
    "Ben",
    "Cheese",
    "Daniel",
    "Eric",
    "Frank"
]

# List of the papers by name
paper_index = [
    "Covert Messaging through TCP Timestamps",  # Module 0
    "Embedding Covert Channels into TCP/IP",  # Module 0
    "A Novel Covert Timing Channel Based On RTP/TRCP",  # Module 1
    "Steganography of VoIP Streams",  # Module 1
    "Exploitation of data streams... : tunneling and covert channesl of HTTP"
    "protocol",  # Module 2
    "Deception on the network: thinking differently about covert"
    "channels"  # Module 2
]

# Ratings of the 6 papers
ratings = np.array([
    [1, 2, 3, 4, 5, 6],  # Allen
    [6, 5, 4, 3, 2, 1],  # Ben
    [2, 3, 4, 5, 6, 1],  # Cheese
    [1, 1, 1, 3, 3, 3],  # Daniel
    [2, 2, 2, 1, 1, 1],  # Eric
    [4, 5, 6, 1, 2, 3]   # Frank
])

# Normalize the ratings
row_sums = ratings.sum(axis=1)
ratings = ratings / row_sums[:, np.newaxis]

# Generate all permutations of possible groupings which are just sequences of
# indexes of 0-5 such as (1,3,5,4,0), etc. Groups are just the pairs in order
# from front to back so Module 0 would be 1 & 3, Module 1 would be 5 & 4 and
# Module 2 would be 4 & 0.
all_permutations = list(itertools.permutations(range(len(ratings))))

# Create variables to hold the best permutation and the running minimum cost
best_permutation = None
min_cost = float('inf')

# Go through all the permutations
for idx, perm in enumerate(all_permutations, start=1):
    # Initialize a 0 cost
    cost = 0

    # Map the permutation to student->module assignment
    module_assignment = {student: i // 2 for i, student in enumerate(perm)}

    # Compute cost for each module in the permutation, this is easy because we
    # have 2 papers per module so you can reliably just increment
    # 2*module index plus 0 or 1 to get the 'cost' of the pairing with larger
    # numbers being bad/more costly
    for student, module in module_assignment.items():
        cost += ratings[student][module*2]
        cost += ratings[student][module*2 + 1]

    # Update best grouping if cost is lower than running minimum
    if cost < min_cost:
        min_cost = cost
        best_permutation = module_assignment

# Output the best permutation and its cost
print(f"Best permutation: {best_permutation}")
print(f"Cost of best permutation: {min_cost}")
for student, module in best_permutation.items():
    individual_cost = 0
    individual_cost += ratings[student][module*2]
    individual_cost += ratings[student][module*2 + 1]
    print(f"{student, name_index[student]} assigned to module {module} with "
          f"cost {individual_cost}")