ISBN-10:
1118054687
ISBN-13:
9781118054680
Pub. Date:
10/09/2012
Publisher:
Wiley
Equitable Resource Allocation: Models, Algorithms and Applications / Edition 1

Equitable Resource Allocation: Models, Algorithms and Applications / Edition 1

by Hanan Luss
Current price is , Original price is $122.0. You

Temporarily Out of Stock Online

Please check back later for updated availability.

Product Details

ISBN-13: 9781118054680
Publisher: Wiley
Publication date: 10/09/2012
Series: Information and Communication Technology Series, Series , #101
Pages: 376
Product dimensions: 6.00(w) x 9.40(h) x 0.90(d)

About the Author

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.

Read an Excerpt

Click to read or download

Table of Contents

Preface xi

Acknowledgments xvii

1 Introduction 1

1.1 Perspective 1

1.2 Equitable Resource Allocation: Lexicographic Minimax(Maximin) Optimization 3

1.3 Examples and Applications 14

1.3.1 Allocation of High-Tech Components 14

1.3.2 Throughput in Communication and Computer Networks 15

1.3.3 Point-to-Point Throughput Estimation in Networks 18

1.3.4 Bandwidth Allocation for Content Distribution 20

1.3.5 Location of Emergency Facilities 23

1.3.6 Other Applications 25

1.4 Related Fairness Criteria 26

1.5 Outline of the Book 30

1.5.1 Chapter 2: Nonlinear Resource Allocation 30

1.5.2 Chapter 3: Equitable Resource Allocation: LexicographicMinimax and Maximin Optimization 30

1.5.3 Chapter 4: Equitable Resource Allocation withSubstitutable Resources 31

1.5.4 Chapter 5: Multiperiod Equitable Resource Allocation32

1.5.5 Chapter 6: Equitable Network Resource Allocation 33

1.5.6 Chapter 7: Equitable Resource Allocation with IntegerDecisions 34

1.6 Concluding Remarks and Literature Review 35

1.6.1 Equitable Allocation of High-Tech Components 38

1.6.2 Equitable Throughput in Communication and ComputerNetworks 38

1.6.3 Point-to-Point Throughput Estimation in Networks 39

1.6.4 Equitable Bandwidth Allocation for Content Distribution39

1.6.5 Equitable Location of Emergency Facilities 39

1.6.6 Other Applications 39

2 Nonlinear Resource Allocation 41

2.1 Formulation and Optimality Properties 42

2.2 Algorithms 48

2.2.1 The Activity Deletion Algorithm 48

2.2.2 The Activity Addition Algorithm 53

2.2.3 The Constraints Evaluation Algorithm 55

2.2.4 Lower and Upper Bounds 58

2.3 Nonlinear Resource-Usage Constraint 58

2.3.1 Formulation and Optimality Properties 59

2.3.2 Algorithms 62

2.4 Multiple Resource Constraints: A Special Case 66

2.5 Concluding Remarks and Literature Review 73

Exercises 75

3 Equitable Resource Allocation: Lexicographic Minimax andMaximin Optimization 77

3.1 Formulation and Optimality Properties 78

3.2 Minimax Algorithms 84

3.2.1 The Minimax Activity Deletion Algorithm 84

3.2.2 The Minimax Activity Addition Algorithm 90

3.2.3 The Minimax Constraints Evaluation Algorithm 94

3.2.4 Lower and Upper Bounds 97

3.3 The Lexicographic Minimax Algorithm 98

3.4 Extension to Nonseparable Objective Function 107

3.5 Concluding Remarks and Literature Review 116

Exercises 120

4 Equitable Resource Allocation with Substitutable Resources123

4.1 Representations of Substitutable Resources 124

4.1.1 Transitive Substitutable Resources Represented by Trees124

4.1.2 Transitive Substitutable Resources Represented by AcyclicGraphs 125

4.1.3 Nontransitive Substitutable Resources Represented byBipartite Graphs 127

4.1.4 Activity-Dependent Substitutable Resources Represented byBipartite Graphs 128

4.1.5 Solution Approach 129

4.2 Transitive Substitutable Resources Represented by Trees131

4.2.1 Formulation 131

4.2.2 The Minimax Algorithm 134

4.2.3 The Lexicographic Minimax Algorithm 143

4.2.4 Lower and Upper Bounds 151

4.3 Transitive Substitutable Resources Represented by AcyclicGraphs 153

4.3.1 Formulation 154

4.3.2 The Feasibility Problem 155

4.3.3 The Minimax Algorithm 161

4.3.4 The Lexicographic Minimax Algorithm 165

4.4 Activity-Dependent Substitutable Resources Represented byBipartite Graphs 172

4.4.1 Formulation 173

4.4.2 The Minimax Algorithm 175

4.4.3 The Lexicographic Minimax Algorithm 179

4.5 Concluding Remarks and Literature Review 180

Exercises 181

5 Multiperiod Equitable Resource Allocation 183

5.1 Formulation for Storable Resource Allocation 184

5.2 Minimax Algorithms for Storable Resources 187

5.2.1 The Search-Based Algorithm 188

5.2.2 The Transformation-Based Algorithm 192

5.2.3 The Multiperiod Activity Deletion Algorithm: A SpecialCase 200

5.3 The Lexicographic Minimax Algorithm 203

5.4 Allocation of Nonstorable Resources 210

5.5 Multiperiod Allocation of Substitutable Resources 213

5.6 Concluding Remarks and Literature Review 218

Exercises 219

6 Equitable Allocation of Network Resources 221

6.1 Multicommodity Network Flows with a Single Fixed Path223

6.2 Multicommodity Network Flows with Multiple Paths 227

6.3 Bandwidth Allocation for Content Distribution 237

6.4 Content Distribution with Node-Dependent PerformanceFunctions 248

6.5 Concluding Remarks and Literature Review 254

Exercises 257

7 Equitable Resource Allocation with Integer Decisions259

7.1 Knapsack Resource Constraints with Integer Variables 261

7.1.1 Formulation and Challenges 261

7.1.2 The Integer Minimax Problem 264

7.1.3 The Integer Lexicographic Minimax Problem with OneResource Constraint 270

7.2 Problems with a Limited Number of Distinct Outcomes 273

7.2.1 The Equitable Facility Location Problem 273

7.2.2 The Equitable Sensor Location Problem 279

7.2.3 Lexicographic Minimization of Counting Functions 281

7.3 Problems with a Large Number of Distinct Outcomes 290

7.3.1 Examples 291

7.3.2 Lexicographic Maximization of Performance Function Values294

7.3.3 The Conditional Maximin Approach 301

7.3.4 The Ordered Weighted Averaging Approach 302

7.3.5 The Convex Integer Optimization Approach 305

7.4 Concluding Remarks and Literature Review 307

Exercises 311

Appendices 313

Appendix A. Summary of Models and Algorithms / 315

Appendix B. The Kuhn–Tucker Conditions / 323

Appendix C. Duality in Linear Programming / 327

References 331

Author Index 343

Subject Index 347

What People are Saying About This

From the Publisher

I 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)

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews