# Library of code in development:

# https://github.com/iliakass/

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_{00} … 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 _{0}x_{0} + … + 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_{0} ≤ 1*

*… … … … …*

*(a _{m0} … a_{nm})/ b_{m} ≤ 1*

* *

*(a _{00} … a_{n0})/ b_{0} = (*α

*α*

_{00}…

_{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_{0} … c_{n})

ρ_{0} = ^{2}√[(c_{0} – α* _{00}*)

^{2}+ … + (c

_{n}– α

*)*

_{ n0}^{ 2}]

…

ρ_{m} = ^{2}√[(c_{0} – α_{0m})^{2} + … + (c_{n} – α* _{nm}*)

^{ 2}]

ξ** = **^{2}√[(c_{0})^{2} + … + (c_{n})^{ 2} ]

Γ_{0} = ^{2}√[(α* _{00}*)

^{2}+ … + (α

*)*

_{ n0}^{ 2}]

…

Γ_{m} = ^{2}√[(α* _{0m}*)

^{2}+ … + (α

*)*

_{ nm}^{ 2}]

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 θ_{0 }= (Γ_{0}^{2}_{ }– ρ_{0}^{2}_{ }– ξ^{2} )/(-2 * ρ_{0} * ξ)

…

cos θ_{m }= (Γ_{m}^{2}_{ }– ρ_{m}^{2}_{ }– ξ^{2} )/(-2 * ρ_{m} * ξ)

ρ_{0 }* cos θ_{0} = Λ_{0}

…

ρ_{m }* cos θ_{m} = Λ_{m}

3.1/ Select constraint with smallest or set of constraints with equally smallest for range { Λ_{0} … Λ_{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 _{0}x_{0} + c_{1}x_{1}*

*Subject to Constraints [A]X _{n} ≤ B_{m}*

[A] = [ a_{oo} … a_{10}

… … …

a_{m0} … a_{1m }]

recall

*(a _{oo} … a_{n0})/ b_{0} ≤ 1 and b_{0 }/ b_{0} = B_{0} = 1*

*… … … … … … …. ….*

*(a _{m0} … a_{nm})/ b_{m} ≤ 1 and b_{m }/ b_{m} = B_{m} = 1*

* *

*(a _{00} … a_{n0})/ b_{0} = (*α

*α*

_{00}…

_{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_{0}

1] * α_{ 0q} α_{ 1q }] = x_{1}]

· 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 _{0}x_{0} + c_{1}x_{1}*

*Constraints [A]X _{n} ≤ B_{m}*

*B _{m} [A]_{ m}^{ -1 }= X_{n}* can be transformed into

[1 [α_{ 0k} α_{ 1k } ^{-1}_{ }[x_{0}

1] * – α_{ 1k }] = x_{1}]

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*

σ_{0} = ^{2}√[( α_{00} – α_{0k})^{2} + … + (α_{n0} – α* _{nk}*)

^{ 2}]

…

σ_{m} = ^{2}√[( α_{0m} – α_{0k})^{2} + … + (α_{nm} – α* _{nk}*)

^{ 2}]

*recall*

cos θ_{0 }= (Γ_{0}^{2}_{ }– ρ_{0}^{2}_{ }– ξ^{2} )/(-2 * ρ_{0} * ξ)

…

cos θ_{m }= (Γ_{m}^{2}_{ }– ρ_{m}^{2}_{ }– ξ^{2} )/(-2 * ρ_{m} * ξ)

ρ_{0 }* cos θ_{0} = Λ_{0}

…

ρ_{m }* cos θ_{m} = Λ_{m}

*for all m ≠ k*

cos Φ_{0 }= (Λ_{0} – Λ_{k})/ σ_{0}

…

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_{0}

1] * α_{ 0q} α_{ 1q }] = x_{1}]

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}^{2}_{ }– ρ_{k}^{2}_{ }– ξ^{2} )/(-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_{0}’

1] * – α_{ 1k }] = x_{1}’ ]

and

[1 [α_{ 0k} α_{ 1k } ^{-1}_{ }[x_{0}

1] * α_{ 0q} α_{ 1q }] = x_{1}]

*and set Ω includes*

[α_{ 0k} α_{ 1k}

– α_{ 1k }

α_{ 0q} α_{ 1q }]

*and where Z = c _{0}x_{0} + c_{1}x_{1} = c_{0}x_{0}’ + c_{1}x_{1}’*

* *

* *

5/Applications

* *

5.1/ Minimization objective function can be converted using dual theory.^{1}

*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^{2}

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_{0}(u,v) = Σ_{r} u_{r}y_{r0} / Σ_{i }v_{i}x_{i0}

Subject to Constraints Σ_{r} u_{r}y_{rj} / Σ_{i }v_{i}x_{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**

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

^{2}Cooper W. Willia, Seiford M. Lawrence, Zhu Joe, DATA ENVELOPMENT ANALSYS, *History, Models and Interpretations*.