Skip to content

OptiTeam: NL-to-ILP Team Formation

OptiTeam addresses a persistent challenge in project-based CS education: converting unstructured instructor requirements — "form teams of 4-5 where every team has at least one student comfortable with React and no two students from the same discussion section" — into formal mathematical optimization models that produce high-quality team assignments. The system operates as a natural-language-to-optimization pipeline, leveraging large language models to bridge the gap between human intent and computational constraint satisfaction.

The Core Problem: Team Formation as Partition Optimization

Unlike expert-team selection (finding the best individuals for a known role), educational team formation is a partition optimization problem: every student must be assigned to exactly one team, no one left out, all teams working on the same task. Formalized as EDU-TF (Educational Team Formation), this requires solving a single-task Partition Team Formation Problem (Partition TFP) — a fundamentally different and computationally distinct problem class from top-k expert selection.

The problem encompasses multiple competing objectives:

  • Skill coverage: Every team has the skills needed for the project.
  • Preference satisfaction: Students work on projects or with teammates they prefer.
  • Diversity and fairness: Balanced teams along criteria specified by the instructor.
  • Minimum perturbation: Minimal reorganization when constraints change mid-semester.

Multi-Agent LLM Formulation Pipeline

OptiTeam employs a multi-agent architecture inspired by systems like OptiMUS, where specialized LLM agents collaborate to build, debug, and refine optimization models:

  1. Manager Agent: Decomposes the instructor's natural language requirements into a structured problem specification, identifying variables, constraints, and objectives.
  2. Formulator Agent: Translates the specification into formal constraints, using RAG-augmented generation to retrieve relevant constraint templates from solver documentation.
  3. Evaluator Agent: Validates the generated ILP model for correctness, completeness, and feasibility before submission to the solver.

This decomposition mirrors the pattern established in constraint programming research (Holy Grail 2.0), where formulation proceeds through NER4OPT → relation extraction → constraint translation → solver code generation → validation → optional human refinement.

RAG-Augmented Constraint Generation

Inspired by CHORUS, OptiTeam uses retrieval-augmented generation for constraint formulation. Rather than relying on the LLM's parametric knowledge of optimization semantics — a known source of hallucinated variables and incorrect solver API calls — the system retrieves relevant constraint templates and solver documentation snippets at generation time. This hierarchical chunking and two-stage retrieval approach reduces formulation errors and improves the reliability of generated ILP models.

The Fairness-Optimality Trade-off

A central research finding across the team formation literature — and a key concern for OptiTeam — is the inherent tension between fair allocation and global optimality. The system explores this through an α-parameter that can be tuned from Pareto-fair (α=0) to utilitarian-optimal (α=100), building on work from the LIFT framework (where students vote on and weight formation criteria) and Kessler's multi-objective ILP with lexicographic priorities.

The LIFT framework's finding that students consistently prefer skill and logistics criteria over demographic ones, and value having control over the process even when outcomes match instructor-led formation, underscores the importance of human-in-the-loop refinement in OptiTeam's architecture.

The Satisfaction–Engagement–Performance Trifecta

The OptiTeam framework optimizes across three interdependent dimensions that collectively define team success:

  • Satisfaction: How well the assignment aligns with individual student preferences and agency. Systems like the Multi-Armed Bandit (MAB) approach iteratively explore team compositions and exploit student feedback to surface preference signals before the ILP solver commits to a partition.
  • Engagement: The quality and balance of participation within formed teams. The tAIfa (Team AI Feedback Assistant) system monitors teams post-formation through seven communication metrics — Sentiment, Engagement, Topic Coherence, Language Style Matching, Transactive Memory, Collective Pronouns, and Communication Flow — providing real-time Slack-based feedback.
  • Performance: Measured skill fulfillment and project outcomes. AI-formed teams in trialing achieved a 98.4% skill fulfillment rate compared to 91.9% for manual assignments.

This trifecta mirrors the full-stack architecture: Hierarchical ILP handles global optimization, MAB provides iterative preference refinement, tAIfa delivers real-time feedback, and PuppeteerLLM enables agent-based simulation for pre-deployment validation.

