Search

This paper introduces a generalization of the frequently discussed problem of finding the optimum redundancy that maximizes the reliability of a network of components. Past work has restricted consideration to arrangements of redundant components called series-parallel networks. This paper allows a much broader class of arrangements called series-parallelseries networks. It is important to consider such arrangements for realistic situations in which components have more than one failure mode, or the combination of parallel paths introduces a failure probability. A dynamic programming algorithm is used to solve the more general problem for the case in which there are no constraints on the optimum solution. The algorithm is extended to handle multiple constraints using dominance and a variety of elimination methods to reduce the storage required in a compurer implementation of the algorithm. Problems with as many as 15 serial components and three constraints have been solved with reasonable digital computer computation times. [ABSTRACT FROM AUTHOR]

This paper gives general conditions for the convergence of a class of cutting-plane algorithms without requiring that the constraint sets for the subproblems be sequentially nested. Conditions are given under which inactive constraints may be dropped after each subproblem. Procedures for generating cutting-planes include those of KELLEY, CHENEY AND GOLDSTEIN, and a generalization of the one used by both ZOUTENDIJK and VEXNoTT. For algorithms with nested constraint sets, these conditions reduce to a special case of those of ZANGWILL for such problems and include as special cases the algorithms of Kelley, Cheney and Goldstein, and Veinott. Finally, the paper gives an arithmetic convergence rate. [ABSTRACT FROM AUTHOR]

This paper treats the problem of project (or machine) scheduling with resource constraints to achieve minimum total duration time as a disjunctive graph. The prospective advantage of this approach is the elimination of the need to consider individual time periods over the program horizon; a feasibility check determines whether the resource constraints can be met by any particular network representation of the project. The paper gives an algorithm that uses partial enumeration for what is essentially a mixed integer program. The algorithm employs a maximum-flow computation as a check for feasibility with respect to available resources. [ABSTRACT FROM AUTHOR]

A mathematical programming problem P: minimize z=d[supT]x+e[supT]u+f[supT]v subject to Ax+Bu+Cv≥g, x, u, v≥0, u[supT]v=0, is called a complementary programming (CP) problem. The condition u[supT]v=0 distinguishes CP problems from ordinary LP problems. A variety of nonlinear programming problems can be formulated in this form, including absolute-value programming problems, 0-1 mixed-integer-programming problems, quadratic-programming problems, and so forth. This paper proposes a branch-and-bound algorithm for CP problems and reports some computational results. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to present an algorithm for solving the quadratic binary programming problem. Although a problem with this structure may arise in many situations, it is particularly common in capital budgeting when a decision-maker is confronted with a set of investment proposals from which he must select a portfolio. If returns of proposals are intercorrelated random variables and if the decision-maker uses as his criterion for selection the mean μ and variance σ[sups] of portfolio returns, his decision requires prior identification of the (μ, σ²) efficient set. The algorithm developed to solve the problem and hence necessary to generate the efficient set is based on the concept of implicit enumeration recently introduced by EGON BALAS for solution of the binary linear programming problem. [ABSTRACT FROM AUTHOR]

Randomly-generated linear programming problems of three different types and five different sizes were solved by the criss-cross method and by the simplex method. One hundred problems of each type and size were solved, and the results are overwhelmingly favorable to the criss-cross method. An improvement to the criss-cross method used in these tests is given, and the extension of the results of the paper to variations of the criss-cross and simplex methods is discussed. [ABSTRACT FROM AUTHOR]

This paper describes an algorithm for the solution of mathematical programming problems having a linear objective function and non-linear constraints. The algorithm is basically an adaptation of the simplex method to the case of non-linear constraints. Certain complications are, however, introduced through non-linearity in the constraints, and it is shown how these can be overcome. [ABSTRACT FROM AUTHOR]

Copyright of INFOR is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Copyright of INFOR is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

