Problem modeling in resource optimization

Details Problem modeling in resource optimization Problem modeling in resource optimization

1998-12-30

2002-06-25

Teska, Kevin J. (Department: 2123)

Data processing: structural design, modeling, simulation, and em

Modeling by mathematical expression

C703S020000, C709S203000, C707S793000

Reexamination Certificate

active

06411922

ABSTRACT:

TECHNICAL FIELD
This invention generally relates to a system and method for resource optimization, and more particularly to a system and method for problem modeling in resource optimization.
BACKGROUND
Generally, the amount of profit that a company earns is directly related to how efficiently the company can utilize its costly or limited resources. The optimal allocation of resources is therefore a critical function in many areas of business for both the service and manufacturing industries. Optimal allocation of resources can, for example, lower costs, reduce waste, shorten cycle time, improve throughput or response time, accelerate delivery time, and optimize equipment design. Some business allocation problems are simple enough to be solved with a direct solution. For many other resource allocation problems, however, the problem structure is complex or the number of possible solutions is extremely large. Optimization techniques have been developed for these situations to determine the optimal solution from a set of possible solutions.
There are many business domains in which optimization techniques provide significant improvement in resource allocation. Optimization can benefit business situations which involve, for example, costly assets, high sensitivity to tradeoffs among decision factors, or narrow margins for error. Specifically, applications for optimization include telecommunications network optimization, supply chain optimization, logistics resource allocation in airports and ports, manpower scheduling, maintenance scheduling, production planning, vehicle dispatching, and technician dispatching.
There are a variety of optimization techniques available, and the specific type used generally depends on the structure of the problem. Typically, if all variables are real, and all functions are linear, then linear programming is appropriate. If a problem includes integer variables, then integer programming may be used. Other techniques include the use of genetic algorithms to control evolution of the population of solutions, and the use of simulated annealing to control the rate movement in the solution space. The technique of domain reduction and constraint propagation is useful for problems with a wide variety of variables and constraints, such as integer, logical and choice variables, and linear and logical constraints. Each of these techniques is described more fully in “Optimization Technology White Paper,” ILOG, Inc., 1997.
Generally, optimization involves two phases: first modeling the problem and then solving the problem. Modeling of the problem is typically performed by an application developer while designing software for a particular user application. Solving of the problem is then typically performed by a solver program at the request of the user application.
In the prior art, an application developer familiar with operations research algorithms generally models a problem manually. The developer typically speaks with a domain expert familiar with the particular industrial application or problem. The expert communicates the problem to be solved in descriptive terms to the developer, who then interprets the information and transforms it into a mathematical model consisting of objective and/or cost functions, and constraints, which abstractly represent the problem. These are often represented as mathematical matrices for traditional linear/integer programming algorithms. The terms “objective” and “cost,” when used in reference to functions, are used interchangeably herein. The developer typically writes software code containing the mathematical model in an object oriented software language such as C++ by calling functions stored in C++ class libraries supplied with a vendor's optimization software suite.
This method of implementation effectively creates a hard-coded mathematical model of the problem for a specific application. This occurs, for example, because simplifying assumptions are generally made about the problem which are very specific to a given application. The result is then a specialized optimization model for a specific application in a specific domain, such as a specific video conferencing network scheduler system for a particular customer. The application developer inputs the information into a fixed data source, from which a user application may extract data and transform it into parameters that are transferred to the solver program. Generally, the data extracted from the data source is transformed using hard-coded functions generated in the implementation phase by the application developer. The parameters are provided to the problem solver in a very specific format so that the problem solver can process them. The developer may also write an application programming interface (API) to handle the interface between the solver program and the application program.
During operation, the user application program sends a solution request to the solver program. The solver program calculates an optimal solution for the solution request by applying an optimization technique to the solution request, subject to the parameters provided by the user application, and then returns an optimized solution result to the application program.
SUMMARY OF THE INVENTION
Prior art optimization software suites may contain a solver program which can receive a solution request from a user application via an API, interpret parameters representing the characteristics of the problem and transferred in a specific format from the user application, calculate an optimized solution, and return the optimized solution to the user application via the API. The prior art optimization software suites, however, still require that an application developer manually hard-code functions for the transformation of the data from the data source into the properly formatted parameters to be interpreted by the problem solver.
Accordingly, it is an object of the present invention to generally provide a generic problem modeler which can examine an existing user information resource and transform the relevant information from the resource into data that can be stored in a solver database which is directly accessible by a problem solver.
It is another object of the invention to provide a generic problem modeler which generally requires substantially less user skill than prior art systems and methods for creating models for resource optimization problems.
These and other objects, features and technical advantages generally are achieved by a system and method which examine a user information resource and transform data objects and object relationships from the resource into optimization metrics for storage in a problem solver database. A preferred embodiment resource optimization system in accordance with the present invention comprises a problem modeler having an interface for retrieving user data objects and object relationships describing a user application from a user information resource, a solver database to which the problem modeler has an interface for storing optimization metrics derived from the user data objects and object relationships by the problem modeler, and a problem solver having an interface to the solver database for retrieving the optimization metrics for solving resource optimization problems for the user application.
A preferred embodiment method for robotically modeling a user application optimization problem in accordance with the present invention comprises examining a user information resource for database objects and object relationships relevant to solving the optimization problem, transforming the database objects and object relationships into optimization metrics readable by a solver program, and storing the optimization metrics in a solver database accessible by the solver program. A preferred embodiment method for robotically solving a user application optimization problem additionally comprises receiving a solution request to the optimization problem from the user application, retrieving the optimization metrics from the solver database, calculating

Affiliated with

Also associated with

Rating

Problem modeling in resource optimization does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Problem modeling in resource optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Problem modeling in resource optimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2925980