Centralized resource allocation with stochastic data

Data Envelopment Analysis (DEA) is a technique based on mathematical programming for evaluating the efficiency of homogeneous Decision Making Units (DMUs). In this technique inefficient DMUs are projected on to the frontier which constructed by the best performers. Centralized Resource Allocation (CRA) is a method in which all DMUs are projected on to the efficient frontier through solving just one DEA model. The intent of this paper is to present the Stochastic Centralized Resource Allocation (SCRA) in order to allocate centralized resources where inputs and outputs are stochastic. The concept discussed throughout this paper is illustrated using the aforementioned example.     

Max-min resource allocation

A problem is considered of the allocation of resources so as to maximize the minimum return from several activities. Optimality conditions are given for the case of a single resource, and are used to derive a solution algorithm. Problems with several resources cannot be solved by resourcewise optimization. Concave return functions are treated approximately by linear programming, and optimality or almost optimality of any feasible solution to such a problem can be evaluated by the solution of a linear programming problem. The evaluation measure is extended to certain feasible solutions of problems which have continuous, but not necessarily concave, return functions. A numerical example is given.     

Fuzzy resource allocation

The problem of allocation of fuzzy resources to fuzzy activities is considered. Following a definition of the problem, a dedicated solution algorithm is defined in terms of a linear programming problem in the allocation variables and an aspiration level variable. Applications are given to max-min and sum of returns resource allocation, extending algorithms previously given.     

Interactive model-based search with reactive resource allocation

We revisit the interactive model-based approach to global optimization proposed in Wang and Garcia (J Glob Optim 61(3):479–495, 2015) in which parallel threads independently execute a model-based search method and periodically interact through a simple acceptance-rejection rule aimed at preventing duplication of search efforts. In that paper it was assumed that each thread successfully identifies a locally optimal solution every time the acceptance-rejection rule is implemented. Under this stylized model of computational time, the rate of convergence to a globally optimal solution was shown to increase exponentially in the number of threads. In practice however, the computational time required to identify a locally optimal solution varies greatly. Therefore, when the acceptance-rejection rule is implemented, several threads may fail to identify a locally optimal solution. This situation calls for reallocation of computational resources in order to speed up the identification of local optima when one or more threads repeatedly fail to do so. In this paper we consider an implementation of the interactive model-based approach that accounts for real time, that is, it takes into account the possibility that several threads may fail to identify a locally optimal solution whenever the acceptance-rejection rule is implemented. We propose a modified acceptance-rejection rule that alternates between enforcing diverse search (in order to prevent duplication) and reallocation of computational effort (in order to speed up the identification of local optima). We show that the rate of convergence in real-time increases with the number of threads. This result formalizes the idea that in parallel computing, exploitation and exploration can be complementary provided relatively simple rules for interaction are implemented. We report the results from extensive numerical experiments which are illustrate the theoretical analysis of performance.     

A single-resource allocation problem with Poisson resource requirements

We consider a stochastic resource allocation problem that generalizes the knapsack problem to account for random item weights that follow a Poisson distribution. When the sum of realized weights exceeds capacity, a penalty cost is incurred. We wish to select the items that maximize expected profit. We provide an effective solution method and illustrate the advantages of this approach via computational experiments.     

Sequential resource allocation with constraints: Two-customer case

We study a two-customer sequential resource allocation problem with equity constraint, which is reflected by a max–min objective. For finite discrete demand distribution, we give a sufficient and necessary condition under which the optimal solution has monotonicity property. However, this property never holds with unbounded discrete distribution.     

Minmax regret linear resource allocation problems

For minmax regret versions of some basic resource allocation problems with linear cost functions and uncertain coefficients (interval-data case), we present efficient (polynomial and pseudopolynomial) algorithms. As a by-product, we obtain an algorithm for the interval data minmax regret continuous knapsack problem.     

Optimal resource allocation in presidential primaries

A model for the optimal allocation of resources in presidential primaries is described, under the assumption that two candidates seek to maximize their expected delegate vote in a sequential game that allows for momentum transfer from earlier to later contests. Specifically, the model assumes that the probability that a voter in a primary state votes for a particular candidate is a function of both the resources that candidate and his opponent allocate to that primary and their performances in the immediately preceding primary - and indirectly on all earlier primaries. Given that the candidates make equal (optimal) allocations to each primary, a local maximum, which heavily emphasizes the earlier primaries, is found. Several modifications in the basic model are discussed. Preliminary financial expenditure data are used to test the basic model for the 1976 primaries, and some cursory comparisons with 1980 are made. Possible normative implications of changes in the primary rules are briefly considered, particularly with respect to inequities the present rules seem to engender.     

Optimal resource allocation in survey designs

Resource allocation is a relatively new research area in survey designs and has not been fully addressed in the literature. Recently, the declining participation rates and increasing survey costs have steered research interests towards resource planning. Survey organizations across the world are considering the development of new mathematical models in order to improve the quality of survey results while taking into account optimal resource planning. In this paper, we address the problem of resource allocation in survey designs and we discuss its impact on the quality of the survey results. We propose a novel method in which the optimal allocation of survey resources is determined such that the quality of survey results, i.e., the survey response rate, is maximized. We demonstrate the effectiveness of our method by extensive numerical experiments.     

Approximation algorithms for dynamic resource allocation

We consider a problem of allocating limited quantities of M types of resources among N independent activities that evolve over T epochs. In each epoch, we assign to each activity a task which consumes resources, generates utility, and determines the subsequent state of the activity. We study the complexity of, and approximation algorithms for, maximizing average utility.     

