LAU_NP
Heuristics for NP problems

LAU_NP is a library of FORTRAN90 routines, using double precision arithmetic, which implement heuristic algorithms for certain "hard" problems.

These problems are hard in the sense that, as the problem size N increases, the amount of work required to compute a solution grows exponentially.

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 multiple knapsack problem;
• the graph matching problem;
• the graph partitioning problem;
• the minimal Steiner tree problem;
• the traveling salesman problem;

Related Data and Programs:

ASA058 is a FORTRAN77 file containing the original text of the Sparks clustering algorithm.

ASA136 is a FORTRAN77 file containing the original text of the Hartigan and Wong clustering algorithm.

CITIES is a FORTRAN90 library which handles various problems associated with a set of "cities" on a map.

CITIES is a dataset directory which contains a number of city distance datasets.

KMEANS is a FORTRAN90 library containing several implementations of the K-Means algorithm.

SPAETH is a library of FORTRAN90 routines which can cluster data according to various principles.

SPAETH is a dataset collection which contains a set of test data.

SPAETH2 is a library of FORTRAN90 routines which can cluster data according to various principles.

SPAETH2 is a dataset collection which contains a set of test data.

TOMS456 is a routine for the routing problem, connecting some nodes in a network.

Author:

Hang Tong Lau

Reference:

1. Rainer Burkard, Ulrich Derigs,
   Assignment and Matching Problems: Solution methods with FORTRAN programs,
   Lecture Notes in Economics and Mathematical Systems,
   Volume 184,
   Springer Verlag, 1980.
2. Nicos Christofides,
   Worst-case analysis of a new heuristic for the traveling salesman problem,
   Management Science Research Report Number 388,
   Carnegie-Mellon University, 1976.
3. Frederick Hillier,
   Efficient heuristic procedure for integer linear programming with an interior,
   Operations Research,
   Volume 17, pages 600-637, 1969.
4. Dorit Hochbaum, David Shmoys,
   A best possible heuristic for the K-center problem,
   Mathematics of Operations Research,
   Volume 10, pages 180-184, 1985.
5. Oscar Ibarra, Chul Kim,
   Fast approximation algorithms for the knapsack and sum of subset problems,
   Journal of the Association for Computing Machinery,
   Volume 22, pages 463-468, 1975.
6. Brian Kernighan, Shen Lin,
   An efficient heuristic procedure for partitioning graphs,
   Bell System Technical Journal,
   Volume 49, pages 291-307, 1970.
7. Brian Kernighan, Shen Lin,
   Heuristic solution of a signal design optimization problem,
   Bell System Technical Journal,
   Volume 52, pages 1145-1159, 1973.
8. Lawrence Kou, George Markowsky, Leonard Berman,
   A fast algorithm for Steiner trees,
   Research report RC 7390,
   IBM Thomas J Watson Research Center,
   Yorktown Heights, New York, 1978.
9. Hang Tong Lau,
   Combinatorial Heuristic Algorithms in FORTRAN,
   Springer Verlag, 1986,
   QA402.5 L37.
10. Yoshiaki Toyoda,
    A simplified algorithm for obtaining approximate solutions to zero-one programming problems,
    Management Science,
    Volume 21, pages 1417-1427, 1975.

Source Code:

• lau_np.f90, the source code.
• lau_np.csh, commands to compile the source code.

Examples and Tests:

• lau_np_prb.f90, a sample problem.
• lau_np_prb.csh, commands to compile, link and run the sample problem.
• lau_np_prb.out, sample problem output.

List of Routines:

• 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.
• I4_SWAP switches two I4's.
• 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.
• PMATCH_SUB_A is used by PMATCH.
• PMATCH_SUB_B is used by PMATCH.
• R8_SWAP switches two R8's.
• R8MAT_PRINT prints an R8MAT.
• R8MAT_PRINT_SOME prints some of an R8MAT.
• R8VEC_SORT_HEAP_INDEX_A does an indexed heap ascending sort of an R8VEC.
• R8VEC_SORT_HEAP_INDEX_D does an indexed heap descending sort of an R8VEC.
• SIMPLEX is used by INT_LP.
• STEINER is a heuristic algorithm for the minimal Steiner tree problem.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TSP is a heuristic algorithm for the traveling salesman problem.

You can go up one level to the FORTRAN90 source codes.