I am wondering if there is any literature on the following combinatorial optimization problem:


* **Input**: $n, k, T\in \mathbb{N}$ and positive integers $s\_1, \ldots, s\_n$.


For intuition, we may think that $n$ represents a number of players; $k$ represents the number of players that form a team; $s\_i$ represents the skill of player $i$ ($i=1,\ldots, n)$; and $T$ represents a desired minimum skill sum for the players in a team (see next).


* **Output**: The maximum integer $m$ such that it is possible to form $m$ teams (each of $k$ players) so that, for each team, the sum of the skills of the players in the team is at least $T$.


(Note: each player can be assigned only to at most one team)


At first glance I thought this is a variation of the [Bin Covering Problem](https://en.wikipedia.org/wiki/Bin_covering_problem), but now I think that having a fixed number of objects (i.e. players) per bin (i.e. team) makes it quite different.



Maximum number of teams of fixed size over a score threshold
You can solve the problem via integer linear programming (ILP) as follows. Let $I=\{1,\dots,n\}$ be the set of players, and let $J=\{1,\dots,\lfloor n/k \rfloor\}$ be the set of potential teams. Let binary decision variable $x\_{i,j}$ indicate whether player $i$ is on team $j$, and let binary decision variable $y\_j$ indicate whether team $j$ is used. The problem is to maximize $\sum\_{j\in J} y\_j$ subject to
\begin{align}
\sum\_{j\in J} x\_{i,j} &\le 1 &&\text{for $i\in I$} \tag1 \\
\sum\_{i\in I} x\_{i,j} &= k y\_j &&\text{for $j\in J$} \tag2 \\
\sum\_{i\in I} s\_i x\_{i,j} &\ge T y\_j &&\text{for $j\in J$} \tag3 \\
\end{align}
Constraint $(1)$ assigns each player to at most one team.
Constraint $(2)$ assigns either $0$ or $k$ players to team $j$ according to the value of $y\_j$.
Constraint $(3)$ enforces the threshold if $y\_j=1$.


One approach is to solve the problem directly with a generic ILP solver. Another is to exploit symmetry with respect to $j$ and use column generation. The latter approach is equivalent to relaxing $(2)$ and $(3)$ and applying Dantzig-Wolfe decomposition with identical blocks, as in the standard approach for the *cutting stock* problem. In that case, each column corresponds to a team of $k$ players who together meet the threshold. If the set of possible columns is small enough (for example, if $\binom{n}{k}$ is small enough), you can generate all columns a priori and solve a single *set packing* problem.