LM4OPT: Fine-Tuned Language Models for Optimization

A key enabler in the NL-to-ILP pipeline is LM4OPT, a fine-tuned Llama-2-7b model trained specifically to translate natural language project descriptions into structured optimization parameters. This model identifies required skills, team-size bounds, and preference constraints from unstructured instructor input. Fine-tuning a 7-billion-parameter model produces approximately 23.52 g CO₂ — a meaningful but tractable environmental cost that motivates continued research into lighter-weight alternatives like RAG-augmented generation (CHORUS) and open-source models (ORLM).

Benchmarking studies show that GPT-4 achieves an F1-score of 0.63 in translating natural language to mathematical optimization problems, indicating substantial room for improvement in the NL-to-optimization task. The fine-tuned 7B approach represents one pathway; RAG-enhanced pipelines (CHORUS) and decomposition-based methods (Holy Grail 2.0) complement it.

MCP Integration with Solvers

OptiTeam integrates with constraint solvers through the Model Context Protocol (MCP) , following the pattern established by MCP-Solver (Szeider), which connects LLMs with MiniZinc constraint solvers through standardized tools: get_model, add_item, solve_model. This solver-agnostic abstraction decouples the LLM formulation layer from any specific solver backend, enabling the system to switch between Gurobi, CP-SAT, or MiniZinc without reformulation.

