LAU_NP
Heuristics for NP problems


LAU_NP is a FORTRAN90 library which implements heuristic algorithms for certain "hard" problems, by Hang Tong Lau.

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:

Languages:

LAU_NP is available in a FORTRAN90 version.

Related Data and Programs:

ASA058, a FORTRAN77 library which contains the original text of the Sparks clustering algorithm.

ASA136, a FORTRAN77 library which contains the original text of the Hartigan and Wong clustering algorithm.

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

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

FLOYD, a FORTRAN90 library which implements Floyd's algorithm for finding the shortest distance between pairs of nodes on a directed graph.

KMEANS, a FORTRAN90 library which contains several implementations of the K-Means algorithm.

KNAPSACK, a FORTRAN77 library which solves a variety of knapsack problems.

KNAPSACK_01, a dataset directory which contains test data for the 0/1 knapsack problem;

KNAPSACK_MULTIPLE, a dataset directory which contains test data for the multiple knapsack problem;

LAMP, a FORTRAN77 library which solves linear assignment and matching problems.

PARTITION_PROBLEM, a FORTRAN90 library which seeks solutions of the partition problem, splitting a set of integers into two subsets with equal sum.

SPAETH, a FORTRAN90 library which can cluster data according to various principles.

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

SPAETH2, a FORTRAN90 library which can cluster data according to various principles.

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

SUBSET_SUM, a FORTRAN90 library which seeks solutions of the subset sum problem.

TOMS456, a FORTRAN77 library which handles the routing problem, connecting some nodes in a network.

TSP, a dataset directory which contains test data for the traveling salesperson problem;

TSP_LAU, a FORTRAN90 library which implements a heuristic algorithm for the solution of the traveling salesperson problem.

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,
    ISBN: 3540171614,
    LC: 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:

Examples and Tests:

List of Routines:

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


Last revised on 27 November 2006.