A branch and bound algorithm for allocation problems in which constraint coefficients depend upon decision variables

A branch and bound algorithm is developed for a class of allocation problems in which some constraint coefficients depend on the values of certain of the decision variables. Were it not for these dependencies, the problems could be solved by linear programming. The algorithm is developed in terms of a strategic deployment problem in which it is desired to find a least-cost transportation fleet, subject to constraints on men/materiel requirements in the event of certain hypothesized contingencies. Among the transportation vehicles available for selection are aircraft which exhibit the characteristic that the amount of goods deliverable by an aircraft on a particular route in a given time period (called aircraft productivity and measured in kilotons/aircraft/month) depends on the ratio of type 1 to type 2 aircraft used on that particular route. A model is formulated in which these relationships are first approximated by piecewise linear functions. A branch and bound algorithm for solving the resultant nonlinear problem is then presented; the algorithm solves a sequence of linear programming problems. The algorithm is illustrated by a sample problem and comments concerning its practicality are made.     

A new storage reduction technique for the solution of the group problem

This paper shows that by making use of an unusual property of the decision table associated with the dynamic programming solution to the goup problem, it is possible to dispense with table storage as such, and instead overlay values for both the objective and history functions. Furthermore, this storage reduction is accomplished with no loss in computational efficiency. An algorithm is presented which makes use of this technique and incorporates various additional efficiencies. The reduction in storage achieved for problems from the literature is shown.     

Multiple-attribute decision making with partial information: The expected-value criterion

We consider the multiple-attribute decision problem with finite action set and additive utility function. We suppose that the decision maker cannot specify nonnegative weights for the various attributes which would resolve the problem, but that he/she supplies ordinal information about these weights which can be translated into a set of linear constraints restricting their values. A bounded polytope W of feasible weight vectors is thus determined. Supposing that each element of W has the same chance of being the “appropriate one,” we compute the expected utility value of each action. The computation method uses a combination of numerical integration and Monte Carlo simulation and is equivalent to finding the center of mass of the bounded polytope W . Comparisons are made with another criterion already presented, the comparative hyper-volume criterion, and two small examples are presented.     

A chance-constrained distribution problem

The transportation model with supplies (S_i) and demands (D_i) treated as bounded variables developed by Charnes and Klingman is extended to the case where the S_i and D_i are independently and uniformly distributed random variables. Chance constraints which require that demand at the jth destination will be satisfied with probability at least β_i and that stockout at the ith origin will occur with probability less than α_i are imposed. Conversion of the chance constraints to their linear equivalents results in a transportation problem with one more row and column than the original with some of the new arcs capacitated. The chance-constrained formulation is extended to the transshipment problem.     

Toward a multi-stage information conversion model of the research and development process

Research and development activities in a business firm or government laboratory are portrayed as a multi-stage information generation and conversion process. A “basic research” phase generates opportunities, in the form of findings in a set of scientific disciplines, which are available for subsequent exploitation. It is assumed that increments to information in a subject area are stochastic, proportional to the amount of knowledge which already exists in the area, and have values which are randomly distributed. An “exploratory development” phase is viewed as a process of selecting a subset of alternative research opportunities, improving each opportunity in the direction of its applications, estimating the value of the improved opportunity and using these estimates to choose the exploratory development results to be implemented in engineering development. The “engineering development” phase makes the value of exploratory results realizable without changing value or risk. Engineering development costs are assumed to increase as value increases. If exploratory development is not successful, additional costs in engineering development must be incurred to bring the design up to a minimum desirable level. The model is intended as a step toward formulating and analyzing problems in management planning and control of the several interrelated stages of the research and development process.     

Book reviews

Nuclear Non-Proliferation and Global Order. By Harald Muller, David Fischer, and Wolfgang Kotter. SIPRI, Oxford, Oxford University Press, (1994) ISBN 0-19-329155-8, hardback, £25.00

Conventional Arms Control: Perspectives on Verification By Sergey Koulik and Richard Kokoski, SIPRI, Oxford University Press, (1994) ISBN 0-19-829149-3 and

Implementing the Comprehensive Test Ban: New Aspects of Definition, Organisation and Verification Edited by Eric Arnett, SIPRI Research Report No. 8, Oxford University Press, (1994) ISBN 019-829188-4

Military Technological Innovation and Stability in a Changing World: Politically assessing and Influencing Weapons Innovation and Military Research and Development, By Wim A. Smit, John Grin and Lev Voronkov (eds.) VU University Press, Amsterdam, Netherlands (1992), ISBN 90-5383-158-4.

Security, democracy, and development in US - Latin American relations. By Lars Schoultz, William C. Smith and Augusto Varas (eds.) Transaction Publishers, New Brunswick (USA), and London (UK) (1994). ISBN 1-56000-760-5     

Multiple-attribute decision making with partial information: The comparative hypervolume criterion

A new approach is presented for analyzing multiple-attribute decision problems in which the set of actions is finite and the utility function is additive. The problem can be resolved if the decision makers (or group of decision makers) specifies a set of nonnegative weights for the various attributes or criteria, but we here assume that the decision maker(s) cannot provide a numerical value for each such weight. Ordinal information about these weights is therefore obtained from the decision maker(s), and this information is translated into a set of linear constraints which restrict the values of the weights. These constraints are then used to construct a polytope W of feasible weight vectors, and the subsets H_i (polytopes) of W over which each action a_i has the greatest utility are determined. With the Comparative Hypervolume Criterion we calculate for each action the ratio of the hypervolume of H_i to the hypervolume of W and suggest the choice of an action with the largest such ratio. Justification of this choice criterion is given, and a computational method for accurately approximating the hypervolume ratios is described. A simple example is provided to evaluate the efficiency of a computer code developed to implement the method.     

空间碎片天基主动清除技术发展现状及趋势

随着国内外航天发射任务逐年增多,大量在轨滞留的失效航天器将成为未来空间资源有效利用所面临的一个严峻挑战。空间碎片天基主动清除技术是从根源上对空间资源化利用与安全处置的措施,将提升和加强近地空间的可持续循环利用。本文明晰了空间碎片天基主动清除的概念,分析了空间碎片天基主动清除技术的发展历程,提出了其发展过程中面临的非合作目标相对导航、协调控制和捕获方式及装置等主要问题,为我国空间碎片天基主动清除技术的发展提出了有益参考。