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 many types of HP-hard problems. These are problems where the combinatorial explosion of the search space makes determination of an optimal solution impossible in a viable amount of time. .

The invention is incorporated in the NP-Hard Solver library developed in C++. The main components are a truth maintenance system for hypothetical reasoning and a non-monotonic search engine

The library that enables creation of applications to find very good solutions to extremely complex problems such as routing, scheduling, language translation, language understanding, data analysis, cryptography, vision recognition, voice recognition, weather forecasting, and climate forecasting.

To show the capabilities of the library I have developed three 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 NP-Hard Solver 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 NP-Hard Solver 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

The problems must allow non-monotonic reasoning – that is, if an assumption if retracted, all subsequent assumptions do not necessarily have to be retracted. For instance, the NP-Hard Solver would be of no value for a chess playing program

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