×

Enumerative approaches to combinatorial optimizaton. Parts 1, 2. Reprint of the journal Annals of Operations Research 10-11, Nos. 1-4 (1987). (English) Zbl 0667.90068

Annals of Operations Research 10-11. Basel: J.C. Baltzer AG (ISBN 3-905-13527-2). xii, 602 p. (1988).
It is often required to solve a given problem even if it is a theoretically difficult one. Within the limit of its inherent complexity, therefore, it is desired to develop an algorithm of the maximum efficiency by exploiting all the possible problem structures useful for facilitating the computation. As a difficult problem rarely has a dominant structure, with which the computational burden can be drastically reduced, such an algorithm should make use of every small characteristic of the given problem. Enumerative algorithms, such as branch-and-bound and dynamic programming, which are main themes of this book, are perhaps the only approaches suitable for such purposes.
Enumerative approaches are based on the enumeration of solutions. However, the explicit enumeration of all the possible solutions is not computationally feasible even for problems of moderate sizes. For example, to test all permutations of n objects, we need examine n! cases. For \(n=15\), this is about \(1.3\times 10^{12}\) and requires roughly 41 years if one case is examined in one millisecond. This means that it is imperative to equip the algorithms with a capability to identify those solutions not yielding optimal solutions, and to exclude them from the explicit enumeration. Different types of enumerative algorithms result depending upon how such exclusion is carried out.
The approach which is most comprehensively discussed in this book is branch-and-bound. This book discusses the branch-and-bound algorithms from the following three points: (1) how a given problem is decomposed into finer and finer partial problems, (2) in what order the generated partial problems are examined and tested, and (3) how to exclude a partial problem from consideration. As the computation is performed on a real computer having a given speed and a memory size, and as the manpower available for the program development is usually limited, it is attempted in this book to clarify which part of an algorithm is strongly related to the computation time, the required storage space and the resulting program complexity. In this way, this book is intended to serve as a practical guidebook for the design of branch-and-bound algorithms. A number of examples are provided throughout the book (especially in chapter 3) so that the above points can be correctly understood against practical problems.
Another useful enumerative approach is dynamic programming which has a different origin of development. Nevertheless, it turns out, as discussed in chapter 6, that dynamic programming for combinatorial optimization problems can be viewed as a special type of branch-and-bound algorithms. Due to its rather rigid structure, however, dynamic programming algorithms are easy to implement and are still quite effective for some classes of problems. Its merits and demerits are compared with the general branch-and-bound approaches.
In an attempt to merge and extend the merits of these two approaches, dynamic programming is extended to successive sublimation dynamic programming (SSDP) in chapter 7. Actual SSDP algorithms are constructed for some combinatorial optimization problems.
All the approaches mentioned so far are intended to be exact algorithms. In practice, however, the sizes of problems we want to solve can be very large, and even with most sophisticated algorithms it may not be possible to solve them exactly. To cope with this type of situation, it is very important to have approximate or heuristic algorithms, which can provide good (if not exactly optimal) solutions quickly. Chapter 8 discusses design principles of approximate algorithms, and also considers the use of branch-and-bound algorithms for such purposes.
It should be noted here that the discussion throughout this book is mainly addressed to explain the underlying computational principle. Actual algorithms need be individually implemented by tailoring the principles to the given problems. This contrasts with the general approach of integer programming in which one algorithm can be used for all problems. However, as a result of these additional efforts, the enumerative methods as discussed in this book have proved to be useful for many important combinatorial optimization problems, expecially for those categorized as difficult.
This book is believed to be one of the first books comprehensively discussing enumerative approaches. It is hoped that this helps stimulate further discussion on the subject and encourage its implementation for wider classes of problems.

MSC:

90C10 Integer programming
90-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming
90B10 Deterministic network models in operations research
90C27 Combinatorial optimization
65K05 Numerical mathematical programming methods
90C09 Boolean programming
90C35 Programming involving graphs or networks
90B35 Deterministic scheduling theory in operations research
90C39 Dynamic programming
PDFBibTeX XMLCite