Search

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]

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]

The purpose of this paper is to illustrate some applications of the functional equation technique of the theory of dynamic programming to a general class of problems arising in the study of networks, particularly those arising in transportation theory. [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]

The author [1], [2] has given an algorithm for finding that stratified allocation which minimizes the posterior variance of the overall population mean subject to a budget constraint under a model in which a normal prior distribution and independent normal sampling distributions were assumed. The budget constraint assumed a variable per unit cost of observation. In the present paper these results are extended to cover the case where there are fixed costs, as well as variable costs, associated with sampling in the ith stratum. The resulting algorithm is noted to be applicable in finding the optimal allocation of sampling effort (with fixed and variable sampling costs) under a variety of distributional assumptions. An interpretation is also given to two and higher stage design questions when there is differential prior information regarding the first stage units. [ABSTRACT FROM AUTHOR]

This article presents abstracts of several papers about economics published in a 1962 issue of the Journal of Regional Science. In the article Programming Models of Interdependence Among Agricultural Sectors and Spatial Allocation of Crop Production, Earl O. Heady and Alvin C. Egbert used linear programming models to estimate the efficient allocation of crop production among 104 producing regions of the U.S. The paper An Efficient Algorithm for the Numerical Solution of the Generalized Weber Problem in Spatial Economics presented an iterative algorithm, suitable for desk calculator or for computer, which yields a numerical solution to the Weber problem for any number of points.

The article proposes to reformulate portfolio theory under the assumption that investment relatives are lognormally distributed. Portfolio theory is shown to be correct under assumptions that returns are normally distributed and the investor's utility function is quadratic. Several reasons for questioning and challenging these assumptions are discussed, such as the unrealistic implications of the utility function. The authors present an algorithm for determining portfolios in an efficient set theorem and discuss the implications for the marginal utility of investors.

Can demand and consequently the market for consumers' durable goods be reduced to a mathematical model? Yes, these business economists contend, provided the right framework is chosen and proper statistical correlations are made to compensate for those eternal marketing variables -- price, credit, income, and use-facilities. They illustrate their point by constructing an econometric model, applicable to any durable good, and demonstrate its use and accuracy by analyzing sales of washing machines. [ABSTRACT FROM AUTHOR]

The paper presents a response to a comment on the article "Economically Optimum Design of CUSUM charts." The author feels that they are making two specific points; they question his use of the word "optimum" and attempt to point out that other search methods may be more appropriate in certain situations. He feels that while they are correct that some search methods work better in certain circumstances, he thinks his use of the word "optimum" is correct and explained thoroughly. Optimum, in this case, refers to the values of the parameter that yield the minimum cost, which he believes he explains in the abstract.

This paper treats the problem of locating a given number of interrelated physical facilities in a single- or multi-story building as an optimization model such that the weighted sum of the distances along orthogonal directions is minimized, and describes a constructive heuristic algorithm for the one-dimensional model. This linear placement algorithm is then extended to higher dimensions for placing uniform-size equipment modules at homogeneous fixed locations. The algorithm accommodates lower-bound constraints for the linear case efficiently and produces near-optimal solutions. Its significance, as demonstrated by comparison with some existing heuristic procedures, is that it has the capability of handling efficiently problems with large numbers of equal-size facilities whose solutions are computationally intractable using the present optimum-producing methods. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for the global maximization of a convex function subject to linear inequality constraints. It is computationally finite and is designed to converge rapidly on problems in which there are few local optima or the global optimum is significantly better than most of the other local optima. [ABSTRACT FROM AUTHOR]

Computational experiments with the primal integer programming algorithm indicate that in many cases the optimal value of the objective function is obtained in a very few iterations but a large number of iterations are required to establish optimality; thus, an alternative proof of optimality is needed. This paper describes an algorithm for obtaining an upper bound (such an alternative) on the value of the objective function. This bound is based on the best bound obtainable from dual solutions to a class of related linear programs. Computational results illustrating the effectiveness of this bounding technique are presented. [ABSTRACT FROM AUTHOR]

This paper introduces and illustrates an efficient algorithm, called the sweep algorithm, for solving medium- as well as large-scale vehicle-dispatch problems with load and distance constraints for each vehicle. The locations that are used to make up each route are determined according to the polar-coordinate angle for each location. An iterative procedure is then used to improve the total distance traveled over all routes. The algorithm has the feature that the amount of computation required increases linearly with the number of locations if the average number of locations for each route remains relatively constant. For example, if the average number of locations per route is 7.5, the algorithm takes approximately 75 seconds to solve a 75-location problem on an IBM 360/67 and approximately 115 seconds to solve a 100-location problem. In contrast, the time to solve a problem with a fixed number of locations increases quadratically with the average number of locations per route. The sweep algorithm generally produces results that are significantly better than those produced by GASKELL'S savings approach and are generally slightly better than CHRISTOFIDES AND EILON'S results; however, the sweep algorithm is not as computationally efficient as Gaskell's and is slightly less so than Christofides and Eilon's. [ABSTRACT FROM AUTHOR]

