Space Race

Another FiveThirtyEight Riddler.The President has bestowed upon you 1 billion dollars with the mission of getting us to an alien artifact as fast as possible! Here's whats available to you:

1. Big Russian engines costing 400 million each. Buying one will reduce the trip time by 200 days. Buying two will save another 100 days.

2. NASA ion engines. There are only eight of these 150 million large-scale engines in the world. For each 150 million fully fueled xenon engine you buy, you can take 50 days off of the trip.

3. Light payloads send ahead of time. For 50 million each, you lighten the main mission and reduce the arrival time by 25 days.

What's the best strategy?

This boils down to an integer programming problem, where we have several variables that with several constraints (in our case the 1 billion dollar budget) and are integer-valued, and we want to maximize some objective function, (in our case reducing our arrival time). So we get two equations:

Budget Constraint:
$$400x_0+800x_1+150x_2+50x_3 \leq 1000$$

Maximizing arrival time:
$$ max(200x_0 + 300x_1 + 50x_2 + 25x_3) $$

And scipy has a solver!

from scipy.optimize import linprog

c = [-200, -300, -50, -25]
A = [400, 800, 150, 50]
b = [1000]

x0_bounds = (0, 1)
x1_bounds = (0, 1)
x2_bounds = (0, 8)
x3_bounds = (0, None)

res = linprog(
    c,
    A_ub=A,
    b_ub=b,
    bounds=(x0_bounds, x1_bounds, x2_bounds, x3_bounds),
    options={"disp": True}
)

print res

Optimization terminated successfully.
         Current function value: -500.000000
         Iterations: 4
     fun: -500.0
 message: 'Optimization terminated successfully.'
     nit: 4
   slack: array([ 0.,  0.,  1.,  8.])
  status: 0
 success: True
       x: array([  1.,   0.,   0.,  12.])

So the solution is to buy one Russian rocket and send out 12 light payloads ahead of time, and we save 500 days!