search

ClaudeMetz / FactoryPlanner

A mod for Factorio. Allows you to plan out your production in detail.
https://mods.factorio.com/mod/factoryplanner
MIT License
92 stars 46 forks source link

Linear programming solver #123

Open eterevsky opened 1 year ago

eterevsky commented 1 year ago

Suggestion

Recently I've been trying to model a mid-game SeaBlock factory in Factory Planner. With too many circular dependencies between the recipes, both traditional and matrix solvers were basically broken. What I am wondering is whether it would be possible to overcome these problems by using a linear programming optimization algorithm, like Simplex method.

The overall logic would be as follows:

  1. Introduce variables $x_i \ge 0$ for each recipe that denote the number of buildings executing each recipe.
  2. Calculate $y_j$ — the number of items of each type produced per unit of time. These are expressed as linear functions of $x_i$: $y = Ax$.
  3. Define the constraints $y_j \ge p_j$ for the ultimate products that the user would like to produce and $y_j \ge 0$ for all other intermediate products.
  4. Calculate the required energy $e = Ex$, which is also a linear function of $x_i$.
  5. Minimize $e$ (possibly in combination with some other values), subject to constraints on $x_i$ and $y_j$.

This looks like a typical linear programming problem, which could be solved by any method of solving linear programming problems. The advantages of this compared to just solving a system of linear equations is that this way we are able to correctly handle several different recipes producing the same products as well as any other cases which result in linear dependencies in the system.

As an additional benefit, it is possible to give user a choice which byproducts they want to allow. Just change some of the constraints on $y_j$ from inequalities $y_j \ge 0$ to $y_j = 0$.

It looks like there's at least one usable implementation of Simplex algorithm in Lua here: https://github.com/geoffleyland/luasimplex.

ClaudeMetz commented 1 month ago

Hello, sorry for not getting back to your well thought-out post earlier. I'm pretty out of my depth when it comes to this topic, but I will try and wade into the topic when I tackle a solver rewrite that is upcoming one of these days. I'll keep this suggestion in mind!

eterevsky commented 1 month ago

After I wrote this proposal, I had a look at a couple of other tools and it looks like Helmod and https://factoriolab.github.io/ are already doing this.

ClaudeMetz commented 1 month ago

Yeah seems like it. It's not a panacea from what I've heard about it in Helmod, it definitely still has failure modes. We'll see how it goes.