The Problem

There are many problems that computers cannot solve.

One type has a deterministic and computable solution, but there are so many combinations of data that the computing time required to solve them is astronomically long. Such problems reside in the realm of chaos theory and computational complexity theory.

Some examples of these problems are routing, scheduling, language translation, language understanding, data analysis, cryptography, vision recognition, voice recognition, weather forecasting, and climate forecasting.

There is no ability to consistently find optimal solutions for these problems. The best that can be done at present is to try for an acceptable to good solution.

The Solution

I have invented a new method to find near-optimal solutions for these problems. There is no other software that can do this.

The invention is incorporated in the Optimization Library. The Optimization Library is a C++ library that enables creation of applications to find very good solutions to extremely complex problems.

To demonstrate the capabilities of the library I have developed four applications:

First, two classical problems with a large body of known optimal solutions were benchmarked to establish the ability to create near optimal solutions. Those benchmark problems are necessarily very simple.

The other two applications show the ability of the library to handle extremely complex problems.

The traveling salesman problem is a classic and well researched problem. Approximation methods have recently improved that guarantee a solution within 40% of the optimal solution. An application written using the Optimization Library averages less than one half of 1% (0.35%) over optimal, with the worst single result 1.84% over optimal. These results, and benchmarks of the capacitated vehicle routing problem, can be viewed here: benchmarks

The traveling salesman problem is actually not a good problem for this technology because the problem is under-constrained and, hence, more dependent on raw search than realistic problems. The Optimization Library is designed to solve very complex problems with intricate data modeling. For instance – if we added a few things to the traveling salesman problem, such as a truck inventory, drivers, delivery schedule requirements, and package weights, the library would perform very well. The approximation methods for the traveling salesman problem would be unable to handle such requirements.

There are two demonstration systems to show the ability to handle very complex problems.

The Reconnaissance Aircraft Problem plans missions to many targets from an inventory of aircraft. It is an extraordinarily complex problem because the program optimizes aircraft speed and fuel consumption to create a plan. Reconnaissance Aircraft Problem

The Job Shop Scheduler plans machines, operators, tooling, machine setups and other resources to optimize meeting due dates and minimize factory operating costs. It plans time-dependent tasks, auxiliary resources, and other situations that require concurrent resource scheduling. It supports minimum transfer quantity operation overlapping. It can split a single task across multiple resources to improve on time performance or split a single task to use multiple non-continuous time intervals. It is a very complex and realistic application. Job Shop Scheduler

The library is written in C++.

For information about library features, click here

For information about the C++ classes and programming the library click here

And, of possible interest, what about Quantum Computers?

Thank you for your interest.
George Anderson Yates


          Site Index     Site Search     About George Yates     Contact Me