Algorithm

Team Generation Algorithm

Overview

The Teambuilder project uses Google OR-Tools CP-SAT Solver (Constraint Programming - Satisfiability) to optimally assign students to EPICS project teams. This is an industrial-strength constraint satisfaction solver that finds globally optimal team assignments while respecting hard constraints and optimizing soft preferences.

Current Version: CPSAT (Google OR-Tools)
Status: Production
Last Updated: May 2026

Algorithm Versions

Version History

Version	Semester	Team	Status	Key Innovation
Fall 2024	F24	Fall 2024 Teambuilder	Archived	Preference-based grouping with manual balancing
Spring 2025	S25	Spring 2025	Legacy	Hungarian/Kuhn-Munkres optimal assignment
Current	CPSAT	Present	Production	Google OR-Tools CP-SAT solver with advanced constraints

Current Algorithm: CPSAT (Google OR-Tools)

Overview

The CPSAT algorithm is a Constraint Programming Satisfiability solver powered by Google's industry-grade OR-Tools. It models team assignment as a constraint satisfaction and optimization problem, finding the globally optimal solution that maximizes student satisfaction while respecting all constraints.

Official Reference: Google OR-Tools
Implementation Language: Python (team_generator.py) + TypeScript wrapper (ortools.ts)

Core Concept

The algorithm models team assignment as:

Decision Variables: Binary variables x[student][project] = 1 if assigned, 0 otherwise
Constraints: Hard requirements that must be satisfied (each student to exactly one project, team sizes, etc.)
Objective Function: Scoring system that maximizes overall satisfaction
Solver: Google OR-Tools CP-SAT engine that finds the provably optimal solution

The CP-SAT solver uses advanced techniques (linear relaxation, constraint propagation, branch-and-bound) to efficiently explore the solution space and guarantee optimality.

Key Features

1. Hard Constraints

These must be satisfied in any solution:

# CONSTRAINT 1: Each student assigned to exactly one project
for s_id in student_ids:
    model.Add(sum(x[s_id][p_name] for p_name in project_names) == 1)

# CONSTRAINT 2: Team sizes between min_team_size and max_team_size (default 4-6)
# With optional project deactivation if needed
for p_name in project_names:
    team_size = sum(x[s_id][p_name] for s_id in student_ids)
    model.Add(team_size >= config['min_team_size']).OnlyEnforceIf(project_active[p_name])
    model.Add(team_size <= config['max_team_size'] + overflow).OnlyEnforceIf(project_active[p_name])

# CONSTRAINT 6: Day matching (students only assigned to projects on their day)
for s_id in student_ids:
    student_day = student[s_id].get('day')
    for p_name in project_names:
        project_day = projects[p_name].get('day')
        if project_day and student_day and student_day != project_day:
            model.Add(x[s_id][p_name] == 0)

2. Objective Function (Maximization)

The solver optimizes a single objective function that combines all preferences and bonuses:

# Base preference scoring (per-student per-project)
if pref_index == 0:  # First choice
    base_score = 1000
elif pref_index == 1:  # Second choice
    base_score = 500
elif pref_index == 2:  # Third choice
    base_score = 200
else:
    base_score = lower_values

# Multipliers for 3200 students (heavily prioritize first choice)
if is_3200:
    base_score *= 100  # 100x multiplier for 3200 students

# Penalties for 2200 students' late choices (avoid 4+ choices)
if is_2200:
    if pref_index == 0:  # First choice
        base_score = 5000
    elif pref_index == 1:  # Second choice
        base_score = 3000
    elif pref_index == 2:  # Third choice
        base_score = 1500
    elif pref_index == 3:  # Fourth choice
        base_score = -20000  # Massive penalty
    elif pref_index == 4:  # Fifth choice
        base_score = -100000  # Extreme penalty
    elif pref_index == 5:  # Sixth choice
        base_score = -500000  # Nuclear penalty

Soft Bonuses Added to Objective:

Returning Students: +500,000 bonus if assigning to their previous project
Skills Match: +50 per matching skill
Gender Balance: -500 penalty per person isolated by gender on team
Major Diversity: +60-100 bonus per student matched to their major's project type
Project Activation: +5,000 bonus for keeping project active

