How can I solve this optimization problem with integer variables?

Question

I was recently watching a video game "speedrunner", who was trying to earn $1 billion of in-game currency in the shortest possible time.

He identified 3 different actions ($a$, $b$ and $c$) he could perform to generate money. The total $ value generated by (repeatedly) performing these actions was:

$$ x_{total}=n_{a}x_{0}\prod_{i=1}^{n_{c}}n_{b}[i] $$

where:

• $x_0=\$25000$ is a known constant.
• $n_a$ is the number of repetitions of action $a$.
• $n_c$ is the number of repetitions of action $c$.
• $n_b[i]$ is the number of repetitions of action $b$ associated with the $i^{th}$ repetition of action $c$.

The corresponding time cost was:

$$ t_{total}=n_{a}t_{a}+\left( \sum_{i=1}^{n_{c}}n_{b}[i]\right)t_{b}+n_{c}t_{c} $$

where $t_a = 52\text{ secs}$, $t_b = 18\text{ secs}$ and $t_c = 600\text{ secs}$ were the known times consumed (per repetition) by actions $a$, $b$ and $c$.

So, the goal was to find the integers $n_a$, $\{n_b\}$ and $n_c$ that minimize $t_{total}$, subject to the requirement that $x_{total} \geq \$1,000,000,000$.

After several minutes of trial and error, the "speedrunner" and his viewers found that $n_a = 7$, $\{n_b\} = \{18, 18, 18\}$ and $n_c = 3$ yielded $x_{total} \approx \$1.02 \text{ billion}$ and $t_{total} \approx 52.3 \text{ minutes}$. This seemed to be difficult to beat, but how can I find the optimal solution?

Some googling led me to a topic called "integer programming", but I couldn't figure out if it was applicable to this problem.

If a numerical/programmatic method is required, then:

• I would prefer to avoid brute force, if possible.
• I would like to understand how the method works, not just feed my parameters into a software package.

Answer 1

Suppose for now that we loosen the obvious restriction on $n_a, n_c, n_b[i]$ necessarily being positive integers, and allow them to take on positive real values instead.

A key observation that simplifies the problem dramatically is that $n_b[i]$ should be fixed for all $i$. This follows from AM-GM: we're given $$\prod_i n_b[i] = \frac{x_{tot}}{n_a x_0}.$$ If we have already found the ideal value of $n_a$, then $$\left(\frac{1}{n_a}\sum_i n_b[i]\right)^{n_a} \ge \prod_i n_b[i] = \frac{x_{tot}}{n_a x_0}$$ with equality only occurring when $n_b[1]=n_b[2]= \dots = n_b[n_c]$. For fixed $n_a$, the left-hand side increases with the value of $\sum_i n_b[i]$, hence this sum is minimized when we have equality of the terms.

Let $n_b$ be the value of all of the $n_b[i]$. Then, after substituting known constants, we have the constraint function $$40000 = n_a \cdot n_b^{n_c}$$ and the objective $$t_{tot} = 52n_a + 18n_bn_c + 600n_c.$$ Conveniently, we may substitute the constraint function into the objective function and reduce the number of variables: $$t_{tot} = 2080000n_b^{-n_c} + 18n_bn_c + 600n_c.$$ Minimizing this value is a multivariable calculus problem, and numerical methods will give you a minimum at $n_b \approx 17.76$ and $n_c \approx 3.05$. This then gives $n_a \approx 6.18$.

Notice how similar these values are to the values that the speedrunner found. You would expect the positive integer values minimizing the time cost to be close to these three values. This is usually true, but it's not an easy problem so solve in general: that's where different integer programming techniques come into play. In this case, however, it's not particularly necessary. The continuous solution gives us a very good starting guess, and that starting guess gives us a bound in which to check the remaining candidates. Any better integer solutions for the values of $n_b$ and $n_c$ would need to at least be contained in the region bounded by

$$2080000n_b^{-n_c} + 18n_bn_c + 600n_c \le 3136$$

