Foundations of Network Optimization and Games

This is a book about infrastructure networks that are intrinsically nonlinear. The networks considered range from vehicular networks to electric power networks to data networks.

The main point of view taken is that of mathematical programming in concert with finite-dimensional variational inequality theory. The principle modeling perspectives are network optimization, the theory of Nash games, and mathematical programming with equilibrium constraints. Computational methods and novel mathematical formulations are emphasized. Among the numerical methods explored are network simplex, gradient projection, fixed-point, gap function, Lagrangian relaxation, Dantzig-Wolfe decomposition, simplicial decomposition, and computational intelligence algorithms.

Many solved example problems are included that range from simple to quite challenging. Theoretical analyses of several models and algorithms, to uncover existence, uniqueness and convergence properties, are undertaken. The bookis meant for use in advanced undergraduate as well as doctoral courses taught in civil engineering, industrial engineering, systems engineering, and operations research degree programs. At the same time, the book should be a useful resource for industrial and university researchers engaged in the mathematical modeling and numerical analyses of infrastructure networks.

Zusammenfassung

Foundations of Network Optimization and Games by Terry L. Friesz and David Bernstein is a book intended for scholars from all disciplines working on deterministic nonlinear network models expressed as nonlinear programs and mathematical games, as well as for graduate students encountering nonlinear network models for the first time.

The book purposely emphasizes model formulation, algorithm selection, and illustrative numerical examples rather than theoretical results on convergence and algorithm complexity. As such Foundations of Network Optimization and Games will be especially useful to individuals who are builders of so-called computable models meant for direct decision support or comprehensive numerical discovery of the properties of complex, networked systems.

Chapter 1 provides a quick tour of timely nonlinear network applications, including traffic assignment, data network flows, electrical power grids, and water resource management. Chapters 2 and 3 provide a review of essential notions and tools from nonlinear programming and graph theory, respectively. These early chapters set the stage for Chapter 4's indepth discussion of the implications of network structure in mathematical programming. Chapter 5 explores algorithms for large-scale as well as near-network programs; among the algorithms considered are Lagrangian relaxation, Dantzig-Wolfe decomposition, Benders decomposition, and simplicial decomposition.

Chapter 6 considers a variety of normative network models, and illustrates how the material of the preceding chapters may be applied. Several solved numerical examples are included. The normative models studied include classical network problems such as the primal minimum cost flow problem with transshipment, the traveling salesman problem, the vehicle routing problem, and the capacitated plant location problem. Also considered are nonlinear network models of irrigation network operations and telecommunications flow routing.

Chapter 7 is devoted to Nash games and the mathematical apparatus needed to model them. The longest chapter of the book, Chapter 7 describes how to create fixed point, variational inequality and complementarity formulations of Nash games. Algorithms for solving Nash games are also presented, including gap-function methods and successive linearization of nonlinear complementarity formulations.

Chapter 8 provides a detailed discussion of vehicular network equilibrium, including alternative formulations and algorithms. Chapter 9 studies spatial network equilibrium using the tools presented in Chapter 7, including Samuelson-Takayama-Judge models of spatial competition. Spatial arbitrage in network oligopolies and freight network equilibrium are also analyzed.

Chapter 10, the final chapter, provides an introduction to Stackelberg games on networks, the price of anarchy, congestion pricing, and network design. The natural formulation of Stackelberg games as mathematical programs with equilibrium constraints (MPECs) is explored from several points of view, including the price of anarchy, the Braess paradox, and the algorithmic implications of variational inequality sensitivity analysis. Nontraditional methods, in particular simulated annealing and swarm optimization, for solving MPECs and Stackelberg games are presented. Numerical examples of Electric power pricing and vehicular network design are included.

Inhalt

Introduction.- Elements of Nonlinear Programming.- Elements of Graph Theory.- Programs with Network Structure.- Near-Network and Large-Scale Programs.- Normative Network Models and Their Solution.- Nash Games.- Network Traffic Assignment.- Spatial Price Equilibrium on Networks.- Network Stackelberg Games and Mathematical Programs with Equilibrium Constraints.