Combinatorial heuristic algorithms with FORTRAN (Q1094328)

This book provides a source of FORTRAN 77 codes for well-known heuristics in combinatorial optimization. Part 1 is devoted to integer programming problems whereas Part 2 deals with optimization problems in networks. The chapters are independent from each other, start with a short problem description and statement of the algorithm, explain the parameters used in the computer program and contain a test example. Then the listing of the program follows. In particular the following topics are dealt with: An integer linear programming heuristic based on ideas of Hillier, a zero-one linear programming heuristic based on a paper of Toyoda, the approximation algorithm of Ibarra and Kim for zero-one knapsack problems, the Christofides heuristic for travelling salesman problems, a heuristic for the Steiner tree problem based on a paper of Kou, Markowsky and Berman, the two-way graph partitioning procedure and K-median location algorithm of Kerningham and Lin and finally an approximation algorithm for the K-center problem with triangle inequality based on a recent paper of Hochbaum and Shmoys.