Discrete Optimization Methods

## Discrete Optimization Methods

The Pascal procedures available in this archive are taken with permission from Discrete Optimization Algorithms with Pascal Programs by Maciej M. Syslo, Narsingh Deo, and Janusz S. Kowalik. This text was published in 1983 by Prentice-Hall, Inc., Englewood Cliffs, NJ. To our knowledge these programs are available nowhere else on the Internet.

The field of discrete optimization (as viewed by the authors of the text above) consists of the areas of linear and integer programming, cover problems, knapsack problems, graph theory, network-flow problems, and scheduling. Their text covers these areas, using Pascal programs to elucidate methods of attacking discrete optimization problems. Those programs are downloadable from this site (see the previous page).

#### Some notes on the programs themselves

The methods used in the programs tend to speak for themselves, however for in-depth coverage of the problems and algorithms it is advised that a copy of the text be obtained. Many of the data types (particularly array data types) used in the Pascal procedures are assumed to be declared elsewhere (these are more "procedures" than complete programs), and are explicitly named only in the text. As a general rule, however, a naming convention is followed which should clear up most ambiguities.

An array of integers which has indices ranging from 1 through N, which would be declared ARRAY[1..N] OF INTEGER , will be denoted by the data-type ARRN . Similarly, a two-dimensional array of integers which would be declared in Pascal as ARRAY[1..N, 1..M] OF INTEGER will be denoted by the data-type ARRNM in the procedures given.

• Files with driver programs and datafiles (local site)
• Index of files in this distribution

• Set Cover (5)
• Set Packing (5)
• Shortest Path (5)
• Traveling Salesman Problem (5)
• Knapsack Problem (4)
• Network Flow (4)
• Job Scheduling (4)
• Vertex Coloring (4)
• Linear Programming (3)
• Matching (3)
• Minimum Spanning Tree (3)