On Resource Allocation in Project Networks

The problem of scheduling activities so as to minimize project duration in the presence of resource constraints is considered. A branch and bound algorithm is described and some limited computational experience is reported.     

论一类资源最优配置问题及应用

本文考虑了一类资源最优配置问题.应用Kuhn-Tucher定理得到了这类问题最优解的充要条件.我们应用这个条件来考虑一类从工业投资、教育投资等问题中导出的最优投资模型,得到了这个问题最优解的充要条件,应用这个条件导出了求解这个模型的具有时间复杂度为o(mn)的多项式型新算法.     

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.     

Resource Allocation with Noise Constraints

In the allocation of resources to activities, each activity is described by a concave return function and the sum of the returns is maximized. There are linear constraints on the available quantity of each essential resource. Existing methods for the incremental generation of almost-optimal allocations and for the evaluation of such allocations are extended to include allocations involving "noise" constraints in addition to the linear constraints on the available quantity of each resource. A noise constraint, which is defined in the paper, may be expressed by any relationship, not necessarily linear. An example is given in which the noise constraints take the form of constraints on additional resources.     

Online Surrogate Problem Methodology for Stochastic Discrete Resource Allocation Problems

We consider stochastic discrete optimization problems where the decision variables are nonnegative integers. We propose and analyze an online control scheme which transforms the problem into a surrogate continuous optimization problem and proceeds to solve the latter using standard gradient-based approaches, while simultaneously updating both the actual and surrogate system states. It is shown that the solution of the original problem is recovered as an element of the discrete state neighborhood of the optimal surrogate state. For the special case of separable cost functions, we show that this methodology becomes particularly efficient. Finally, convergence of the proposed algorithm is established under standard technical conditions; numerical results are included in the paper to illustrate the fast convergence of this approach.     

Inverse Hyperbolic Problems with Time-Dependent Coefficients

We consider the inverse problem for the second order self-adjoint hyperbolic equation in a bounded domain in R ⁿ with lower order terms depending analytically on the time variable. We prove that, assuming the BLR condition, the time-dependent Dirichlet-to-Neumann operator prescribed on a part of the boundary uniquely determines the coefficients of the hyperbolic equation up to a diffeomorphism and a gauge transformation. As a by-product we prove a similar result for the nonself-adjoint hyperbolic operator with time-independent coefficients.     

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.     

Efficient Resource Allocation with Non-Concave Objective Functions

We consider resource allocation with separable objective functions defined over subranges of the integers. While it is well known that (the maximization version of) this problem can be solved efficiently if the objective functions are concave, the general problem of resource allocation with non-concave functions is difficult. In this article we show that for fairly well-shaped non-concave objective functions, the optimal solution can be computed efficiently. Our main enabling ingredient is an algorithm for aggregating two objective functions, where the cost depends on the complexity of the two involved functions. As a measure of complexity of a function, we use the number of subintervals that are convex or concave.     

具有模糊系数的模糊线性规划问题

本文考虑具有模糊系数的模糊线性规划问题中各系数的模糊可能性分布，而用指数（或线性）的隶属函数来描述，然后使用模糊数集上的实值函数，使模糊数在模型均值的意义下对应于一个实数，借此，将原问题公式化为一个普通线性规划。     

Pseudodifferential Boundary Value Problems with Non-Smooth Coefficients

ABSTRACT

In this contribution, we establish a calculus of pseudodifferential boundary value problems with Hölder continuous coefficients. It is a generalization of the calculus of pseudodifferential boundary value problems introduced by Boutet de Monvel. We discuss their mapping properties in Bessel potential and certain Besov spaces. Although having non-smooth coefficients and the operator classes being not closed under composition, we will prove that the composition of Green operators a ₁(x, D _x )a ₂(x, D _x ) coincides with a Green operator a(x, D _x ) up to order m ₁ + m ₂ ? Θ, where Θ ∈ (0, τ₂) is arbitrary, a _j (x, ξ) is in C ^{τ _j} (? ⁿ ) w.r.t. x, and m _j is the order of a _j (x, D _x ), j = 1, 2. Moreover, a(x, D _x ) is obtained by the asymptotic expansion formula of the smooth coefficient case leaving out all terms of order less than m ₁ + m ₂ ? Θ. This result is used to construct a parametrix of a uniformly elliptic Green operator a(x, D _x ).     

On Coefficients of Eigenfunction Expansions for Boundary-Value Problems with Parameter in Boundary Conditions

In this paper, we consider boundary-value problems for an nth-order ordinary differential equation with polynomials of the spectral parameter in the equation and in the boundary conditions. For a wide class of such problems, we find coefficients of the eigen and associated function expansions for the Shkalikov linearizer.     

A Branch and Bound Procedure for a Class of Discrete Resource Allocation Problems with Several Constraints

Journal of the Operational Research Society - A branch and bound algorithm is developed in this paper for a class of discrete resource allocation problems with many constraints. The algorithm...     

Arrangement Increasing Resource Allocation

Consider a system composed of several units. The performance of each unit can be affected by providing a portion of a limited amount of costly resources available. An allocation of resources to a unit results in a unit’s response that depends on the level of resources allocated to it and some of its random parameters. In this paper we consider cases where each unit has one or two random parameters. The overall performance of the system is mapped by a function on the vector of responses generated by all the units in the system. Our interest is in identifying the conditions on the response function of the units, the system performance function and the random parameters under which the random system performance as a function of the resource allocation has stochastic arrangement increasing property. This allows one to substantially reduce the number of allocation that needs to be searched to identify an optimal allocation that maximizes the expected utility derived from the system response as a result of the resource allocation.     

Condition Number Bounds for Problems with Integer Coefficients

An explicit a priori bound for the condition number associated to each of the following problems is given: general linear equation solving, least squares, nonsymmetric eigenvalue problems, solving univariate polynomials, and solving systems of multivariate polynomials. It is assumed that the input has integer coefficients and is not on the degeneracy locus of the respective problem (i.e., the condition number is finite). Our bounds are stated in terms of the dimension and of the bit-size of the input.  In the same setting, bounds are given for the speed of convergence of the following iterative algorithms: QR iteration without shift for the symmetric eigenvalue problem and Graeffe iteration for univariate polynomials.     

Newton-Multigrid for Biological Reaction-Diffusion Problems with Random Coefficients

An algebraic Newton-multigrid method is proposed in order to efficiently solve systems of nonlinear reaction-diffusion problems with stochastic coefficients. These problems model the conversion of starch into sugars in growing apples. The stochastic system is first converted into a large coupled system of deterministic equations by applying a stochastic Galerkin finite element discretization. This method leads to high-order accurate stochastic solutions. A stable and high-order time discretization is obtained by applying a fully implicit Runge-Kutta method. After Newton linearization, a point-based algebraic multigrid solution method is applied. In order to decrease the computational cost, alternative multigrid preconditioners are presented. Numerical results demonstrate the convergence properties, robustness and efficiency of the proposed multigrid methods.     

On Coefficients Problems for Typically Real Functions Related to Gegenbauer Polynomials

We solve problems concerning the coefficients of functions in the class \(\mathcal {T}(\lambda )\) of typically real functions associated with Gegenbauer polynomials. The main aim is to determine the estimates of two expressions: \(|a_4-a_2 a_3|\) and \(|a_2 a_4 -a_3{}^2|\). The second one is known as the second Hankel determinant. In order to obtain these bounds, we consider the regions of variability of selected pairs of coefficients for functions in \(\mathcal {T}(\lambda )\). Furthermore, we find the upper and the lower bounds of functionals of Fekete–Szegö type. Finally, we present some conclusions for the classes \(\mathcal {T}\) and \(\mathcal {T}(1/2)\).     

On Dirichlet Series with Periodic Coefficients

We investigate Dirichlet series L(s, f) = _n=1 with q-periodic coefficients f(n), i.e. f(n+q) = f(n) for all integers n and some fixed integer q, and we prove an asymptotic formula for the number of nontrivial zeros of L(s, f). Further, we give a necessary condition for L(s, f) to have a distribution of the nontrivial zeros symmetrical with respect to the critical line.     

On an Identity with Binomial Coefficients

Mathematical Notes -