Equitable Resource Allocation

HANAN LUSS, PhD, serves as an Adjunct Professor, teaching operations research courses at Columbia University. Dr. Luss was at AT&T Bell Laboratories/AT&T Labs for twenty-five years, serving as technical manager of the Operations Research Studies Group, and at Telcordia Technologies for twelve years, serving as senior scientist. He led research activities and applied work with an emphasis on operations research methodologies for resource allocation, communication network design, capacity expansion, manufacturing, and related topics. A Fellow of the Institute for Operations Research and the Management Sciences (INFORMS), Dr. Luss has published over seventy papers in major refereed journals and books and has been granted more than ten patents.

I am very pleased to see this book available. Former comprehensive book on mathematical methods for resource allocation by Ibaraki and Katoh is excellent but it is already almost 25 years old. Meantime, a lot of new methods has been developed. Models and algorithms for equitable resource allocation are likely the most important advancements among them. They are extremely useful in a variety of practical application areas, but are not widely known. They had been scattered among specific research and application areas.The book fills out the gap by presenting the equitable techniques in a coherent and convenient form to readers from wide areas of engineering and operations management. It is indeed a unique book that specifically addresses equitable resource allocation problems with applications in many areas, not restricted to the information and communication technologies. Actually, it is an excellent book. Various models are widely motivated while the algorithms are clearly presented in details as ready to implement. Each chapter is also accompanied by a set of interesting exercises.I strongly recommend this book to professionals in Operations Management, Industrial Engineering, Computer Science and Telecommunications as well as a textbook for graduate students.- Wlodzimierz OgryczakI am very pleased to have this book available.  Algorithms for equitable resource allocation are extremely useful in a variety of practical application areas, but are not as widely known as they should be among engineering and operations research professionals. Much of the research has taken place in the last 20 years or so, and had been scattered among various journals.  It has now been brought together into one coherent and convenient volume.  Dr. Luss does an excellent job of motivating the various models and of describing the algorithms in a logical step-by-step fashion.The set of problems that can be solved using these lexicographic min-max algorithms is quite broad.  Initially, they were developed to solve resource allocation problems in the manufacturing area.  Specifically, they addressed the question of how to allocate electronic components to various product lines, when there was a shortage of components.  This can be naturally extended to allocating other sorts of scarce resources (e.g. manpower, computing resources, funding).But what I find exciting is that these very same mathematical programming techniques can be directly applied to problems that seem totally unrelated.  For example, they can be used to impute a traffic matrix for a packet communications network (such as the network operated by an Internet Service Provider).I wholeheartedly recommend this book to professionals – both in academia and in industry – in Operations Research, Management Science, Industrial Engineering, Telecommunications and Computer Science.                                                                                                          -John G. Klincewicz Mathematical models and methods for optimization enable resources of various kinds to be used ‘as best as possible’ under given constraints, and have been responsible for major advances in various fields, including control systems, operations research, and telecommunication networks. When there are multiple and competing objectives to be considered for optimization, the trade-off among the competing objectives introduces the new dimension of ‘fairness’ into the optimization. In such cases, the use of a single criterion for optimization is often inadequate and artificial. A particular form of posing multiple optimization criteria that captures a notion of fairness among competing objectives gives rise to the class of problems known as ‘lexicographic’ optimization, which goes beyond the usual minimax or maximin criterion to define the concept of ‘equitable’ optimization. Such equitable optimization is the subject of the book “Equitable Resource Allocation: Models, Algorithms, and Applications” by Dr. Hanan Luss. The book is a clear and systematic exposition of lexicographic optimization. After introductory chapters on single-criterion optimization, the book discusses algorithms for the usual minimax (or maximin) criterion for dealing with multi-objective problems, and shows how algorithms for lexicographic optimization can be built up from those for the minimax (or maximin) criterion. The later chapters consider various extensions of the basic model to take account of substitutable resources and multi-period optimization. The book considers theory and algorithms for both continuous and discrete decision variables. The book contains a variety of illustrative applications of the optimization models, drawn from the author’s long and distinguished research career at AT&T Labs and Bellcore/Telcordia. The material is organized in a clear and helpful manner among the chapters and within each chapter, and the writing is crisp and precise. A notable feature of the book is the neat classification of the various algorithms that are presented, making it a valuable compendium of optimization models and algorithms. The book will be a valuable text-book for an advanced course in optimization and a comprehensive reference for scientists and practitioners in operations research, engineering, telecommunications, and economics.-K.R. Krishnan (Bellcore/Telcordia - Retired)