This paper presents an investigation of the effects of errors in the estimation of the gradient of the objective function on the FRANK-WOLFE nonlinear programming algorithm. The investigation was motivated by a desire to reconcile the use of interactive programming approaches to the solution of the multiple-criteria problem with utility models that allow for intransitive statements of indifference and preference. Results are provided regarding the ultimate convergence of the algorithm, and its initial convergence rate. [ABSTRACT FROM AUTHOR]

An examination of computational results using the simplified primal integer programming algorithm of GLOVER reveals the existence of long sequences of iterations following a specific pattern. This paper examines the structure of these sequences so that both the termination of a sequence and the tableau at that point can be predicted. It then constructs an algorithm that exploits this structure by performing the iterations of the sequence implicitly and presents computational results. [ABSTRACT FROM AUTHOR]

This paper gives counterexamples to: (1) Ritter's algorithm for the global maximization of a quadratic subject to linear inequality constraints, and (2) Tui's algorithm for the global minimization of a concave function subject to linear inequality constraints. [ABSTRACT FROM AUTHOR]

This paper proposes a production model for quality surveillance, which is based on a cusum chart using the decision integral criterion. An algorithm for determining the economically optimum control parameters is presented. Some criticisms of the conventional ad hoc design of a cusum chart are made, and it is suggested that the average run lengths (ARL) at the rejectable quality level should be less than 2 when this model is applicable. A simplified version of the algorithm is also devised which 8gives control plans which are close to optimum. This scheme is suitable for application at the factory level. Also included is a table of ARL for some neglected, but useful, values of the decision interval and the process deviate. [ABSTRACT FROM AUTHOR]

This paper presents a dynamic programming algorithm for determining optimal production in a series type multi-echelon inventory system with stochastic final product demand. Setup costs at individual facilities are permitted. For the case where it is physically possible (but not required) for a product unit to pass through all the facilities within a single time period, a second dynamic programming algorithm is presented which can be used in conjunction with the first to substantially decrease computation time. The model can also be readily specialized to the case of deterministic demand and permits a larger class of cost functions than existing deterministic multi-echelon models. [ABSTRACT FROM AUTHOR]

In Part I of this paper, we developed an algorithm for finding planning horizons for the deterministic production smoothing problem when all demand was required to be met from regular production, under rather general assumptions for the production smoothing, and holding cost functions. Here, in Part II, we develop analogous planning horizons when the model is extended to include such factors as overtime, lost sales, simple subcontracting, undertime, and backlogging. Part II depends heavily on Part I. To avoid unnecessary tedium, all cost functions will be assumed to be stationary in Part II. Overtime, undertime, holding, and backlogging will be assumed to be convex increasing, all other costs linear and proportional. However, it is not difficult to see that the techniques of Part I can be utilized directly to cover more general cost functions. Part II concludes with a discussion of the application of our general approach to actual data. [ABSTRACT FROM AUTHOR]

Bounding techniques similar to those used with branch and bound procedures are used in this study in conjunction with zero-one programming to produce minimum duration schedules for the resource constrained, project scheduling problem, The algorithms developed consist of examining the feasibility of a series of zero-one programming problems rather than solving one zero-one problem optimally, Computational results demonstrate the advantage of this method over using zero-one programming without employing any form of bounding. A comparison with other exact procedures for solving the resource constrained, project scheduling problem is also given. [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]

This paper presents an implicit enumeration algorithm for redrawing school attendance boundaries in order to meet integration requirements. The basis of the approach is the division of the city into smaller areas or zones corresponding to neighborhoods. These zones are assigned to schools with the objective of minimizing the required bussing while meeting the school capacity and racial mix constraints. An entire zone is assigned to one school, thus preserving the neighborhood school concept. Viewing the possible zone-school assignments as a combinatorial problem, a general enumerative procedure is combined with probability theory to form the implicit enumeration algorithm. An explanation of the algorithm along with computational results of an application of the method to an existing school system is presented. [ABSTRACT FROM AUTHOR]

