Resource allocation model and double-sphere crowding distance for evolutionary multi-objective optimization

Convergence speed and diversity of nondominated solutions are two important performance indicators for Multi-Objective Evolutionary Algorithms (MOEAs). In this paper, we propose a Resource Allocation (RA) model based on Game Theory to accelerate the convergence speed of MOEAs, and a novel Double-Sphere Crowding Distance (DSCD) measure to improve the diversity of nondominated solutions. The mechanism of RA model is that the individuals in each group cooperate with each other to get maximum benefits for their group, and then individuals in the same group compete for private interests. The DSCD measure uses hyper-spheres consisting of nearest neighbors to estimate the crowding degree. Experimental results on convergence speed and diversity of nondominated solutions for benchmark problems and a real-world problem show the efficiency of these two proposed techniques.     

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.     

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.     

A weak linearization of the Kuhn-tucker conditions for a class of allocation problems

The return obtained from the allocation of resources to an activity is occasionally modelled by means of concave, strictly increasing functions. Exponential functions of a certain class conveniently lend themselves to such modelling. A nonlinear programming formulation of a multiresource allocation problem with return functions of the class appears to have Kuhn-Tucker conditions which in a sense are intrinsically linear. The paper shows how this fact can be utilised to save processing time in the execution of numerical algorithms for the solution of this mathematical programming problem.     

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.     

Resource allocation for end-to-end QoS provisioning in a hybrid wireless WCDMA and wireline IP-based DiffServ network

In the future UMTS network, the heterogeneous traffics of multimedia services demand various QoS provisioning. At the same time, the seamlessly conveying of information between mobile users and a hybrid network requires the networking from wireless to wireline domains. However, in both academia and industries, the end-to-end QoS provisioning in the integration of wireline and wireless networks remains a challenge. In this paper, a modeling of a hybrid wireless WCDMA and wireline IP-based DiffServ network is presented to investigate the resource allocation for end-to-end QoS provisioning for multimedia services. In the wireless domain, the mathematical modeling of the cross-layer model including the physical layer, the link layer and the network layer is built. The connection admission control scheme is implemented based on the cross-layer model to determine the amount of resource for different services. In the wireline domain, we define the mapping of QoS classes between UMTS and DiffServ networks according to different QoS requirements. We propose a bandwidth allocation scheme to provide satisfactory packet loss and delay guarantee in DiffServ networks. The final end-to-end admission control scheme combines the resource allocation and admission control in both wireless and wireline domains. The analytical and simulation results show that the proposed resource allocation and admission control schemes work cooperatively in the presented hybrid wireless and wireline networks to guarantee the end-to-end QoS requirements for multimedia services.     

Stochastic models for strategic resource allocation in nonprofit foreclosed housing acquisitions

Increased rates of mortgage foreclosures in the U.S. have had devastating social and economic impacts during and after the 2008 financial crisis. As part of the response to this problem, nonprofit organizations such as community development corporations (CDCs) have been trying to mitigate the negative impacts of mortgage foreclosures by acquiring and redeveloping foreclosed properties. We consider the strategic resource allocation decisions for these organizations which involve budget allocations to different neighborhoods under cost and return uncertainty. Based on interactions with a CDC, we develop stochastic integer programming based frameworks for this decision problem, and assess the practical value of the models by using real-world data. Both policy-related and computational analyses are performed, and several insights such as the trade-offs between different objectives, and the efficiency of different solution approaches are presented.     

Envelope Theorems in Dynamic Programming

The envelope theorem is a statement about derivatives along an optimal trajectory. In dynamic programming the envelope theorem can be used to characterize and compute the optimal value function from its derivatives. We illustrate this here for the linear-quadratic control problem, the resource allocation problem, and the inverse problem of dynamic programming.     

Modeling time allocation for prevention in primary care

This paper discusses the problem of allocating time for prevention at the primary care level, focusing on a general practitioner (GP) practice. The basic trade-off is between improved state of the health of the population, which translates into less demand for the GP services, and a decreased capacity for curative services, which translates into increased congestion. The problem of how much time to devote to prevention is modeled as a non-linear optimization problem. As an extension of the problem, selection of preventive activities to perform among recommended alternatives is modeled using a knapsack formulation, and its application is illustrated with a numerical example. The author is supported in part by Türkiye Bilimsel ve Teknik Araştirma Kurumu (TüBİTAK) Career Grant No. 106K260.     

Approximate dynamic programming for capacity allocation in the service industry

We consider a problem where different classes of customers can book different types of service in advance and the service company has to respond immediately to the booking request confirming or rejecting it. The objective of the service company is to maximize profit made of class-type specific revenues, refunds for cancellations or no-shows as well as cost of overtime. For the calculation of the latter, information on the underlying appointment schedule is required. In contrast to most models in the literature we assume that the service time of clients is stochastic and that clients might be unpunctual. Throughout the paper we will relate the problem to capacity allocation in radiology services. The problem is modeled as a continuous-time Markov decision process and solved using simulation-based approximate dynamic programming (ADP) combined with a discrete event simulation of the service period. We employ an adapted heuristic ADP algorithm from the literature and investigate on the benefits of applying ADP to this type of problem. First, we study a simplified problem with deterministic service times and punctual arrival of clients and compare the solution from the ADP algorithm to the optimal solution. We find that the heuristic ADP algorithm performs very well in terms of objective function value, solution time, and memory requirements. Second, we study the problem with stochastic service times and unpunctuality. It is then shown that the resulting policy constitutes a large improvement over an “optimal” policy that is deduced using restrictive, simplifying assumptions.     

An Interval Assignment Problem for Resource Optimization in LTE Networks

In this paper we study the problem of resource allocation in SC-FDMA (Single Carrier Frequency Division Multiple Access) which is adopted as the multiple access scheme for the uplink in the 3GPP-LTE (3rd Generation Partnership Project - Long Term Evolution) standard. The problem can be modeled as an assignment problem where each user can be given a subset of consecutive channels seen as an interval. After introducing the problem, we first prove that it is NP-hard to solve. Then we review some cases where the problem is solvable in polynomial time. An efficient cutting plane algorithm is presented with experimental results.     

Greedy primal-dual algorithm for dynamic resource allocation in complex networks

In Stolyar (Queueing Systems 50 (2005) 401–457) a dynamic control strategy, called greedy primal-dual (GPD) algorithm, was introduced for the problem of maximizing queueing network utility subject to stability of the queues, and was proved to be (asymptotically) optimal. (The network utility is a concave function of the average rates at which the network generates several “commodities.”) Underlying the control problem of Stolyar (Queueing Systems 50 (2005) 401–457) is a convex optimization problem subject to a set of linear constraints. In this paper we introduce a generalized GPD algorithm, which applies to the network control problem with additional convex (possibly non-linear) constraints on the average commodity rates. The underlying optimization problem in this case is a convex problem subject to convex constraints. We prove asymptotic optimality of the generalized GPD algorithm. We illustrate key features and applications of the algorithm on simple examples. AMS Subject Classifications: 90B15 · 90C25 · 60K25 · 68M12     

A biobjective method for sample allocation in stratified sampling

The two main and contradicting criteria guiding sampling design are accuracy of estimators and sampling costs. In stratified random sampling, the sample size must be allocated to strata in order to optimize both objectives.     

路政应急管理中资源布局的混合整数规划模型

本文根据道路灾害事故的发生特点,对城市路桥养护系统的运行模式和资源的合理调用机理进行分析,考虑到事发地点潜在的资源需求概率,建立资源布局的混合整数规划模型.本模型中资源布局方案的调度决策基础是在灾害事故的资源需求不发生变化的条件下,使得每个救助点的资源同时部分地为辖区内现有事故和潜在事故服务,而现有事故的剩余需求由其他救助点派出资源来满足.该模型的目标是解决城市中因同一时间段内发生两起灾害事故而造成路桥破坏导致的救助资源短缺问题,同时避免资源的闲置浪费.最后,通过算例证明,本方法较通常方法对城市总的资源配置量大大减少.     

Optimal dynamic asset allocation of pension fund in mortality and salary risks framework

In this paper, we consider the optimal dynamic asset allocation of pension fund with mortality risk and salary risk. The managers of the pension fund try to find the optimal investment policy (optimal asset allocation) to maximize the expected utility of terminal wealth. The market is a combination of financial market and insurance market. The financial market consists of three assets: cashes with stochastic interest rate, stocks and rolling bonds, while the insurance market consists of mortality risk and salary risk. These two non-hedging risks cause incompleteness of the market. By martingale method and dynamic programming principle we first derive the approximate optimal investment policy to overcome the difficulty, then investigate the efficiency of the approximation. Finally, we solve an optimal assets liabilities management(ALM) problem with mortality risk and salary risk under CRRA utility, and reveal the influence of these two risks on the optimal investment policy by numerical illustration.     

On the Existence Problem of Solutions for a Class of Functional Equations Arising in Multistage Allocation Processes

The purpose of this paper is to study the existence problems of solutions for some classes of functional equations and systems of functional equations arising in multistage allocation processes.     

三部门封闭经济系统资源配置的动态优化模型

通过建立一个三部门的封闭经济系统的资源配置动态优化模型,在理论上分析及证明,通过提高劳动力的素质及技能,劳动力可以从补偿劳动力再生产的生产部门向最终产品的生产部门及资本性资源的生产部门流动,使资本性资源增加生产,增量配置到其它生产部门,从而在保证劳动力再生产产品能满足需要的同时,激发整体经济的成长.最后运用数据分析方法对以上原理及模型进行了验证     

Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n ² m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm logn). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.Research partially supported by a Presidential Young Investigator Award from the National Science Foundation, Grant No. CCR-8858097, an IBM Faculty Development Award, and AT&T Bell Laboratories.Research partially supported by the Office of Naval Research, Contract No. N00014-87-K-0467.Research partially supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. N00014-87-K-0467.     

A stochastic programming model using an endogenously determined worst case risk measure for dynamic asset allocation

We present a new approach to asset allocation with transaction costs. A multiperiod stochastic linear programming model is developed where the risk is based on the worst case payoff that is endogenously determined by the model that balances expected return and risk. Utilizing portfolio protection and dynamic hedging, an investment portfolio similar to an option-like payoff structure on the initial investment portfolio is characterized. The relative changes in the expected terminal wealth, worst case payoff, and risk aversion, are studied theoretically and illustrated using a numerical example. This model dominates a static mean-variance model when the optimal portfolios are evaluated by the Sharpe ratio. Received: August 15, 1999 / Accepted: October 1, 2000?Published online December 15, 2000