Configurational density process and structure

• US 7,376,633 B2
• Filed: 05/04/2005
• Issued: 05/20/2008
• Est. Priority Date: 05/04/2004
• Status: Active Grant

• Current Assignee: SAP AG (SAP SE)
• Original Assignee: Khimetrics, Inc. (SAP SE)
• Inventors: Ouimet, Kenneth J.
• Primary Examiner(s): Vincent; David
• Assistant Examiner(s): Kennedy; Adrian L
• Application Number:
  US11/121,447
• Publication Number:
  US 20050251434A1
• Time in Patent Office: 1,112 Days
• Field of Search: 706/19, 706/15, 706/62, 700/28, 716/2
• US Class Current: 706/19
• CPC Class Codes: G06Q 10/00 Administration; Management
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202

Abstract

A computer program product is described for solving the traveling salesman problem in polynomial time. The probability distribution of the space of all paths is modeled in a configurational density distribution. A Hamiltonian is constructed specifying the costs, distance, or penalty associated with different legs of paths encompassed in the configurational density distribution. Starting at a maximum temperature where free energy dominates and the penalty function plays little role, the system is iteratively adapted to reduce the temperature in steps incrementally chosen to preserve the linear characteristic of the approximation, until a lower temperature state of reduced energy is reached in which a preferred set of paths can be identified from the configurational density distribution.

Claims

1. A computer system for solving a traveling salesman problem comprising:

a memory for storing data and instructions to control flow;

a central processing unit for executing instructions and manipulating data stored in the memory;

a traveling salesman problem definition stored in said memory specifying cities as nodes on a graph, said city being able to be visited in a sequence of stops defining a path;

a configurational density component in said memory, said configurational density component producing a value indicating the combined probability of a specified pair of cities and stops;

a configurational activity component stored in said memory, said configurational activity component producing a value indicating whether any allowable path includes a specified pair of cities and stops;

a Hamiltonian component stored in said memory, said Hamiltonian component indicating the cost associated with a path including a specified pair of cities and stops;

a traveling salesman solution space system comprising said configurational density component, configurational activity component, and Hamiltonian component;

a temperature parameter characterizing an entropy associated with said traveling salesman solution space system;

an entropic relaxation process stored in said memory for execution by said central processing unit, said entropic relaxation process comprising iterative reduction of said temperature parameter, said reduction of said temperature parameter iteratively reducing said entropy, recalculation of said traveling salesman solution space system based on said reduction of said temperature parameter, said entropic relaxation process producing a state of lower energy defining a set of preferred paths.

2. A computer readable medium containing a data structure for storing information relating to a solution to traveling salesman problem, said traveling salesman problem being characterized by a list of cities and costs associated with paths traversing said cities, the data structure comprising:

a configurational density table, said configurational density table being characterized by a first CD city index, a first CD stop index, a second CD city index, and a second CD stop index, the configurational density table containing a configurational density value for each said first CD city index, first CD stop index, second CD city index, and second CD stop index ordered quadruple, said configurational density value corresponding to the probability of having a first city corresponding to said first CD city index at a stop corresponding to said first CD stop index and a second city corresponding to said second CD city index at said CD second stop;

a configurational activity table, said configurational activity table being characterized by a first CA city index, a first CA stop index, a second CA city index, and a second CA stop index, the configurational activity table containing an configurational activity value for each said first CA city index, first CA stop index, second CA city index, and second CA stop index ordered quadruple, said configurational activity value corresponding to whether there exists an allowable path having a first city indicated by said first CA city index at a stop indicated by said first CA top index and a second city indicated by said second CA city index at stop indicated by said second CA stop index;

a Hamiltonian table, said Hamiltonian table being characterized by a first HM city index, a first HM stop index, a second HM city index, and a second HM stop index, the Hamiltonian table containing a cost value for each said first HM city index, first HM stop index, second HM city index, and second HM stop index ordered quadruple, said cost value corresponding to the cost associated with having a first city indicated by said first HM city index at a stop indicated by said first HM stop index and a second city indicated by said second HM city index at stop indicated by said HM second stop index.

3. The data structure according to claim 2, wherein said configurational activity table and said configurational density are combined in one table.

4. The data structure according to claim 2, wherein said configurational activity table and said Hamiltonian table are combined in one table.

5. The data structure according to claim 2, further comprising a city-city density table, said city-city density table being characterized by a first CC city index and a second CC city index, the city-city density table containing a city-city density value for each said first CC city index and second CC city index pair, said city-city density value corresponding to the probability across all paths if traveling from a city corresponding to said first CC city index to a city corresponding to said second CC city index.

6. The data structure according to claim 2, further comprising a city-stop density table, said city-stop density table being characterized by a CS city index and a CS stop index, the city-stop density table containing a city-stop density value for each said CS city index and CS stop index pair, said city-city density value corresponding to the probability across all paths of finding a city corresponding to the CS city index at a stop corresponding the CS stop index.

7. A computer program product including a medium containing computer program code for controlling execution of instructions, flow of control, and transformation of data in a computer system, comprising:

computer program code defining a configurational density function, said configurational density function being characterized by a first CD city parameter, a first CD stop parameter, a second CD city parameter, and a second CD stop parameter, the configurational density function producing a configurational density value for each said first CD city parameter, first CD stop parameter, second CD city parameter, and second CD stop parameter, said configurational density value corresponding to the probability of having a first city corresponding to said first CD city parameter at a stop corresponding to said first CD stop parameter and a second city corresponding to said second CD city parameter at said CD second parameter;

computer program code defining a configurational activity function, said configurational activity function being characterized by a first CA city parameter, a first CA stop parameter, a second CA city parameter, and a second CA stop parameter, the configurational activity function producing a configurational activity value for each said first CA city parameter, first CA stop parameter, second CA city parameter, and second CA stop parameter, said configurational activity value corresponding to the probability of having a first city corresponding to said first CA city parameter at a stop corresponding to said first CA stop parameter and a second city corresponding to said second CA city parameter at said CA second parameter;

computer program code defining a Hamiltonian function, said Hamiltonian function being characterized by a first HM city parameter, a first HM stop parameter, a second HM city parameter, and a second HM stop parameter, the Hamiltonian function producing a Hamiltonian value for each said first HM city parameter, first HM stop parameter, second HM city parameter, and second HM stop parameter, said Hamiltonian value corresponding to the probability of having a first city corresponding to said first HM city parameter at a stop corresponding to said first HM stop parameter and a second city corresponding to said second HM city parameter at said HM second parameter.

8. The computer program product according to claim 7, wherein said configurational activity function and said configurational density function are combined in one function.

9. The computer program product according to claim 7, wherein said configurational activity function and said Hamiltonian function are combined in one function.

10. The computer program product according to claim 7, further comprising a city-city density function, said city-city density function being characterized by a first CC city parameter and a second CC city parameter, the city-city density function containing a city-city density value for each said first CC city index and second CC city parameter pair, said city-city density value corresponding to the probability across all paths if traveling from a city corresponding to said first CC city parameter to a city corresponding to said second CC city parameter.

11. The computer program product according to claim 7, further comprising a city-stop density function, said city-stop density function being characterized by a CS city index and a CS stop index, the city-stop density function containing a city-stop density value for each said CS city parameter and CS stop parameter pair, said city-city density value corresponding to the probability across all paths of finding a city corresponding to the CS city index at a stop corresponding the CS stop parameter.