Has this optimization problem already been solved?

71 Views Asked by At

Here's a simplified version of the problem I'm thinking of.

Say there are three levers I can pull. Lever 1 takes 1s to pull, provides me \$1, and has a cooldown of 2s (i.e. after it's been pulled, I cannot pull it again for 2 seconds). Lever 2 takes 3s to pull, provides \$10, and has a cooldown of 10s. Lever 3 takes 2s to pull, provides \$4, and has a cooldown of 3s. What is the fastest way for me to reach \$100?

I'm not so much thinking about the solution to this problem, but rather if an algorithm to find the optimal solution is already known. I genuinely have no idea. It vaguely sounds like the travelling salesperson problem, though. If this problem is also NP-hard and has no efficient solution, then that is an answer I will accept.

1

There are 1 best solutions below

0
On

My understanding of the problem: I believe that if the target amount is large, a periodic pattern will emerge. Every single lever has a known yield, i.e. the number of \$ it rewards in the time it takes before you can repeat it (that includes the cooldown). Then two levers pulled in turn also have a yield, which is better than that of the two individual levers, because you don't have to wait for whole cooldowns. This generalizes to longer sequences.

By expanding the tree of lever choices, you get the yield for various patterns, and some of them will be "cool". A cool pattern is one that you can replay immediately, because the first lever has already cooled down.

My intuition is that the optimal solution for large amounts is made by repetition of the cool pattern with the best yield (in case of ties, take the shortest). I also believe that the exact target value to be reached will break the periodicity to some distance of the end. I would try a greedy approach based on the optimal patterns and do exhaustive search for the last, incomplete period.

This reasoning should be validated more formally.