Linear programming, except each "thing you can spend time on" has its own feasible region/requirements

Question

In a game I am trying to optimize for, the goal of the game is to get each of your 23 "skills" to exceed a certain amount of "experience" in the shortest time possible. There are various "training methods" you can use to gain experience in possibly multiple skills at once, and each of these methods has a set amount of experience per unit-time you gain for using that training method.

For example, the goal might be to get skill A to at least 10,000 experience, and skill B to at least 5,000 experience, and there are 3 methods:

• Method 1 gives 10 experience in skill A and 5 experience in skill B per hour
• Method 2 gives 20 experience in skill A and 0 experience in skill B per hour
• Method 3 gives 0 experience in skill A and 7 experience in skill B per hour

We want to reach the experience goals while spending the minimal number of hours. So far this seems like a classic LP, where $\mathbf{A}$ contains each method's hourly rates for each skill, $c$ is the experience goal, $x$ is the number of hours spent on each method, and $b$ is just the ones-vector... and we want to minimize $b\cdot x$ subject to $\mathbf{A}x \ge c$.

However...what happens if each "training method" itself has a "feasible region" in which it can be trained? For example, say Method 1 can't be used until you have at least 2,000 experience in skill A. Can this still be formulated as something resembling a LP, or does it suddenly become a much harder problem because the order of events starts to matter? Do you know of any research on this sort of problem, where it's a dual LP except each "thing you can spend time on" has its own resource requirements?

Answer 1

Without knowing the full problem, it is difficult to be definitive. That said, I suspect you can model this as a mixed integer linear program (MILP), assuming that you are only training one person and that person can only perform a single training task at any time. You would use binary variables, one for each combination of time period (hour) and method, to indicate if you were using that training method in that hour. You would use a nonnegative continuous variable for each combination of skill and hour to indicate your "inventory" (level) of that skill at the end of that hour. Constraints would limit you to at most a single method in each hour, update skill inventory based based on training method, and impose any restrictions on particular methods that could be expressed in terms of skill inventory (such as needing 2,000 experience in skill A to employ method 1). To minimize total training time, you could minimize the sum of the binary variables.

Answer 2

The first part of your problem is identical to the well known Diet problem. See e.g. this example.

In the 2nd part of your question, ordering becomes important, i.e. the order in which you acquire skills. There's various ways you could model this. One way would be a dynamic program, where a state represents (i) experience level for each skill and (ii) total hours of accumulated training. A state transition is performed by taking 1 hour of a particular method. A state $S_1$ dominates a state $S_2$ if $S_1$ spent fewer hours to accumulate the same or higher experience levels than $S_2$. A terminal state is a state where the experience levels for each skill meet or exceed the target experience levels. You could implement this as a labeling algorithm.

Answer 3

I cant comment on specific method but I'd go with MILP, say by the given example, training method $ \alpha$ from among all other methods ${t}$ cant be used until training of $y$ hrs completed for skill s. So
Using a binary variable $ \delta_s = 1$ if accumulated training hours for skill $s$ is $H_s$, $0$ otherwise, you'd need couple of constraints:

$ T_{min}(\delta_s - 1) \le \sum_{t \neq \alpha} A_t x_t - H_s \le T_{max}\delta_s$
$T_{min} \delta_s \le x_{\alpha}A_{\alpha} \le T_{max}\delta_s$
where $ 0 \le T_{max}$ can be large number, may be capacity in terms of hours possible & $ 0\le T_{min}$ is a small number, like minimum training hours needed.

Answer 4

For clarity of discussion, I've written down a mathematisation/formalisation of your problem. I think I've got all the aspects you mention, but comment if I missed anything you want.

Given

• a matrix $A$ of size $m \times n$,
• an 'enabling matrix' $K$ of size $m \times n$,
• a boolean 'enabled vector' $\alpha$ of length $n$,
• an input vector $x$ of length $n$,
• an output bound vector $b$ of length $m$, and
• a weights vector $c$ of length $m$.

We want to solve the optimisation problem

$$\begin{align} &\mathbf{minimise}\ c \cdot x\\ &\mathbf{subject\ to}\\ &\quad A (x \circ \alpha) \geq b \\ &\quad x \geq 0 \\ &\quad \alpha_j = [K e_j \leq A(x \circ \alpha)] \qquad(\text{for}\ 1 \leq j \leq n) \end{align}$$ and where $c$ is the Hadamard product and $[P] = \begin{cases} 1 \quad\text{if}\ P \\ 0 \quad\text{if}\ \neg P \end{cases}\ $ the Iverson bracket.

Now, the difficult thing about this is $\alpha$, the definition of which is dependent on the output of the multiplication of $A$ by $x \cdot \alpha$, which includes $\alpha$ again! I feel like this is going to make the problem very hard, unless I've missed some clever encoding.