Solver functions

LProg(A, s, b, c, vector, [epsilon], [m])

Finds one or more solutions for a given linear programming problem for 'm' constraints of the type

(1) sum(x[j]*a[i,j]) <= b[i]
(2) sum(x[j]*a[i,j]) = b[i]
(3) sum(x[j]*a[i,j]) >= b[i]

and a maximized objective function sum<j=1, n>(x[j]*c[j]).

The 'A', 'b' and 'c' arguments contains the a[], b[] and c[] elements as specified above; 'A' is a 'm' x 'n' matrix, 'b' is a one-column, m-element vector, 'c' is a one-column n-element vector. The 's' argument is a one-column, m-element vector specifying used constraint types:

(1) s[i]=1 (<=)
(2) s[i]=0 (=)
(3) s[i]=-1 (>=)

The 'vector' argument specifies what should be returned:
0 - the number of optimum vectors found i > 0 - the i-th optimum vector.

The 'epsilon' argument specifies the precision used during the calculation: intermediate coefficients smaller than 'epsilon' will be treated as 0. If it's omitted, it's assumed to be 1e-08. The 'm' argument specifies some number significantly bigger than other initial coefficients. It's used as a coefficient for artificial variables. If it's omitted, the function will guess the proper value based on the input data.

All the returned x[i] values can be any non-negative numbers. If the problem allows negative values for some x[i] variables, each such variable must be replaced by a pair of new nonnegative variables. To minimized the objective function, change its sign and use the default maximizing procedure. If the objective function is unconstrained, LProg returns the #N/A! error value. If the constraints are inconsistent and the solution can't be found, LProg returns the #NULL! error value.

The initial constraints:
2*x1 + x2 + 2*x3 <= 20
3*x1 - x2 + x3 = 10
the objective function: 3*x1 + x2 - x3 -> max
=LProg({2, 1, 1; 1, 1, 3}, {1; 0}, {5; 10}, {4; 2; 2},1,,) returns {1; 0; 3}

LProgBin(A, s, b, c, bin, vector, [epsilon], [m])

Finds one or more solutions for a given linear programming problem for 'm' constraints of the type

(1) sum(x[j]*a[i,j]) <= b[i]
(2) sum(x[j]*a[i,j]) = b[i]
(3) sum(x[j]*a[i,j]) >= b[i]

and a maximized objective function sum<j=1, n>(x[j]*c[j]) where some or all of the x[i] values are required to be 0 or 1.

(1) s[i]=1 (<=)
(2) s[i]=0 (=)
(3) s[i]=-1 (>=)

The 'bin' argument is a one-column m-element vector defining the type of each x[i] variables. If bin[i] is 1, the x[i] variable can be only 0 or 1, otherwise bin[i] equals 0.

The 'vector' argument specifies what should be returned:
0 - the number of optimum vectors found
i > 0 - the i-th optimum vector.

The 'epsilon' argument specifies the precision used during the calculation: intermediate coefficients smaller than 'epsilon' will be treated as 0. If it's omitted, it's assumed to be 1e-08.

The 'm' argument specifies some number significantly bigger than other initial values. It's used as a coefficient for artificial variables. If it's omitted, the function will guess the proper value based on the input data.

If the objective function is unconstrained, LProgBin returns the #N/A! error value. If the constraints are inconsistent and the solution can't be found, LProgBin returns the #NULL! error value.

The initial constraints: 2.5*x1 + 1.5*x2 + x3 <= 15
x1 + 1.5*x2 + 3*x3 = 10
the objective function: x1 + x2 + 2*x3 -> max

=LProgBin({2.5, 1.5, 1; 1, 1.5, 3}, {1; 0}, {15; 10}, {1; 1; 2}, {1; 0; 1}, 1,,) returns {1; 4; 1}

LProgInt(A, s, b, c, int, vector, [epsilon], [m])

Finds one or more solutions for a given linear programming problem for 'm' constraints of the type

(1) sum(x[j]*a[i,j]) <= b[i]
(2) sum(x[j]*a[i,j]) = b[i]
(3) sum(x[j]*a[i,j]) >= b[i]

and a maximized objective function sum<j=1, n>(x[j]*c[j]) where some or all of the x[i] values are required to be integer.

The 'A', 'b' and 'c' arguments contains the a[], b[] and c[] elements as specified above; 'A' is a 'm' x 'n' matrix, 'b' is a one-column, m-element vector, 'c' is a one-column n-element vector.

