Method, apparatus, and computer program product for optimizing parameterized models using functional paradigm of spreadsheet software

• US 9,286,286 B1
• Filed: 01/03/2015
• Issued: 03/15/2016
• Est. Priority Date: 01/03/2015
• Status: Active Grant

• Current Assignee: Chahid Kamel Ghaddar
• Original Assignee: Chahid Kamel Ghaddar
• Inventors: Ghaddar, Chahid Kamel
• Primary Examiner(s): Baderman, Scott
• Assistant Examiner(s): Lee, Sookil
• Application Number:
  US14/588,909
• Time in Patent Office: 437 Days
• Field of Search: 715/219
• US Class Current: 1/1
• CPC Class Codes: G06F 17/11 for solving equations , e.g. nonlinear equations, general mathematical optimization problems optimization specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 40/166 Editing, e.g. inserting or deleting
• CPC Class Codes: G06F 40/18 of spreadsheets form-filling G06F40/174

Abstract

The present disclosure provides a method, an apparatus, and a computer program product to interact with a spreadsheet application for computing the value of a formula that depends explicitly or implicitly on one or more cells designated as variables, based on provided values for the variables, and without modifying any data of the spreadsheet application. In one aspect, the present disclosure provides an optimization process executed by spreadsheet functions of a spreadsheet application, and arranged in a functional paradigm for computing optimal parameters for a parameterized system modelled by variables, parameters, and dependent formulas.

Claims

1. A method for optimizing solution of a parameterized equation system that satisfies one or more constraints using a spreadsheet software application, the method comprising:

A) displaying and operating a tabular datasheet by executing the spreadsheet software application on a computer device, the tabular datasheet having a plurality of cells each being designated with a column identifier and a row identifier, the cells being configured to receive input and display output;

B) receiving, from a first group of the cells, one or more formula expressions representing the parameterized equation system, each of the formula expressions including a first sequence of substrings respectively representing a logical building block of the parameterized equation system;

C) receiving, from a second group of the cells, variables of the formula expressions and, from a third group of the cells, parameters of the formula expressions;

D) receiving, from a fourth group of the cells, a first solver function of the spreadsheet software application having one or more first input arguments, the first input arguments at least referencing the formula expressions in the first group of the cells and the variables in the second group of the cells;

E) computing the first solver function to obtain an initial solution of the parameterized equation system, and displaying values of the initial solution in the fourth group of the cells;

wherein computing the first solver function comprises;

E1) constructing, for each of the formula expressions, an evaluable tree-structured graph of relational nodes containing an equivalent sequence of evaluable sub-expressions of said one or more formula expressions;

E2) evaluating, by a graph evaluator, the relational nodes for the formula expressions to obtain values of the formula expressions based on values of the variables of the formula expressions; and

E3) using an underlining algorithm of the first solver function to compute the initial solution in accordance with the formula expressions in the first group of the cells and the variables in the second group of the cells;

wherein the underlining algorithm of the first solver function utilizes the graph evaluator to repeatedly evaluate the parameterized equation system for the values of the variables thereby computing the initial solution;

F) receiving, from a fifth group of the cells, one or more constraint expressions representing the constraints for the parameterized equation system, each of the constraint expressions including a second sequence of substrings respectively representing a logical building entity of the constraint expressions, said one or more constraint expressions referencing the initial solution in the fourth group of the cells;

G) receiving, from a sixth group of the cells, a second solver function of the spreadsheet software application having one or more second input arguments, the second input arguments at least referencing the constraint expressions in the fifth group of the cells and the parameters in the third group of the cells;

H) computing the second solver function to obtain an optimized solution of the parameterized equation system, and displaying values of the optimized solution in the sixth group of the cells;

wherein computing the second solver function comprises;

H1) constructing, for each of the constraint expressions, an evaluable tree-structured graph of relational nodes containing evaluable sub-expressions including an expression of the first solver function;

H2) evaluating, by the graph evaluator, the relational nodes for the constraint expressions to obtain dynamic values of the constraint expressions based on values of the parameters in the third group of the cells;

wherein evaluating the relational nodes for the constraint expressions comprises computing a solution of the first solver function at said values of the parameters; and

H3) using an underlining algorithm of the second solver function to compute the optimized solution in accordance with the constraint expressions in the fifth group of the cells and the parameters in the third group of the cells;

wherein the underlining algorithm of the second solver function utilizes the graph evaluator to repeatedly evaluate the dynamic values of the constraints expressions for the values of the parameters thereby computing the optimized solution.

2. The method of claim 1, wherein the spreadsheet software application comprises a native spreadsheet software application.

3. The method of claim 1, wherein the spreadsheet software application comprises a web-based spreadsheet software application.

4. The method of claim 1, wherein the parameterized equation system comprises differential algebraic equations.

5. The method of claim 1, wherein computing the second solver function comprises computing a property value from a selected data set of the initial solution by one or more criterion spreadsheet functions using a prescribed calculus operation selected from one of integration, differentiation, and interpolation using a spline curve fitting of the selected data set.

