User:Zhan

DoA

Discrete formulation

What are the next starts i should choose to reduce gemstones type difference, the discrete optimization point of view.

Let us consider the gemstones as a vector y = (y₁, y₂, y₃, y₄) in N⁴, where the components respectively respresent the number of margonite gemstones, stygian gemstones, torment gemstones, titan gemstones.

Then, we consider successful runs by the following functions going from N⁴ to N⁴:

f₁(x) = x + k(1, 2, 3, 4)

f₂(x) = x + k(4, 1, 2, 3)

f₃(x) = x + k(3, 4, 1, 2)

f₄(x) = x + k(2, 3, 4, 1)

Where k = 2 in Hard Mode (HM), and where the functions respectively represent start city, start veil, start gloom, start foundry.

Now, let g be a finite number n_i of composition of functions f_i, (i in {1,...,4}). We consider g to be solution if it is the minimal number of composition which gives the minimum possible difference of gemstones. This gives the following minimization problem:

g^* = argmin_g (max_{(i, j)} |g_i(y) - g_j(y)| + d||n||₁), where d is small.

Let us set h_(i,j)(y) = |g_i(y) - g_j(y)|. This is a polyhedral function with respect to n:

h_(i,j)(n, y) = |y_i - y_j + k<D_(i,j),n>|

where <., .> is the usual scalar product and D_(i,j) is the difference of the lines i, j of the system matrix.

Continuous setting

Let us now consider z in R. The discrete problem is equivalent to this one:

min_z z + <n, 1>

under:

z >= y_i - y_j + k<D_(i,j),n>

z >= y_j - y_i + k<D_(j,i),n>

for all couple (i,j) in {(1, 2), (2, 3), (3, 4), (1, 3), (2, 4), (1, 4)}

We remark that each of these constraints are convex.

Computation of the solution

Due to the nature of the problem, it is possible to get the global solution numerically.

This was tested using Juniper.jl : https://github.com/lanl-ansi/Juniper.jl

Contact

In game character name Kunvie Zhan