2

This is something I'm doing for a video game so may see some nonsense in the examples I provide.

Here's the problem: I want to get a specific amount minerals, to get this minerals I need to refine ore. There are various kinds of ore, and each of them provide different amounts of minerals per volume. So I want to calculate the optimum amount of ore (by least possible volume) to get the amount of minerals.

For example:

  • 35 m3 of Plagioclase is refined into 15 Tritanium, 19 Pyerite, 29 Mexallon
  • 120 m3 of Kernite is refined into 79 Tritanium, 144 Mexallon, 14 Isongen

How could I go and calculate the combination of Plagioclase and Kernite that gives at least 1000 Tritanium and 500 Mexallon with the least amount of Ore (by volume)

I think this is a linear programming problem, but I haven't touched this subject in years

Juan Fuentes
  • 123
  • 3

2 Answers2

2

Yes, this is linear programming. \begin{align} &\text{minimize} & 35p+120k \\ &\text{subject to} &15p+79k &\ge 1000 \\ &&29p+144k &\ge 500 \\ &&p &\ge 0\\ &&k &\ge 0 \end{align} The unique optimal solution is $(p,k)=(0,1000/79)$. If $p$ and $k$ are required to be integers, the unique optimal solution is $(p,k)=(0,13)$.

RobPratt
  • 45,619
0

Rob's answer shows the problem definition in both linear and integer programming. Here is an integer programming code for experimenting. In practice you would typically use some library for the job, here is an example in Python 3 using Python-MIP library.

Problem definition:

ores_def={
    "Plagioclase": {
        "materials": {
            "Tritanium": 15,
            "Pyerite": 19,
            "Mexallon": 29
        },
        "volume": 35
    },

"Kernite": {
    "materials": {
        "Tritanium": 79,
        "Mexallon": 144,
        "Insongen": 14
    },
    "volume": 120
},



}


expected={
    "Tritanium": 1000,
    "Mexallon": 500
}

Now if you mine $x_i$ units of $i$-th ore, $c_i$ is a volume of $i$−th ore (by mining unit) and $a_{i,1},a_{i,2},\dots,a_{i,k}$ are amounts of individual materials for $i$-th ore. So if you want to mine $b_1,b_2,\dots,b_k$ of each material, you want to minimize $\sum c_i x_i$ subject to $\sum_i a_{i,j}x_i \geq b_j$ and $x_i \geq 0$ for $i=1,2,\dots,n$. So, internal definition transformation into the variables described:

mats = set()
a = dict()
for name, ore in ores_def.items():
    for mat in ore["materials"]:
        mats.add(mat)
mats_list=list(sorted(mats))
ores_list=list(sorted(ores_def.keys()))

n=len(ores_list)
k=len(mats_list)
b=[0]*len(mats_list)
for mat, value in expected.items():
    b[mats_list.index(mat)] = value


c=[0]*n
for i in range(n):
    c[i] = ores_def[ores_list[i]]["volume"]


a=dict()
for i in range(n):
    d = ores_def[ores_list[i]]
    for j in range(k):
        m = mats_list[j]
        if m in d["materials"]:
            a[i,j] = d["materials"][m]
        else:
            a[i,j] = 0

And finally the optimization itself:

from mip import *
m = Model()
x = [ m.add_var(var_type=INTEGER, lb=0, name=ores_list[i]) for i in range(n) ]
for j in range(k):
    m += xsum(a[i,j]*x[i] for i in range(n)) >= b[j]
m.objective = minimize(xsum(c[i]*x[i] for i in range(n)))
m.verbose = 0
status = m.optimize()
if status == OptimizationStatus.OPTIMAL or status == OptimizationStatus.FEASIBLE:
    print(f'solution found ({"optimal" if status == OptimizationStatus.OPTIMAL else "non-optimal"}):')
    for v in m.vars:
        print(f'{v.name} : {round(v.x)}')
else:
    print("no optimal or feasible solution found")

Output:

solution found (optimal):
Kernite : 13
Plagioclase : 0

Now it should be easy to play with starting definition and see how it affects the result.

Sil
  • 16,612