Exact and heuristic methods in combinatorial optimization. A study on the linear ordering and the maximum diversity problem (Q2122552)

This book gives a precise overview of solution methods in combinatorial optimization by showing how the linear ordering problem and the maximum diversity problem can be solved by Branch-and-Bound or Branch-and-Cut together with several heuristics. The first version of the book [\textit{R. Martí} and \textit{G. Reinelt}, The linear ordering problem. Exact and heuristic methods in combinatorial optimization. Berlin: Springer (2011; Zbl 1213.90005)] only considers the linear ordering problem as an example. By giving a second example in this edition with quite different characteristics, the authors show that many of their methods still work and can be applied to various combinatorial optimization problems. The book is well suited for readers who want to learn how to solve real world combinatorial optimization problems as the methods are well explained and a lot of algorithms are given with pseudo-code. The authors explain all terms they use and the book is well understandable. Some knowledge in linear programming might be useful for some parts of the book. The book contains the following chapters: \begin{itemize} \item Chapter 1 defines the linear ordering and maximum diversity problem. It introduces alternative formulations and variants. Furthermore, benchmark instances for both problems are described. \item The second chapter gives some simple construction and improving heuristics for both problems, for example local search heuristics which can be easily adjusted for many other combinatorial optimization problems. All heuristics introduced in this chapter are tested on the benchmark instances of the first chapter. \item Chapter 3 shows how the simple search heuristics can be improved by using meta-heuristics as for example tabu search, variable neighborhood search or simulated annealing. Tests on the benchmark instances show a performance gain compared to the simple heuristics. \item The fourth chapter introduces the branch-and-bound method, which is a method to solve general combinatorial optimization methods, not only the linear ordering or maximum diversity problem. It can be used as an exact method or as a heuristic if one stops the process before it is finished. \item The fifth chapter shows how branch-and-bound can be improved by adding cutting planes leading to the so-called branch-and-cut method. This method is very powerful in solving real world combinatorial optimization methods. Again this method is tested on the benchmark instances described in the first chapter. \item The sixth chapter investigates the linear ordering polytope by describing several classes of inequalities that are facet defining. The authors also show how to calculate a complete description of the linear ordering polytope for small dimensional polytopes. To really understand this chapter some knowledge in linear programming is helpful though the authors define all terms needed. \item The last chapter is a summary of further aspects related to the linear ordering or maximum diversity problem as for example approximation algorithms. \end{itemize} All in all this book can be recommended to anyone interested in combinatorial optimization who wants to get an overview of the classical solution approaches in this field.