Nested partitions method, theory and applications (Q930431)

This book is devoted to a relatively new optimization method that has been found to be very effective in solving discrete optimization problems. The subject nested partitions method (NP) is an innovative mix of traditional optimization methodology and probabilistic assumptions. The Nested Partitions (NP) framework combines many well-known optimization techniques, including dynamic programming, mixed integer programming, genetic algorithms and tabu search and also integrates many problem specific local search heuristics. In this book, the authors show how the NP method has been successful in solving complex problems in planning and scheduling, logistics and transportation, supply chain design, data mining, and health care. The book is intended to be a reference material for researchers and practitioners in management science, industrial engineering, economics, computer science, and environmental science. Also, because of its emphasis on practical applications, the book can appropriately be used as a textbook in a graduate course. I feel this intension is more or less fulfilled. The book is organized in two parts. Part I develops the general theory and implementation framework for the NP method, while Part II provides a detailed look at several application areas. Chapter 1 presents an introduction to large scale optimization, exact solution methods, heuristic solution methods, NP method and application examples that illustrate the type of optimization problems for which the NP method is particularly effective. Chapter 2 develops the foundation for the NP method and its implementation. Chapter 3 focuses on the special case where the objective function is not known analytically but must be estimated and is hence noisy. This introduces additional challenges but the NP method can still be applied effectively. This chapter discusses what makes the NP method effective for problems with noisy performance, provides a convergence analysis, and suggests how the NP method is best implemented for such problems. Mathematical programming methods have been shown to solve numerous large-scale problems and in Chapter 4, the authors show how such methods can be effectively incorporated into the NP framework to improve its efficiency. In Chapter 5, the authors demonstrate how various random search methods, metaheuristics, and local search can be incorporated into the NP framework. The second part of the book presents several applications. Readers who are primarily interested in applications may want to focus on the second part of the book but should first familiarize themselves with the first five sections of Chapter 2. The application section of the book consists of seven independent chapters illustrating how the NP method can be used to solve problems that arise in a broad range of application areas. Chapter 6 looks at a very complex production scheduling problem that arises where there are flexible resources that must be scheduled simultaneously to the jobs that are to be completed, namely the Parallel-Machine Flexible-Resource Scheduling (PMFRS) problem. Chapter 7 looks at a problem that arises frequently in practical data mining projects, namely the feature selection problem. An important problem for many organizations today is the design of their supply chain network. Chapter 8 considers how to apply the NP method to difficult optimization problems that arise in this context. In Chapter 9, the authors demonstrate that the NP method provides an effective framework for obtaining high-quality solutions to the beam angle selection (BAS) problem. Chapter 10 deals with a problem in another important area, namely transportation and logistics. In particular, the chapter provides a mixed integer programming (MIP) formulation of the local pickup and delivery problem (LPDP). Chapter 11 deals with a complex extension of the classic job shop scheduling problem, where bill-of-material and work-shift constraints are also accounted for in the the formulation. This problem is motivated by observations of real job shop systems, and this chapter illustrates how the NP method can effectively handle realistic problems with very complex constraints. The final chapter considers problems where uncertainty plays a key role. Specifically, the design of discrete event systems gives rise to many resource allocation problems, and in Chapter 12, the authors discuss two such examples, namely buffer allocation in communication networks and resource allocation in manufacturing systems. This book aims to provide an optimization framework with which researchers will be able to discover and develop new hybrid optimization methods for successful application of real optimization problems. I consider that this is a very valuable book. I certainly recommend buying it.