Robust discrete optimization and its applications. (English) Zbl 0873.90071

Nonconvex Optimization and Its Applications. 14. Dordrecht: Kluwer Academic Publishers. xvi, 356 p. (1997).
The book deals with decision environments of data uncertainty with emphasis on operations management applications. The authors suggest the robustness approach to decision making. The book has nine chapters with references given at the end of each chapter. Chapter 1 introduces the concept of the robustness approach and its format definition. Chapter 2 presents a variety of problems for which the formulation of robust discrete optimization framework applies. Chapter 3 discusses complexity results on many classes of robust discrete optimization problems which are difficult to solve in general. Chapter 4 describes six polynomially solvable problems. Chapter 5 is restricted to robust discrete optimization problems with equivalent single scenario problems that can be solved efficiently with a polynomial or pseudo-polynomial procedure based on branch-and-bound with both upper and lower bounds generated by surrogate relaxation. Chapter 6 proposes a unifying approach for incorporating dynamic and uncertain aspects in the location decision making process by focussing on the robust 1-median location problem on a tree. Chapter 7 concentrates on robust single machine and two machine flowshop scheduling problems. Chapter 8 presents ways to adapt the Benders decomposition methodology to solve the robust network design problems. Chapter 9 summarizes the main results of the book and suggests some future research directions in robust discrete optimization.


90C10 Integer programming
90B80 Discrete location and assignment
90-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming
90C35 Programming involving graphs or networks
90B35 Deterministic scheduling theory in operations research