Gerhard Reinelt – författare

In 1958, Ralph E. Gomory transformed the field of integer programming when he published a paper that described a cutting-plane algorithm for pure integer programs and announced that the method could be refined to give a finite algorithm for integer programming. In 2008, to commemorate the anniversary of this seminal paper, a special workshop celebrating fifty years of integer programming was held in Aussois, France, as part of the 12th Combinatorial Optimization Workshop.

It contains reprints of key historical articles and written versions of survey lectures on six of the hottest topics in the field by distinguished members of the integer programming community. Useful for anyone in mathematics, computer science and operations research, this book exposes mathematical optimization, specifically integer programming and combinatorial optimization, to a broad audience.

Martin Grötschel is one of the most influential mathematicians of our time. He has received numerous honors and holds a number of key positions in the international mathematical community. He celebrated his 65th birthday on September 10, 2013. Martin Grötschel’s doctoral descendant tree 1983–2012, i.e., the first 30 years, features 39 children, 74 grandchildren, 24 great-grandchildren and 2 great-great-grandchildren, a total of 139 doctoral descendants.

This book starts with a personal tribute to Martin Grötschel by the editors (Part I), a contribution by his very special “predecessor” Manfred Padberg on “Facets and Rank of Integer Polyhedra” (Part II), and the doctoral descendant tree 1983–2012 (Part III). The core of this book (Part IV) contains 16 contributions, each of which is coauthored by at least one doctoral descendant.

The sequence of the articles starts with contributions to the theory of mathematical optimization, including polyhedral combinatorics, extended formulations, mixed-integer convex optimization, super classes of perfect graphs, efficient algorithms for subtree-telecenters, junctions in acyclic graphs and preemptive restricted strip covering, as well as efficient approximation of non-preemptive restricted strip covering.

Combinations of new theoretical insights with algorithms and experiments deal with network design problems, combinatorial optimization problems with submodular objective functions and more general mixed-integer nonlinear optimization problems. Applications include VLSI layout design, systems biology, wireless network design, mean-risk optimization and gas network optimization.

Computational studies include a semidefinite branch and cut approach for the max k-cut problem, mixed-integer nonlinear optimal control, and mixed-integer linear optimization for scheduling and routing of fly-in safari planes.

The two closing articles are devoted to computational advances in generalmixed integer linear optimization, the first by scientists working in industry, the second by scientists working in academia.

These articles reflect the “scientific facets” of Martin Grötschel who has set standards in theory, computation and applications.

In the last decades, algorithmic advances as well as hardware and software improvements have provided an excellent environment to create and develop solving methods to hard optimization problems. Modern exact and heuristic techniques are dramatically enhancing our ability to solve significant practical problems. This monograph sets out state-of-the-art methodologies for solving combinatorial optimization problems, illustrating them with two well-known problems.

This second edition of the book extends the first one by adding to the ‘linear ordering problem’ (LOP), included in the first edition, the ‘maximum diversity problem’ (MDP). In this way, we provide the reader with the background, elements and strategies to tackle a wide range of different combinatorial optimization problems. The exact and heuristic techniques outlined in these pages can be put to use in any number of combinatorial optimization problems. While the authors employ the LOP and the MDP to illustrate cutting-edge optimization technologies, the book is also a tutorial on how to design effective and successful implementations of exact and heuristic procedures alike.

This monograph provides the basic principles and fundamental ideas that will enable students and practitioners to create valuable applications based on both exact and heuristic technologies. Specifically, it is aimed at engineers, scientists, operations researchers, and other applications specialists who are looking for the most appropriate and recent optimization tools to solve particular problems. The book provides a broad spectrum of advances in search strategies with a focus on its algorithmic and computational aspects.