Library of code in development: Trig Heuristic Method


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 = Cn  Xn 

·      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]Xn ≤ Bm

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

 

[A] = [ a00       …         an0

            …         …         …

            a0m      …         anm ]

 

·      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

 

Bm [A] m -1 = Xn

·      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 (a0x0 + … + anm xnm )/ bm = 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 = Cn x Xn  

Subject to Constraints [A]Xn ≤ Bm

 

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

 

(aoo      …         an0)/ b0 ≤ 1

…         …         …       …     …

(am0     …         anm)/ bm ≤ 1

 

(a00      …         an0)/ b0 =         (α00      …         αn0)

…         …         …       …           …         …         …

(a0m     …         anm)/ bm =       (α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. 

 

Cn = (c0 … cn)

 

ρ0 = 2[(c0 – α00)2 + … + (cn – α n0) 2 ]

ρm = 2[(c0 – α0m)2 + … + (cn – αnm) 2 ]


ξ = 2[(c0)2 + … + (cn) 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 θ= (Γ02 – ρ02 – ξ2 )/(-2 * ρ0 * ξ)

cos θ= (Γm2 – ρm2 – ξ2 )/(-2 * ρm * ξ)

 

ρ* cos θ0 = Λ0

ρ* 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 = c0x0  + c1x1

Subject to Constraints [A]Xn ≤ Bm

[A] = [ aoo       …         a10

            …         …         …

            am0      …         a1m ]

 

recall

(aoo      …         an0)/ b0 ≤ 1      and      b/ b0 = B0 = 1

…         …         …       …     …               …         ….        ….

(am0     …         anm)/ bm ≤ 1    and      b/ bm = Bm = 1

 

(a00      …         an0)/ b0 =         (α00      …         αn0)

…         …         …       …           …         …         …

(a0m     …         anm)/ bm =       (α0m     …         αnm)

 

Bm [A] m -1 = Xn can be transformed into 

[1        [α 0k     α 1k   -1     [x0

   1]   *     α 0q    α 1q ]   =   x1]

 

·      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 = c0x0  + c1x1

Constraints [A]Xn ≤ Bm

 

Bm [A] m -1 = Xn can be transformed into 

[1        [α 0k     α 1k   -1     [x0

   1]   *             α 1k ]   =   x1]

 

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

cos θ= (Γm2 – ρm2 – ξ2 )/(-2 * ρm * ξ)

 

ρ* cos θ0 = Λ0

ρ* cos θm = Λm

 

for all m ≠ k

cos Φ= (Λ0 – Λk)/ σ0

cos Φ= (Λm – Λk)/ σm

 

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

 

Bm [A] m -1 = Xn can be transformed into 

[1        [α 0k     α 1k   -1     [x0

   1]   *     α 0q    α 1q ]   =   x1]

 

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 θ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 θ= (Γk2 – ρk2 – ξ2 )/(-2 * ρk * ξ) when θk = 0

 

and

 

(α0m) ≤  (α0k) … and … (αnm) ≤  (αnk) for all n            and except when m=q

 

then

Bm [A] m -1 = Xn transformed into 

[1        [α 0k     α 1k   -1     [ x0

   1]   *             α 1k ]   =   x1’ ]

 

and

 

[1        [α 0k     α 1k   -1     [x0

   1]   *     α 0q    α 1q ]   =   x1]

 

and set Ω includes

[α 0k     α 1k

          α 1k    

   α 0q     α 1q ]

 

and where                               Z = c0x0  + c1x1 = c0x0’  + c1x1

 

 

5/Applications

 

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

From Maximization setup                                          To Minimization setup

Objective function Z = Cn x Xn                                     Objective function W = Bm x Yn 

Subject to Constraints [A]Xn ≤ Bm                              Subject to Constraints Yn [A] ≤ Cn

X≥ 0                                                                           Y≥ 0

 

5.2/ Data Envelopment Analysis2

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 h0(u,v) = Σr uryr0 / Σvixi0

 

Subject to Constraints Σr uryrj / Σvixij         for all j from 1 to n

 

ur and vare non-zero decision variables, and yrj and xij are constraint coefficients

 

References

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

 

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