∫ Linear programming calculator for Dyson sphere program

Kernel:

Derive the optimal conditions for Dyson sphere program.
A web-assembly-based linear programming calculator.

In Dyson sphere programhttps://store.steampowered.com/app/1366540/Dyson_Sphere_Program, you are set to design and build dyson spheres, theoretical structures that allow the builder to harnest virtually limitless energy of a starhttps://en.wikipedia.org/wiki/Dyson_sphere. You are not going to put structures piece by piece however. Instead, you are going to design a planetary factory that spans across systems to automate the process of building dyson spheres. If you have a knack for factory management games like me, the word interesting for this game is an gross understatement.

My own unique design only with the frame.https://steamcommunity.com/sharedfiles/filedetails/?id=2910743746

There's a mathematical puzzle to solve in this and any other factory management games. How do you optimize the production of a certain product? By optimize, I mean finding the optimal ratio of the factories that produce the each of the intermediate product, So that I can produce the final product with the least amount of resources and time.

∂ Dynamic programming approach

Here's the setting. There are many products that you can produce. For each product, there can be more than one process that can produce it. And for each process, it takes a certain amount of time to produce the product, but it can produce more than one product at a time. The processes can also require other products with different amount as the input components.

Let \(n_p\) be the number of product per tick crafted by the process p.
Let \(t_p\) be the time for the process p to craft.
Let \(r\) be the required rate of the product.

The required number of the factories for that process is therefore given by \(\frac{t_p}{r n_p} = F_p(r)\). Let \( K_a(r) \) the minimal cost of crafting product \( a \) at rate \(r\). Bellman's equationKirk, D. E. (2004). Optimal control theory: an introduction. Courier Corporation. for this problem is as follows:

\[ K_a(r) = \min_{p \in P_a} F_p(r) \sum_{c \in C_p} K_c\left(\frac{m_{p, c}}{t_p}\right) \]

\(P_a\) is the set of processes that make a.
\(C_p\) is the component list of the process p.
\(m_{p, c}\) is the number of component c required by the process p.
Suppose that all mining operations are automated and has the base cost of 1.

Unrolling the recursion, this Bellman's equation can be solved by dynamic programming at \(O(|C|^2|P|)\), where \(|P|\) is the total number of the processes, and \(|C|\) is the total number of the products. Although this problem is polynomial on the dimension of the input, I'm interested to see whether I can use mathematical programming to solve this problem instead.

∂ Mathematical programming approach

Using mathematical programming requires that we think about how to approach the problem in a different way. If you're trying to solve the dynamic programming, you must think about how to break down the problem into smaller subproblems, i.e. you're designing the process of solving by yourself. However when you're using mathematical programming, you're telling the computer what are the conditions for the solution and let it do the search for you.

Here in our case,

Let \(\vec{l}\) be the cost vector associated with each process. (Which is assumed to be the all-one vector.)
Let \(\vec{f}\) be the vector of factory count for each process.
Let \(\vec{r}\) be the vector of resource production rate.
Let \(\vec{v}\) be the eligible vector associated with each process. (Allow or not allow this process.)
Let \(D\) be the matrix of net production rate for each product x process. (If it's negative instead of positive, that process consumes that product rather than producing it.)

We can formulate the problem as a linear programming problem. The goal is to minimize the number of factories, with nothing fewer than zero. The total production rate of each product must also be non-negative and equal to the net production rate given the number of factories:

Minimize: \[ \vec{l}^\intercal.\vec{f} \] Subject to: \[ \begin{align} 0 &\leq \vec{f} \\ 0 &\leq \vec{r} \\ \vec{f}^\intercal.\vec{v} &= 0 \\ D.\vec{f} &= \vec{r} \\ \end{align} \]

With every theoretical aspect sorted out, I have made a prototype calculator using the web assembly technologyhttps://webassembly.org via HiGHs.jshttps://github.com/lovasoa/highs-js. Interact with the calculator below to try it out.