Compact extended linear programming models (Q1693865)

This book is dedicated to presenting and applying the methods of compact extended formulations of linear optimization problems and polyhedra. Roughly speaking, an optimization problem/polyhedron with ``too many'' constraints/facets is extended to one with less constraints/facets, but with a larger number of variables/dimension. The main merit of this book is that it presents in a unified way the state of the art in the matter in discussion. It is well written and the authors, who have coauthored themselves a part of the contained results, were successful in finding a good equilibrium between the mathematical rigor and the direct applicability of the presented methods by the practitioners, as the theoretical investigations and results are completed by suitable applications and examples. Worth noticing is also the fact that each chapter begins with a small introductive section where the problem in discussion is presented from different angles and its study motivated by both examples and historical information. This 208-page long book is divided into thirteen chapters preceded by a list of notations and followed by the usual lists of references and index of the most important terms. After an introduction dedicated to presenting a motivation for writing this book and to presenting the organisation of its content, one finds four chapters dedicated to an exposition on the background concepts regarding polyhedra, linear programming, integer linear programming and large-scale linear programming, respectively. Among the themes presented here we mention the slack matrix, projections and unions of polyhedra, polyhedral characterizations of linear programs, duality and algorithms for linear optimization problems, integral \(LP\)-relaxations, the branch-and-bound and cutting-plane algorithms, \(MILP\) solvers, column generation and linear programs with exponentially many columns and/or rows, respectively. The last chapter dedicated to theoretical investigations is the sixth one, where the general way to build compact extended formulations is presented together with some useful tools such as the Dantzig-Wolfe decomposition technique. Examples and tricky situations, such as unions of polyhedra, are given as well, illustrating the general theoretical approach. In the second part of the book the authors present compact extended formulations for concrete particular problems that are modelled as large scale (integer) linear programming problems. In the seventh chapter we are accoustomed with the permutahedron, for which three different compact extended formulations are provided, then the same happens for the parity polytope. These two combinatorial problems are followed by three classical topics in graph theory, namely trees, cuts and stable sets. Compact extended formulations are provided in each case, with significant special cases and, where possible, comparisons of the considered models. Chapter 12 deals with the maybe most famous problem in combinatorial optimization, the one of the traveling salesman, for which compact integer \(LP\) models have been proposed for about seventy years, but still the exponential-size one due to Dantzig seems to be the most computationally competitive one. A more flexible alternative to it is proposed, that at least in some particular cases provides competitive results. Two chapters dedicated to different packing and scheduling problems with the corresponding compact extended formulations follow. The last chapter of the book is dedicated to combinatorial optimization problems arising in computational biology, approached by means of compact extended formulations, too. The three types of problems presented are the one of the evolutionary distance between two genomes, the noncrossing matching and the protein fold comparison. As the authors mention in the introduction, the book contains no computational results or concrete implementations of the sketched methods. However, this should not be seen as a disadvantage for the interested reader, as the theory is presented in a nice and comprehensive manner. Some chapters (such as the fourth one) are suitable also as companion lecture notes for courses. Worth mentioning are also the well-choosen examples and the new results and even conjectures contained in this book. All in one, I consider the book to be a useful contribution to the literature on applications of (combinatorial) linear optimization problems, with emphasis on compact extended formulations for some interesting problems that can be reformulated or modelled as such.