The purpose of this paper is to describe a new gradient method for maximizing general functions. After a brief discussion of various known gradient methods the mathematical foundation is laid for the new algorithm which rests on maximizing a quadratic approximation to the function on a suitably chosen spherical region. The method requires no assumptions about the concavity of the function to be maximized and automatically modifies the step size in the light of the success of the quadratic approximation to the function. The paper further discusses some practical problems of implementing the algorithm and presents recent computational experience with it. [ABSTRACT FROM AUTHOR]

This paper presents mathematical evaluation measures to characterize the effect of known erroneous performance by stemming routines, and generalizes these procedures to other types of nonstatistical clustering algorithms. When clusters, or groups of intrinsically related elements, are split into smaller groups (by under-matching the elements), there is a loss in recall in information retrieval; larger groups (caused by over- matching) induce a loss in precision or relevance. The magnitude of error is taken to be a function of frequencies of cluster elements. When these ore words in a subject-term index generated by a stemming algorithm, retrieval capability is also affected by the strength of the algorithm, the size and content of the stemmed index, and the number of words in a query. The present Project Intrex stemming algorithm has estimated stemming-error losses of 4% in recall and 1% in relevance on one-word queries; the former could be reduced to almost zero by straightforward corrections of known errors in the algorithm. An expanded probabilistic model is introduced to handle a more general case in which any element need not belong unambiguously to a single cluster. Error evaluation in document classification and thesauri also is discussed in broad terms. [ABSTRACT FROM AUTHOR]

Geometric programming is a mathematical programming technique that is designed to determine the constrained minimum value of a generalized polynomial objective function. To date, most applications of the technique have been restricted to certain classes of engineering problems. This paper presents a brief summary of geometric programming and then illustrates its application to managerial problems by applying it to three well-known inventory models. [ABSTRACT FROM AUTHOR]

A new cluster-analysis method, the bond energy algorithm, has been developed recently; it operates upon a raw input object-object or object-attribute data array by permuting its rows and columns in order to find informative variable groups and their interrelations. This paper describes the algorithm and illustrates by several examples its use for both problem decomposition and data reorganization. [ABSTRACT FROM AUTHOR]

The DANTZIG-WOLFE decomposition procedure for concave programs can be viewed as inner linearization followed by restriction. This paper presents an approach that allows selective inner linearization of functions and utilizes a generalized pricing problem. It allows considerable flexibility in the choice of functions to be approximated using inner linearization. Use of the generalized pricing problem guarantees that strict improvement in the value of the objective function is achieved at each iteration and provides a termination criterion that is both necessary and sufficient for optimality. A specialization of this procedure results in an algorithm that is a direct extension of the Dantzig-Wolfe decomposition algorithm. [ABSTRACT FROM AUTHOR]

The P-model objective of chance-constrained programming reflects the desire of management to maximize the probability of achieving or exceeding a given level of performance. This paper explores the implications of being able to make a sequence of decisions with the P-model objective function, and introduces some new possibilities for the P-model objective function that arise from the sequential nature of the problem. However, it is shown that, except for a special form of the objective function, the maximization in the sequential problem is not of a quasiconcave function, so that local optimality conditions are not sufficient to guarantee that a proposed solution is a global optimum. An example is worked out in detail to illustrate the computations involved for the objectives considered. [ABSTRACT FROM AUTHOR]

This paper presents two algorithms for targeting strikes in a lines-of-communication (LOC) network. The LOCs are represented by a network of nodes and directed arcs. It is assumed that the user of the LOCs is attempting to achieve a circulation flow at minimum cost, a very general goal that includes, as special cases, maximizing flow between two points, meeting required flows between two points at minimum cost, and combinations of these two. The algorithms presented here attempt to make such costs as large as possible over time when the effect of targeting strikes is to increase arc-cost functions and decrease arc capacities for a given period of time. The first algorithm treats the situation where arc costs are linear functions of flow; the second treats the situation where arc costs are piecewise linear functions of flow with one break point. [ABSTRACT FROM AUTHOR]

