Data processing: artificial intelligence – Miscellaneous
Reexamination Certificate
1998-10-29
2001-08-07
Chaki, Kakali (Department: 2122)
Data processing: artificial intelligence
Miscellaneous
C706S061000
Reexamination Certificate
active
06272483
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to computerized information management and, more particularly, to systems and methods of optimization that can be used independently or as part of a hybrid global/local approach.
2. Description of the Related Art
A class of problems known as “Optimization Problems” arises often in diverse areas such as resource allocation, event planning, and the like. These problems are characterized in having a set of elements and a set of possible resources, and in calling for a particular assignment of elements to resources that approaches optimality in some measurable manner. Processes using artificial intelligence (AI) techniques have been applied to such optimization problems to find solutions.
“Elements,” as used herein, refers to a set of things, such as tasks, variables, or people, that is assigned to one or more resources. For example, elements may be tasks or people in a scheduling problem or variables in a register allocation problem. “Resources,” in contrast, refers to a set of things to which the elements are assigned. For example, resources may be manufacturing lines capable of performing tasks, doctors capable of meeting with patients, or registers capable of holding variables. In general, the set of resources is relatively fixed and defines the domain of the problem while the set of elements typically changes for each problem instance. In the example of patients and doctors described above, the set of patients (elements) may change every day, but the set of doctors (resources) remains relatively stable.
Other optimization problems include planning feasible schedules for meetings, assisting scientists in interpreting images from artificial vision devices, and even allowing cartographers to select colors for countries or other municipal areas when designing maps. A particular example of an optimization problem is scheduling a manufacturing process for fiber optic cables. This type of problem features multiple tasks/jobs and multiple manufacturing lines on which jobs can be run. Each job corresponds to a cable to be made, and each cable has certain characteristics that affect how and when it can be manufactured. These include a release time, a deadline, and a length for each job.
Continuing with this example, each line may have different characteristics affecting which cables can be made on each, and how fast each line is. Furthermore, there is a changeover cost between any two adjacent jobs on a given line. A goal for such a sample problem might be to minimize lateness (missed deadlines) and changeover costs.
This type of optimization problem may be decomposed into subproblems involving subschedules for the individual lines. It is desirable in such a problem to find a assignment of line schedules that have each job scheduled exactly once and to do so with minimal cost.
Optimization problems are related to another set of problems known as constraint-satisfaction problems, or CSPs. One approach to dealing with such problems uses artificial intelligence (AI) search techniques in one of two ways. The first way is known as “systematic” because under this approach, every possible set of element-resource pairings is eventually considered, unless a set of pairings that meets all of the constraints is found at some point in the process. These processes often rely on maintaining a database of possible reasons why certain assignments, or groups of assignments, will not satisfy the constraints of the problem. The sets of reasons indicating assignments that do not work are commonly referred to as sets of “nogoods”. When a process of this class fails to provide a set of workable assignments, one can be sure that no workable set of assignments exists. Numerous such systematic processes are known, for instance as described in M. L. Ginsberg, Dynamic Backtracking,
JOURNAL OF ARTIFICIAL I
NTELLIGENCE
R
ESEARCH
1:25-46, 1993.
The second way is known as “nonsystematic” and is typically faster to find a solution. However, because processes of this class do not keep track of whether they have considered all possible sets of element-resource pairings, where such processes do not yield a solution, one cannot know whether a workable set of assignments exists but has not been found, or whether no workable set of assignments exists. A well-known example of such a nonsystematic technique is the GSAT technique, now known under an improved version as WSAT and described in B. Selman, et al., Local Search Strategies for Satisfiability Testing, P
ROCEEDINGS
1993 DIMACS W
ORKSHOP ON
M
AXIMUM
C
LIQUE
, G
RAPH
C
OLORING, AND
S
ATISFIABILITY
, 1993.
Several other known strategies within these two broad classes of processes have been employed to solve CSPs.
One known process is to simply apply a heuristic, or “rule of thumb,” and to see whether the heuristic results in an acceptable solution. One such heuristic might be: If machine A is available, use it; otherwise if machine B is available use it; otherwise if machine C is available use it; otherwise wait for machine A to finish and then use it. In some instances, such a technique works very well and provides a simple solution. When the heuristic fails, however, alternate techniques must be used.
One possible alternate scheme, known as iterative sampling, or isamp, involves following random paths, or probes, from a starting point to a candidate solution until eventually a path leading to an acceptable solution is discovered. At each node on a path, one of the successor nodes is selected at random and followed; next, one of the successors to that node is selected, and so on, until either a “goal node”, i.e., acceptable solution, or a dead end is reached. If a path terminates at a dead end, a new probe is begun from the original starting point.
This process samples with replacement, resulting in a uniform chance of finding a goal node on any particular probe. Accordingly, the probability of achieving a goal node progresses uniformly to 1 as the number of probes grows without limit.
Iterative sampling works well in applications exhibiting high solution densities, but not otherwise.
Another scheme, known as “backtracking,” uses the heuristic approach as far as possible. When the heuristic is found to fail, the last decision before the failure is changed, unless all possible changes at that point have already been tried. If they have, the decision prior to that is changed, and so on. This process works well where heuristics early in the process are more reliable than those later in the process, because it does not revisit the earliest decisions until all of the subsequent paths have been found to fail. Unfortunately, in most real-world problems, heuristics generally become more reliable as a solution is approached and the problem is reduced in size.
Similarly, a number of approaches have been developed for processing optimization problems. As with CSP, heuristic approaches have been widely used, and have the advantage of speed and scalability (i.e., ability to handle problem instances of increasing size gracefully). Exact approaches, on the other hand, often provide results that are closer to the theoretically optimal results, but require much more time-consuming processing to do so.
The Operations Research (OR) community has a history of successfully solving large optimization problems that can be formulated as Linear Programming/Integer Programming (LP/IP) problems. For truly large problems, it is not computationally possible to pass a full definition of a problem (all possible rows and all possible columns) to an LP/IP engine. To even enumerate, let alone solve, such large problems would take more resources than feasible for many commercial purposes.
The particular type of problem described above is somewhat decomposable into subproblems, but is not fully decomposable because there is interaction among the subproblems. This class of problem allows for parts of different solutions to be recombined to form new solutions. Typical OR approaches to such problems begin with generating on
Clements David P.
Joslin David E.
Chaki Kakali
Fenwick & West LLP
Starks, Jr. Wiblert L.
The State of Oregon acting by and through the State Board of Hig
LandOfFree
Cost-optimizing allocation system and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cost-optimizing allocation system and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cost-optimizing allocation system and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2539525