Data processing: financial – business practice – management – or co – Automated electrical financial or business practice or... – Operations research or analysis
Patent
1996-12-20
1999-06-15
MacDonald, Allen R.
Data processing: financial, business practice, management, or co
Automated electrical financial or business practice or...
Operations research or analysis
705 8, G06F 1760
Patent
active
059131993
DESCRIPTION:
BRIEF SUMMARY
FIELD OF THE INVENTION
The invention relates to a process and a system for automatic, computer-system-supported optimisation in accordance with the preambles to Claims 1 and 15.
BACKGROUND OF THE INVENTION
In many technical areas there are difficult optimisation problems, which can only be solved to a very limited extent by an automated technical--mathematical computer treatment. Thus, traditional optimisation systems are often already pushed to their limits in the interpretation of simple telephone, power, water distribution or remote heating networks and deliver inadequate results. Similar problems arise in the numerical control of machine tools, in laying out electronic circuits on one integrated computer chip as well as in drawing up plans for optimal loading of machines--or fleets of vehicles. Particularly complex problems were thus often handled only with intuition and experience, but not with the aid of computers.
Classic processes for the solution--even though it might be of only limited usefulness--of more complex optimisation problems (where "solution" for any problem is to be understood as the solvable "solution" to that problem, but not the "optimal" solution) make use of iterative processes with local change searches. Thus, for example, there is an iterative solution to the problem of finding the shortest connecting route through a given number of places, often of course generally solutions, which are about 10% from the optimum. However, 10% in the case of complex and economically significant optimisation problems like chip placement is a deviation which is fundamentally no longer acceptable.
Different optimization methods in accordance with the state of the art are found in the following articles, which are incorporated herein in their entirety by reference: Oldenbourg, 3rd edition (199); Parallele Systeme und Algorithmen, Bonn l./2. April 1993, pp.81-87; Algorithm Appearing superior to Simulated Annealing", Journal of Comp. Physics, Vol. 9, pp. 161-165, 199; in der Transportwirtschaft", Verlag "Peter Lang".
According to DUECK et al., optimisation problems with a technical background can be formulated in mathematical language as follows: Given a number X of states x (or "solutions"). Since the states have a kind of geometric mutual relationship--one can describe two very similar ones as narrowly adjacent, two very different ones as remote -, X is also called a space of states. In this space a real value target function f is defined. That is to say: For each state x from the space X a real number f (x) can be calculated, which should represent a measure of the quality of x: for example f (x) can be the length of a tour x or the number of parts in a knapsack with the package x. Optimize means: look for a state x in the space X, for which f (x) is minimal (as in the Travelling Salesman problem) or maximum (as in the knapsack problem). Since minimizing f means the same as maximizing -f, only a theory for maximizing is necessary (cf. also: "Optimieren mit Evolutionsstrategien" by Paul Ablay, Spektrum der Wissenschaft, July 1987, page 14).
It is generally usual, for the solution of scheduling problems, such as the Travelling Salesman problem, to use iterative processes with local change search, where the search for a good solution starts with any solution, for example, a spontaneously selected round tour. An optimizing computer changes this and checks, whether the new solution is better (shorter). If so, the optimizing computer replaces the old tour by the new and checks again: Can it be changed around, so that an even better solution results? If it succeeds in doing so, it continues working with this solution, until the solution found can no longer be improved by changing it locally (local optimum or minimum). Such iteration methods can become very complicated even in local extrema, without getting sufficiently close to an overall extremum.
A clear improvement over the classical optimizing method results from the processes developed by DUECK et al., "Threshold Accepting (TA)" and "flood". This
REFERENCES:
patent: 4983898 (1991-01-01), Kanda
patent: 5196997 (1993-03-01), Kurtzberg et al.
patent: 5325292 (1994-06-01), Crockett
Dueck Gunter
Eddelbuttel Jochen
Gerhardt Martin
Pospiech Christof
Reusch Hans-Georg
International Business Machines Corp.
Kaufman, Esq. Stephen C.
Kazimi Hani. M.
MacDonald Allen R.
LandOfFree
Process and system for automatic, computer-system-supported opti does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Process and system for automatic, computer-system-supported opti, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Process and system for automatic, computer-system-supported opti will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-410408