6. The method of claim 1, wherein computing the second solver function comprises computing a property value from a selected data set of the initial solution by one or more criterion spreadsheet functions receiving a first formula to map individual ones of the selected data set and a second formula to map all of the selected data set to the property value.

7. The method of claim 1, wherein computing the first solver function comprises computing an integral of said one or more formula expressions.

8. The method of claim 7, wherein computing the integral comprises recursively computing nested multiple integrals of said one or more formula expressions.

9. The method of claim 1, wherein computing the first solver function comprises computing a derivative of said one or more formula expressions.

10. The method of claim 9, wherein computing the derivative comprises recursively computing nested or mixed partial derivatives of said one or more formula expressions.

11. The method of claim 1, wherein computing the first solver function comprises computing a response of an ordinary differential-algebraic equations system.

12. The method of claim 11, wherein displaying the values of the initial solution comprises displaying values of the response in a tabular array of the datasheet;

wherein values of the equations system'"'"'s independent variable are listed in a first column of the tabular array; and

wherein corresponding values of the equations system'"'"'s dependent variables are listed in subsequent columns of the tabular array.

13. The method of claim 1, wherein computing the first solver function comprises computing a response of a partial differential-algebraic equations system.

14. The method of claim 13, wherein displaying the values of the initial solution comprises displaying values of the response in a tabular array of the cells;

wherein values of the equations system'"'"'s first independent variable being listed in ascending order in a first column of the tabular array;

wherein values of the equations system'"'"'s second independent variable being listed in blocks of ascending order in a first row of the tabular array; and

wherein values of the equations system'"'"'s dependent variables being listed in multiple columns, such that values in each dependent variable column correspond to the values of the first independent variable in the first column and the values of the second independent variable in the first row.

15. The method of claim 1, wherein computing the first solver function comprises computing a solution to a system of algebraic equations and inequalities.

16. The method of claim 1, wherein computing the second solver function comprises computing a solution to a system of equations and inequalities.

17. The method of claim 1, wherein E2) comprises:

evaluating the relational nodes for the formula expressions in an order of their interdependence to obtain the values of the relational nodes for the formula expressions, and aggregating the values of the relational nodes to obtain the values of the formula expressions;

wherein the graph evaluator evaluates the values of the relational nodes in accordance with the values of the variables of the formula expressions.

18. The method of claim 1, wherein E) comprises:

computing the first solver function to obtain the initial solution without using a dialogue interface.

19. The method of claim 1, wherein the first solver function is a pure function.

20. The method of claim 1, wherein H) comprises:

computing the second solver function to obtain the optimized solution of the parameterized equation system without using a dialogue interface.

21. The method of claim 1, wherein the second solver function is a pure function.

22. A computer program product in combination with a spreadsheet software program for optimizing solution of a parameterized equation system that satisfies one or more constraints, the computer program product and the spreadsheet software application being stored in a non-transitory storage medium and, when executed by a computer device, causing the computer device to perform a method comprising:

A) displaying and operating a tabular datasheet having a plurality of cells each being designated with a column identifier and a row identifier, the cells being configured to receive input and display output;

B) receiving, from a first group of the cells, one or more formula expressions representing the parameterized equation system, each of the formula expressions including a first sequence of substrings respectively representing a logical building block of the parameterized equation system;

C) receiving, from a second group of the cells, variables of the formula expressions and, from a third group of the cells, parameters of the formula expressions;

D) receiving, from a fourth group of the cells, a first solver function of the spreadsheet software application having one or more first input arguments, the first input arguments at least referencing the formula expressions in the first group of the cells and the variables in the second group of the cells;

E) computing the first solver function to obtain an initial solution of the parameterized equation system, and displaying values of the initial solution in the fourth group of the cells;

wherein computing the first solver function comprises;

E1) constructing, for each of the formula expressions, an evaluable tree-structured graph of relational nodes containing an equivalent sequence of evaluable sub-expressions of said one or more formula expressions;

E2) evaluating, by a graph evaluator, the relational nodes for the formula expressions to obtain values of the formula expressions based on values of the variables of the formula expressions; and

E3) using an underlining algorithm of the first solver function to compute the initial solution in accordance with the formula expressions in the first group of the cells and the variables in the second group of the cells;

wherein the underlining algorithm of the first solver function utilizes the graph evaluator to repeatedly evaluate the parameterized equation system for the values of the variables thereby computing the initial solution;

F) receiving, from a fifth group of the cells, one or more constraint expressions representing the constraints for the parameterized equation system, each of the constraint expressions including a second sequence of substrings respectively representing a logical building entity of the constraint expressions, said one or more constraint expressions referencing the initial solution in the fourth group of the cells;

G) receiving, from a sixth group of the cells, a second solver function of the spreadsheet software application having one or more second input arguments, the second input arguments at least referencing the constraint expressions in the fifth group of the cells and the parameters in the third group of the cells;

