main-content

## Über dieses Buch

In recent years researchers have spent much effort in developing efficient heuristic algorithms for solving the class of NP-complete problems which are widely believed to be inherently intractable from the computational point of view. Although algorithms have been designed and are notorious among researchers, computer programs are either not implemented on computers or very difficult to obtain. The purpose of this book is to provide a source of FORTRAN coded algorithms for a selected number of well-known combinatorial optimization problems. The book is intended to be used as a supplementary text in combinatorial algorithms, network optimization, operations research and management science. In addition, a short description on each algorithm will allow the book to be used as a convenient reference. This work would not have been possible without the excellent facilities of Bell-Northern Research, Canada. H. T. Lau lIe des Soeurs Quebec, Canada August 1986 CONTENTS Page Introduction Part I. INTEGER PROGRAMMING Chapter 1. Integer Linear Programming Chapter 2. Zero-one Linear Programming 30 Chapter 3. Zero-one Knapsack Problem 38 Part II. NETWORK DESIGN Chapter 4. Traveling Salesman Problem 52 Chapter 5. Steiner Tree Problem 81 Chapter 6. Graph Partitioning 98 Chapter 7. K-Median Location 106 Chapter 8. K-Center Location 114 List of Subroutines 123 Bibliographic Notes 124 INTRODUCTION Following the elegant theory of NP-comp1eteness, the idea of developing efficient heuristic algorithms has been gaining its popularity and significance.

## Inhaltsverzeichnis

### Chapter 1. Integer Linear Programming

Abstract
The integer linear programming problem has the form
$$\begin{gathered} {\text{maximize}}\quad \sum\limits_{{{\text{j = 1}}}}^{{\text{n}}} {{{{\text{c}}}_{{\text{j}}}}{{{\text{x}}}_{{\text{j}}}}} \hfill \\ {\text{subject}}\;{\text{to}}\quad \sum\limits_{{{\text{j = 1}}}}^{{\text{n}}} {{{{\text{a}}}_{{{\text{ij}}}}}{{{\text{x}}}_{{\text{j}}}}} \quad \leqslant \quad {{{\text{b}}}_{{\text{i}}}}\quad ({\text{i = 1,2,}} \ldots {\text{,m}}) \hfill \\ \quad \quad \quad {{{\text{x}}}_{{\text{j}}}}\quad \geqslant \quad 0\quad ({\text{j = 1,2,}} \ldots {\text{,n}}) \hfill \\ {{{\text{x}}}_{{\text{j}}}}\;{\text{is}}\;{\text{an}}\;{\text{integer}}\quad ({\text{j = 1,2,}} \ldots {\text{,m}}) \hfill \\ \end{gathered}$$
such that cj, aij and bi are real numbers.
H. T. Lau

### Chapter 2. Zero-One Linear Programming

Abstract
Consider the zero-one linear programming problem
$${\text{maximize}}\;Z = \sum\limits_{{j = 1}}^{n} {{{c}_{j}}{{x}_{j}}}$$
$$subject{\mkern 1mu} to\;\sum\limits_{{j = 1}}^{n} {{{a}_{{ij}}}{{x}_{j}}{{b}_{i}}\left( {i = 1,2, \ldots ,m} \right)}$$
$${{x}_{j}} = 0{\mkern 1mu} ,1\;\left( {j = 1,2, \ldots ,n} \right)$$
such that all the data aij, bi cj are nonnegative.
H. T. Lau

### Chapter 3. Zero-One Knapsack Problem

Abstract
The zero-one knapsack problem has the form
$${\text{maximize}}\;\sum\limits_{{j = 1}}^{n} {{{c}_{j}}{{x}_{j}}}$$
$$subject{\mkern 1mu} to\;\sum\limits_{{j = 1}}^{n} {{{a}_{j}}{{x}_{j}}b}$$
$${{x}_{{ji}}} = 0\;or\;1\;\left( {j = 1,2, \ldots ,n} \right)$$
such that aj, b and cj are nonnegative numbers.
H. T. Lau

### Chapter 4. Traveling Salesman Problem

Abstract
Let G be a complete graph with an associated distance matrix (dij) on its edges. The traveling salesman problem is to start from a node in G, visit every other node exactly once and return back to the starting node in such a way that the total traveled distance is minimum. In graph terminology, the traveling salesman problem is to find the least cost Hamiltonian circuit in a given undirected graph.
H. T. Lau

### Chapter 5. Steiner Tree Problem

Abstract
Consider an undirected graph G, each of its edges is labeled with a distance. Let S be a specified subset of nodes of G. The Steiner tree problem is to find a tree of G that spans S with minimal total distance on its edges. The nodes in the set S are called Steiner points.
H. T. Lau

### Chapter 6. Graph Partitioning

Abstract
Let V be the set of 2n nodes of a complete graph with an associated 2n by 2n symmetric cost matrix (cij) on its edges. The graph partitioning problem is to partition the nodes into two parts P and Q = V - P, each with n nodes, such that the total cost of the edges cut
$$\sum\limits_{{\mathop{{p \in P}}\limits_{{q \in Q}} }} {{{c}_{{pq}}}}$$
is minimized.
H. T. Lau

### Chapter 7. K-Median Location

Abstract
Let C = (cij) be an m by n matrix, and k be an integer l ≤ k < m. The k-median location problem is to find a subset S of k rows of C that maximizes
$$\sum\limits_{{j = 1}}^{n} {\mathop{{\max }}\limits_{{i \in S}} {\mkern 1mu} {{c}_{{ij}}}}$$
. The heuristic procedure to be described finds a near-optimum solution in time proportional to mn.
H. T. Lau

### Chapter 8. K-Center Location

Abstract
Let V be the set of nodes of a complete undirected graph of n nodes with edge weights cij ≥ 0 associated with edge (i,j) for all nodes i, j in V; and cii = 0. Given an integer k, l ≤ k ≤ n, the k-center location problem is to find a subset S of V of size at most k such that
$$Z = \mathop{{\max }}\limits_{{i \in V}} {\mkern 1mu} \mathop{{\min }}\limits_{{j \in S}} {\mkern 1mu} {{c}_{{ij}}}$$
is minimized.
H. T. Lau

### Backmatter

Weitere Informationen