(since $3136$ is what we get for $t_{tot}$ when $n_b = 18$, $n_c = 3$, and the actual value for $n_a$ will be larger than its real approximation $40000n_b^{-n_c}$, which satisfies the constraint perfectly). There's only one such pair in this region, and that's $n_b = 19$, $n_c = 3$. This gives $n_a=6$, and a $t_{tot}$ of $3138$, which is slightly larger.

Answer 2

You can solve the problem as an integer linear program. I can show one possible formulation here, but I am not going to attempt to explain branch-and-cut algorithms in a Stack Exchange answer.

To start, we know from context that $n_a\ge 1$ and $n_c\ge 1,$ and that $n_{b,i}\ge 1$ if $n_c \ge i$ and $n_{b,i} = 0$ if $n_c < i.$ We will need upper bounds on all those variables. One approach is to guess an upper limit $T$ on $t_{total}.$ To maximize $n_a$ within that time budget, you would set $n_c=1=n_{b,1},$ so $$n_a \le N_{a} =\left\lfloor \frac{T-t_{b}-t_{c}}{t_{a}}\right\rfloor.$$ Similarly $$n_{b,i} \le N_b = \left\lfloor \frac{T-t_{a}-t_{c}}{t_{b}}\right\rfloor.$$ For an upper bound on $n_c,$, note that each $i\in \lbrace{1,\dots,n_c}$ requires $n_{b,i}\ge 1,$ eating up at least $t_b$ time units. So $$n_c \le N_c = \left\lfloor \frac{T-t_{a}}{t_{b}+t_{c}}\right\rfloor.$$

To get around the nonlinearity in the formula for $x_{total},$ we can expand all the above variables in terms of binary variables as follows: $$n_a = \sum_{j=1}^{N_a} j\cdot y_j$$ $$n_c = \sum_{j=1}^{N_c} j\cdot w_j$$ and $$n_{b,i} = \sum_{j=0}^{N_b} j\cdot z_{i,j}\quad \forall i$$ where $y,$ $w$ and $z$ are all binary variables. In each case, exactly one of the binary variables must be 1, leading to what are called SOS1 constraints: $$\sum_{j=1}^{N_a} y_j = 1$$ $$\sum_{j=1}^{N_c} w_j = 1$$ and $$\sum_{j=0}^{N_b} z_{i,j} = 1\quad \forall i.$$ As noted before, $n_{b,i}=0$ if and only if $n_c < i,$ which we capture with the constraints $$z_{i,0}+\sum_{k=i}^{N_{c}}w_{k}=1 \quad \forall i.$$

The objective function is to minimize $$t_{a}n_{a}+t_{b}\sum_{i=1}^{N_{c}}n_{b,i}+t_{c}n_{c}.$$Note that we can use the constant $N_c$ as the upper limit of the summation index, since $n_{b,i}=0$ for $i>n_c.$ Last, we have to linearize the constraint on winnings, which we do by taking the logarithm of the expression for $x_{total}$ (using whatever log base you like) and expressing it in terms of our binary variables: $$\log(x_{0})+\sum_{j=1}^{N_{a}}\log(j)\cdot y_{j}+\sum_{i=1}^{N_{c}}\sum_{j=1}^{N_{b}}\log(j)\cdot z_{i,j}\ge \log(10^9).$$ Note that, in the double summation, the case $j=0$ is skipped (avoiding any attempt to take the log of zero) because $z_{i,0}=1 \implies i > n_c,$ meaning that factor would not be present in the original product.

I ran this model through an integer programming solver. It turns out that the posted solution is optimal. Since any solution with $n_a=7,$ $n_c=3$ and $n_{b,1}+n_{b,2}+n_{b,3}=54$ has the same objective value (elapsed time), the solver is free to pick a solution with, say, $n_b = [19, 19, 16],$ which is "optimal" and meets the winnings lower limit but with slightly lower winnings. To force the model to maximize winnings within the minimum possible time limit, we would need to impose a secondary objective, which requires either solving two models or using a solver that supports multiobjective optimization.