Optimal resource allocation across related channels

In this paper, we consider resource allocation strategies of a limited resource across two related channels in a multi-period setting. We study a stochastic control problem where the objective is to determine the optimal limited resource allocation policy across two related channels and optimal transshipment policy between these two channels. We characterize some structural results of the optimal resource allocation policy and show that it is determined by three monotone curves.     

Solution of a resource allocation game

Translated from Vychislitel'nye Sistemy i Voprosy Prinyatiya Reshenii, pp. 180–183, 1991.     

Fair resource allocation for demands with sharp lower tail inequalities

We consider a fairness problem in resource allocation where multiple groups demand resources from a common source with the total fixed amount. We show that for many common demand distributions satisfying sharp lower-tail inequalities, a natural allocation that provides resources proportional to each group's average demand performs very well. More specifically, this natural allocation is approximately fair and efficient (i.e., it provides near maximum utilization). We also show that, when a small amount of unfairness is allowed, the Price of Fairness (PoF), in this case, is close to 1.     

Linking stakeholder visions with resource allocation scenarios and multi-criteria assessment

Stakeholders and decision makers often develop visions of the ideal-type future as a response to complex societal problems and design their actions accordingly. However, these actors sometimes have a limited understanding as to whether their visions are feasible, what action is required and what the potential consequences are. This paper presents a methodology for linking visions with quantitative resource allocation scenarios which show different options in implementing the visions. The consequences are then appraised by multi-criteria assessment in order to find optimal and acceptable ways of implementation. As a result, stakeholders and decision makers learn about their visions and may even rethink them before decision making. The methodology thus couples visionary ideas with analytical information, providing a novel approach using quantitative techniques in a soft framework. The methodology is illustrated via a real-world case study concerning the future energy system in a small Swiss community.     

Relaxation-based algorithms for minimax optimization problems with resource allocation applications

We consider minimax optimization problems where each term in the objective function is a continuous, strictly decreasing function of a single variable and the constraints are linear. We develop relaxation-based algorithms to solve such problems. At each iteration, a relaxed minimax problem is solved, providing either an optimal solution or a better lower bound. We develop a general methodology for such relaxation schemes for the minimax optimization problem. The feasibility tests and formulation of subsequent relaxed problems can be done by using Phase I of the Simplex method and the Farkas multipliers provided by the final Simplex tableau when the corresponding problem is infeasible. Such relaxation-based algorithms are particularly attractive when the minimax optimization problem exhibits additional structure. We explore special structures for which the relaxed problem is formulated as a minimax problem with knapsack type constraints; efficient algorithms exist to solve such problems. The relaxation schemes are also adapted to solve certain resource allocation problems with substitutable resources. There, instead of Phase I of the Simplex method, a max-flow algorithm is used to test feasibility and formulate new relaxed problems.Corresponding author.Work was partially done while visiting AT&T Bell Laboratories.     

Solving nested-constraint resource allocation problems with an interior point method

Efficient methods for convex resource allocation problems usually exploit algebraic properties of the objective function. For problems with nested constraints, we show that constraint sparsity structure alone allows rapid solution with a general interior point method. The key is a special-purpose linear system solver requiring only linear time in the problem dimensions. Computational tests show that this approach outperforms the previous best algebraically specialized methods.     

Centralized resource allocation for enhanced Russell models

This paper proposes a centralized resource allocation (CRA) model for the enhanced Russell model. All the DMUs can be easily projected onto the efficient frontier by solving only one model. This projection can be made by transforming the proposed model to a linear programming problem. In this paper, instead of non-radially increasing or decreasing the inputs or outputs individually, we increase or decrease non-radially all of the inputs and outputs at the same time. By solving a single model, we can provide targets for all DMUs. By the proposed approximation, different targets can be found for all DMUs, as compared to those obtained by the previous approximations. The proposed model can be developed to CRA models. Finally, an applied example emphasizes the importance of the proposed model.     

Optimality conditions in a resource allocation problem

Translated from Vychislitel'nye Kompleksy i Modelirovanie Slozhnykh Sistem, pp. 138–141, Moscow State University, 1989.     

On swarm-level resource allocation in BitTorrent communities

BitTorrent is a peer-to-peer computer network protocol for sharing content in an efficient and scalable way. Modeling and analysis of the popular private BitTorrent communities has become an active area of research. In these communities users are strongly incentivized to contribute their resources, i.e., to share their files. In BitTorrent terminology, users who have finished downloading files and stay online to share these files with others in the network are called seeders. The combination of seeders and downloaders of a file is called a swarm. In this paper we examine and evaluate the efficiency of the resource allocation of seeders in multiple swarms. This is formulated as an integer linear fractional programming problem. The evaluation is done on traces representing two existing BitTorrent communities. We find that in communities, particularly with low users-to-files ratio (which is typically the case), there is room for improvement.     

Optimal resource allocation for multiqueue systems with a shared server pool

We study optimal allocation of servers for a system with multiple service facilities and with a shared pool of servers. Each service facility poses a constraint on the maximum expected sojourn time of a job. A central decision maker can dynamically allocate servers to each facility, where adding more servers results in faster processing speeds but against higher utilization costs. The objective is to dynamically allocate the servers over the different facilities such that the sojourn-time constraints are met at minimal costs. This situation occurs frequently in practice, for example, in Grid systems for real-time image processing (iris scans, fingerprints). We model this problem as a Markov decision process and derive structural properties of the relative value function. These properties, which are hard to derive for multidimensional systems, give a full characterization of the optimal policy. We demonstrate the effectiveness of these policies by extensive numerical experiments.