Let’s say you are a trading card manufacturer and you have an inventory of cards that you want to divide into packs of 5 cards each, with no duplicates in a single pack.
There are 17 different types of cards (A through Q), and some are more rare than others.
You have the following inventory:
- 25 of A
- 50 of B
- 50 of C
- 50 of D
- 50 of E
- 100 of F
- 100 of G
- 100 of H
- 100 of I
- 200 of J
- 200 of K
- 200 of L
- 200 of M
- 400 of N
- 400 of O
- 400 of P
- 400 of Q
This gives a total of 3025 cards, which is divisible by 5 but may not be when we impose the restriction of having no duplicates per pack.
Ideally, there would be some variety to the assortments, so packs would not contain simply A through E cards, or M through Q. There should be some randomness to them, or at least enough variation to seem random.
What is the cleanest way to approach this?
I have tried using a SQL database and assigning each individual card a random ID, then sorting by that ID and grabbing the first 5 rows with distinct types. This worked fairly well, but I was left with 15 cards of type L and 3 of type C, which was not ideal.
One approach is to use integer linear programming to minimize the maximum number of times that a particular pack is used. There are $\binom{17}{5}+1=6189$ nonnegative integer decision variables and $\binom{17}{5}+17=6205$ constraints.
Explicitly, let $C$ be the set of cards ($|C|=17$), let $a_c$ be the inventory of card $c\in C$, let $P$ be the set of packs ($|P|=\binom{17}{5}=6188$), let $C_p$ be the set of (five) cards in pack $p\in P$, let nonnegative integer decision variable $x_p$ be the number of times that pack $p$ is used, and let nonnegative integer decision variable $z$ represent $\max_p x_p$. The problem is to minimize $z$ subject to \begin{align} \sum_{p\in P: c \in C_p} x_p &= a_c &&\text{for $c\in C$} \tag1 \\ z &\ge x_p &&\text{for $p\in P$} \tag2 \end{align} Constraint $(1)$ assigns the full inventory of cards to packs. Constraint $(2)$ enforces the minimax objective.
The minimum $z$ turns out to be $2$, attained by the following set of packs, where the fifth column shows $x_p$: