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.     

Fast value iteration: an application of Legendre-Fenchel duality to a class of deterministic dynamic programming problems in discrete time*

ABSTRACT

We propose an algorithm, which we call ‘Fast Value Iteration’ (FVI), to compute the value function of a deterministic infinite-horizon dynamic programming problem in discrete time. FVI is an efficient algorithm applicable to a class of multidimensional dynamic programming problems with concave return (or convex cost) functions and linear constraints. In this algorithm, a sequence of functions is generated starting from the zero function by repeatedly applying a simple algebraic rule involving the Legendre-Fenchel transform of the return function. The resulting sequence is guaranteed to converge, and the Legendre-Fenchel transform of the limiting function coincides with the value function.     

Discrete allocation of a linear resource according to a sum-of-products objective

The allocation of a linear resource according to the sum of the returns from independent activities is considered. The return from each activity is given by a product of concave and nondecreasing functions of a single allocation variable. The model can be used, for instance, to describe probabilities of success of several serial tasks, into which an activity is subdivided. An incremental algorithm is defined and conditions are given for the algorithm to generate an optimal solution; otherwise, the problem is solved by a two-step procedure involving the incremental maximization of the return corresponding to a single activity and the combination of the activities by dynamic programming. Examples are given of problems solvable and not solvable by the incremental algorithm.     

Oil Exploration: A Property of Beale's Model

In this paper we assume that an oil company has k areas in which to drill and occurrences of undiscovered oilfields are represented by the model of Beale. The company is seeking a strategy for drilling that maximizes its expected return under the constraint that the total amount spent on drilling in all areas must not exceed R. This leads to an integer programming problem. We establish that the expected return functions for the separate areas are concave and that this property can be used to reduce the computational effort required to find an optimal solution.     

Totally balanced games arising from controlled programming problems

A cooperative game in characteristic-function form is obtained by allowing a number of individuals to esercise partial control over the constraints of a (generally nonlinear) mathematical programming problem, either directly or through committee voting. Conditions are imposed on the functions defining the programming problem and the control system which suffice to make the game totally balanced. This assures a nonempty core and hence a stable allocation of the full value of the programming problem among the controlling palyers. In the linear case the core is closely related to the solutions of the dual problem. Applications are made to a variety of economic models, including the transferable utility trading economies of Shapley and Shubik and a multishipper one-commodity transshipment model with convex cost functions and concave revenue functions. Dropping the assumption of transferable utility leads to a class of controlled multiobjective or ‘Pareto programming’ problems, which again yield totally balanced games.     

Incremental allocation of a discrete and convex resource to concave activities

The problem considered is that of the allocation of a given quantity of a discrete resource to activities described by concave return functions. The resource-consumption corresponding to each allocation is described by a convex function of the quantity allocated. An incremental solution algorithm is given, which specializes to the algorithm of Fox if the resource is linear, and to an algorithm of Katoh, Ibaraki and Mine if the return functions are linear.     

Discrete Resource Allocation by a Branch and Bound Method

A branch and bound method given by Shih for the solution of a class of discrete single resource allocation problems with concave return functions and several constraints of any type is extended to cover problems with arbitrary non-decreasing return functions.     

Allocation of dependent divisional resources

A resource allocation problem is considered with resources that are dependent in the sense that an allocation to an activity requires the application of several resources, except for certain activities which are divisional in the sense that an allocation to such an activity requires the use of only a single resource. Return and cost functions are assumed to be continuous and increasing, and the allocation variables are continuous. Conditions are given for the replacement of the continuous problem by an associated problem with discrete variables and a single constraint, and to a given degree of accuracy. The associated problem can be efficiently solved by dynamic programming. Certain divisional resource allocation problems with discrete variables and several linear constraints are shown to be equivalent to a discrete problem with a single constraint. A numerical example is given.     

The selection of joint projects by a consortium: Cost sharing mechanisms

