You are here

CATBox: An Interactive Course in Combinatorial Optimization

W. Hochstättler and A. Schliep
Publication Date: 
Number of Pages: 
[Reviewed by
Keith Sinkhorn
, on

According to the Preface of CATBox: An Interactive Course in Combinatorial Optimization, authors Winfried Hochstättler and Alexander Schliep intend to provide both mathematical rigor as well as an interactive tool to assist the learning process. The tool, of course, is the CATBox software package, which is available online. CATBox uses the Gato open source animation software. The authors’ algorithm implementations, algorithm visualizations and problem instances combine with Gato to form the CATBox package.

The text is proposed for use at the graduate or advanced undergraduate levels. The authors argue that the separation of mathematical rigor from interactive tools is a weak point of many courses in combinatorial optimization. This text is their attempt at incorporating tools and rigor from the ground up. As indicated in the Preface, most interactive tools in this area of mathematics are created by people other than textbook authors. This book was written as a rigorous mathematical text, but with the CATBox interactive tool in mind throughout. Consequently, theory and practice come together admirably. The dynamic visual reinforcement facilitated by CATBox is an excellent tool for learning the presented algorithms and concepts.

Topics and examples in the text include minimum spanning trees, shortest paths, maximal flows and minimum-cost flows along with weighted and non-weighted matching. Duality in linear programming is a major feature of the text. The authors suggest skipping duality in an undergraduate course, however. In addition, the minimum-cost flow and weighted matching topics make heavy use of duality. Thus, the authors recommend passing over the three corresponding chapters in an undergraduate course — and possibly supplementing the text with outside material.

Gato uses the Python scripting language, so while CATBox is well integrated with the text, students with little or no programming experience may find the text difficult to approach without the assistance of an excellent instructor. Students with a strong background in both computer science and the methods of mathematical proof would be well-served by this text.

Keith Sinkhorn possesses a PhD in Industrial Engineering from the University of Louisville. He is an Assistant Professor of Mathematics at Peru State College in Peru, NE with research interests including applied operations research, logistics, discrete optimization, and heuristic algorithms.