Optimization using a multi-dimensional data model

• US 7,031,955 B1
• Filed: 04/27/2001
• Issued: 04/18/2006
• Est. Priority Date: 04/27/2001
• Status: Expired due to Fees

• Current Assignee: JDA Software Group Incorporated (RedPrairie Holding Incorporated)
• Original Assignee: i2 Technologies US Incorporated (Panasonic Holdings Corporation)
• Inventors: de Souza, Pedro S., Abada, Assia, Mallipeddi, Rajasekhar, Kazzaz, Yasser A.
• Primary Examiner(s): Corrielus, Jean M.
• Assistant Examiner(s): To, Baoquoc N.
• Application Number:
  US09/844,847
• Time in Patent Office: 1,817 Days
• Field of Search: 707/3, 707/4, 707/5, 707/10, 707/101, 707/102, 707/103.Y, 707/103, 707/2, 707/100
• US Class Current: 1/1
• CPC Class Codes: G06Q 10/00 Administration; Management
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/957 Multidimensional
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A system (10) for optimization using multi-dimensional data includes a server (12) that uses a multi-dimensional data model to organize data stored at one or more data storage locations (14). The multi-dimensional data model includes a number of data dimensions (50, 70) that each include a hierarchy of members (54, 74). The server (12) receives input from a user specifying a problem instance to be solved using an optimization engine (20). The problem instance is specified by the user in a multi-dimensional format and the optimization engine (20) is unable to solve the problem instance in the multi-dimensional format. The system (10) also includes a transformation module (22) that receives the problem instance in the multi-dimensional format, transforms the problem instance into a format appropriate for the optimization engine (20), and communicates the transformed problem instance to the optimization engine (20) to be solved.

Claims

1. A system for optimization using multi-dimensional data, comprising:

a server operable to;

using a multi-dimensional data model, organize data stored at one or more data storage locations, the multi-dimensional data model including a plurality of data dimensions each including a hierarchy of members;

receive input from a user specifying a problem instance to be solved using an optimization engine, the problem instance specified by the user in a multi-dimensional format, the optimization engine being unable to solve the problem instance in the multi-dimensional format, the problem instance including;

a problem domain including all data in the multi-dimensional data model located hierarchically below one or more specified intersections in the multi-dimensional data model, each intersection identified by specifying a member in each data dimension;

an evaluation level specified by identifying a particular level in the hierarchy of each data dimension;

an objective function including a data measure or a combination of data measures to be optimized; and

one or more problem constraints; and

communicate the problem instance in the multi-dimensional format; and

a transformation module operable to;

receive the problem instance in the multi-dimensional format;

transform the problem instance into a format appropriate for the optimization engine, the transformation including parsing the received problem instance to identify pre defined multi-dimensional syntax and translating the multi-dimensional syntax to a syntax appropriate for the optimization engine;

communicate the transformed problem instance to the optimization engine to be solved;

receive a solution associated with the problem instance from the optimization engine;

transform the solution into the multi-dimensional format; and

communicate the transformed solution to the server.

2. The system of claim 1, further comprising a business repository operable to store the multi-dimensional data model, the server further operable to communicate with the business repository to access data specified using the multi-dimensional format.

3. The system of claim 1, wherein transforming the problem instance further comprises generating multiple problem constraints in a format appropriate for the optimization engine from a single problem constraint included in the received problem instance, the single problem constraint identifying a member in each data dimension to which the constraint is applicable.

4. The system of claim 1, wherein transforming the problem instance further comprises importing data applicable to the problem instance from one or more data storage locations, the imported data being included in the transformed problem instance in a format appropriate for the optimization engine.

5. The system of claim 1, wherein one or more data measures included in the objective function have an associated data value in a data storage location for each of one or more intersections in the problem domain.

6. The system of claim 1, wherein the objective function further comprises an aggregation domain for each data measure.

7. The system of claim 1, wherein the server is further operable to replicate a single constraint in the multi-dimensional format into multiple constraints in the multi-dimensional format, the single constraint including one or more coverage sets identifying multiple members of one or more data dimensions to which the constraint applies.

8. A method for optimization using multi-dimensional data, comprising:

receiving a problem instance to be solved using an optimization engine, the problem instance specified in a multi-dimensional format associated with a multi-dimensional data model including a plurality of data dimensions each including a hierarchy of members, the optimization engine being unable to solve the problem instance in the multi-dimensional format, the problem instance including;

a problem domain including all data in the multi-dimensional data model that located hierarchically below one or more specified intersections in the multi-dimensional data model, each intersection identified by specifying a member in each data dimension;

an evaluation level specified by identifying a particular level in the hierarchy of each data dimension;