The 's' argument is a one-column, m-element vector specifying used constraint types:

(1) s[i]=1 (<=)
(2) s[i]=0 (=)
(3) s[i]=-1 (>=)

The 'int' argument is a one-column m-element vector defining the type of each x[i] variables. If int[i] is 1, the x[i] variable must be integer, otherwise int[i] equals 0.

The 'vector' argument specifies what should be returned:
0 - the number of optimum vectors found
i > 0 - the i-th optimum vector.

The 'epsilon' argument specifies the precision used during the calculation: intermediate coefficients smaller than 'epsilon' will be treated as 0. If it's omitted, it's assumed to be 1e-08.

If the objective function is unconstrained, LProgInt returns the #N/A! error value. If the constraints are inconsistent and the solution can't be found, LProgInt returns the #NULL! error value.

The initial constraints: 2.5*x1 + 1.5*x2 + x3 <= 15
x1 + 1.5*x2 + 3*x3 = 10
the objective function: x1 + x2 + 2*x3 -> max
=LProgInt({2.5, 1.5, 1; 1, 1.5, 3}, {1; 0}, {15; 10}, {1; 1; 2}, {1; 0; 1}, 1,,) returns {4; 0; 2}

QProg(A, s, b, p, C, vector, [epsilon])

Finds one or more solutions for a given quadratic programming problem for 'm' constraints of the following types:

(1) sum(x[j]*a[i,j]) <= b[i]
(2) sum(x[j]*a[i,j]) = b[i]
(3) sum(x[j]*a[i,j]) >= b[i]

and a maximized objective function

p^T*x - x^T*C*x

where 'p' is a (column) n-element vector and 'C' is a positively determined 'n' x 'n' matrix representing a quadratic form.

The 'A', 'b', 'p' and 'C' arguments contains the a[], b[], p[] and c[] elements as specified above; 'A' is a 'm' x 'n' matrix, 'b' is a (column) m-element vector, 'p' is a (column) n-element vector, 'C' is a 'n' x 'n' matrix.

The 's' argument is a column m-element vector that determines constraint types:

(1) s[i]=1 (<=)
(2) s[i]=0 (=)
(3) s[i]=-1 (>=)

The 'vector' argument specifies what should be returned:
0 - the number of optimum vectors found
i > 0 - the i-th optimum vector.

The 'epsilon' argument specifies the precision used during the calculation: intermediate coefficients smaller than 'epsilon' will be treated as 0. If it's omitted, it's assumed to be 1e-08.

All x[i] can be any non-negative numbers. If the problem allows negative values for some x[i] variables, each such variable must be replaced by a pair of new non-negative variables.To minimized the objective function, change its sign and use the default maximizing procedure. If the objective function is unconstrained, QProg returns the #N/A! error value. If the constraints are inconsistent and the solution can't be found, QProg returns the #NULL! error value.

Example:

x1 + 2*x2 <= 10
x1 + x2 <= 9
x1 >= 0, x2 >= 0
f(x1, x2) = 10*x1 + 25*x2 - 10x1^2 - x2^2 - 4*x1*x2 -> max
A = {1, 2; 1, 1}
s = {1, 1}
b = {10; 9}
p = {10; 25}
C = {10, 2; 2, 1}
=QProg({1, 2; 1, 1}, {1; 1}, {10; 9}, {10; 25}, {10, 2; 2, 1}, 1,) returns {0; 5}

minMC(f(x), x, v, from, to, points)

Performs n-dimensional minimization of a given function using the MonteCarlo method. The function generates a number of random points in n-dimensions and returns the point for which the value of the function is the smallest. This method can be used to obtain the initial vector for the 'minSimplex' function.

The 'f(x)' argument is a reference to a cell containing a desirable function (a numeric formula) with 'n' variables.

The 'x' argument is a reference to a one-column vector containing 'n' cells (numbers or formula returning numbers) that represent variables in f(x).

The 'v' argument is a one-column vector indicating how to use a given variable: if v[i] is 0, the corresponding i-th variable has a fixed value and won't be modified, if v[i] is 0, the i-th variable can be modified.

The 'from' and 'to' arguments specify the search limits for all x[i].

The 'points' argument specifies how many sample n-dimensional points should be generated.
Note: Since the points are generated randomly for each calculation, the results change after each update.

If 'f(x)' is not a reference to a cell containing a valid numeric formula or if 'x' is not a reference to 'n' not empty cells containing numbers (or numeric formulas), 'minMC' returns the #REF! error.

