Network Optimization: Continuous And Discrete Models

An insightful, comprehensive, and up-to-date treatment of linear, nonlinear, and discrete/combinatorial network optimization problems, their applications, and their analytical and algorithmic methodology. It covers extensively theory, algorithms, and applications, and it aims to bridge the gap between linear and nonlinear network optimization on one hand, and integer/combinatorial network optimization on the other. Among its special features, the book: 1) provides a comprehensive account of the principal algorithms for linear network flow problems, including simplex, dual ascent, and auction algorithms 2) describes the application of network algorithms in many practical contexts, with special emphasis on data communication networks 3) develops in detail the computational complexity analysis of the main linear network optimization algorithms 4) covers extensively the main algorithms for specialized network problems, such as shortest path, max-flow, assignment, and traveling salesman 5) describes the main models for discrete network optimization problems, such as constrained shortest path, traveling salesman, vehicle routing, multidimensional assignment, facility location, spanning tree construction, etc 6) describes the main algorithmic approaches for integer-constrained network problems, such as branch-and-bound, Lagrangian relaxation and subgradient optimization, genetic algorithms, tabu search, simulated annealing, and rollout algorithms 7) develops the main methods for nonlinear network problems, such as convex separable and multicommodity flow problems arising in communication, transportation, and manufacturing contexts 8) discusses extensively auction algorithms, based on the author's original research on the subject 9) contains many examples, practical applications, illustrations, and exercises 10) contains much new material not found in any other textbook

Dimitri Bertsekas is McAffee Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology, and a member of the National Academy of Engineering. He has researched a broad variety of subjects from optimization theory, control theory, parallel and distributed computation, systems analysis, and data communication networks. He has written numerous papers in each of these areas, and he has authored or coauthored sixteen textbooks. Professor Bertsekas was awarded the INFORMS 1997 Prize for Research Excellence in the Interface Between Operations Research and Computer Science for his book "Neuro-Dynamic Programming" (co-authored with John Tsitsiklis), the 2001 ACC John R. Ragazzini Education Award, the 2009 INFORMS Expository Writing Award, the 2014 ACC Richard E. Bellman Control Heritage Award for "contributions to the foundations of deterministic and stochastic optimization-based methods in systems and control," the 2014 Khachiyan Prize for Life-Time Accomplishments in Optimization, and the 2015 George B. Dantzig Prize. In 2018, he was awarded jointly with John Tsitsiklis, the INFORMS John von Neumann Theory Prize, for the contributions of the research monographs "Parallel and Distributed Computation" and "Neuro-Dynamic Programming". In 2001, he was elected to the United States National Academy of Engineering for "pioneering contributions to fundamental research, practice and education of optimization/control theory"