an objective function including a data measure or a combination of data measures to be optimized; and

one or more problem constraints; and

communicate the problem instance in the multi-dimensional format; and

using a transformation module, transforming the problem instance into a format appropriate for the optimization engine, the transformation including parsing the received problem instance to identify pre-defined multi-dimensional syntax and translating the multi-dimensional syntax to a syntax appropriate for the optimization engine;

communicating the transformed problem instance to the optimization engine to be solved;

receiving a solution associated with the problem instance from the optimization engine;

using the transformation module, transforming the solution into the multi-dimensional format; and

communicating the transformed solution to the server.

9. The method of claim 8, wherein transforming the problem instance further comprises:

parsing the received problem instance to identify pre-defined multi-dimensional syntax; and

translating the multi-dimensional syntax to a syntax appropriate for the optimization engine.

10. The method of claim 8, wherein transforming the problem instance further comprises importing data applicable to the problem instance from one or more data storage locations, the imported data being included in the transformed problem instance in a format appropriate for the optimization engine.

11. The method of claim 8, wherein one or more data measures included in the objective function have an associated data value in a data storage location for each of one or more intersections in the problem domain.

12. The method of claim 8, wherein the objective function further comprises an aggregation domain for each data measure.

13. The method of claim 8, further comprising automatically replicating a single constraint in the multi-dimensional format into multiple constraints in the multi-dimensional format, the single constraint including one or more coverage sets identifying multiple members of one or more data dimensions to which the constraint applies.

14. Software enabling optimization using multi-dimensional data, the software embodied in a computer-readable medium and when executed operable to:

receive a problem instance to be solved using an optimization engine, the problem instance specified in a multi-dimensional format associated with a multi-dimensional data model including a plurality of data dimensions each including a hierarchy of members, the optimization engine being unable to solve the problem instance in the multi-dimensional format, the problem instance including;

a problem domain including all data in the multi-dimensional data model located hierarchically below one or more specified intersections in the multi-dimensional data model, each intersection identified by specifying a member in each data dimension;

an evaluation level specified by identifying a particular level in the hierarchy of each data dimension;

an objective function including a data measure or a combination of data measures to be optimized; and

one or more problem constraints; and

communicate the problem instance in the multi-dimensional format; and

transform the problem instance into a format appropriate for the optimization engine, the transformation including parsing the received problem instance to identify pre-defined multi-dimensional syntax and translating the multi-dimensional syntax to a syntax appropriate for the optimization engine;

communicate the transformed problem instance to the optimization engine to be solved;

receive a solution associated with the problem instance from the optimization engine;

transform the solution into the multi-dimensional format; and

communicate the transformed solution to the server.

15. The software of claim 14, wherein transforming the problem instance further comprises generating multiple problem constraints in a format appropriate for the optimization engine from a single problem constraint included in the specified problem instance, the single problem constraint identifying a member in each data dimension to which the constraint is applicable.

16. The software of claim 14, wherein transforming the problem instance further comprises importing data applicable to the problem instance from one or more data storage locations, the imported data being included in the transformed problem instance in a format appropriate for the optimization engine.

17. The software of claim 14, wherein one or more data measures included in the objective function have an associated data value in a data storage location for each of one or more intersections in the problem domain.

18. The software of claim 14, wherein the objective function further comprises an aggregation domain for each data measure.

19. The software of claim 14, further operable to replicate a single constraint in the multi-dimensional format into multiple constraints in the multi-dimensional format, the single constraint including one or more coverage sets identifying multiple members of one or more data dimensions to which the constraint applies.

20. A system for optimization using multi-dimensional data, comprising:

means for receiving a problem instance to be solved using an optimization engine, the problem instance specified in a multi-dimensional format associated with a multi-dimensional data model including a plurality of data dimensions each including a hierarchy of members, the optimization engine being unable to solve the problem instance in the multi-dimensional format;

means for including a problem domain including all data in the multi-dimensional data model that is located hierarchically below one or more specified intersections in the multi-dimensional data model, each intersection identified by specifying a member in each data dimension;

means for including an evaluation level specified by identifying a particular level in the hierarchy of each data dimension;

means for including an objective function including a data measure or a combination of data measures to be optimized and one or more problem constraints;

means for transforming the problem instance into a format appropriate for the optimization engine;

means for parsing the received problem instance to identify pre defined multi-dimensional syntax;

means for translating the multi-dimensional syntax to a syntax appropriate for the optimization engine;

means for communicating the transformed problem instance to the optimization engine to be solved;

means for receiving a solution associated with the problem instance to the optimization engine;

means for transforming the solution into the multi-dimensional format; and

means for communicating the transformed solution to the server.