This paper discusses the hidden-surface problem from tile point of view of sorting. The various surfaces of an object to be shown in hidden-surface or hidden-line form must be sorted to find out which ones are visible at various places on the screen. Surfaces may be sorted by lateral position in the picture (X I'), by depth (Z), or by other criteria. The paper shows that the order of sorting and the types of sorting used form differences among the existing hidden-surface algorithms. To reduce the work of sorting, each algorithm capitalizes on some coherence property of the objects represented. ‘Scan-line coherence,’ the fact that one TV scan line of output is likely to be nearly the same as the previous TV scan line, is one commonly used kind of coherence. ‘Frame coherence,’ the fact that the entire picture does not change very much between successive frames of a motion picture can be very helpful if it is applicable. By systematically looking for additional kinds of coherence and untried sorting orders and sorting types, the paper is able to suggest two promising new approaches to the hidden-surface problem. The first, a combination of three existing algorithms, is promising because it would capitalize on both frame and scan-line coherence. The second new approach would sort in the order Y, Z, X, … the only sorting order for which an existing algorithm could not be found. [ABSTRACT FROM AUTHOR]

It is known that prices only cannot usually be utilized to coordinate a linear economic system. This paper considers a linear economic system. formally represented as a linear programming model which is interpreted as a resource-allocation problem. An algorithm founded on the idea of associating with each resource a linearly increasing price schedule rather than a constant price is developed. The paper hence demonstrates that a mechanism rather similar to a pure price mechanism can be used both to find and sustain an optimal allocation of resources in a linear economic system. [ABSTRACT FROM AUTHOR]

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]

The article presents information on a method or algorithm for finding proposals on which all members of a group can agree. The method is confined to situations where the variables can be changed by any "small" amount and, where the group is attempting to decide on a change in the variables from some "existing situation." A possible change in the variables will be called a "proposal." A proposal would be "acceptable" to an individual if it would increase his utility. The problem is not to pick a particular proposal which is acceptable to all individuals.

This paper describes the result of carrying out such a maximisation of a social welfare function prescribed for a model of the United Kingdom economy over the period 1957-66. The choice of social welfare function was a crucial part of the exercise and is discussed in some detail. Optimisation of the welfare function was achieved using modern control theory.[1] The next section of this paper describes the model; its dynamic properties are then evaluated in a subsequent section. Next, the optimisation goal is presented in terms of the model, and a social welfare function is chosen. The optimisation procedure is then applied and the results obtained are presented and discussed. Finally, consideration is given to the ways in which the procedures might in later research be modified as a result of the lessons learnt from this experiment. The results presented in this paper have shown that this model gives a good picture of how controls influence the economic system, despite the restrictions placed upon its size. The major cycles of the fitting period were reproduced and the model's poor ability at forecasting was a direct result of the primitive assumption of a fixed exchange rate. One advantage of its structure was that, apart from the control variables, it had only two exogenous variables. Although there was no quantitative way of assessing the dynamic properties of the model, the results of the dynamic multiplier tests were qualitatively satisfactory. On the other hand the attempt to use a control algorithm in order to suggest a policy which might have given better economic results at the end of 1961 must be admitted to have been a failure. The procedure correctly reflected the instructions given to it in the form of the social welfare function which was selected, but this function treated public and consumers' expenditure as perfect substitutes and omitted to take account of the desirability of certain items and overstated the undesirability of certain oth... [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]

While Dantzig and Wolfe have formulated the decomposition algorithm as a computational device, it was subsequently recognized that the principle underlying the algorithm may also be utilized by a planning system to achieve a centralized planning within the framework of a decentralized organizational structure. This paper illustrates the workings of such a planning system and, at the same time, explores some of the problems connected with its actual implementation. The planning system under the study is called the decomposed planning system in order to distinguish it from either the centralized planning or the decentralized planning. [ABSTRACT FROM AUTHOR]

The algorithms of this paper solve problems of the ‘decomposition’ structure. It presents the basic framework for a class of algorithms, along with two possible versions. The basic algorithm generates a sequence of solutions that satisfy complementary slackness with a sequence of dual feasible solutions such that, when the linking constraints are satisfied, an optimum is obtained. Computational experience is reported for the first version in comparison with RSMFOR, a simplex program, on randomly generated problems and a three-period refinery model Using the number of nonzero multiplications as the bade for comparison, the results show the first version substantially better than the simplex method. The computational experience is discussed at some length. [ABSTRACT FROM AUTHOR]