This paper presents computational algorithms for the solution of a clam of stochastic programming problems. Let z and y represent the decision and state vectors, and suppose that x must be chosen from some set K and that p is a linear function of both x and an additive random vector ξ. If y is uniquely determined once z is chosen and ξ is observed, we say that the problem has simple recourse. The algorithms presented apply, e.g., when the preference functions h(x) and g(y) are convex, and continuously differentiable, K is a convex polytope, ξ has a distribution that satisfies mild convergence conditions, and the objective is to minimize the expectation of the sum of the two preference functions. An illustrative example of an inventory problem is formulated, and the special ease when p is asymmetric, quadratic, and separable is presented in detail to illustrate the calculations involved. [ABSTRACT FROM AUTHOR]

This paper extends the algorithm developed by Hartley and Wortham [2] for the calculation of the c.d.f. of the critical time in a PERT network. Additional first order crossed networks and their operators are given. In addition, a technique for developing an integral operator for any PERT network is presented. [ABSTRACT FROM AUTHOR]

Multi-level fixed-charge problems are mathematical optimization problems in which the separable portion of the objective function is the sum of piecewise continuous functions of a single variable. This paper describes a branch-and-bound algorithm that will find a global solution to this type of problem. The algorithm has the feature that a good feasible solution is generated at the start. Moreover, at each step of the algorithm an additional feasible solution may be generated for comparison with the best solution found previously. [ABSTRACT FROM AUTHOR]

This article focuses on the journal "Mathematical Systems Theory." "Mathematical Systems Theory" is a new quarterly journal that began publication in 1967. The journal will feature articles in such fields as topological dynamics, theory of dynamical polysystems, general systems theory, formal systems theory, mathematical theory of automata and algorithms, mathematical linguistics, algebraic systems theory, ergodic theory, several aspects of the qualitative theory of differential equations and the like. In addition, articles in functional analysis, topology, algebra and logic directly related to the theory of mathematical systems will be published. From time to time, the journal will contain expository papers or survey articles in the fields mentioned above, as well as in related fields. By publishing under a single cover contributions in these general areas presently appearing in diverse publications, it is hoped that a means may be provided for improved communication, perhaps ultimately leading to a unification of certain concepts and terminology and to the emergence of a more coherent field dealing with the mathematical problems encountered in various branches of systems theory.

This note points out an example in which an algorithm reported by P. M. GHASS AND R. E. TAYLOR [Opns. Res. 17, 838–847 (1969)] for determining optimum redundancy in a series system does not produce an optimal solution. It presents the Ghare-Taylor solution along with a better feasible solution, and explains the necessary corrections to the Ghare-Taylor algorithm and the cause of the difficulty with it. The note thus questions the validity of the computer times reported by Ghare and Taylor and indicates a source yielding computer times for the corrected algorithm. [ABSTRACT FROM AUTHOR]

In many cases Bayes' theorem is an appropriate algorithm for the aggregation of probabilistic evidence. As with other statistical procedures, there are restrictions that must be taken into account. In the present paper we shall comment on several approaches that have been devoted to one of these restrictions; the incorporation of uncertainty about the true state of a datum. A datum is a variable which can be partitioned into equivalence classes. These classes represent the possible data states which will be also called events. In Bayes' theorem an event is an item of information which will be used for revising the opinion about the relative likelihood of hypotheses. In any specific situation only one of the possible events will be the true event. An event may come from a source whose reporting or observational accuracy is not perfect. An example may illustrate the issue. A medical doctor wants to come to a diagnosis. To achieve this he considers several data. One datum might be the result of a medical test, which has three possible states: positive, negative, inconclusive. If the doctor reports the state of the datum to be positive, he may be wrong by whatever reasons. That is, the report of an event must not necessarily coincide with the actual or true event of the datum under consideration. This kind of uncertainty about the true event in any specific situation is a characteristic of the source. In most cases it will reduce the diagnostic impact of an event. Whenever the report of an event and the true event coincide imperfectly, measures of source inaccuracy must be incorporated into Bayes' theorem. The task can be considered as two stage probabilistic induction. The first step is induction from the reported to the actual event, the second is induction from the actual event to the creditation of hypotheses. This is the reason why Gettys and Willke (1969) speak about "cascaded inference." [ABSTRACT FROM AUTHOR]

