Question - Karmarkar's Algorithm
- To: mathgroup at smc.vnet.net
- Subject: [mg33719] Question - Karmarkar's Algorithm
- From: Mark Van Noy <mvannoy at mac.com>
- Date: Mon, 8 Apr 2002 03:05:06 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
I am working on an AI project and have been looking for a computer application of "Karmarkar's Algorithm." I had half expected that Mathematica would contain this application. However, the information on Wolfram's website doesn't mention it. Is there an available application of Mathematica that implements Karmarkar's Algorithm? BACKGROUND: Mr. Karmarkar's algorithm was highlighted in a scientific publication around 1989. At that time it was very new. The story is basically this: Mr. Karmarkar is (was?) a mathematician working for AT&T (Bell Labs?). He came up with an optimization algorithm that far exceeds the ability of linear algebra. Its advantage is that it can work with a very large number of variables and still quickly calculate an accurate solution, using a reasonable amount of computing power. The "secret" of the algorithm is that it uses vectors. AT&T's application was/is rapid optimization of phone call routing during heavy calling periods. Another obvious application is 'real-time' scheduling of airline equipment, crews, gates, times, and routes. The ability to do this on the fly (so to speak), using desktop computing rather than mainframes, has significant implications. According to the article, AT&T would not let Mr. Karmarkar discuss it or publish his findings, due to obvious commercial considerations. When AT&T had completed implementation, they allowed him to present them in a professional forum. After he made his presentation, there was discussion of whether it actually worked, and some challenged his assertions. In defense of his professional standing, Mr. Karmarkar found it necessary to meet with doubters on an individual basis to explain his algorithm. Right now, this project is wholly my personal creation (i.e., I am not doing this for a company, as part of my job or something), so it's slow work. I am developing an AI concept based on the machine-formation of "opinions" from assimilation and correlation of real-time raw data streams and existing opinions. The idea is to correlate data to form symbols, associate knowledge and opinions with those symbols, and enable formation of layers of opinions through integration. I have a construct of opinions as vectors and need a computer application that rapidly considers a vast array of loosely associated opinions and either selects existing opinions, or forms new opinions, upon which to base selection and execution of a set of "learned" output sequences that become real-time response (e.g., conversational robotic speech). I believe Mr. Karmarkar's algorithm holds promise. OK, that's the basic situation. If anyone has useful information about this admittedly esoteric application, I would appreciate it if they could provide a helping hand. Thanks, Mark Van Noy