3. The TypeScript Wrapper

export async function generateTeamsORTools(
  students: Student[],
  projects: Project[],
  config?: CPSATConfig
): Promise<TeamAssignments> {
  // 1. Prepare data and spawn Python process
  const pythonProcess = spawn('python', [pythonScriptPath]);
  
  // 2. Send JSON input via stdin
  pythonProcess.stdin.write(inputJson);
  
  // 3. Receive solution JSON from stdout
  const result: CPSATResult = JSON.parse(stdout);
  
  // 4. Convert back to TypeScript objects
  return teamAssignments;
}

This handles the TypeScript ↔ Python communication via process streams.

Data Structures

StudentWithChoices


The CPSAT solver is highly configurable:

```typescript
interface CPSATConfig {
  min_team_size?: number;                    // Default: 4
  max_team_size?: number;                    // Default: 6
  allow_overflow_if_needed?: boolean;        // Default: true
  overflow_per_team?: number;                // Default: 1
  overflow_penalty?: number;                 // Default: 20,000
  prioritize_returning_students?: boolean;   // Default: true
  prioritize_3200_first_choice?: boolean;    // Default: true
  prefer_major_diversity?: boolean;          // Default: true
  match_skills?: boolean;                    // Default: true
  balance_gender?: boolean;                  // Default: true
  prefer_2200_early_choices?: boolean;       // Default: true
}

Data Structures

Student

type Student = {
  id: string;
  name: string;
  major: "CS" | "SE" | "EE" | "ME" | "BME" | "DS" | "CE" | "Systems" | "Other";
  seniority: "Freshman" | "Sophomore" | "Junior" | "Senior";
  choices: string[];        // Ordered list of project names
  class: "2200" | "3200";
  previousProject?: string; // For returning students
  skills?: string[];
  gender?: "Male" | "Female" | "Non-binary" | "Prefer not to say";
  day?: "Wednesday" | "Thursday";
}

Project

type Project = {
  id: string;
  nSetup & Usage

### Prerequisites

1. **Python 3.8+**
   ```bash
   python --version

Google OR-Tools
```
pip install ortools
```

Running the Algorithm

TypeScript:

import { generateTeamsORTools } from './algorithms/CPSAT/ortools';

const teamAssignments = await generateTeamsORTools(students, projects, {
  min_team_size: 4,
  max_team_size: 6,
  prioritize_returning_students: true,
});

Test Suite:

cd algorithms/CPSAT
npx tsx test.ts

Output Example

Starting OR-Tools CP-SAT team generation...
Students: 150, Projects: 29

Solution found in 1.245s
Status: OPTIMAL
Score: 1847250
Deactivated Projects (2): Project A, Project B

Total execution time: 1387ms

Legacying;

type: "SW" | "HW" | "Both"; requiredSkills?: string[]; preferredMajors?: string[]; day?: "Wednesday" | "Thursday"; }


