Search

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 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 gives a detailed description of an algorithm for the solution of a specialized Linear Programming model, to be called the Machine Loading model. It is a generalization of the Transportation Problem, in that weighting factors are applied to the individual elements which form the row and column sums. For the Machine Loading model, the simplex method reduces to a specialized algorithm which generalizes the stepping stone method of the Transportation Problem [2], [3]. With the resulting generalized stepping stone method, it becomes practicable to solve many large-scale problems for which the direct application of the simplex method would be impracticable. The present paper is restricted to a discussion of the following topics: (I) the general characteristics of the model and its topological features; (ii) a detailed solution algorithm, including a consideration of degenerate cases and the use of a computer; (iii) a more restrictive capacitated model and the corresponding modifications to the solution algorithm; and (iv) the complete illustrative solution of a numerical example. The purpose is to aid interested readers in gaining familiarity with the algorithm and facility in the solution of numerical problems. No derivations or proofs will be included. [ABSTRACT FROM AUTHOR]

The linear programing algorithms available for optimizing the routing of shipments in multi-plant, multi-destination systems cannot, in the current state of knowledge, be applied directly to the more general problem of determining the number and location of regional warehouses in large-scale distribution networks. This paper outlines a heuristic computer program for locating warehouses and compares it with recently published efforts at solving the problem either by means of simulation or as a variant of linear programing. The heuristic approach outlined in this paper appears to offer significant advantages in the solution of this class of problems in that it (1) provides considerable flexibility in the specification (modeling) of the problem to be solved, (2) can be used to study large-scale problems, that is, complexes with several hundred potential warehouse sites and several thousand shipment destinations, and (3) is economical of computer time. The results obtained in applying the program to small scale problems have been equal to or better than those provided by the alternative methods considered. [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.

This paper considers fluid analogues for the standard linear programming problem and for a separable nonlinear programming problem. In the former case the usual duality results are demonstrated using the principle of minimum potential energy. In addition by examining the dynamics of the system a new method, referred to as the R-method, is derived for solving linear programmes, although it is not demonstrated that this has any computational advantages over the standard simplex method, except that degeneracy causes no problems. In the nonlinear case the weak Lagrangian principle is derived. The purpose of the paper is to demonstrate that analogue methods, while being impracticable as a physical method of solving optimisation problems, may give some insight into computational algorithms via dual energy concepts and/or dynamic behaviour. [ABSTRACT FROM AUTHOR]

The paper considers a class of optimization problems. The problems are linear programming problems: maximize ex subject to Ax = b with the additional constraint that x must also be an extreme point of a second convex polyhedron Dx = d. X ≥ 0. A cutting-plane algorithm for solving such problems is presented. Two numerical examples are also included. [ABSTRACT FROM AUTHOR]

A framework of concepts is developed which helps to unify a substantial portion of the literature on large-scale mathematical programming. These concepts fall into two categories. The first category consists of problem manipulations that can be used to derive what are often referred to as "master" problems; the principal manipulations discussed are Projection, Inner Linearization, and Outer Linearization. The second category consists of solution strategies that can be used to solve the master problems, often with the result that "subproblems" arise which can then be solved by specialized algorithms. The Piecewise, Restriction, and Relaxation strategies are the principal ones discussed. Numerous algorithms found in the literature are classified according to the manipulation/strategy pattern they can be viewed as using, and the usefulness of the framework is demonstrated by using it (see Part II of this paper) to rederive a representative selection of algorithms. The material presented is listed in the following order: The first section is introductory in nature, and discusses types of large-scale problems, the scope of discussion and the literature, and the notation used. The second section, entitled "Problem Manipulation: Source of 'Master' Problems" covers the subjects of projection, inner linearization and outer linearization. The third section, "Solution Strategies: Source of 'Subproblems'," discusses piecewise strategy, restriction and relaxation. The fourth section is entitled "Synthesizing Known Algorithms from Manipulations and Strategies," and is followed by a concluding section and an extensive bibliography. [ABSTRACT FROM AUTHOR]

The article presents an algorithm for solving a linear integer programming problem and describes the theoretical foundations for a new approach to integer programming. According to the authors, the approach may be described as an extension of the methods using enumeration, but by using a new, more powerful approach based on population statistics. The optimal solution to the integer programming problem in this paper is viewed as one of selecting the optimal function among a certain class of functions which map elements of one set into another. With this method in mind, the authors intend to view the different problems by characterizing the statistical structure of the associated finite class of maps.

The usefulness of integer programming as a tool of capital budgeting hinges on the development of an efficient solution technique. An algorithm based on partial enumeration has been developed by E. L. Lawler and M. D. Bell for solving integer linear programs with 0-1 decision variables; however their algorithm is not general enough to deal with all problems in which the objective function is quadratic. This paper extends Lawler and Bell's method so that it can be generally applied to integer quadratic programs. The new algorithm is illustrated by examples from capital budgeting. [ABSTRACT FROM AUTHOR]

The literature is replete with analyses of minimum cost flows in networks for which the cost of shipping from node to node is a linear function. However, the linear cost assumption is often not realistic. Situations in which there is a set-up charge, discounting, or efficiencies of scale give rise to concave functions. Although concave functions can be minimized by an exhaustive search of all the extreme points of the convex feasible region, such an approach is impractical for all but the simplest of problems. In this paper some theorems are developed which explicitly characterize the extreme points for certain single commodity networks. By exploiting this characterization algorithms are developed that determine the minimum concave cost solution for networks with a single source and a single destination, for acyclic single source multiple destination networks, and for acyclic single destination multiple source networks. An interesting theorem then establishes that for either single source or single destination networks the multi-commodity case can be reduced to the single commodity case. [ABSTRACT FROM AUTHOR]

This paper demonstrates the equivalence of several published algorithms for solving the so-called linear fractional programming problem. [ABSTRACT FROM AUTHOR]

This paper attempts to present the major methods, successful or interesting uses, and computational experience relating to integer or discrete programming problems. Included are descriptions of general algorithms for solving linear programs in integers, as well as some special purpose algorithms for use on highly structured problems. This reflects a belief, on the author's part, that various clever methods of enumeration and other specialized approaches are the most efficacious means existent by which to obtain solutions to practical problems. A serious try at gathering computational experience has been made—but facts are difficult to uncover. The paper is written with intent to enable readers to read selected sections without having to read the whole. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for the solution of dynamic programming problems requiring the determination of optimal policies for the control of a special class of stochastic processes when the time horizon of the planning period is at infinity. These processes can be mathematically described as discrete time parameter Markov chains with a finite number of states which have been "embedded" in continuous time in the sense that the time between transitions is a random variable whose probability distribution depends only on the states between which the transition takes place. Such processes are called Markov-renewal processes. The Markov processes considered by R. A. Howard in [1] are really two special cases of this somewhat wider class of stochastic processes. In these two special cases, the algorithm of this paper is identical with Howard's. In fact, with only slight modification, Howard's algorithm can be extended to this wider class of stochastic processes. [ABSTRACT FROM AUTHOR]

For a project that consists of numerous jobs subject to technological ordering restrictions the polygon representing project cost versus completion time is to be determined when the normal and crash completion times are known for each job and the cost of doing the job varies linearly between these times. A linear programming formulation of this problem was given by Keliey [1] and a network flow formulation by Fulkerson [2]. Since the traditional mathematical background of civil engineers includes neither linear programming nor network flow theory, these methods are not as widely used in the building industry as they deserve. This paper shows that Fulkerson's algorithm can be given a structural interpretation using concepts that are familiar to civil engineers. [ABSTRACT FROM AUTHOR]

The well known chemical equilibrium problem is expressed in the form of minimizing the free energy of a mixture in order to compute the chemical composition at equilibrium. By piece-wise linear approximations to the free energy function, the problem becomes a linear program which can be solved by a standard code on a computing machine. Successive approximations give any degree of accuracy. [ABSTRACT FROM AUTHOR]

In this paper, it is shown that the "caterer" problem, a problem in mathematical economics and logistics which has been discussed by Jacobs, Gaddum, Hoffman and Sokolowsky, and Prager, can be reduced to the problem of determining the maximum of the linear form Ln = ∑I=1nv1, subject to a series of constraints of the form V1 ≦ b1, v1 +v2 ≦ b2, v1 + v2 +v3 ≦ b2, ߪ, v1 + v2 + … + vK ≦ bK, v2 + v3 + … + vK+1 ≦ bK+1, …, vb-h+1 + … + Vn ≦ bn, 0 ≦ rI, I = 1, 2, … , n, under an assumption concerning the nonaccumulation of dirty laundry. This maximization problem is solved explicitly, using the functional equation technique of dynamic programming. [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]

In their paper [1], Doulliez and Rao present algorithms that solve two flow problems for a single source, multi-terminal network. The first problem that they solve is the construction of a flow that maximizes the value of t, where the demand at each sink is a nondecreasing, linear function of t. Given such a flow, the second problem that they solve is the construction of a flow that maximizes the value of t when the capacity of an arc is reduced. This paper supplies a finiteness proof for the first algorithm and sketches a finiteness proof for the second algorithm. The proofs are based on the well-known fact that a network possesses only a finite number of different spanning trees. [ABSTRACT FROM AUTHOR]

This paper presents an in-depth computational comparison of the basic solution algorithms for solving transportation problems. The comparison is performed using "state of the art" computer codes for the dual simplex transportation method, the out-of-kilter method, and the primal simplex transportation method (often referred to as the Row-Column Sum Method or M O D I method). In addition, these codes are compared against a state of the art large scale LP code, O P H E L I E/LP. The study discloses that the most efficient solution procedure arises by coupling a primal transportation algorithm (embodying recently developed methods for accelerating the determination of basis trees and dual evaluators) with a version of the Row Minimum start rule and a "modified row first negative evaluator" rule. The resulting method has been found to be at least 100 times faster than OPHELIE, and 9 times faster than a streamlined version of the SHARE out-of-kilter code. The method's median solution time for solving 1000 X 1000 transportation problems on a CDC 6600 computer is 17 seconds with a range of 14 to 22 seconds. Some of the unique characteristics of this study are (1) all of the fundamental solution techniques are tested on the same machine and the same problems, (2) a broad spectrum of problem sizes are examined, varying from 10 X 10 to 1000 X 1000; (3) a broad profile of nondense problems are examined ranging from 100 percent to 1 percent dense; and (4) additional tests using the best of the codes have been made on three other machines (IBM 360/65, UNIVAC 1108, and CDC 6400), providing surprising insights into conclusions based on comparing times on different machines and compilers. [ABSTRACT FROM AUTHOR]

A multi-stage linear program is defined with linking variables that connect consecutive stages. Optimality conditions for the composite problem are partitioned into local and linking conditions. When the Dantzig-Wolfe decomposition scheme is applied with the first stage as the master, the subproblem is also a MLP with one less stage. The same decomposition is then applied to the subproblem, giving rise to a nested decomposition scheme, in which each stage acts as a master for the following stage and a subproblem for the preceding. Optimizing a single stage problem results in satisfying the "local" optimality conditions. A very general rule is given for selecting the next subproblem to optimize, and finite convergence to a solution satisfying all linking conditions is demonstrated. Procedures for extracting the optimal primal solution at the end of the main algorithm and for initialization are given. Particular rules for selecting the next subproblem and for generating additional proposal vectors are discussed. Finally, it is shown how a variety of problems may be restructured as multi-stage linear programs to which this algorithm may be applied, and some computational experience is reported. [ABSTRACT FROM AUTHOR]

The multiparametric linear programming (MLP) problem for the right-hand sides (RHS) is to maximize z = cT x subject to Ax = b (λ), x ≧ 0, where b(λ) can be expressed in the form b(λ) = b* + Fλ, where F is a matrix of constant coefficients, and λ is a vector-parameter. The multiparametric linear programming (MLP) problem for the prices or objective function coefficients (OFC) is to maximize z = cT (v)x subject to Ax = b, where x ≧ 0, where c(v) can be expressed in the form c(v) = c* + Hv, and where H is a matrix of constant coefficients, and v a vector-parameter. Let Bi be an optimal basis to the MLP-RHS problem and Ri be a region assigned to Bi such that for all λ Ri the basis, Bi is optimal. Let K denote a region such that K = ui Ri , provided that the Ri for various i do not overlap. The purpose of this paper is to present an effective method for finding all regions Ri that cover K and do not overlap. This method uses an algorithm that finds all nodes of a finite connected graph. An analogous method is presented for the MLP-OFC problem. [ABSTRACT FROM AUTHOR]

This paper gives efficient methods for solving four specially structured network problems that arise in connection with certain integer programming methods developed by Cook and Cooper, Hillier, and Glover. Such problems have also independently been studied in inventory theory by Ignall and Veinott, who have developed extensive qualitative (nonalgorithmic) implications of their structures. In the integer programming context, special subclasses of these network problems are generated and solved as part of a strategy for solving more general integer linear programs. By providing particularly efficient methods for accommodating somewhat broader network structures, our results enable the development of related integer programming solution strategies that generate more complex subproblems. We show that the first of the four network problems can be solved by a procedure that assigns each variable a value exactly once, without subsequent revision. Properties of optimal solutions for the remaining problems are developed that enable the algorithm for the first to be extended to the second and then, by suitable transformation of variables, to the third and last problems as well. Moreover, while the last three problems involve an additional linear constraint that nullifies the "integer extreme point property", we show that optimal integer solutions to these problems can nevertheless easily be obtained from the optimal continuous solutions. [ABSTRACT FROM AUTHOR]

If the constraint matrix of a linear program has special structure it may be possible to speed computation. Techniques have been developed to take advantages of such special structures as generalized networks, generalized upper bounding, and decomposition. For these matrix structures, it is shown in this paper how to extend the techniques to Zangwill's mathematical programming algorithm, the convex simplex method. [ABSTRACT FROM AUTHOR]

Conditions which are necessary and sufficient for convergence of a nonlinear programming algorithm are stated. It is also shown that the convergence conditions can be easily applied to most programming algorithms. As examples, algorithms by Arrow, Hurwicz and Uzawa; Cauchy; Frank and Wolfe; and Newton-Raphson are proven to converge by direct application of the convergence conditions. Also the Topkis-Veinott convergence conditions for feasible direction algorithms are shown to be a special case of the conditions stated in this paper. [ABSTRACT FROM AUTHOR]

The general linear programming problem is considered in which the coefficients of the objective function to be maximized are assumed to be random variables with a known multinormal distribution. Three deterministic reformulations involve, respectively, maximizing the expected value, the α,-fractile (α fixed, 0 < α < ½), and the probability of exceeding a predetermined level κ of payoff. In this paper the author's previous work on "hi-criterion programs" is specialized to give an algorithm for routinely and efficiently solving the second and third reformulations. A by-product of the calculations in each ease is the tradeoff-curve between the criterion being maximized and expected value. The intimate relationships between all three reformulations are illuminated, with the cumulative effect of considerably lessening the burden on the decision-maker to preselect with finality a particular value of α or κ. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for yielding an improved initial dual solution of the transportation problem when the network flow algorithm of Ford and Fulkerson is used. (1) The algorithm is described. (2) It is demonstrated by means of a numerical example. (3) Computational experience is reported. 400 medium-sized (30 X 80; 50 X 60; 50 X 80) test problems with three different kinds of distance matrices and two different kinds of shipment quantity vectors were evaluated. The average improvement over the usual method was about 30%. [ABSTRACT FROM AUTHOR]

In formulating linear programming problems, analysts tend to include constraints that are not binding at the optimal solution for fear of excluding necessary constraints. The inclusion of such constraints does not alter the optimum solutions, but may require many additional iterations to be taken, as well as increase the computational difficulties encountered. Most of the methods proposed to date for identification of redundant and non-binding constraints are not warranted in practice because of the excessive computations required to implement them. These methods are reviewed in the present paper, and some of them are extended. A number of additional methods are also considered. Two of these new methods are not only practical, but have proven to be powerful in solving a number of problems. These methods may be incorporated in a variant of the simplex method. After each simplex iteration is made, constraints and variables are tested and, when identified as non-binding, are eliminated. The procedure is continued, with the problem size dwindling as the algorithm progresses, until the optimum is reached. Then the values of the eliminated variables are computed by substitution into the eliminated constraints. Early evidence shows that a size reduction for small problems (having 25-30 constraints) of 50 percent is not unusual. It is hoped that the results on larger problems will be even more significant.(n4) [ABSTRACT FROM AUTHOR]

This paper considers the problem of scheduling m independent, immediately available tasks on n parallel processors. Each task has a waiting cost rate, that is a function of time, and a service time. There are no feasibility restrictions on the order in which the tasks are to be processed. An optimal scheduling rule is presented for the single processor scheduling of tasks with continuously discounted linear waiting costs. A dynamic programming algorithm has been developed for a wide class of parallel-processor problems. Linear waiting costs (with or without discounting), arbitrary processor use costs, and certain other costs are considered. In certain cases, the service time of a task may be a function of the processor that performs it. [ABSTRACT FROM AUTHOR]

This paper describes a variant of the Simplex algorithm, applicable to matrices containing blocks of elements along and just below the diagonal. It uses the emptiness of the other blocks to save space and computation. [ABSTRACT FROM AUTHOR]

The problem considered in this paper is that of allocating a budget of resources among the links of a network for the purpose of increasing its flow capacity relative to given sources and sinks. On the assumption that the cost of increasing each link capacity is linear, a labeling algorithm is described that permits rapid calculation of optimal allocations for all budgets. [ABSTRACT FROM AUTHOR]

It has been established that integer programs with integral, recursive constraint matrices have integral extreme points for integral, nonnegative requirement vectors. In this paper, it is first shown that the assignment problem can be transformed to such a program, but with upper bounds on some variables. This equivalent program leads to additional results for solving the assignment problem. Algorithms are then delineated to transform matching, covering and travelling salesman problems to equivalent recursive programs of the aforementioned type, but with bounds on some variables. These results are extended to programs with special structure in their constraint matrices. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for determining the minimum cost schedule of tasks in a critical path network in which task cost-time curves may be concave. A computer program for the case of cost-time curves that are piecewise linear in two segments is described, and a numerical example is presented. [ABSTRACT FROM AUTHOR]

The methods of R. E. Gomory for the iterative solution of the mixed-integer linear programming problem are extended directly to the case where some or all of the variables are nonuniformly discrete, i.e., they are restricted to assume values from certain specified sets of unequally-spaced constants. The algorithm presented is shown to converge in a finite number of steps for a discrete-valued objective function. [ABSTRACT FROM AUTHOR]

By constructing a new infinite dimensional space for which the extreme point--linear independence and opposite sign theorems of Charnes and Cooper continue to hold, and, building on a little-known work of Ear (herein presented), an extended dual theorem comparable in precision and exhaustiveness to the finite space theorem is developed. Building further on this a dual theorem is developed for arbitrary convex programs with convex constraints which subsumes in principle all characterizations of optimality or duality in convex programming. No differentiability or constraint qualifications are involved, and the theorem lends itself to new computational procedures. [ABSTRACT FROM AUTHOR]

An algorithm is presented for the special integer linear program known as the set partitioning problem. This problem has a binary coefficient matrix, binary variables, and unit resources. Furthermore, all of its constraints are equations: In spite of its very special form, the set partitioning problem has many practical interpretations. The algorithm is of the branch and bound type. A special class of finite mappings is enumerated rather than the customary set of binary solution vectors. Linear programming is used to obtain bounds on the minimal costs of the subproblems that arise. Computational results are reported for several large problems. [ABSTRACT FROM AUTHOR]

A unifying framework is developed to facilitate the understanding of most known computational approaches to integer programming. A number of currently operational algorithms are related to this framework, and prospects for future progress are assessed. [ABSTRACT FROM AUTHOR]

A new algorithm is developed for solving zero-one polynomial problems. The algorithm is a direct extension of the well-known Balasian algorithm for zero-one linear programs. The basic idea underlying the development is that every zero-one polynomial programming problem can be converted into an equivalent zero-one linear system with nonlinear secondary constraints representing the polynomial terms. Moreover, the optimal solution to the original polynomial problem must be a feasible solution to the converted linear problem. Thus, the optimal solution is determined by searching for the best solution among the feasible solutions to the linear problem such that the secondary constraints are satisfied. The important point is that the secondary constraints are considered implicitly so that the size of the problem is determined by its equivalent linear form. Computational experience indicates that the new algorithm compares favorably with the existing ones due to Lawler and Bell [12] and to Watters [20]. The application of the algorithm to a special class of nonlinear binary problems is also investigated. [ABSTRACT FROM AUTHOR]

An efficient branch-bound algorithm is presented for solving the n-job, sequence-independent, single machine scheduling problem where the goal is to minimize the total penalty costs resulting from tardiness of jobs. The algorithm and computational results are given for the case of linear penalty functions. The modifications needed to handle the case of nonlinear penalty functions are also presented. [ABSTRACT FROM AUTHOR]

The usefulness of group theoretic methods in solving integer programming (IP) problems is extended by procedures for controlling the size of the groups. The main procedure given shows how an optimal linear programming basis can be altered to reduce the magnitude of its determinant thereby reducing the size of the group induced by the basis. An adaption of Benders' mixed IP algorithm is given which uses these methods. Some limited computational experience is given. [ABSTRACT FROM AUTHOR]

Some new properties associated with the special class of integer programs known as weighted set covering problems are derived. While it is well known that an optimal integer solution to the set covering problem is a basic feasible solution to the corresponding linear program, we show that there exists an optimal basis which is involutory (i.e., B = B[sup -l]). This property and others are used to develop a new algorithm which uses strong cutting planes. The cutting planes are strong in the sense that they exclude both integer and noninteger solutions. Computational experience is presented. [ABSTRACT FROM AUTHOR]

A Generalized Upper Bounding technique, similar to that introduced by Dantzig and Van Slyke [6], for solving large linear programs "with m + L equations (m « L), L of which have the property that each variable has at most one nonzero coefficient in them" is offered. The algorithm is a variant of the dual simplex method, uses a working basis of order m and allows implementation of various pivoting strategies. The necessary modifications to the algorithm for handling bounded variables are also described. [ABSTRACT FROM AUTHOR]

In this report, twenty-nine integer linear programming problems, ranging from very simple to apparently rather difficult, are introduced. The results of running these problems on four different computer codes, involving five distinct algorithms, are presented as both time and iteration data. A brief description of the codes used is also included. [ABSTRACT FROM AUTHOR]

A simple procedure is given for solving minimal cost flow problems in which feasible flows are maintained throughout. It specializes to give primal algorithms for the assignment and transportation problems. Convex cost problems can also be handled. [ABSTRACT FROM AUTHOR]

A branch and bound algorithm for solution of the "knapsack problem," max Σ v[sub i],x[sub i] where Σ w[sub i]x[sub i] ≤ W and x[sub i] = 0, 1, is presented which can obtain either optimal or approximate solutions. Some characteristics of the algorithm are discussed and computational experience is present. Problems involving 50 items from which approximately 25 items were loaded were solved in an average of 0.07 minutes each by a coded version of this algorithm for the IBM 7094 computer. [ABSTRACT FROM AUTHOR]

A stochastic game is played in a sequence of steps; at each step the play is said to be in some state i, chosen from a finite collection of states. If the play is in state i, the first player chooses move k and the second player chooses move l, then the first player receives a reward aikl, and, with probability pijkl, the next state is j. The concept of stochastic games was introduced by Shapley with the proviso that, with probability 1, play terminates. The authors consider the case when play never terminates, and show properties of such games and offer a convergent algorithm for their solution. In the special case when one of the players is a dummy, the nonterminating stochastic game reduces to a Markovian decision process, and the present work can be regarded as the extension to a game theoretic context of known results on Markovian decision processes. [ABSTRACT FROM AUTHOR]

The La Grange linear similarity transformation (completing the square) can be used to remove all cross-product terms from a quadratic form. It is shown that the La Grange transformation may be found conveniently by adapting the well-known Gauss elimination procedure for solving linear equations. A simple algorithm for finding the inverse transformation is given. This diagonalization scheme takes much less effort than finding the characteristic roots and vectors. It produces important simplifications in quadratic programming, statistics, and optimization problems. [ABSTRACT FROM AUTHOR]

The problem under consideration involves scheduling of the processing of an initial queue of jobs and subsequent Poisson arrivals on a single processor. Each job to be processed incurs a loss which increases linearly with its waiting time. The scheduling algorithm is sought which minimizes the average rate of expected loss over infinite time. It is shown that if statistical equilibrium exists for the total loss of an individual arrival, the optimal schedule minimizes the expected total loss of a single arrival, and is given by the scheduling rule which applies when there are no additional arrivals. [ABSTRACT FROM AUTHOR]

A linear programming model is set forth for maximizing a vector of final demand deliveries under both regional production constraints and transportation network constraints. The model is essentially designed to study short-run effects, and hence no provision is made for the expansion of either industrial or transportation capacities. Within available capacities, however, the location of production is chosen so as to maximize final demand deliveries. A rough dynamic version of the model is presented as well as an algorithm for reaching an approximation of the optimum solution. [ABSTRACT FROM AUTHOR]