Optimize combination of cards to least multicolored cards

Question

I asked a question about how to calculate a combination of specific color pair cards. I'd now like to optimize the calculation in a way, that the least number of triple and double colored cards are used but the criteria are still met. How would I do that?

Answer 1

Let $N$ be the required number of cards. Let $A$ be the required number of cards of color $1$. Let $B$ be the required number of cards of color $2$. Let $C$ be the required number of cards of color $3$. Let $n_i$ be the number of single-color cards of color $i$, $i=1,2,3$. Let $n_{ij}$ be the number of two-color cards of colors $i$, and $j$, $1\leq i<j\leq3$. Let $n_{123}$ be the number of three-color cards.

Then the problem is:

Minimize $$n_{12}+n_{13}+n_{23}+n_{123}\tag1$$ subject to $$ \begin{align} N&= n_1+n_2+n_3+n_{12}+n_{13}+n_{23}+n_{123}\\ A &= n_1+n_{12}+n_{13}+n_{123}\\ B&=n_2+n_{12}+n_{23}+n_{123}\\ C &= n_3+n_{13}+n_{23}+n_{123} \end{align} $$ where all the variables are non-negative integers.

This is an integer linear programming (ILP) problem, and hand solution would probably be arduous. I looked for an online solver, but didn't find one. I did find this video which apparently explains how to use the ILP solver in Excel, if you have that available.

The way $(1)$ is set up, the total number of multi-color cards is minimized. If you especially want to reduce the number of three color cards, you can add a weight in the objective function. Instead of minimizing $(1)$, minimize
$$n_{12}+n_{13}+n_{23}+2n_{123}\tag{1'}$$ You might want to experiment with some other weights.

EDIT

I don't have Excel, but it turns out that Libre Office Calc also has a linear programming solver. Unfortunately, it requires a java runtime, and I don't have one installed. Libre Office is free.

EDIT

Here's a thought. I'll give an example to show what I have in mind. Suppose $$\begin{align} N&=24\\ A&=17\\ B&=17\\ C&=19 \end{align}$$ First imagine that we have $17$ cards of color $1$, $17$ of color $2$, and $19$ of color $3$. That's $54$ cards, $29$ more than we're allowed. Can we satisfy the requirements without using three-color cards? Every time we replace two single-color cards by a two-color card, we have a net reduction of $1$ card. To reduce the number of cards by $29$ using only two-color cards would take $29$ two-color cards, and that's already more cards than we're allowed, so we must use three-color cards.

What's the smallest number of three-color cards we can use? If we use $t$ of them, we get a new problem, with $$\begin{align} N'&=N-t\\ A'&=A-t\\ B'&=B-t\\ C'&=C-t \end{align}$$ If we are to solve this without using any more three-color cards, we must have$$A'+B'+C'\leq N'$$ which results in $$t\geq\frac{A+B+C-N}2$$ In this problem we have $t\geq10$. If we use $10$ three-color cards, we have $$\begin{align} N'&=14\\ A'&=7\\ B'&=7\\ C'&=9 \end{align}$$ and since $A'+B'+C'-N'=9$ we must use $9$ two-color cards. There are many ways to do this. We could, for example, use $4$ cards with colors $1$ and $3$ and $5$ cards with colors $2$ and $3$. Then we'd also have $3$ monotone cards in color $1$, $2$ in color $2$ and $0$ in color $3$.

Answer 2

If double- and triple-color cards are equally costly, I think you can solve the problem without resorting to an integer program. Let $z=n_{12} + n_{13} + n_{23} + n_{123}$ be the quantity to be minimized. Starting from the constraints in the answer from @saulspatz, we can observe that $$A + B + C - N = z + n_{123}.$$So you minimize $z$ by maximizing $n_{123}$, subject to balancing the four equations. For the example with $N=24, A=B=17, C=19$, we have $$A + B + C - N = 29 = n_{12} + n_{13} + n_{23} + 2n_{123}.\,\,(1)$$ So we set $n_{123}=14$ (the most it can be in (1)), leaving us with $N-n_{123}=10$ more cards to choose, of which $29-2(14)=1$ must be two-colored. "Net demands" are $A-n_{123}=17-14=3=B-n_{123}$ and $C-n_{123}=19-14=5$. We can complete the solution with any two-colored card and the requisite number of single color cards. (If any net demand were zero, that would rule out two of the two-color combinations.) I tested this with the solver in LibreOffice and it confirmed the solution.

Note that the solution will always involve exactly zero or one two-color card, depending on whether $A+B+C-N$ is odd or even. It depends on the assumption that three-color cards are no worse than two-color cards.