H) computing the second solver function to obtain an optimized solution of the parameterized equation system, and displaying values of the optimized solution in the sixth group of the cells;

wherein computing the second solver function comprises;

H1) constructing, for each of the constraint expressions, an evaluable tree-structured graph of relational nodes containing evaluable sub-expressions including an expression of the first solver function;

H2) evaluating, by the graph evaluator, the relational nodes for the constraint expressions to obtain dynamic values of the constraint expressions based on values of the parameters in the third group of the cells;

wherein evaluating the relational nodes for the constraint expressions comprises computing a solution of the first solver function at said values of the parameters; and

H3) using an underlining algorithm of the second solver function to compute the optimized solution in accordance with the constraint expressions in the fifth group of the cells and the parameters in the third group of the cells;

wherein the underlining algorithm of the second solver function utilizes the graph evaluator to repeatedly evaluate the dynamic values of the constraints expressions for the values of the parameters thereby computing the optimized solution.

23. The computer program product of claim 22, wherein computing the first solver function comprises computing an integral of said one or more formula expressions.

24. The computer program product of claim 23, wherein computing the integral comprises recursively computing nested multiple integrals of said one or more formula expressions.

25. The computer program product of claim 22, wherein computing the first solver function comprises computing a derivative of said one or more formula expressions.

26. The computer program product of claim 25, wherein computing the derivative comprises recursively computing nested or mixed partial derivatives of said one or more formula expressions.

27. The computer program product of claim 22, wherein computing the first solver function comprises computing a response of an ordinary differential-algebraic equations system.

28. The computer program product of claim 22, wherein computing the first solver function comprises computing a response of a partial differential-algebraic equations system.

29. The computer program product of claim 22, wherein computing the first solver function comprises computing a solution to a system of algebraic equations and inequalities.

30. A computer apparatus for optimizing solution of a parameterized equation system that satisfies one or more constraints using a spreadsheet software application, the computer apparatus comprising a hardware processor configured to perform a method comprising:

A) displaying and operating a tabular datasheet by executing the spreadsheet software application on the computer apparatus, the tabular datasheet having a plurality of cells each being designated with a column identifier and a row identifier, the cells being configured to receive input and display output;

B) receiving, from a first group of the cells, one or more formula expressions representing the parameterized equation system, each of the formula expressions including a first sequence of substrings respectively representing a logical building block of the parameterized equation system;

C) receiving, from a second group of the cells, variables of the formula expressions and, from a third group of the cells, parameters of the formula expressions;

D) receiving, from a fourth group of the cells, a first solver function of the spreadsheet software application having one or more first input arguments, the first input arguments at least referencing the formula expressions in the first group of the cells and the variables in the second group of the cells;

E) computing the first solver function to obtain an initial solution of the parameterized equation system, and displaying values of the initial solution in the fourth group of the cells;

wherein computing the first solver function comprises;

E1) constructing, for each of the formula expressions, an evaluable tree-structured graph of relational nodes containing an equivalent sequence of evaluable sub-expressions of said one or more formula expressions;

E2) evaluating, by a graph evaluator, the relational nodes for the formula expressions to obtain values of the formula expressions based on values of the variables of the formula expressions; and

E3) using an underlining algorithm of the first solver function to compute the initial solution in accordance with the formula expressions in the first group of the cells and the variables in the second group of the cells;

wherein the underlining algorithm of the first solver function utilizes the graph evaluator to repeatedly evaluate the parameterized equation system for the values of the variables thereby computing the initial solution;

F) receiving, from a fifth group of the cells, one or more constraint expressions representing the constraints for the parameterized equation system, each of the constraint expressions including a second sequence of substrings respectively representing a logical building entity of the constraint expressions, said one or more constraint expressions referencing the initial solution in the fourth group of the cells;

G) receiving, from a sixth group of the cells, a second solver function of the spreadsheet software application having one or more second input arguments, the second input arguments at least referencing the constraint expressions in the fifth group of the cells and the parameters in the third group of the cells;

H) computing the second solver function to obtain an optimized solution of the parameterized equation system, and displaying values of the optimized solution in the sixth group of the cells;

wherein computing the second solver function comprises;

H1) constructing, for each of the constraint expressions, an evaluable tree-structured graph of relational nodes containing evaluable sub-expressions including an expression of the first solver function;

H2) evaluating, by the graph evaluator, the relational nodes for the constraint expressions to obtain dynamic values of the constraint expressions based on values of the parameters in the third group of the cells;

wherein evaluating the relational nodes for the constraint expressions comprises computing a solution of the first solver function at said values of the parameters; and

H3) using an underlining algorithm of the second solver function to compute the optimized solution in accordance with the constraint expressions in the fifth group of the cells and the parameters in the third group of the cells;

wherein the underlining algorithm of the second solver function utilizes the graph evaluator to repeatedly evaluate the dynamic values of the constraints expressions for the values of the parameters thereby computing the optimized solution.