The MCP bridge also enables persistent storage of modeling insights (a "memo system" analogous to OptiTeam's knowledge base), concurrent solving sessions, and item-based model editing with validation — all through a standardized protocol.

  • Student Team Formation — Direct implementation of the algorithmic team formation research in OptiTeam and Team Genesis.
  • Skill Networks — SkillNet provides the skill graph embeddings that OptiTeam consumes for coverage constraints.
  • AI-Assisted Assessment — Test Forge shares the NL-to-formal-model pipeline concept.

Deeper Concepts: Algorithmic Team Building — Neuro-Symbolic Optimization for Large Classrooms

The following sections extend the OptiTeam discussion with deeper theoretical and algorithmic concepts drawn from 50+ research papers on team formation, with a focus on ILP/MILP, LLM-to-solver pipelines, and large-classroom scalability.

General Team Formation Problem (General TFP)

Kessler et al. (2025) define General TFP as "identifying one or multiple teams of collaborators to solve one or multiple tasks from a pool of candidate teammates, fulfilling specific requirements." Four problem families emerge:

  • Top-k TFP — Select expert teams, exclude candidates (used in business recruitment, crowd work).
  • Partition TFP — Partition everyone; no one left out (the educational setting).
  • Overlapping Top-k TFP — People can be on multiple teams.
  • Overlapping Complete TFP — Everyone participates, possibly in multiple teams.

The key axis is whether candidates can be excluded and whether overlap is allowed. For large classrooms, Partition TFP (Single-task) is the primary target — every student assigned, no exclusions.

EDU-TF Problem Formalization

Kessler et al. (2025) formalize EDU-TF (Educational Team Formation) as: given m students, partition into n teams with size bounds [kmin, kmax], skill coverage c, and a preference matrix P ∈ [-d, d]^(m×m). Feasibility requires (1) a team-size constraint and (2) a team-skill constraint (each team covers ≥ c skills). They prove EDU-TF is NP-complete via reduction from SET COVER.

Three core objectives: - O1 — Maximize sum of realized preferences. - O2 — Maximize minimum realized preference (maximin fairness). - O3 — Maximize/minimize count of preferences at a specific value.

This NP-completeness proof is critical: it justifies why exact ILP may be intractable for 200+ students and why hybrid neuro-symbolic approaches (LLM + heuristic + ILP warm-start) are needed. The three objectives map to tunable sliders for preference weight, fairness weight, and must-pair/must-avoid constraints.

Hierarchical / Multi-Objective ILP (Kessler 2025)

Kessler et al. extend Candel's base model with modular objectives. Their ILP uses binary x_a,j (student→team), integer y_j,i (skill count per team), and binary z_j,i (skill coverage). The teacher sets objective priority order. Evaluated on 9 real-world university datasets, the ILP outperforms heuristic teacher assignments in preference satisfaction.

This hierarchical ILP is the primary algorithmic reference for the classroom optimizer. The modular objective design enables configurable constraint plugins.

Column Generation / Decomposition for Large-Scale ILP

Candel's ILP model pre-generates all feasible teams — an approach that hits a combinatorial wall beyond ~60 students (O(choose(m, k)) variables; for m=200, k=5, ~2.5×10⁹). The solution is column generation (Dantzig-Wolfe decomposition): generate promising teams on-demand via a pricing subproblem (often another ILP or CP). This enables scaling to large enrollments without enumerating all possibilities.

Candel et al. (2023): ILP with Pre-Enumeration

Candel et al. present the foundational ILP: binary variable δᵢ for each feasible team tᵢ, constraint Σδᵢ = 1 ensures partition, with constraints for co-team locking and team-size bounds. The objective maximizes Σf(tᵢ)·δᵢ where f(·) is any team evaluation heuristic (Belbin behavioral roles, MBTI personality dimensions). Benchmarking SCIP, CBC, and CP-SAT across 20–60 student classrooms, CP-SAT is fastest. The pre-enumeration + selection formulation serves as the baseline ILP design.

Market-Based and Bargaining Approaches

A two-phase approach: (1) round-robin initial allocation, then (2) constraint-aware bargaining where projects trade students to improve satisfaction, controlled by an α parameter tunable from Pareto-fair (α=0) to utilitarian-optimal (α=100). This represents a novel algorithmic paradigm distinct from both ILP and stable matching.

Algorithmic Approaches Taxonomy

Five structured approaches are compared: greedy score-based heuristic, stable matching (Gale-Shapley), min-cost max-flow, integer linear programming, clustering + local assignment, plus the market-based approach. Each has distinct constraint-handling profiles, informing algorithm selection per classroom instance.

Dynamic Skill Matching and Preference Scoring

The capstone matchmaking algorithm introduces a weighted scoring function:

MS(s,p) = α · PS(s,p) + Σ(βₚₖ · SS(s,k))

This combines student project preferences with dynamic skill weights that boost currently unfulfilled skills. βₚₖ varies per team per assignment step, rewarding students who fill skill gaps — more nuanced than binary skill-coverage constraints and potentially producing better subjectively-balanced teams. Stable matching (Gale-Shapley) handles lab section constraints before skill-preference optimization.

Natural Language to Optimization Pipeline (LLM-to-Solver)

OptiMUS (Teshnizi et al. 2024, 2025) defines the end-to-end architecture: Natural Language → Pre-processing (extract parameters, clauses, background) → Structured Problem → Formulator agent (writes LaTeX constraints, maintains connection graph) → Programmer agent (generates Gurobi/Pyomo code) → Evaluator agent (executes, catches errors, loop back). The connection graph tracks which variables/parameters appear in each constraint, enabling modular prompting.

CHORUS: Retrieval-Augmented Generation for LP Code

Ahmed & Choudhury (2025) propose CHORUS, a RAG framework for generating Gurobi LP code with: 1. Hierarchical tree chunking of solver documentation (preserves semantic coherence). 2. Metadata-augmented code examples (keywords + synopsis bridges vocabulary gap). 3. Two-stage retrieval with cross-encoder reranking. 4. Structured parser with reasoning steps.

Open-source LLMs (Llama 3.1, Phi-4, DeepSeek) achieve GPT-4 parity, demonstrating that RAG can replace fine-tuning as the maintenance strategy for constraint generation.

OptiMUS: Multi-Agent LLM for MILP

Teshnizi et al. (2024) detail a multi-agent framework: a Manager agent coordinates Formulator, Programmer, and Evaluator agents, iterating until code compiles and solves correctly. Ablation studies show each agent contributes meaningfully. The NLP4LP dataset (355 problems, long descriptions, real-world complexity) is released. OptiMUS beats prior SOTA by >20% on easy, >30% on hard datasets.

Autoformulation via MCTS + LLM

Astorga et al. (2025) treat optimization model formulation as a search problem, decomposing modeling into 4 stages: (m1) parameters/variables, (m2) objective, (m3) equality constraints, (m4) inequality constraints. Monte-Carlo Tree Search explores each stage's formulation space, with the LLM as hypothesis generator and an LLM-based evaluator for correctness. SMT-based symbolic pruning eliminates trivially equivalent candidate formulations. This handles ambiguous requirements better than one-shot generation.

Holy Grail 2.0: Decomposition-Based NL → Constraint Model

Tsouros et al. (2023) propose a modular 4-step framework: 1. NER4OPT — Extract entities (variables, domains, constraints, objective). 2. REL — Find relations between entities. 3. Formulation — Formal constraint problem. 4. Translation — CPMpy/MiniZinc code.

A fix loop (compile/run) and a user-refine loop complete the pipeline. Four levels of abstraction are defined for problem descriptions, from fully explicit (L1) to purely natural language (L4).

PuppeteerLLM: LLM-Based Team Simulation

Almutairi (2025) presents PuppeteerLLM, a multi-agent LLM simulation framework for modeling team dynamics with task-driven collaboration and long-term coordination. Part of a broader dissertation covering: - MAB-based team formation — Upper Confidence Bound (UCB) algorithm for iterating toward consensus. - tAIfa — LLM-powered real-time team feedback via Slack.

LLM-based team simulation serves as a testing/validation tool: before deploying a team formation strategy, outcomes can be simulated with PuppeteerLLM agents. The MAB approach models team composition as sequential arm-selection, balancing exploration vs. exploitation.

RAGDYS: Dynamic Scheduling via RAG

Tang et al. (2024) propose RAGDYS for dynamic scheduling: takes a base problem description + dynamic constraint (NL) + existing code → planning agent (identifies new params/vars/constraints) → coding agent (modifies code) → execution/fix loop. Uses ChromaDB with all-MiniLM-L6-v2 embeddings. Applies minimum perturbation constraints to minimize schedule changes — critical for mid-semester team adjustments when a student drops.

Minimum Perturbation Problem (MPP)

Given an existing solution (schedule/team assignment) and new constraints, find the minimally changed new solution. Formally: (Θᵢ, αᵢ, C_del, C_add, δ) where Θᵢ is the CSP, αᵢ the initial solution, C_del/C_add constraint changes, δ a distance function over solutions. Implemented as a hard constraint: Hamming distance ≤ threshold T. This enables "re-balance with minimal disruption" — the threshold T maps to a Workbench slider.

Brawer et al. (2023): NL Interface for MILP Task Assignment

Brawer et al. propose a natural language interface for multi-agent task assignment as a MILP. Users add/remove constraints via spoken dialogue; the LLM translates NL ↔ MILP constraints. A consistency monitor performs three-phase checks: 1. Semantic — LLM detects conflicts. 2. Relaxation — Branch-and-bound detects infeasibility. 3. Ablation — Remove conflicting constraints.

Users can ask "why" (counterfactual queries), enabling bidirectional NL ↔ MILP translation — constraints in, explanations out.

EnsembleCRF + T5 for LP Formulation

He et al. (2022) win the NL4Opt competition (F1 = 0.939) with EnsembleCRF: multiple NER models with a CRF layer to optimally combine predictions. For meaning representation, they decompose generation into multiple tasks (one prompt per constraint type) with negative sampling for missing constraints and token-level data augmentation (LwTR, SR, MR, SiS).

ILP Inference Cookbook for NLP

Srikumar & Roth (2023) provide a definitive reference for converting Boolean expressions into ILP constraints. Recipes include: - Variable negation: ¬xi = 1 − xi - Disjunction: Σxi ≥ 1 - Conjunction: Σxi = n - Implication: xi → xj as xi ≤ xj - Complex constructions: spanning trees, graph connectivity, and soft constraints.

These logical→ILP conversion patterns (e.g., "at least k of n" → Σxi ≥ k, "if-then" → xi ≤ xj) serve as constraint templates for the system.

MCP-Solver: Model Context Protocol for CP Systems

Szeider (2025) implements the first MCP server bridging LLMs with MiniZinc constraint programming. Key design features: - Item-based model editing with validation at each atomic operation (model is always consistent). - Persistent knowledge base (memo system across sessions). - Concurrent solving sessions.

MCP-based integration is more flexible than fixed-pipeline approaches. The memo system is the architectural analog of a long-term knowledge store, and the item-based editing maps directly to constraint editing interfaces.

ORLM: Training Open-Source LLMs for Optimization

Huang et al. (2024) train 7B-scale open-source LLMs (ORLMs) using OR-Instruct (semi-automated data synthesis) and benchmark on IndustryOR (industrial optimization benchmark). Shows open-source models can approach GPT-4 performance on NL4OPT and MAMO benchmarks. This represents a possible long-term upgrade path — replacing closed-source API calls with fine-tuned open models.

Li et al. (2023): Three-Phase MILP Synthesis from NL

Li, Zhang & Mak-Hau propose: Phase I identifies decision variables; Phase II classifies objective and constraints (using constraint-type templates); Phase III generates the MILP model. Their constraint classification scheme defines 7 constraint types (sum, upper/lower bound, linear, ratio, xby, xy) plus logic constraints via binary variables. Fine-tuned LLM achieves 86.67% problem accuracy vs ChatGPT's 26.67% — a powerful data point motivating structured templates over pure NL generation.

Nurse Scheduling: Participative AI with MIP/CP/RL

Sariyar et al. (2025) map nurse preferences to AI scheduling methods: MIP for fair shift allocation, CP for complex rule-based conditions, GP for handling absences, RL for dynamic adaptation. 85% of participants want fairness/participation; 76% want flexibility/autonomy. The human-AI hybrid pattern validates the LLM + optimizer + human review approach for classroom formation.

Knowledge Representation Structure for MILP from NL

Li et al. (2023) introduce a formal knowledge representation with: relational knowledge (variable–constraint links), inheritable knowledge (default constraint patterns), a constraint classification scheme (7 types + logic), and constraint templates mapping NL patterns to MILP constraints. Each template maps an NL pattern to an ILP constraint structure, and relational knowledge tracks which variables link to which constraints — forming the connection graph.

Team Evaluation Heuristics

Functions estimating team performance before task execution include: - Belbin — 8 behavioral roles, binary coverage score → sum normalized. - MBTI — 4 personality dimensions, diversity-weighted score → sum normalized. - Preference-based scoring — O1/O2/O3 (sum, maximin, specific count).

The Workbench supports pluggable evaluation heuristics — skill coverage, preference satisfaction, personality diversity, schedule compatibility — with each formula stored normalized to [0,1] for weighted composition.

Multi-Armed Bandit (MAB) for Team Formation

Almutairi (2025) models team formation as a sequential MAB problem: each candidate team composition is an "arm," user feedback is the reward signal. Upper Confidence Bound (UCB) balances exploration vs. exploitation. Offline evaluation using Big Five personality traits shows high alignment with user preferences. MAB serves as a lightweight preference-discovery precursor before the ILP solves the full partition.

NLP-Driven Team Formation

Heston et al. (2024) apply sentiment analysis, topic modeling, and NER to extract student attributes from essays, discussion posts, and surveys. Extracted features → clustering or optimization → balanced/diverse teams. This provides an alternative to explicit surveys, reducing survey fatigue by extracting skills from student free-text responses.

Neuro-Symbolic Architecture Pattern

Across the literature, the consistent winning pattern: LLM handles NL understanding and generation → Symbolic solver (ILP/CP/SAT) handles constrained optimization → Feedback loop (execution, validation, repair). Examples: OptiMUS (LLM agents + Gurobi), MCP-Solver (Claude + MiniZinc), Brawer et al. (LLM + MILP + consistency monitor), Astorga et al. (LLM + MCTS + SMT pruning). No paper relies on LLM alone for correct solutions.

This pattern forms the architecture blueprint: LLM (NL→structure, explanation, debugging, retrieval) + ILP solver (optimal partition) + MCP bridge (validation, iteration, persistence).

Supplementary Reading

The following reports expand on specific aspects of the OptiTeam framework and its neuro-symbolic foundations: