Search

A study was undertaken to classify mechanically a document collection using the free-language words in the titles and abstracts of a corpus of 261 physics research papers. Using a clustering algorithm, results were obtained which closely duplicated the clusters obtained by previous experiments with citations. A brief comparison is made with a traditional manual classification system. It is shown that the mechanical procedure Is capable of achieving simultaneous average relevance and recall figures above 80%. [ABSTRACT FROM AUTHOR]

The article presents comments on the management science paper "On Sequencing n Jobs on One Machine to Minimize the Number of Late Jobs," by William L. Maxwell. The paper focused on an integer programming formulation of a one-machine job shop problem. The author contends that Maxwell made in error in proving the validity of an optimal algorithm by applying cutting plane constraints to the problem. The author explains that the problem cannot be solved through traditional cutting plane procedures. The author provides a mathematical model in an attempt to correct the proof.

The problem of determining continuous flows of minimum cost in a network with convex cost functions is considered. The approach used is that of finding, for any given feasible flow, circuit flows of negative incremental costs. In the main theoretical result of this paper, it is proved that if at each stage, given a feasible nonoptimal flow X, the circuit flow with most negative incremental cost is added to X, linear convergence to the optimal solution will be obtained. In addition, this most negative incremental cost determines an upper bound on the difference in cost between the given feasible solution and the optimal. Based on these concepts, an algorithm, which preserves linear convergence, is presented to determine minimum cost flows in networks with convex costs in the arcs. Results of computer runs made for this algorithm are given. The special case of networks with linear costs is also considered. [ABSTRACT FROM AUTHOR]

The main purpose of this paper is to delineate an algorithm for fractional programming with nonlinear as well as linear terms in the numerator and denominator. The algorithm presented is based on a theorem by Jagannathan [7] concerning the relationship between fractional and parametric programming. This theorem is restated and proved in a somewhat simpler way. Finally, it is shown how the given algorithm can be related to the method of Isbell and Marlow [6] for linear fractional programming and to the quadratic parametric approach by Ritter [10]. The Appendix contains a numerical example. [ABSTRACT FROM AUTHOR]

Commentary is presented for an article published in the July 1960 issue of "Management Science," written by L. V. Kantorovich with an introductory note by T. C. Koopmans. According to the author, in his introduction Koopmans addresses in particular a linear programming problem and a matrix game presented by Kantorovich. Also presented is an interpretation of the article's treatment of decision variables and mathematical optimization. The author notes that the article presents algorithms that have been improved from their contemporary presentations.

This article presents comments on a paper by M.L. Wolfson related to selecting the best lengths to stock. The problem considered in the paper by Wolfson is a classic specimen of the type ideally structured for direct and practical solution by dynamic programming. The author's algorithm, given in the paper, is in the spirit of this method, but its understanding could be greatly simplified if put into the recursive formalism of dynamic programming.

The mean-variance (EV) portfolio selection rule has recently been challenged by a new procedure referred to as the Stochastic Dominance Rule (SD), which is touted as being theoretically and empirically superior. However, the SD procedure suffers from at least one technical deficiency not associated with the EV model--the lack of a search algorithm that builds efficient combinations of assets. The purpose of this paper is to evaluate the significance of this problem and to consider procedures for its alleviation. [ABSTRACT FROM AUTHOR]

This paper studies the linear programming problem in which all coefficients (even those of the stipulations matrix) are rational functions of a single parameter t called ‘time,’ and provides an algorithm that can serve problems of the following two types: (1) Steady-state behavior [the algorithm can be used to determine the functional form x(t) of the optimal solution as a function of t, this form being valid for all ‘sufficiently large’ values of t], and (2) sensitivity analysis [if a value t0 of ‘time’ is given, the algorithm can be used to determine the two possible functional forms of the optimal solution for all values of t ‘sufficiently dose’ to t0 (the first functional form valid for t«t0, the second for t»t0)]. In addition, the paper gives certain qualitative information regarding steady-state behavior, including the following result: If for some one of the properties of consistency, boundedness, or bounded constraint set, there exists a sequence tn↗+∞ such that the linear program at tn has this property for all n, then the program has this property for all ‘sufficiently large’ values of t. [ABSTRACT FROM AUTHOR]

This letter calls attention to the problems of validating the claim made for algorithms in published papers, and proposes a system for review that will validate such claims thoroughly before publication. [ABSTRACT FROM AUTHOR]