This paper discusses the application of Bayes's theorem to those cases where the true state of the world is not known with certainty. An algorithm is proposed that relaxes the requirement of Bayes's theorem that the true data state be known with certainty by postulating a true but unobservable elementary event, ω, which gives rise to posterior probabilities which reflect the uncertainty of the data. A derivation is presented for the calculation of Bayesian posterior probabilities which uses as its input these probabilities, rather than the true event, o, which is assumed to be unavailable. Suggestions are made as to the application of this modification of Bayes's theorem to cascaded inference processes. [ABSTRACT FROM AUTHOR]

A production and transportation system is considered in which the produced items successively are transported to n different selling places. Transportation to the N places may be ordered in NI different ways and the effects on the system of different orderings among the selling places when servicing them are studied. If the production capacity is K units per unit of time, and if the N places have associated with them times of transport t1,⋯tN and functions fl,⋯,fN expressing the demand as depending on the time of arrival, it is possible to obtain the total sale on the form KgN,{gN-1[A⋯g1(0)⋯]} where the functions gn are defined in terms of K, tn, and fn. Thus the problem to determine the order to serve that maximizes the total sale is reduced to the problem of finding the optimal permutation of gN {gN-1[ ⋯g1(0⋯). When deriving criterions of optimality for the total sale and related measures of effectiveness the following principle is used: Let E(1,⋯, N) be the effectiveness associated with the ordering 1,⋯, N and let kn. be some characteristic of place n. If k1≦⋯≦kn is sufficient (necessary) for E(l,⋯,N)≧E(l,⋯, n-1 , n+l, n, n+2,⋯N) for n=1⋯, N-1 then this condition is also sufficient (necessary) for E(1,⋯,N)≧E (i1, iN) for every permutation i1,⋯ of 1⋯,N. [ABSTRACT FROM AUTHOR]

The article comments on the paper "Syminv: An Algorithm for the Inversion of a Positive Definite Matrix by the Cholesky Decomposition," by Terry Seaks, published in volume 40 of "Econometrica." In his article Seaks describes an algorithm for the Cholesky decomposition of a positive symmetric matrix, citing J.H. Wilkinson's work. The author explains that the relevant conclusions in Wilkinson's paper are those for floating point calculation and that the numerical advantage of the Cholesky procedure depends on being able to accumulate inner products accurately.

This note considers the question of why some convex quadratic programming algorithms fail and others succeed when applied to nonconvex quasiconvex quadratic programs. Several algorithms are identified as being capable of solving quasiconvex quadratic programs using only a finite number of arithmetic and logical operations. These algorithms are all primal feasible, pivot algorithms. [ABSTRACT FROM AUTHOR]

A summary of the important variations on the simplex method is presented, with an emphasis placed on the connection between these techniques, the revised simplex method, and the dual theorem. Only elementary matrix algebra is employed to enable the nonmathematician to utilize the various algorithms. Specifically, the dual simplex algorithm, parametric programming, and techniques for additional and secondary constraints, and for upper bounded variables are discussed. [ABSTRACT FROM AUTHOR]

Allocating funds to independent R&D projects is a problem of practical importance for many firms. We formulate the problem as a 0-1 integer programming problem with the objective of selecting projects that will maximize the anticipated dollar contract volume, yet not exceed cost budgets. Our formulation accommodates R&D projects extending over several budget periods and permits carryover of unspent funds from one budget period to later periods. Experience in solving such problems by using the Balas [1] algorithm in its literal form and in reformulated form is summarized. Several other modifications to the algorithm are described and their effect on efficiency is shown through presentation of computational experience on problems with as many as 50 variables. [ABSTRACT FROM AUTHOR]

The article reports on the computational solution of linear programming equations involving almost-block-diagonal matrices. The author focuses on dynamic programming methods that can be used to solve weakly coupled and multi-stage economic systems. He suggests that most economic and industrial problems can be reduced to the problem of maximizing the linear form. It is suggested that finding the mathematical solutions to multi-dimensional problems is important because of the wide range of values of the solution's parameters. Dantzig's simplex algorithm enables programming problems of this type to be solved using digital computers.