This paper considers the problem of project selection and cost allocation for a partly decentralised organisation such as a research consortium, whose members have conflicting preferences and limited budgets. Three normative properties that project selection and cost sharing mechanisms which should satisfy are proposed. We introduce a class of efficient mechanisms called willingness to pay that satisfies the properties and solves the interdependent selection and allocation mechanisms through mathematical programming. These mathematical programming procedures are shown first, to improve upon existing cost sharing plans used in practice, and second, to be undominated by any other selection and allocation mechanism that satisfies the properties. However, in the case of private information the procedures are not incentive compatible. For this case, we provide an incentive compatible, though inefficient, mechanism, and prove that no efficient mechanism can exist for this class of problems.     

Resource Allocation with Wobbly Functions

We consider resource allocation with separable objective functions defined over subranges of the integers. While it is well known that (the maximisation version of) this problem can be solved efficiently if the objective functions are concave, the general problem of resource allocation with functions that are not necessarily concave is difficult.In this article, we focus on a large class of problem instances, with objective functions that are close to a concave function or some other smooth function, but with small irregularities in their shape. It is described that these properties are important in many practical situations.The irregularities make it hard or impossible to use known, efficient resource allocation techniques. We show that, for this class of functions the optimal solution can be computed efficiently. We support our claims by experimental evidence. Our experiments show that our algorithm in hard and practically relevant cases runs up to 40–60 times faster than the standard method.     

Compromise allocation in multivariate stratified sample surveys under two stage randomized response model

A general model for the randomized response (RR) method was introduced by Warner (J. Am. Stat. Assoc. 60:63–69, 1965) when a single-sensitive question is under study. However, since social surveys are often based on questionnaires containing more than one sensitive question, the analysis of multiple RR data is of considerable interest. In multivariate stratified surveys with multiple RR data the choice of optimum sample sizes from various strata may be viewed as a multiobjective nonlinear programming problem. The allocation thus obtained may be called a “compromise allocation” in sampling literature. This paper deals with the two-stage stratified Warner’s RR model applied to multiple sensitive questions. The problems of obtaining compromise allocations are formulated as multi-objective integer non linear programming problems with linear and quadratic cost functions as two separate problems. The solution to the formulated problems are achieved through goal programming technique. Numerical examples are presented to illustrate the computational details.     

Optimality conditions and duality in continuous programming II. The linear problem revisited

This is Part II of a two-part paper; the purpose of this two-part paper is (a) to develop new concepts and techniques in the theory of infinite-dimensional programming, and (b) to obtain fruitful applications in continuous time programming. In Part II the continuous time version of Farkas' theorem developed in Part I serves as the foundation for the duality theory for a broad class of linear continuous time programming problems distinct from those previously examined. In particular, we establish duality under analytic conditions, e.g., whether the given functions are measurable or continuous, that are weaker, and algebraic conditions that are more general, than those previously imposed. The new class of problems arising from these conditions allows for several important resource allocation problems previously excluded from consideration. In addition, an assumption needed to prove the Kuhn-Tucker theorem for the nonlinear problem of Part I is shown in the linear case to be completely analogous to the well-known Slater condition utilized in finite-dimensional programming theory. An example is given that exhibits the essential role of the constraint qualification in linear continuous time programming, a result at variance with the theory in finite dimensions but consistent with other results concerning linear programs in infinite-dimensional spaces.     

Fractional Resource Allocation with S-Shaped Return Functions

A fractional resource allocation problem with S-shaped return functions and an affine cost function is considered. Properties of optimal solutions are derived, including conditions for certain allocations to be zero. Conditions are given for the determination of an optimal solution by concave approximations of the return functions; otherwise an error bound is obtained.     

Analysis of maximum total return in the continuous knapsack problem with fuzzy object weights