This paper examines properties and interrelations of several concepts of generalized concavity. It shows that the class of functions that are both ‘generalized concave’ and ‘generalized convex’ is closely related to the class of monotone functions of a single variable. After excluding a certain small class of exceptions, the paper shows that, for arbitrary (perhaps not differentiable) functions, concave implies pseudoconcave, pseudoconcave implies strictly quasiconcave, and strictly quasiconcave implies quasiconcave. Several results characterizing the extreme values of generalized concave functions are given. [ABSTRACT FROM AUTHOR]

This paper deals with a nonstationary discrete-time Markov process whose transition probabilities vary periodically in time. Each transition results in a reward that varies within the same cycle as the transition matrix. For infinite processes a policy-iteration algorithm is developed that effectively determines an optimal policy maximizing the total discounted reward. The paper represents an extension of R. A. HOWARD's policy-iteration technique for stationary Markov processes. A numerical example is given in which the developed iteration algorithm is demonstrated. [ABSTRACT FROM AUTHOR]

This paper considers the mathematical properties of chance constrained programming problems where the restriction is on the joint probability of a multivariate random event. One model that is considered arises when the right-hand side constants of the linear constraints are random. Another model treated here occurs when the coefficients of the linear programming variables are described by a multinormal distribution. It is shown that under certain restrictions both situations can be viewed as a deterministic nonlinear programming problem. Since most computational methods for solving nonlinear programming models require the constraints be concave, this paper explores whether the resultant problem meets the concavity assumption. For many probability laws of practical importance, the constraint in the first type of model is shown to violate concavity. However, a simple logarithmic transformation does produce a concave restriction for an important class of problems. The paper also surveys the `generalized linear programming' method for solving such problems when the logarithmic transformation is justified. For the second type model, the constraint is demonstrated to be nonconcave. [ABSTRACT FROM AUTHOR]

The multi-index transportation problem is defined and a summary of the algorithm described in an earlier paper is given. This paper discusses the theorems justifying the use of the algorithm and gives a necessary condition for the existence of a solution. It also describes the formulation of three special-structure linear-programming problems as examples of multi-index problems. The three problems discussed are the capacitated Hitchcock problem, transportation where there is more than one method of transport available, and the transformation of one type of multi-index problem into another. A final section describes problems that have restrictions in the form of inequalities. [ABSTRACT FROM AUTHOR]

This paper considers a test score model in which the true score and the measurement error are autocorrelated. After some preliminary remarks on corrections for attenuation, the paper focuses on the three-wave ease (t = 1, 2, 3), demonstrating identifiability, showing an estimation algorithm, and providing a numerical illustration. [ABSTRACT FROM AUTHOR]

In this paper we discuss the relevancy of the geometric mean as a portfolio selection criteria. A procedure for finding that portfolio with the highest geometric mean when returns on portfolios are lognormally distributed is presented. The development of this algorithm involves a proof that the portfolio with maximum geometric mean lies on the efficient frontier in arithmetic mean variance space. This finding has major implications for the relevancy of much of portfolio and general equilibrium theory. These implications are explored. [ABSTRACT FROM AUTHOR]

This paper presents the application of a modified mixed-integer programming algorithm to plan menus in which the portion size of the menu items can vary over a specified positive range. Previous mathematical programming formulations of menu planning problems have either required the variables representing menu items to be bivalent, or have formulated the problem with food groups as decision variables and no integer requirements at all. The former gives rise to a zero-one programming problem and the latter to a "feed-mix" problem. In many instances, a more realistic formulation would require that if a menu item is offered, its portion size must be between a specified upper and lower bound. Although this paper addresses itself chiefly to menu planning, it is readily seen that problems in capital budgeting may be tractable with a similar formulation. It is shown how a branch-and-bound algorithm for mixed-integer programming of the type proposed by Beale and Tomlin can be modified to solve the quasi-integer programming problem resulting from a variable portion size formulation of menu planning problems. [ABSTRACT FROM AUTHOR]

This paper presents a systematic procedure for obtaining the optimum packaging frequencies for a number of items which are manufactured jointly but packaged individually immediately after manufacture. The method described in the paper is equally applicable to those problems where the optimum purchasing policy is to be obtained for a number of items procured from a single supplier. An example involving twenty jointly replenished items is solved to illustrate the procedure given in the paper. [ABSTRACT FROM AUTHOR]

This paper investigates the optimal allocation of the marketing budget within the marketing-mix decision variables so that sales (or profit) is maximized in a planning horizon. Since the influence of marketing mix variables upon sales are, in reality, nonlinear and interactive, a geometric programming algorithm is used that solves this problem. A procedure to estimate a functional of sales on the marketing mix and environmental variables utilizing the experienced judgments of the firm's executives and the raw data is provided. The derived functional is later optimized by the Geometric Programming algorithm under a constraint set consisting of budget and strategy restrictions imposed by a firm's marketing environment, and conditions under which the optimal solution is either local or global are identified. An empirical application for a large midwestern brewery is provided which utilizes and illustrates both the estimation an optimization procedures. [ABSTRACT FROM AUTHOR]

This paper deals with planning production of a single good over a prescribed finite interval of time [0, T]. The costs considered within the problem are production and holding costs; holding costs are incurred for negative inventory (caused by backlogged sales) and positive inventory (caused by production in excess of demand). The demand for the product is treated as a stochastic process. Problem formulation and optimization use tools from continuous-time stochastic variational calculus and control theory. Among its results, the paper proves the uniqueness of the optimal solution and provides an algorithm for the problem. [ABSTRACT FROM AUTHOR]

This paper deals with systems (such as electronic devices and corporations) that are designed to accomplish multiple goals and whose internal structures are characterized by networks of interacting component parts. Each component of such a system is typically associated with a probability of failure, while each system goal is associated with a reward value. Failure of any network component may ultimately result in the inability to achieve one or more goals and force the forfeiture of the associated rewards. A basic problem in component-system design is to determine how the expectation of total reward may be maximized through the cost-limited acquisition of redundant (backup) components. This paper provides a formal statement of this redundancy-optimization problem and argues that the problem may not be solved easily by standard linear or integer programming techniques. It introduces an algorithm to solve this problem, proves its convergence, and presents computational results taken from a battery of test problems and an algorithm-efficiency study based on these tests. [ABSTRACT FROM AUTHOR]

This paper treats the optimal location of nuclear-power plants in the Pacific Northwest with respect to capital-construction, operating, and transmission costs. It presents a mathematical formulation of this two-product (peak and energy power) plant-location problem, using the simplex method in conjunction with a branch-and-bound process, and indicates a check procedure using Vogel's approximation method in conjunction with an algorithm for solving the transportation problem and a branch-and-bound process. The paper gives results for demand-growth rates of 4, 5, 6 and 7 percent and alternative designs and their costs. It also discusses the stability of the optimal solution. [ABSTRACT FROM AUTHOR]

This paper develops a new cutting plane for primal integer programming. This cut, when it exists and is used as pivot row, has the property that the minimum of the simplex evaluators of the next tableau is strictly larger (by an integer) than the minimum for the current tableau. The paper gives a sufficient condition in the form of a linear program for the existence of such a cut, and proposes an algorithm for generating such cuts. It also presents two additional sufficient conditions. The process of cut generation is then imbedded into a convergent primal algorithm to be used in an attempt to overcome the proof-of-optimality problem experienced with the primal algorithm. [ABSTRACT FROM AUTHOR]

This paper presents a formal model of the one-machine job-shop scheduling problem with variable capacity. Its primary interest focuses on the trade-off between overtime and detailed scheduling costs. The scheduling problem considered is minimizing the sum of weighted tardiness and weighted flow-time costs for a given capacity plan (i.e., a given overtime plan). The paper generalizes sequence-theory results to this case where possible, analyzes various lower-bounding structures for the problem, outlines a preliminary branch-and-bound algorithm, and illustrates several interesting features of the algorithm and bounding structures by an example. Extensions of the results to more complex environments are discussed. [ABSTRACT FROM AUTHOR]

This paper addresses a fundamental short-run resource-allocation problem confronting retail distribution: simultaneously finding the specific brands, from many, that should be displayed, and the amount of retail product-display area that should be assigned to these brands, in order to maximize the retail institution's profit. The paper decomposes total market demand according to the various levels of brand preference that could conceivably exist in final markets, and then, employs an algorithm, similar to the one used to solve the fixed-charge problem, to find the optimal brand mix and display-area allocation. [ABSTRACT FROM AUTHOR]

This paper formulates the optimal control problem for a class of mathematical models in which the system to be controlled is characterized by a finite-state discrete-time Markov process. The states of this internal process are not directly observable by the controller; rather, he has available a set of observable outputs that are only probabilistically related to the internal state of the system. The formulation is illustrated by a simple machine-maintenance example, and other specific application areas are also discussed. The paper demonstrates that, if there are only a finite number of control intervals remaining, then the optimal payoff function is a piecewise-linear, convex function of the current state probabilities of the internal Markov process. In addition, an algorithm for utilizing this property to calculate the optimal control policy and payoff function for any finite horizon is outlined. These results are illustrated by a numerical example for the machine-maintenance problem. [ABSTRACT FROM AUTHOR]