A mathematical optimization solver for generating groups of instructors for leisure centers based on constraints and preferences.
Brot-e
optimization
Python
Challenge: Optimizing volunteer team assignments with conflicting constraints
In Catalan scout groups ("caus"), the annual leader assignment process called "Brot" is notoriously challenging. Leaders must be distributed across different age groups ("branches") while balancing multiple competing factors: personal preferences, interpersonal dynamics, experience levels, commitment availability, and branch size requirements.
The traditional manual approach to this problem involves lengthy discussions that can last an entire day, often resulting in compromises that leave some volunteers dissatisfied. The challenge was to develop a mathematical optimization system that could find the optimal distribution of leaders across groups while respecting all hard constraints and maximizing overall satisfaction.
Approach: Mathematical optimization with weighted preferences
I approached this complex assignment problem using linear programming techniques. The solution involved creating a mathematical model that could handle multiple constraint types while optimizing for two competing objectives: individual leader preferences for specific groups and interpersonal compatibility between team members.
Key components of the mathematical formulation included:
Auxiliary variables to model pairwise leader interactions within groups
Hard constraints for group size limits, experience requirements, and prohibited assignments
Weighted objective function balancing group preferences and team compatibility
Commitment level requirements to ensure each group had sufficient leadership
A tunable parameter (alpha) allowed for adjusting the relative importance of individual preferences versus team dynamics, providing flexibility in how assignments were optimized.
Mathematical Formulation: Formal optimization model
The assignment problem was formulated as a mixed-integer linear program (MILP) with the following mathematical structure:
\begin{align}
I &= \{1, 2, \ldots, N\} \quad \text{set of leaders} \\
G &= \{\text{Follets, Llops, Raiers, Pios, Clan}\} \quad \text{set of groups}
\end{align}
\begin{align}
\text{preferences}_{i,g} &\in [1,5] \quad \text{preference of leader $i$ for group $g$} \\
\text{ratings}_{i,j} &\in [1,5] \quad \text{compatibility rating between leaders $i$ and $j$} \\
\text{experience}_i &\in \{1,2,3,\ldots\} \quad \text{years of experience of leader $i$} \\
\text{commitment}_i &\in \{0,1\} \quad \text{commitment level of leader $i$ (1 = 100\% commitment)} \\
(L_g, U_g) &\quad \text{lower and upper bounds on size of group $g$} \\
\alpha &\in [0,1] \quad \text{weight parameter balancing preferences vs. compatibility} \\
M &\quad \text{large constant for constraint formulation}
\end{align}
\begin{align}
x_{i,g} &\in \{0,1\} \quad \text{1 if leader $i$ is assigned to group $g$, 0 otherwise} \\
y_{i,j,g} &\in \{0,1\} \quad \text{1 if both leaders $i$ and $j$ are assigned to group $g$, 0 otherwise} \\
z_{i,j,g} &\geq 0 \quad \text{compatibility score between leaders $i$ and $j$ in group $g$ if both assigned} \\
c_i &\in \{0,1\} \quad \text{commitment level of leader $i$} \\
w_{i,g} &\in \{0,1\} \quad \text{1 if leader $i$ is assigned to group $g$ with 100\% commitment}
\end{align}
The objective function balances two competing goals: maximizing leader preferences for their assigned groups and maximizing the compatibility between co-leaders within the same group. The parameter α controls this trade-off, with higher values prioritizing individual preferences over team dynamics.
\begin{align}
&\text{Family/prohibited group constraints:} \\
&x_{i,g} = 0 \quad \forall i \in I, g \in \text{family\_constraints}_i \\
&\text{One group per leader:} \\
&\sum_{g \in G} x_{i,g} = 1 \quad \forall i \in I \\
&\text{Group size limits:} \\
&\sum_{i \in I} x_{i,g} \geq L_g \quad \forall g \in G \\
&\sum_{i \in I} x_{i,g} \leq U_g \quad \forall g \in G
\end{align}
\begin{align}
&\text{Experience restrictions:} \\
&\sum_{g \in \{\text{Pios, Clan}\}} x_{i,g} = 0 \quad \forall i \in I \text{ where } \text{experience}_i = 1 \\
&\text{Auxiliary variable definitions:} \\
&y_{i,j,g} \geq x_{i,g} + x_{j,g} - 1 \quad \forall i,j \in I, i \neq j, \forall g \in G \\
&y_{i,j,g} \leq x_{i,g} \quad \forall i,j \in I, i \neq j, \forall g \in G \\
&y_{i,j,g} \leq x_{j,g} \quad \forall i,j \in I, i \neq j, \forall g \in G
\end{align}
\begin{align}
&\text{Compatibility score definitions:} \\
&z_{i,j,g} \geq \text{ratings}_{i,j} - M \cdot (1 - y_{i,j,g}) \quad \forall i,j \in I, i \neq j, \forall g \in G \\
&z_{i,j,g} \leq \text{ratings}_{i,j} \quad \forall i,j \in I, i \neq j, \forall g \in G \\
&\text{Commitment level constraints:} \\
&c_i = \text{commitment}_i \quad \forall i \in I \\
&w_{i,g} \geq c_i + x_{i,g} - 1 \quad \forall i \in I, \forall g \in G \\
&w_{i,g} \leq c_i \quad \forall i \in I, \forall g \in G \\
&w_{i,g} \leq x_{i,g} \quad \forall i \in I, \forall g \in G \\
&\sum_{i \in I} w_{i,g} \geq 2 \quad \forall g \in G
\end{align}
The auxiliary variables y and z are used to model the nonlinear interactions between leaders assigned to the same group. Similarly, the w variables capture the interaction between commitment levels and group assignments, ensuring that each group has at least two fully committed leaders.
Solution: Brot-e: An interactive optimization tool
The final solution, playfully named "Brot-e" (a reference to the scout group's mascot "Broti"), consisted of two main components:
A Streamlit web application for data collection, allowing leaders to input their preferences, restrictions, and compatibility ratings
A linear programming solver using PuLP to process the constraints and find the optimal assignment
Visualization tools to display the results, including leader assignments, satisfaction scores, and group metrics
The system incorporated several types of constraints to ensure practical and balanced assignments:
Each leader could only be assigned to one group
Groups had minimum and maximum size requirements
First-year leaders couldn't be assigned to certain advanced groups
At least two leaders in each group needed 100% commitment availability
Leaders could specify groups they absolutely could not join
Results: Visualizing the optimal assignments
The optimization algorithm produced several key outputs to help understand and evaluate the assignments:
Visualization of leader assignments across the five scout groups (Follets, Llops, Raiers, Pios, and Clan)
Individual satisfaction scores for each leader based on their group assignment and team compatibility
The visualizations provided clear insights into both individual leader satisfaction and the overall balance of the groups, with metrics showing which assignments were optimal according to the mathematical model.
Implementation: Technical details
The core of the implementation utilized several key technologies:
Python with PuLP for linear programming model definition and solving
Streamlit for the interactive web interface and data collection
Matplotlib for data visualization and result presentation
Custom mathematical formulations to handle the complex constraints
The model incorporated both hard constraints (such as group size limits and experience requirements) and soft preferences (such as individual preferences and interpersonal compatibility) to find a balance that maximized overall satisfaction while respecting all necessary restrictions.
Impact: A computational starting point for human decisions
While the Brot-e tool didn't completely replace the traditional assignment process, it provided valuable insights and a mathematically optimal starting point for discussions. The project highlighted several important realities about complex assignment problems:
In many real-world scenarios, not all constraints can be simultaneously satisfied
Visualizing individual and group satisfaction metrics helped make difficult trade-offs more transparent
The computational approach reduced the initial discussion time by providing a reasonable first assignment
Human adjustments were still necessary to address factors not captured in the mathematical model
Though created partly as a joke, the project demonstrated the potential for mathematical optimization in volunteer management while also revealing the limitations of purely algorithmic approaches to complex social arrangements. The tool became a conversation starter and educational example of how operations research techniques can be applied to community organization problems.
~10%
Discussion Time Reduction
Estimated reduction in initial discussion time
8/10
Fun
People enjoyed the different mathematical perspective!