This paper proposes a parametric programming approach to analyze the fuzzy maximum total return in the continuous knapsack problem with fuzzy objective weights, in that the membership function of the maximum total return is constructed. The idea is based on Zadeh’s extension principle, α-cut representation, and the duality theorem of linear programming. A pair of linear programs parameterized by possibility level α is formulated to calculate the lower and upper bounds of the fuzzy maximum total return at α, through which the membership function of the maximum total return is constructed. To demonstrate the validity of the proposed procedure, an example studied by the previous studies is investigated successfully. Since the fuzzy maximum total return is completely expressed by a membership function rather than by a crisp value reported in previous studies, the fuzziness of object weights is conserved completely, and more information is provided for making decisions in real-world resource allocation applications. The generalization of the proposed approach for other types of knapsack problems is also straightforward.     

Reflections on a New Approach to Gittins Indexation

Traditional approaches to stochastic resource allocation problems (including the classical multi-armed bandit problems) have usually made use of dynamic programming (DP) methodology, perhaps buttressed by further ad hoc arguments. While such approaches seem ‘natural’ they have usually proved technically very difficult. Bertsimas and Niño-Mora have recently given a radically new account of many important results in this area which relate to Gittins indices. The key to their approach is in the characterisation of the region of achievable performance. The optimisation problems of interest are then solved as linear programs over this region. Here we exploit elements within the Bertsimas and Niño-Mora framework (in particular, its capacity to give formulae for the total return of a given policy in closed form) to obtain (i) a simple dynamic programming proof of the optimality of Gittins index policies and (ii) a range of index-based suboptimality bounds for general policies for a variety of stochastic models for resource allocation.     

An interval approach based on expectation optimization for fuzzy random bilevel linear programming problems

This paper considers a class of bilevel linear programming problems in which the coefficients of both objective functions are fuzzy random variables. The main idea of this paper is to introduce the Pareto optimal solution in a multi-objective bilevel programming problem as a solution for a fuzzy random bilevel programming problem. To this end, a stochastic interval bilevel linear programming problem is first introduced in terms of α-cuts of fuzzy random variables. On the basis of an order relation of interval numbers and the expectation optimization model, the stochastic interval bilevel linear programming problem can be transformed into a multi-objective bilevel programming problem which is solved by means of weighted linear combination technique. In order to compare different optimal solutions depending on different cuts, two criterions are given to provide the preferable optimal solutions for the upper and lower level decision makers respectively. Finally, a production planning problem is given to demonstrate the feasibility of the proposed approach.     

免疫粒子群优化算法在农业水资源优化配置中的应用

求解农业水资源优化配置模型(高维非线性优化模型),较常采用大系统分解协调原理和动态规划相结合的方法,这样减少了变量个数,便于优化求解,但协调的过程需要多次从低阶模型中返回信息,而且对于每层的寻优求解过程存在难以克服的矛盾.采用标准的粒子群优化算法则优化程度不易保证并容易陷入局部最优,优化结果对初始种群依赖性较强.因此应用免疫进化算法对标准粒子群优化算法进行改进并应用于灌区农业水资源优化配置模型的求解.算例分析表明,免疫粒子群算法为求解高维复杂的优化配置问题提供了新思路.     

Characterization of vector strict global minimizers of order 2 in differentiable vector optimization problems under a new approximation method

In this paper, a new approximation method is introduced to characterize a so-called vector strict global minimizer of order 2 for a class of nonlinear differentiable multiobjective programming problems with (F,ρ)-convex functions of order 2. In this method, an equivalent vector optimization problem is constructed by a modification of both the objectives and the constraint functions in the original multiobjective programming problem at the given feasible point. In order to prove the equivalence between the original multiobjective programming problem and its associated F-approximated vector optimization problem, the suitable (F,ρ)-convexity of order 2 assumption is imposed on the functions constituting the considered vector optimization problem.     

一类二层凸规划的对偶二层规划

本文讨论上层目标函数以下层子系统目标函数的最优值作为反馈的一类二层凸规划的对偶规划问题 ,在构成函数满足凸连续可微等条件的假设下 ,建立了二层凸规划的 Lagrange对偶二层规划 ,并证明了基本对偶定理 .