Skip to content

Constraints

What Are Constraints?

Constraints enforce that the selected subset includes a minimum and/or maximum number of vectors from specific groups. Each constraint is defined by:

  • int_set -- a set of vector indices that form the group
  • min_count -- minimum number of vectors to select from this group
  • max_count -- maximum number of vectors to select from this group
from max_div import Constraint

# At least 3 and at most 7 vectors from indices 0-49
Constraint(int_set=set(range(50)), min_count=3, max_count=7)

Overlapping Constraints

A single vector can belong to multiple constraint groups. This is useful for modeling multi-dimensional fairness requirements.

For example, you might have demographic groups and geographic groups:

constraints = [
    # Demographic constraints
    Constraint(int_set=group_a_indices, min_count=5, max_count=10),
    Constraint(int_set=group_b_indices, min_count=5, max_count=10),
    # Geographic constraints
    Constraint(int_set=region_north,    min_count=3, max_count=8),
    Constraint(int_set=region_south,    min_count=3, max_count=8),
]

A vector can be in both group_a_indices and region_north, and both constraints will be tracked independently.

Infeasible Constraints

Constraints can be infeasible -- either individually or jointly. For example:

  • Individually infeasible: min_count=15 on a group with only 10 members
  • Jointly infeasible: two non-overlapping groups each requiring min_count=11 when k=20

The solver does not fail on infeasible constraints. Instead, it finds the least infeasible solution -- the one with the smallest total constraint violation. This is a natural consequence of the score's priority ordering: the solver always prefers better constraint satisfaction over higher diversity.

How Constraints Are Tracked

Internally, constraints are represented as numpy arrays for efficient access within numba-compiled solver code. For each constraint, the solver tracks how many additional selections are needed (min_remaining) and how many more are allowed (max_remaining):

  • A constraint is satisfied when min_remaining <= 0 and max_remaining >= 0
  • Adding a vector from a constraint group decreases both counters by 1
  • Removing a vector increases both counters by 1

This incremental tracking avoids recomputing constraint satisfaction from scratch after each swap, keeping the per-iteration cost constant regardless of constraint complexity.

Impact on Diversity

Adding constraints restricts the search space, which generally reduces the achievable diversity. The tighter the constraints, the more diversity is sacrificed. This is expected and visible in the solution's score: a constrained solution will typically have a lower diversity value than an equivalent unconstrained one.