Book Reviews

Integer Programming

Conforti, Michele, Gérard Cornuéjols, Giacomo Zambelli. 2015. Integer Programming. Springer. 456 pp. $69.00.

The authors of this textbook on integer programming have an impressive research record in both integer programming and in related areas, such as graph theory and matrix analysis. The first author is known particularly for his exceptionally clear lecturing style. For these reasons, we were pleased to hear about the book and very much looked forward to reading it. We were not disappointed.

The book has 10 chapters. The first three chapters cover the fundamentals of integer programming, including applications and modeling, basic computational complexity, and polyhedral theory. Chapter 4 addresses techniques for deriving “perfect” formulations and techniques for proving that a given formulation is perfect. Chapter 5 covers the two classical families of general-purpose cutting planes, namely Chvátal-Gomory cuts and disjunctive or split cuts. Chapter 6 covers intersection cuts, corner polyhedra, and group relaxations. Chapter 7 moves on to consider problem-specific cutting planes that are derived from polyhedral studies. The knapsack, fixed-charge network-flow and traveling salesman problems are used to illustrate the ideas involved. The chapter also contains a section about using the ellipsoid algorithm to show the polynomial equivalence of separation and optimization. Chapter 8 describes various decomposition approaches, including Lagrangian relaxation, Dantzig-Wolfe decomposition, and Benders decomposition. Chapter 9 describes enumerative techniques, including branch-and-bound and branch-and-cut. It also mentions Lenstra’s algorithm for integer programming in a fixed dimension. Finally, Chapter 10 covers the semidefinite programming (SDP) hierarchies of Lasserre and Lovász and Schrijver, and the closely related linear programming (LP) hierarchy of Sherali and Adams.

The book is written in a very clear and didactic style. The profound understanding and enthusiasm that the authors have for the topic is evident throughout. Another very nice aspect of this book is that it contains information on a number of current hot topics that existing textbooks do not cover. This includes, for example, recent work on compact extended formulations (Chapter 4), lattice-point-free sets (Chapter 6), sequence-independent lifting (Chapter 7), exploiting symmetry (Chapter 9), and the aforementioned LP and SDP hierarchies in Chapter 10. This will make the book very useful for mathematically mature undergraduates, graduate students, postdocs, and established researchers who are interested in the techniques.

We have a few minor criticisms. First, at times (especially in Chapter 8), the material is not sufficiently detailed. Presumably, this is simply a result of the need to keep the book within a reasonable length, while maintaining a wide-ranging coverage. Second, in a few places, the authors are somewhat liberal in their wording, especially in their statements on computational complexity. For example, on p. 389, they write that semidefinite programs “can also be solved in polynomial time”; they then correct themselves on p. 391 by writing “one cannot hope to compute the solution exactly.” This could be confusing to students. Third, the book would have benefited from more figures. For example, the exposition of Lagrangian relaxation in Section 8.1 would have been better had the authors presented the usual diagram of the Lagrangian dual as the minimization of a convex piecewise-linear function.

Finally, we compare this book with a few related texts. Classic works on the topic in chronological order include Garfinkel and Nemhauser (1972), Schrijver (1986), Nemhauser and Wolsey (1988), and Wolsey (1998). A number of techniques have emerged since those works were published, and we believe the present work covers all of the major ones and the classic material. This inevitably means, however, that the treatment of each topic is less detailed. For example, Garfinkel and Nemhauser (1972) contains a very full treatment of Gomory’s dual integral and primal cutting-plane methods, topics that this book touches on very briefly. Similarly, Schrijver (1986) lists seven characterizations of totally unimodular matrices with a number of special classes and beautiful proofs of related results, whereas the book under review lists only four. We would like to mention Achterberg (2007), which has a very good discussion of the implementational aspects, and Chen et al. (2010) and Williams (2013), which focus on modeling skills. These books could be very useful as supplementary reading.

To sum up, this is an excellent and impressive book. We wholeheartedly recommend it as a textbook for advanced undergraduate and introductory graduate courses on integer programming.

Adam Letchford

Lancaster University, Lancaster, UK, [email protected]

Jakub Marecek

IBM Research, Dublin, Ireland, [email protected]

Mapping Urban Practices Through Mobile Phone Data

Pucci, Paola, Fabio Manfredini, Paola Tagliolato. 2015. Mapping Urban Practices Through Mobile Phone Data. Springer. 90 pp. $54.99.

What opportunities do mobile phone data provide researchers who are interested in comprehending how urban populations move around a city and the ways in which they utilize city services? The central objective of this slim book is to shed light on this salient question. To meaningfully answer this question, the authors report the results of two research projects that Telecom Italia conducted and funded in 2009 and 2011.

The authors begin by pointing out that using traditional data sources to understand the “space-time variability of urban practices…” (p. 1) is difficult. Therefore, they assume that the complexity of contemporary urban processes can be best understood as an evolutionary process in which the geography of human movements is constantly being reorganized and restructured. Further, we are told that this task of comprehension is significantly aided by the use of mobile phone data.

The mobile phone data that the authors—and many other researchers—use are essentially Erlang data, an expression that refers to the expected number of concurrent contacts in a specified time unit. In this regard, the authors helpfully explain that the Erlang data provided to them by Telecom Italia “describe the density of mobile phone traffic every 15 minutes across areas measuring 250 × 250 meters” (p. 16). Erlang data are helpful because they can be used, inter alia, to zone urban areas on the basis of the actual behavior of humans.

The bulk of the analysis in this book is described in the third chapter; this chapter shows how maps based on mobile phone data can be used to represent “spatialized urban practices and origin-destination flows of daily movements” (p. 27). The discussion undertaken in this chapter leads to several noteworthy findings, including the following three examples. First, we learn that at various scales of analysis, statistical correlations between Erlang and other comparable data demonstrate that cell phone activity usefully reflects the daily activities of humans. Second, focusing on railway stations in the city of Milan, we see that via trends in the Erlang data, it is possible to find correlations between “the intensity and amount of telephone traffic during the day…” (p. 47) and the role played by each station in terms of its relative hierarchical standing as measured by, for example, the number of trains per day. Finally, and again in the context of Milan, certain types of mobile phone data are a salient tool for monitoring visitors and tourists and for evaluating the attractiveness of major events, such as International Design Week.

What are the similarities and the differences between conventional data sources and Erlang-type mobile phone data? In answering this question, the authors correctly point out that, whereas the temporal resolution of conventional data sources is yearly, the resolution of mobile phone data is either hourly or even subhourly. In addition, although providing conventional data is typically very expensive, the provision of mobile phone data is likely to be inexpensive. Therefore, an opposite analysis of the spatial and the temporal use of cities “requires an integration between traditional data…and new sources of information, closer to users such as mobile phone data activity or geolocated digital traces…” (p. 75). The authors conclude this tome by reminding readers that mobile phone traffic data can be used to improve the effectiveness of specific urban policies.

Let me conclude this review with the following five observations. First, although the subject matter of this book is interesting, the book is written in a dense style; hence, it is not easy to peruse. Second, it includes a small number of claims and sentences (e.g., footnote 8 on p. 20) that are difficult to fathom. Third, instead of settling on one spelling format (e.g., American or British), the book inexplicably uses both; as an example, see p. 81. Fourth, although this book raises several pertinent questions about the public policy uses of mobile phone data, it does not always answer these questions in a satisfactory manner. Finally, subject to the above four caveats, readers are likely to find the material in this tome useful.

Amitrajeet A. Batabyal

Department of Economics, Rochester Institute of Technology, Rochester, New York, [email protected]