Last active
July 24, 2024 23:37
-
-
Save fgregg/59fa9cb21f130368ea325b67d46ec519 to your computer and use it in GitHub Desktop.
Randomize Reviewers
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import csv | |
| import itertools | |
| import math | |
| import random | |
| import string | |
| import sys | |
| import click | |
| from pulp import PULP_CBC_CMD, LpBinary, LpMaximize, LpProblem, LpVariable, lpSum, value | |
| def assign_reviewers(reviewers, n_applications, reviewers_per_application): | |
| applications = list(range(1, n_applications + 1)) | |
| n_reviewers = len(reviewers) | |
| applications_per_reviewer = n_applications * reviewers_per_application / n_reviewers | |
| # Create LP problem | |
| prob = LpProblem("AssignmentProblem", LpMaximize) | |
| # Define decision variables | |
| vars = LpVariable.dicts( | |
| "x", | |
| [ | |
| (application, reviewer) | |
| for application in applications | |
| for reviewer in sorted(reviewers) | |
| ], | |
| 0, | |
| 1, | |
| LpBinary, | |
| ) | |
| # Objective function: maximize random variables | |
| prob += lpSum(variable * random.random() for variable in vars.values()) | |
| # Constraints | |
| # Each application is assigned exactly reviewers_per_application reviewers | |
| for application in applications: | |
| prob += ( | |
| lpSum(vars[application, reviewer] for reviewer in reviewers) | |
| == reviewers_per_application | |
| ) | |
| # Each reviewer is assigned at most the ceiling of applications_per_reviewer | |
| for reviewer in reviewers: | |
| prob += lpSum( | |
| vars[application, reviewer] for application in applications | |
| ) <= math.ceil(applications_per_reviewer) | |
| prob += lpSum( | |
| vars[application, reviewer] for application in applications | |
| ) >= math.floor(applications_per_reviewer) | |
| # We also want to make the number of combos pretty even, to do that | |
| # we need to linearize https://or.stackexchange.com/questions/37/how-to-linearize-the-product-of-two-binary-variables | |
| joint_reviewers = LpVariable.dicts( | |
| "joint", | |
| [ | |
| (application, combo) | |
| for application in applications | |
| for combo in itertools.combinations( | |
| sorted(reviewers), reviewers_per_application | |
| ) | |
| ], | |
| 0, | |
| 1, | |
| LpBinary, | |
| ) | |
| for (application, combo), joint_variable in joint_reviewers.items(): | |
| for reviewer in combo: | |
| prob += joint_variable <= vars[(application, reviewer)] | |
| prob += joint_variable >= ( | |
| lpSum(vars[application, reviewer] for reviewer in combo) - n_reviewers + 1 | |
| ) | |
| applications_per_combo = n_applications / math.comb( | |
| n_reviewers, reviewers_per_application | |
| ) | |
| for combo in itertools.combinations(sorted(reviewers), reviewers_per_application): | |
| prob += lpSum( | |
| joint_reviewers[application, combo] for application in applications | |
| ) <= math.ceil(applications_per_combo) | |
| prob += lpSum( | |
| joint_reviewers[application, combo] for application in applications | |
| ) >= math.floor(applications_per_combo) | |
| # Solve LP | |
| prob.solve(PULP_CBC_CMD(logPath="/dev/stderr")) | |
| counts = {} | |
| # Extract solution | |
| solution = {} | |
| for (application, reviewer), variable in vars.items(): | |
| if value(variable) > 0.999: | |
| if application in solution: | |
| solution[application].append(reviewer) | |
| else: | |
| solution[application] = [reviewer] | |
| if reviewer in counts: | |
| counts[reviewer] += 1 | |
| else: | |
| counts[reviewer] = 1 | |
| print(counts, file=sys.stderr) | |
| combo_counts = {} | |
| for reviewers in solution.values(): | |
| combo = tuple(sorted(reviewers)) | |
| if combo in combo_counts: | |
| combo_counts[combo] += 1 | |
| else: | |
| combo_counts[combo] = 1 | |
| print(combo_counts, file=sys.stderr) | |
| return solution | |
| @click.command() | |
| @click.option( | |
| "--reviewer", | |
| "-r", | |
| type=str, | |
| multiple=True, | |
| required=True, | |
| help="Name of reviewer, can be specified multiple times", | |
| ) | |
| @click.option( | |
| "--n-applications", | |
| "-n", | |
| type=int, | |
| required=True, | |
| help="Number of applications", | |
| ) | |
| @click.option( | |
| "--reviewers-per-application", | |
| "-rp", | |
| type=int, | |
| required=True, | |
| help="Reviewers per application", | |
| ) | |
| def main(reviewer, n_applications, reviewers_per_application): | |
| assigned_reviewers = assign_reviewers( | |
| reviewer, n_applications, reviewers_per_application | |
| ) | |
| writer = csv.writer(sys.stdout) | |
| writer.writerow( | |
| ["application"] | |
| + [ | |
| f"reviewer {string.ascii_lowercase[i]}" | |
| for i in range(reviewers_per_application) | |
| ] | |
| ) | |
| for application, assigned_reviewers_list in assigned_reviewers.items(): | |
| writer.writerow([application] + sorted(assigned_reviewers_list)) | |
| if __name__ == "__main__": | |
| main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment