Equitable Resource Allocation
Bringing together much of the equitable resource allocation research from the past thirty years, this book is a valuable reference for anyone interested in solving diverse optimization problems. Se
Equitable Resource Allocation
Golf is a game whose aim is to hit a very small ball into an even smaller hole, with weapons singularly ill-designed for that purpose.
- Winston Churchill
Over 70 years have passed since the emergence of operations research during World War II. During this relatively short period, operations research has contributed significantly to diverse areas in the military, industry, and government, including to logistics, communication, transportation, energy, health care, manufacturing, marketing, finance, and more. A significant part of operations research focuses on allocating limited resources among competing activities, or to put it simply, how to allocate the cake among the cake lovers ( Fig. 1.1 ).
Figure 1.1 Resource allocation: allocating the cake among people with different needs.
This chapter introduces the reader to certain classes of resource allocation models for which elegant and efficient solution methodologies have been developed, and which have been found to be valuable in diverse application areas.
Resource allocation problems focus on the allocation of limited resources among competing activities with the intent of optimizing an objective function. Initially, during World War II, solution methodologies were developed to support critically important military activities including deployment of radar systems, antisubmarine warfare, and bombing strategies. After the war, these methodologies were welcomed enthusiastically in order to help solve problems across diverse application areas in the public and private sectors. Major companies in the telecommunication, oil, transportation, automobile, high-tech, and other sectors established operations research groups to solve major recurring resource allocation problems in support of strategic and tactical problems. Government agencies used these methodologies to address important societal issues such as those occurring in health care, education, water resources, and environmental topics.
It is no doubt that linear programming has been, and still is, the most celebrated methodology used to solve resource allocation problems. Kantorovich, Dantzig, and von Neumann are regarded as the founders of linear programming, and the simplex method for solving such problems was published by Dantzig in 1947. Linear programming models consist of either minimizing or maximizing a linear objective function while satisfying linear constraints. Major advances in linear programming methodologies and increased computing power have facilitated solving very large problems with hundreds of thousands and even millions of decision variables and constraints.
This book covers a large variety of resource allocation models with special mathematical structures, solvable by elegant, efficient algorithms that take advantage of these structures. Moreover, the book primarily considers models that attempt to allocate the limited resources equitably (fairly) among competing activities; the notion of such equitable allocation will be described in the next section. From a historical perspective, the first well-known paper on resource allocation models with a special mathematical structure was published by Koopman in 1953 under the title of Optimum Distribution of Effort . Koopman followed up with a series of three papers on the theory of search, where the third of these papers presents a solution methodology for optimal distribution of searching effort. These seminal papers mark the beginning of the topic of resource allocation models with special mathematical structures.
1.2 EQUITABLE RESOURCE ALLOCATION: LEXICOGRAPHIC MINIMAX (MAXIMIN) OPTIMIZATION
Consider a resource allocation problem where multiple resources are allocated among numerous activities. We use the