Trigonometric heuristic method for the determining solution set for an objective function Z with n coefficients and m constraints.

By Ilia Kassianenko

Under The Artistic License 2.0, https://opensource.org/licenses/Artistic-2.0

Definition

Maximization objective function and constraints

Objective function Z = C_n X_n

· where C is a vector of size “n”, which includes the coefficients for each “x”

· where X is a vector of size “n”, which includes the maximum quantity for each “x” and within the constraints defined below and which is non-zero

Subject to Constraints [A]X_n ≤ B_m

· where [A] is an “m x n” matrix where n ≤ m, which includes the coefficients of each constraint for each “x”

[A] = [ a₀₀ … a_n0

… … …

a_0m … a_nm ]

· where X is a vector of size “n”, which includes the maximum quantity for each “x” and within the constraints

· where B is a vector of size “m”, which includes the limiting factor for each constraint

B_m [A] _m ^-1 = X_n

· There is exists a set of constraints in matrix A, out which “n” constraints are chosen to compute the inverse of an “n x n matrix” and multiplied by their corresponding coefficients in vector B of size “n”, in order to determine the optimal quantity for each “x”.

· For instance, for a matrix A of size “n x m”, there are at least “n” out “m” constraints that are fully utilized, i.e. the multiplication of the optimal quantity for “x” yields the constraint coefficient (a₀x₀ + … + a_nm x_nm )/ b_m = 100%.

· Also, there is a set “p” , which includes at least “n” constraints that are fully utilized, that lists all possible combinations of “n” constraints that are used to determine the optimal quantity.

Initialization

Objective function Z = C_n x X_n

Subject to Constraints [A]X_n ≤ B_m

1/ Division of all [A] coefficients by the respective coefficient B_m

(a_oo … a_n0)/ b₀ ≤ 1

… … … … …

(a_m0 … a_nm)/ b_m ≤ 1

(a₀₀ … a_n0)/ b₀ = (α₀₀ … α_n0)

… … … … … … …

(a_0m … a_nm)/ b_m = (α_0m … α_nm)

2/ Computation of shorted distances between objective function variables and each constraint, by taking the square root of the sum of the square difference.

C_n = (c₀ … c_n)

ρ₀ = ²√[(c₀ – α₀₀)² + … + (c_n – α _n0) ² ]

…

ρ_m = ²√[(c₀ – α_0m)² + … + (c_n – α_nm) ² ]

ξ = ²√[(c₀)² + … + (c_n) ² ]

Γ₀ = ²√[(α₀₀)² + … + (α _n0) ² ]

…

Γ_m = ²√[(α_0m)² + … + (α _nm) ² ]

3/ Determine the cosine angle and projected distance “Λ” on the segment, which connects the objective variable and the origin that is of length “ξ”. The segment will also be denoted as “ξ”.

cos θ₀ = (Γ₀² – ρ₀² – ξ² )/(-2 * ρ₀ * ξ)

…

cos θ_m = (Γ_m² – ρ_m² – ξ² )/(-2 * ρ_m * ξ)

ρ₀ * cos θ₀ = Λ₀

…

ρ_m * cos θ_m = Λ_m

3.1/ Select constraint with smallest or set of constraints with equally smallest for range { Λ₀ … Λ_m }

3.2/ For smallest Λ or set of equally smallest Λ, select constraint with smallest θ

3.3/This constraint will referenced as “k” in the range {0 … m}

4/The k-th constraint will be used for all subsequent iterations. Also, it is included in the set of constraints used in a matrix to determine the optimal quantity for each “x”.

For example,

Objective function Z = c₀x₀ + c₁x₁

Subject to Constraints [A]X_n ≤ B_m

[A] = [ a_oo … a₁₀

… … …

a_m0 … a_1m ]

recall

(a_oo … a_n0)/ b₀ ≤ 1 and b₀ / b₀ = B₀ = 1

… … … … … … …. ….

(a_m0 … a_nm)/ b_m ≤ 1 and b_m / b_m = B_m = 1

(a₀₀ … a_n0)/ b₀ = (α₀₀ … α_n0)

… … … … … … …

(a_0m … a_nm)/ b_m = (α_0m … α_nm)

B_m [A] _m ^-1 = X_n can be transformed into

[1 [α _0k α _1k ^-1 [x₀

1] * α _0q α _1q ] = x₁]

· where the k-th and q-th constraints are included in the matrix inverse, and they are included in the set “Ω” of constraints used to determine the optimal quantity for “x”

· where the sum product of the matrix inverse and the unit vector yields the optimal quantity for “x”

4.1/In the subsequent iterations, the size of the set “Ω” is determined based on the following presumptions

4.1.1/The k-th constraint may be the binding for all constraints or a set of constraints.

The m-th constraint is bound by the k-th constraint

(α_0m … α_nm) ≤ (α_0k … α_nk) if and only if

(α_0m) ≤ (α_0k) … and … (α_nm) ≤ (α_nk) for all n

then the k-th constraint is used to determine span of intersection planes with “ξ”.

4.1.1.1/ For example of a k-th constraint binding all other (m-1) constraints :

Objective function Z = c₀x₀ + c₁x₁

Constraints [A]X_n ≤ B_m

B_m [A] _m ^-1 = X_n can be transformed into

[1 [α _0k α _1k ^-1 [x₀

1] * – α _1k ] = x₁]

4.1.1.2/When only a set of constraints are bound by the k-th constraints, these constraints are removed from the set {0 … m} constraints before proceeding to the subsequent iteration.

4.1.2/When the k-th constraint is not binding, then subsequent constraint q or set of constraints must be determined, based on the angles “Φ” formed from the k-th constraint.

The segment connecting the k-th and q-th constraints must intersect with “ξ”; conversely, the span of planes including the k-th constraint must intersect with “ξ”.

4.1.2.1/The angle “Φ” between the k-th and q-th constraint must be determined, by taking the square root of the sum of the squared differences.

for all m ≠k

σ₀ = ²√[( α₀₀ – α_0k)² + … + (α_n0 – α_nk) ² ]

…

σ_m = ²√[( α_0m – α_0k)² + … + (α_nm – α_nk) ² ]

recall

cos θ₀ = (Γ₀² – ρ₀² – ξ² )/(-2 * ρ₀ * ξ)

…

cos θ_m = (Γ_m² – ρ_m² – ξ² )/(-2 * ρ_m * ξ)

ρ₀ * cos θ₀ = Λ₀

…

ρ_m * cos θ_m = Λ_m

for all m ≠ k

cos Φ₀ = (Λ₀ – Λ_k)/ σ₀

…

cos Φ_m = (Λ_m – Λ_k)/ σ_m

The smallest angles Φ_q indicates that the q-th constraint to be included in the solution set “Ω”.

B_m [A] _m ^-1 = X_n can be transformed into

[1 [α _0k α _1k ^-1 [x₀

1] * α _0q α _1q ] = x₁]

4.1.2.2/ Work in Progress: for n > 2, the methodology for determining the span of planes including the k-th constraint and included in the set “Ω”, which must intersect with “ξ”, is being investigated and is not yet developed. It will be included in the Gamma Version of the code.

4.1.3/ When angle θ_k for the k-th constraint is null, then iterations 4.1.1 and 4.1.2 must sequentially computed. Work in Progress: for n < 3, the methodology is known and will be released in the Beta Version of the code in C++.

For example, for θ_k = 0 and the k-th constraint binding all other (m-2) constraints

if and only if

1 = cos θ_k = (Γ_k² – ρ_k² – ξ² )/(-2 * ρ_k * ξ) when θ_k = 0

and

(α_0m) ≤ (α_0k) … and … (α_nm) ≤ (α_nk) for all n and except when m=q

then

B_m [A] _m ^-1 = X_n transformed into

[1 [α _0k α _1k ^-1 [ x₀’

1] * – α _1k ] = x₁’ ]

and

[1 [α _0k α _1k ^-1 [x₀

1] * α _0q α _1q ] = x₁]

and set Ω includes

[α _0k α _1k

– α _1k

α _0q α _1q ]

and where Z = c₀x₀ + c₁x₁ = c₀x₀’ + c₁x₁’

5/Applications

5.1/ Minimization objective function can be converted using dual theory.¹

From Maximization setup To Minimization setup

Objective function Z = C_n x X_n Objective function W = B_m x Y_n

Subject to Constraints [A]X_n ≤ B_m Subject to Constraints Y_n [A] ≤ C_n

X_n ≥ 0 Y_n ≥ 0

5.2/ Data Envelopment Analysis²

One of the principal development and inspirational goals behind the Trigonometric Heuristic Method is to compile the Data Envelopment Method in its defined state, without further transformations.

max h₀(u,v) = Σ_r u_ry_r0 / Σ_i v_ix_i0

Subject to Constraints Σ_r u_ry_rj / Σ_i v_ix_ij for all j from 1 to n

u_r and v_i are non-zero decision variables, and y_rj and x_ij are constraint coefficients

References

¹Hillier S. Frederick, Liebereman J. Gerald, INTRODUCTION TO OPERATIONS Research, 8^th Edition, McGrall Hill.

²Cooper W. Willia, Seiford M. Lawrence, Zhu Joe, DATA ENVELOPMENT ANALSYS, History, Models and Interpretations.