#### Result
```typescript
interface CPSATResult {
  success: boolean;
  teams?: { [projectName: string]: string[] };  // Maps project name to student IDs
  score?: number;                               // Total optimization score
  solve_time?: number;                          // Milliseconds to solve
  status?: string;                              // OPTIMAL, FEASIBLE, etc.
  error?: string;
  warning?: string;
  deactivated_projects?: string[];
}

Algorithm Performance

Metric	Value
Typical Solve Time	0.5-2 seconds
Students Tested	~150 students, 29 projects
Optimality	Guaranteed global optimum
Time Limit	30 seconds (configurable)
Time Complexity	Exponential worst-case, but practical with constraint propagation

Previous Algorithm: Fall 2024 (Greedy with Grouping)

Status: Archived
Location: algorithms/F24/index.ts
Note: Kept for historical reference and educational purposes

Overview

The Fall 2024 algorithm used a greedy assignment strategy with hierarchical grouping to balance student preferences with constraints.

Process Flow

Step 1: Initialize Teams

const teams = projects.reduce((acc, current) => {
    acc[current.name] = [];
    return acc;
}, {} as TeamAssignments);

Creates an empty team for each project.

Step 2: Sort Students

const sortedStudents = [...students].sort(
    (a, b) => a.choices.length - b.choices.length
);

Prioritizes students with fewer choices to reduce assignment conflicts.

Step 3: Hierarchical Grouping

Students are grouped in three stages:

3A: Group by Preference

function groupStudentsByPreference(students: Student[]) {
    return students.reduce((grouped, student) => {
        const preference = student.choices[0] || "No preference";
        grouped[preference] = grouped[preference] || [];
        grouped[preference].push(student);
        return grouped;
    }, {});
}

3B: Group by Degree Type

function getDegreeType(major) {
    if (["EE", "ME", "BME", "CE"].includes(major)) return "HW";    // Hardware
    if (["CS", "SE", "DS"].includes(major)) return "SW";            // Software
    return "Other";
}

3C: Group by Class Level

grouped[preference] = {
    "2200": [],  // Lower-level students
    "3200": [],  // Upper-level students
    null: [],
};

Step 4: Team Placement

3200 students assigned to their first choice (if exists)
2200 students assigned to first choice with room available
Students with no preferences assigned to smallest team

Step 5: Ensure Upperclassmen

function ensureUpperClassmen(teams, projects) {
    projects.forEach(project => {
        const team = teams[project.name];
        if (!team.some(student => student.class === "3200")) {
            const availableUpperClassman = findAvailableUpperClassman(teams, project.name);
            if (availableUpperClassman) {
                // Move upperclassman to team
            }
        }
    });
}

Every team must have at least one 3200-level student.

Step 6: Balance Team Sizes

All Algorithms

Criteria	Fall 2024 (Greedy)	Spring 2025 (Hungarian)	CPSAT (Current)
Optimality	Heuristic (local optima)	Globally optimal (2D)	Globally optimal (multi-dimensional)
Constraints	Hard-coded sequential	Limited by cost matrix	Fully flexible & composable
Time Complexity	O(n²) balancing	O(n³) Hungarian	Exponential (w/ propagation)
Solve Time	Instant	< 1 second	0.5-2 seconds
Gender Balance	No	No	Yes (soft constraint)
Skills Matching	No	No	Yes (soft constraint)
Returning Students	No	No	Yes (500k bonus)
Day Preferences	No	No	Yes (hard constraint)
Project Deactivation	No	No	Yes (if needed)
3200 Prioritization	Binary check	Two-pass system	100x scoring multiplier
2200 Late-Choice Penalties	No	No	-100k to -500k penalties
Production Status	Archived	Legacy	ACTIVEudents) {

        const studentToMove = findBestStudentToMove(
            teams[largestTeam.name],
            smallestTeam.name
        );
        // Move student with lowest impact score
    }
}

}


#### Impact Score Calculation

```typescript
function calculateImpactScore(student, projectName) {
    const preferenceIndex = student.choices.indexOf(projectName);
    const preferenceScore = preferenceIndex === -1 ? 100 : preferenceIndex + 1;
    const classScore = student.class === "3200" ? 0.5 : 1;
    
    return (preferenceScore + classScore) / 2;
}

Scoring Factors:

Preference Position: Not in list = 100, First choice = 1, Second choice = 2, etc.
Class Level: 3200 students have lower impact (0.5) to avoid moving them
Lower score = less disruptive move

Advantages & Limitations

| AdvMulti-Round Optimization**

Run multiple solver instances with different random seeds
Compare Pareto frontiers of solutions
Present top 3 alternative solutions to user

Incremental Assignment
- Support late student additions
- Rebalance existing teams with partial freezing
- "Lock" certain assignments and reoptimize others
Advanced Constraints
- Team leader preferences (must have upperclassman lead)
- Project affinity (students who worked together before)
- Skill level requirements per project
Dynamic Configuration
- Per-project min/max team sizes
- Per-student hard constraints (e.g., "must be with X")
- Semester-specific penalties
Warm-starting
- Use previous semester's solution as initial hint
- Minimize disruption for returning students
- Track "stability" metric across semesters
Web Dashboard
- Real-time solver progress indicator
- Interactive "what-if" scenario testing
- Swapping suggestions for manual refinement

Testing

Running Tests

# Navigate to algorithms directory
cd algorithms/S25

# Run tests with tsx
tsx test.ts

Test Coverage

