LAU_NP: Heuristics for NP problems

LAU_NP is a set of implementations of heuristic algorithms for certain problems that are essentially impossible to solve exactly with an algorithm.

The classic example of this is the "traveling salesman problem", which seeks the shortest roundtrip that visits each location exactly once. The obvious method of solution, to compute the length of every possible path, is not much worse than the best known method of solution, in terms of the amount of computing required to find the exact answer. However, there are heuristic methods that can find a "reasonable" approximation to the answer for most problems, in a much shorter amount of time.

The problems considered include:

• the integer linear programming problem;
• the K-center problem;
• the K-median problem;
• the 0-1 knapsack problem;
• the graph partitioning problem;
• the minimal Steiner tree problem;
• the traveling salesman problem;

Files you may copy include:

• lau_np.f90, the source code.
• lau_np_prb.f90, a sample problem.
• lau_np_prb.out, sample problem output.

The list of routines includes:

• GRAPH_ARC_EULER_CIRC finds an Euler circuit in an Eulerian graph.
• GRAPH_ARC_MIN_PATH finds the shortest path between two nodes.
• GRAPH_ARC_MIN_SPAN_TREE finds a minimum spanning tree of a graph.
• GRAPH_ARC_PRINT prints out a graph from an edge list.
• GRAPH_ARC_WEIGHT_PRINT prints out a weighted graph from an edge list.
• GRAPH_DIST_MIN_SPAN_TREE3 finds a minimum spanning tree.
• GRAPH_DIST_PRINT prints a distance matrix.
• I_SWAP switches two integer values.
• INT_LP is a heuristic algorithm for the integer linear programming problem.
• K_CENTER is a heuristic algorithm for the K-center problem.
• K_MEDIAN is a heuristic algorithm for the K-median problem.
• KNAPSACK is a heuristic algorithm for the zero-one knapsack problem.
• MULTI_KNAP is a heuristic algorithm for the multi-dimensional 0/1 knapsack problem.
• PARSE1 is used by INT_LP.
• PARSE2 is used by INT_LP.
• PARSE3 is used by INT_LP.
• PARSE4 is used by INT_LP.
• PARSE5 is used by INT_LP.
• PARSE6 is used by INT_LP.
• PARSE7 is used by INT_LP.
• PARSE8 is used by INT_LP.
• PARTITION is a heuristic algorithm for the graph partitioning problem.
• PMATCH finds a minimum weight perfect matching in a graph.
• R_SWAP switches two real values.
• RMAT_PRINT prints out a portion of a dense matrix.
• RVEC_SORT_HEAP_INDEX_A does an indexed heap ascending sort of a real vector.
• RVEC_SORT_HEAP_INDEX_D does an indexed heap descending sort of a real vector.
• SIMPLEX is used by INT_LP.
• STEINER is a heuristic algorithm for the minimal Steiner tree problem.
• PMATCH_SUB_A is used by PMATCH.
• PMATCH_SUB_B is used by PMATCH.
• TSP is a heuristic algorithm for the traveling salesman problem.

Return to the FORTRAN software page.