• Preface xi Acknowledgments xvii1 Introduction 11.1 Perspective 11.2 Equitable Resource Allocation: Lexicographic Minimax (Maximin) Optimization 31.3 Examples and Applications 141.3.1 Allocation of High-Tech Components 141.3.2 Throughput in Communication and Computer Networks 151.3.3 Point-to-Point Throughput Estimation in Networks 181.3.4 Bandwidth Allocation for Content Distribution 201.3.5 Location of Emergency Facilities 231.3.6 Other Applications 251.4 Related Fairness Criteria 261.5 Outline of the Book 301.5.1 Chapter 2: Nonlinear Resource Allocation 301.5.2 Chapter 3: Equitable Resource Allocation: Lexicographic Minimax and Maximin Optimization 301.5.3 Chapter 4: Equitable Resource Allocation with Substitutable Resources 311.5.4 Chapter 5: Multiperiod Equitable Resource Allocation 321.5.5 Chapter 6: Equitable Network Resource Allocation 331.5.6 Chapter 7: Equitable Resource Allocation with Integer Decisions 341.6 Concluding Remarks and Literature Review 351.6.1 Equitable Allocation of High-Tech Components 381.6.2 Equitable Throughput in Communication and Computer Networks 381.6.3 Point-to-Point Throughput Estimation in Networks 391.6.4 Equitable Bandwidth Allocation for Content Distribution 391.6.5 Equitable Location of Emergency Facilities 391.6.6 Other Applications 392 Nonlinear Resource Allocation 412.1 Formulation and Optimality Properties 422.2 Algorithms 482.2.1 The Activity Deletion Algorithm 482.2.2 The Activity Addition Algorithm 532.2.3 The Constraints Evaluation Algorithm 552.2.4 Lower and Upper Bounds 582.3 Nonlinear Resource-Usage Constraint 582.3.1 Formulation and Optimality Properties 592.3.2 Algorithms 622.4 Multiple Resource Constraints: A Special Case 662.5 Concluding Remarks and Literature Review 73Exercises 753 Equitable Resource Allocation: Lexicographic Minimax and Maximin Optimization 773.1 Formulation and Optimality Properties 783.2 Minimax Algorithms 843.2.1 The Minimax Activity Deletion Algorithm 843.2.2 The Minimax Activity Addition Algorithm 903.2.3 The Minimax Constraints Evaluation Algorithm 943.2.4 Lower and Upper Bounds 973.3 The Lexicographic Minimax Algorithm 983.4 Extension to Nonseparable Objective Function 1073.5 Concluding Remarks and Literature Review 116Exercises 1204 Equitable Resource Allocation with Substitutable Resources 1234.1 Representations of Substitutable Resources 1244.1.1 Transitive Substitutable Resources Represented by Trees 1244.1.2 Transitive Substitutable Resources Represented by Acyclic Graphs 1254.1.3 Nontransitive Substitutable Resources Represented by Bipartite Graphs 1274.1.4 Activity-Dependent Substitutable Resources Represented by Bipartite Graphs 1284.1.5 Solution Approach 1294.2 Transitive Substitutable Resources Represented by Trees 1314.2.1 Formulation 1314.2.2 The Minimax Algorithm 1344.2.3 The Lexicographic Minimax Algorithm 1434.2.4 Lower and Upper Bounds 1514.3 Transitive Substitutable Resources Represented by Acyclic Graphs 1534.3.1 Formulation 1544.3.2 The Feasibility Problem 1554.3.3 The Minimax Algorithm 1614.3.4 The Lexicographic Minimax Algorithm 1654.4 Activity-Dependent Substitutable Resources Represented by Bipartite Graphs 1724.4.1 Formulation 1734.4.2 The Minimax Algorithm 1754.4.3 The Lexicographic Minimax Algorithm 1794.5 Concluding Remarks and Literature Review 180Exercises 1815 Multiperiod Equitable Resource Allocation 1835.1 Formulation for Storable Resource Allocation 1845.2 Minimax Algorithms for Storable Resources 1875.2.1 The Search-Based Algorithm 1885.2.2 The Transformation-Based Algorithm 1925.2.3 The Multiperiod Activity Deletion Algorithm: A Special Case 2005.3 The Lexicographic Minimax Algorithm 2035.4 Allocation of Nonstorable Resources 2105.5 Multiperiod Allocation of Substitutable Resources 2135.6 Concluding Remarks and Literature Review 218Exercises 2196 Equitable Allocation of Network Resources 2216.1 Multicommodity Network Flows with a Single Fixed Path 2236.2 Multicommodity Network Flows with Multiple Paths 2276.3 Bandwidth Allocation for Content Distribution 2376.4 Content Distribution with Node-Dependent Performance Functions 2486.5 Concluding Remarks and Literature Review 254Exercises 2577 Equitable Resource Allocation with Integer Decisions 2597.1 Knapsack Resource Constraints with Integer Variables 2617.1.1 Formulation and Challenges 2617.1.2 The Integer Minimax Problem 2647.1.3 The Integer Lexicographic Minimax Problem with One Resource Constraint 2707.2 Problems with a Limited Number of Distinct Outcomes 2737.2.1 The Equitable Facility Location Problem 2737.2.2 The Equitable Sensor Location Problem 2797.2.3 Lexicographic Minimization of Counting Functions 2817.3 Problems with a Large Number of Distinct Outcomes 2907.3.1 Examples 2917.3.2 Lexicographic Maximization of Performance Function Values 2947.3.3 The Conditional Maximin Approach 3017.3.4 The Ordered Weighted Averaging Approach 3027.3.5 The Convex Integer Optimization Approach 3057.4 Concluding Remarks and Literature Review 307Exercises 311Appendices 313Appendix A. Summary of Models and Algorithms / 315Appendix B. The Kuhn–Tucker Conditions / 323Appendix C. Duality in Linear Programming / 327References 331Author Index 343Subject Index 347