Using the RC notation:

Using the A1 notation:

The D2 cell contains:
=exp((D3-1)*D3 + (C4-2)*C4 + (C5-3)*C5) - 10*exp(-((D3-3)*(D3-3) + (D4-3)*(D4-3) + (D5- 3)*(D5-3)))
The D3:D5 range contains any numbers.
=minMC(D2, D3:D5, {1; 1; 1}, -5, 5, 10000) returns {0.554969, 2.661842, 3.279377}

minSimplex(f(x), x, v, [start], [epsilon], [max_steps], result)

Performs n-dimensional minimization of a given function using the downhill simplex method.

The 'f(x)' argument is a reference to a cell containing a desirable function (a numeric formula) with 'n' variables.

The 'x' argument is a reference to a one-column vector containing 'n' cells (numbers or formula returning numbers) that represent variables in f(x). The initial values of 'x' can be obtained with the 'minMC()' function.

The 'v' argument is a one-column vector indicating how to use a given variable: if v[i] is 0, the corresponding i-th variable has a fixed value and won't be modified, if v[i] is 1, the i-th variable will be modified.

The 'start' argument is the initial simplex value. If it's 0 or if it's omitted, it's assumed to be 1e-05.

The 'epsilon' argument is the precision used to evaluate the changes of the function value. If it's 0 or if it's omitted, it's assumed to be 1.0e-25.

The 'max_steps' argument specifies the maximum allowable number of steps the function can perform. The default value is 2000.

The 'result' argument specifies what should be returned.
If 'result'=1, the function returns the 'x' vector for the found minimum 'f(x)' value.
If 'result'=2, the function returns the found minimum f(x) value.
If 'result'=3, the function returns the number of steps that it performed.

If 'f(x)' is not a reference to a cell containing a valid numeric formula or if 'x' is not a reference to 'n' not empty cells containing numbers (or numeric formulas), 'minSimplex' returns the #REF! error. If the procedure is not convergent after performing 'max_steps' steps, the function returns the #NUM! error code.

Using the RC notation:

The r2c4 cell contains:
=exp((r3c4-1)*r3c4 + (r4c3-2)*r4c3 + (r5c3-3)*r5c3) - 10*exp(-((r3c4-3)*(r3c4-3) + (r4c4- 3)*(r4c4-3) + (r5c4-3)*(r5c4-3)))
The r3c4:r5c4 range contains:
{0.5; 3; 2} =minSimplex(r2c4, r3c4:r5c4, {1;1;1},,,,1) returns {0.59358762694774; 3.00000004102304; 2.9999999389697}
=minSimplex(r2c4, r3c4:r5c4, {1;1;1},,,,2) returns 0.75509
=minSimplex(r2c4, r3c4:r5c4, {1;1;1},,,,3) returns 275

Using the A1 notation:

The D2 cell contains:
=exp((D3-1)*D3 + (C4-2)*C4 + (C5-3)*C5) - 10*exp(-((D3-3)*(D3-3) + (D4-3)*(D4-3) + (D5- 3)*(D5-3)))
The D3:D5 range contains:
{0.5; 3; 2}
=minSimplex(D2, D3:D5, {1;1;1},,,,1) returns {0.59358762694774; 3.00000004102304; 2.9999999389697}
=minSimplex(D2, D3:D5, {1;1;1},,,,2) returns 0.75509
=minSimplex(D2, D3:D5, {1;1;1},,,,3) returns 275

root(f(x), x, x0, x1, [epsilon])

Finds a root in one dimension for a given function. The equation has the form f(x) = 0. The function uses modified secant method and it's always convergent for 'f(x)' that is continuous between 'x0' and 'x1'.

The 'f(x)' argument is a reference to a cell containing a desirable function/formula with one variable.

The 'x' argument is a single cell reference that represent the variable.

The 'x0' and 'x1' arguments specify the initial search limits, such that f(x0)*f(x1) < 0.

The 'epsilon' argument specifies the precision used to evaluate the changes of the function value. If it's 0 or if it's omitted, it's assumed to be 1.0e-15.

If 'f(x)' is not a reference to a function or if 'x' is not a reference to a numeric cell, 'root' returns the #REF! error.

The r2c3 cell contains:
=r3c3*r3c3 + sin(r3c3) - 5
=root(r2c3, r3c3, 0, 3, ) returns 2.02521163744482
=root(r2c3, r3c3, -3, 0, ) returns -2.38467666014657