Unit tests for cost matrix generation
Integration tests for full assignment pipeline
Edge cases:
- All students prefer same project
- Imbalanced student/project ratio
- Students with no preferences
- Projects with no student interest

Test File

algorithms/S25/test.ts

Future Improvements

Potential Enhancements

Skill-Based Assignment
- Incorporate required and preferred skills in cost calculation
- Weight skills matching similar to preference ranking
Team Diversity
- Add diversity constraints (major distribution, gender balance)
- Modify cost matrix to incentivize diverse teams
Prior Team History
- Factor in previous team experience
- Penalize reassigning students to same project
Real-time Updates
- Support incremental assignment (new students joining)
- Rebalance without full reassignment
Multi-objective Optimization
- Balance multiple goals (preference, diversity, skills)
- Pareto frontier exploration
Graphical Visualization
- Show preference flow and assignment rationale
- Generate team composition reports

Architecture Integration

Team Generation Flow

Student Data (Preferences + Ranking)
         ↓
Generate Team Assignments (S25 Algorithm)
         ↓
Validate Constraints (Upperclassmen, Size Balance)
         ↓
Store in Database (teams table)
         ↓
Display in UI (teams page)

API Integration

Endpoint: POST /api/teams/generate

Request:

{
    "semester": "S25",
    "projectIds": ["proj-1", "proj-2", ...],
    "studentIds": ["std-1", "std-2", ...]
}

Response:

{
    "teamAssignments": {
        "proj-1": [{ id: "std-1", name: "Alice", ... }, ...],
        "proj-2": [{ id: "std-2", name: "Bob", ... }, ...],
        ...
    },
    "metadata": {
        "algorithm": "hungarian-s25",
        "timestamp": "2026-05-08T12:00:00Z",
        "totalCost": 145
    }
}

Troubleshooting

Common Issues

Issue: Some teams are significantly smaller than others

Check: maxTeamSize calculation in lower cost matrix
Fix: Ensure Math.ceil(students.length / projects.length) is correct

Issue: Student assigned to project they didn't choose

Check: Default ranking is 7 (unchosen projects)
Fix: Verify student choices are properly populated in database

Issue: No upperclassman in a team

Check: Likely an issue with the database filtering or the upperStudentSlots calculation
CPSAT Documentation: Google OR-Tools CP-SAT
Implementation: algorithms/CPSAT/team_generator.py
TypeScript Wrapper: algorithms/CPSAT/ortools.ts
Test Suite: algorithms/CPSAT/test.ts
Legacy (S25): algorithms/S25/index.ts
**Legacy (F24)*: Number of projects/students combination
Estimate: O(n³) complexity with n = total cost matrix size
Fix: Consider splitting into multiple semesters or rolling cohorts

References

Hungarian Algorithm: Munkres Algorithm GitLab
Optimization Theory: Assignment Problem
Implementation: algorithms/S25/index.ts
Legacy: algorithms/F24/index.ts

Contributing

When modifying the algorithm:

Update tests in algorithms/S25/test.ts
Document changes in this file
Run full test suite before committing
Add migration notes if changing data structures
Update version in header section

Wiki

Website Functionality

Demographics Workflows

Project Plans

Resources

S.C.I.P.E. Wiki

Algorithm

Team Generation Algorithm

Overview

Algorithm Versions

Version History

Current Algorithm: CPSAT (Google OR-Tools)

Overview

Core Concept

Key Features

1. Hard Constraints

2. Objective Function (Maximization)

3. The TypeScript Wrapper

Data Structures

StudentWithChoices

Data Structures

Student

Project

Running the Algorithm

Output Example

Legacying;

Algorithm Performance

Previous Algorithm: Fall 2024 (Greedy with Grouping)

Overview

Process Flow

Step 1: Initialize Teams

Step 2: Sort Students

Step 3: Hierarchical Grouping

Step 4: Team Placement

Step 5: Ensure Upperclassmen

Step 6: Balance Team Sizes

Advantages & Limitations

Testing

Running Tests

Test Coverage

Test File

Future Improvements

Potential Enhancements

Architecture Integration

Team Generation Flow

API Integration

Troubleshooting

Common Issues

References

Contributing

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Clone this wiki locally