This paper considers the problem of choosing the discrete antiballistic missile (ABM) defense levels of reliable subtractive area and paint defenses protecting a get of targets so as minimize the total damage done to the targets by in optimal attack by a given number of reliable offensive missiles of one type. It assumes that the offensive side knows the ABM defense levels chosen fund that the defensive side knows the number of missiles possessed by the oftensive side. The cost of the defensive allocation chosen must not exceed a stated budget level; the cost function need not be continuous or separable. The 0-1 implicit enumeration scheme of Lawler and Bell is combined with a brunch-and-bound procedure to effect a solution. [ABSTRACT FROM AUTHOR]

This paper look at the maximal-flow-with-gains problem from a new point of view. We wish to discover the maximum output possible for any input. This approach leads naturally to a two-step parametric solution procedure: The step finds the maximum output far zero input, and resolves all difficulties with flow-generating loops; the second determines how the maximum output increases as input is increased. [ABSTRACT FROM AUTHOR]

This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric travelling-salesman problem. The procedure is based on a general approach to heuristics that is believed to have wide applicability in combinatorial optimization problems. The procedure produces optimum solutions for all problems tested, 'classical' problems appearing in the literature, as well as randomly generated test problems, up to 110 cities. Run times grow approximately as n² in absolute terms, a typical 100-city problem requires less than 25 seconds for one case (GE63S), end about three minutes to obtain the optimum with above 95 per cent confidence. [ABSTRACT FROM AUTHOR]

This paper connects some of the recent developments in concave and integer programming. In particular, it points out parallels between the work of HOANG TUI and R. D. YOUNG. From these methods, a finite algorithm for solving a special class of 0–1 integer programs is developed. Our approach contrasts with an earlier extension of Tui's method due to M. RAGHAVACHARI and general ‘intersection’ or ‘convexity’ cut approaches. [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]

MILLER and WAGNER [Opns. Res. 13, 930–945 (1965)] define joint chance-constrained programming by specifying a set of consists that are joint probability measures of the extent to which constraint violations are permitted. For the special case of a random right-hand-side vector whose elements are independent random variables, they show that an equivalent deterministic concave program exists. The purpose of this paper is to generalize this result to a class of nonlinear chance-constrained programming models with joint constraints. [ABSTRACT FROM AUTHOR]

This paper presents a realistic chemical-process optimization problem in detail, and notes the fact of its equivalence to the general nonlinear programming problem. The eight equality constraints that arise are handled by algebraic substitution, and the resulting four-variable problem is solved by a modified form of the Davidon-Fletcher-Powell algorithm. Details of the method are presented (including a FORTRAN computer program), and results of two typical cases are summarized. [ABSTRACT FROM AUTHOR]

This paper considers a special class of transportation problems in which the needs of each user are to be supplied entirely by one of the available sources. We first show that an optimum solution to this special transportation problem is a basic feasible solution to a slightly different standard transportation problem. A branch-and-bound solution procedure for finding the desired solution to the latter is then presented and illustrated with an example. We then consider an extension of this problem by allowing the possibility of increasing (at a cost) the source capacities. The problem formulation is shown to provide a generalization to the well known assignment problem. The solution procedure appears to be relatively more efficient when the number of uses greatly exceeds the number of sources. [ABSTRACT FROM AUTHOR]

This paper describes an algorithm that finds globally optimum flows in networks having nonlinear costs of arc flows, the flows being finite-dimensional vectors such as multicommodity flows. The algorithm is an extension of an idea of ALLSOP [Trans. Sci. 2, 1–13 (1968)] for minimizing total delays in a traffic network; it is also intimately related to results in nonserial dynamic programming. [ABSTRACT FROM AUTHOR]

This paper describes a new method of generating all vertices of a given convex polytope. Additionally, irrelevant constraints are easily identified without the necessity of enumerating any of the vertices of the given convex polytope. The method embeds the given polytope in a one-higher-dimensional space. The projection of the additional vertices formed by the embedding process into the original space lie in the interior of the polytope and have a tree structure for one and two polytopes. For higher dimensions, the embedding process associates a number with each interior point that facilitates the construction of a spanning tree for all of the interior points. The interior points added can be efficiently generated by a variant of the simplex method. The vertices of the original polytope can be generated easily from these internal points by analyzing the appropriate simplex tableaux. [ABSTRACT FROM AUTHOR]

This paper studies a class of integer programming problems in which squares of variables may occur in the constraints, and shows that no computing device can be programmed to compute the optimum criterion value for all problems in this class. [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]

This paper studies multistage mathematical programs with an arbitrary transient phase followed by an infinite stationary phase with linear constraints and objective. It presents conditions under which a derived linear program will determine an optimal solution to the infinite problem. These conditions are general and may be validated by simple algebraic tests (perhaps solving a finite linear program). No topological restrictions are placed on the model. [ABSTRACT FROM AUTHOR]