Search

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.

The article presents a zero-one linear program and a dynamic programming algorithm for finding the shortest route containing exactly q arcs from node 1 to node n in a network (N, A) with distances c(i, j). This note shows that the linear programming formulation and his extension based on it are defective, and that the dynamic programming algorithm can lead to suboptimal solutions, but a minor change in the dynamic programming formulation relieves the difficulty. A special feature of this linear program is that there can never be a loop in the basis, because the vectors corresponding to the variables of a loop are linearly dependent. The last comment is related to the dynamic programming algorithm. One is allowed to pass through a node more than once in the shortest route . The proposed method for solving this program consists of converting it into a shortest route problem containing exactly q arcs. But for some arbitrary reason, the dynamic program is formulated in such a way that one can never have starting node 1 more than once in the final solution.

This note presents a description of a time-sharing computer program written to implement a man-machine interactive algorithm for the solution of the multiple criteria problem. The interactive algorithm was suggested in a recent paper by Geoffrion, "Vector Maximal Decomposition Programming," Working Paper No. 164, Western Management Science Institute, University of California, Los Angeles, September 1970. A unique feature of this program is the man-machine dialog which obtains information from the decision-maker through a series of simple, ordinal comparisons. [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]

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 B. 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]

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]

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]

This paper presents an algorithm for finding the K loopless paths that have the shortest lengths from one node to another node in a network. The significance of the new algorithm is that its computational upper bound increases only linearly with the value of K. Consequently, in general, the new algorithm is extremely efficient as compared with the algorithms proposed by Bock, Kantner, and Haynes [2], Pollack [7], [8], Clarke, Krikorian, and Rausan [3], Sakarovitch [9] and others. This paper first reviews the algorithms presently available for finding the K shortest loopless paths in terms of the computational effort and memory addresses they require. This is followed by the presentation of the new algorithm and its justification. Finally, the efficiency of the new algorithm is examined and compared with that of other algorithms. [ABSTRACT FROM AUTHOR]

The paper presents a new approach to solving a class of combinatorial economic allocation problems. One member of this class is known as the quadratic assignment problem. Besides presenting an algorithm to solve this problem, we will discuss in general terms the techniques for treating combinatorial problems. A novel feature of the paper is the development of the statistical properties of the criterion function. These statistical properties are used in conjunction with a general enumerative procedure to form the main parts of the algorithm. Using the idea of confidence level enumeration, an extension of the algorithm is proposed which should allow for the effective treatment of large scale combinatorial problems. Finally we present some computational results in order to illustrate the effectiveness of the general approach. [ABSTRACT FROM AUTHOR]

This paper analyzes the problem of balancing resource capacity utilization against the costs of user delay or inventory investment. Instead of formulating algorithms to solve more classical versions of the problem, this paper describes ways that organizations can drop the cost curve prior to applying an optimizing algorithm. This is done by classifying the techniques and giving examples from organizations which have faced serious smoothing problems. Other organizations can improve their coat performance by adopting some of these techniques. [ABSTRACT FROM AUTHOR]

In this paper we study a model that minimizes the sum of production, employment smoothing, and inventory costs subject to a schedule of known demand requirements over a finite time horizon. The three instrumental variables are work force producing at regular-time, work force producing on overtime, and the total work force. Overtime is limited to be not more than a fixed multiple of regular time. The idle portion of the work force and the levels of inventory are resultant variables. We postulate the following shape characteristics for the cost functions production costs are convexlike, smoothing costs are V-shaped, and holding costs are increasing, both the production and holding cost functions need not be stationary. In this paper, we provide upper and lower bounds on the cumulative regular-time plus overtime work force for any sequence of demand requirements. We also give the form of an optimal policy when demands are monotone (either increasing or decreasing). Finally, we derive the asymptotic behavior of optimal policies when demands are monotone and the planning horizon becomes arbitrarily long. All of these results, which convey information about the numerical values of optimal policies, given specific demands and an initial level of inventory, depend only on the shape characteristics of the cost functions. Algorithmic techniques are discussed elsewhere. [ABSTRACT FROM AUTHOR]

This paper considers "critical path" networks which are used for the planning and scheduling of projects that consist of well defined sequences of individual activities. When the number of activities is large, it becomes difficult to prepare a network for the project as one unit, and it may also be difficult to store the network in the high speed memory of a digital computer. Also, in the cases where there are two or more independent projects, which are weakly inter-related by common activities, the problem of efficient scheduling of all the projects becomes quite difficult. This paper presents a method to "tear" or "decompose" a project network into several subnetworks, schedule the subnetworks and then to put the subnetworks back together. A computational algorithm is first given for time-only networks; then two computational formulations are given for cost-time network of project subnetworks. The latter essentially generalize the algorithm due to Fulkerson, in order to handle piecewise linear, convex, cost-time curves for some or all of the activities. [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 purpose of the present paper is to extend the loop-technique of the stepping-stone algorithm to the generalized transportation problem. The main result (Theorem and Corollary of §6) is, that passing from a basic feasible solution to another one may always be carried out by constructing a simple symmetrical or a double loop (as defined in §2) and computing new values for the variables only along this path. The amount of computations needed for this turns out to be substantially reduced as compared to the usual way of solving the system of equations relating the new basis to the old one. [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]

In an earlier paper [20] combinatorial programming procedures were presented for solving a class of integer programming problems in which all elements are zero or one. By representing the problem elements in a binary computer as bits in a word and employing logical "and" and "or" operations in the problem-solving process, a number of problems involving several hundred integer variables were solved in a matter of seconds. In the present paper a number of improvements in these earlier algorithms are presented, including a new search strategy, methods for reducing the original problem, and mechanisms for feasibility filtering in multi-word problems. With these improvements problem-solving efficiency has been increased in many instances by an order of magnitude. In addition, the present paper contains computational experience obtained in solving problems for the k-best solutions. [ABSTRACT FROM AUTHOR]

The bond portfolio problem is viewed as a multistage decision problem in which buy, sell, and hold decisions are made at successive (discrete) points in time. Normative models of this decision problem tend to become very large, particularly when its dynamic structure and the uncertainty of future interest rates and cash flows are incorporated in the model. In this paper we present a multiple period bond portfolio model and suggest a new approach for efficiently solving problems which are large enough to make use of as much information as portfolio managers can reasonably provide. The procedure utilizes the decomposition algorithm of mathematical programming and an efficient technique developed for solving subproblems of the overall portfolio model. The key to the procedure is the definition of subproblems which are easily solved via a simple recursive relationship. [ABSTRACT FROM AUTHOR]

This paper is concerned with finding the optimal way of rearranging items in a warehouse from their initial positions to their desired final locations. Such a rearrangement may become necessary because of changes in the relative demand for each item, with the result that what were once fast-moving items at the 'front' end of the warehouse, are now only slow-moving ones that must be moved towards the 'rear.' Although the problem, as treated in this paper, is addressed to the rearrangement of items in a warehouse, many other applications come immediately to mind, such as the reorganization of the layout of open-plan orates and factories. The paper gives a two-stage algorithm that produces the sequence of item movements necessary to achieve the desired rearrangement and incur the minimum cost (or time) spent in the rearranging process; the result is optimal in the restricted case where the rearrangement must be done in a number of cycles each one being of a short time duration (the case, for example, if the warehouse were to remain operative during the rearrangement). [ABSTRACT FROM AUTHOR]

This paper proves two properties of maximal network flows: (1) If there exist a maximal network flow with a given departure pattern at the sources and a maximal flow with a given arrival pattern at the sinks, then there exists a flow that has both this departure pattern at the sources nd this arrival pattern at the sinks. (2) There exists a maximal dynamic network flow that simultaneously has a latest (earliest) departure schedule at the sources and an earliest (latest) arrival schedule at the sinks. The paper modifies FORD AND FULKERSON'S maximal dynamic flow algorithm to construct a maximal dynamic network flow with a latest departure schedule and an earnest arrival schedule. [ABSTRACT FROM AUTHOR]

A complementary programming problem is a linear programming problem with the additional restriction that xpxq=0 holds for each specified pair (xp, xq). This paper obtains constraints called C-cuts from the restriction xpxq=0, and uses them to facilitate the computation of the branch-and-bound procedure proposed in an earlier paper [Opns. Res. 19, 1523–1528 (1971)]. Some computational results are also reported. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm that will minimize the total processing time for a particular case of the n-job, m-machine scheduling problem. In many industrial processes, jobs are processed by a given sequence of machines. Often, once the processing of a job commences, the job must proceed immediately from one machine to the next without encountering any delays en route. The machine sequence need not be the same for all jobs. Because of this processing constraint that prohibits intermediate queues, most normal scheduling techniques are not applicable. This paper obtains a solution to this constrained scheduling problem by modeling it as a traveling-salesman problem; known solution techniques can then be employed. The paper solves a sample problem and discusses computational considerations. [ABSTRACT FROM AUTHOR]

This paper develops an inventory model in which season length is specifically included as a variable for seasonal style goods under the assumption that the demands exhibit a simple contagion pattern, namely, the influence of past demands on future occurrence of demands. The paper first derives an s-S optimal order policy as a function of the selling season, then determines the optimal duration and timing of the selling season, and, finally includes an algorithm for computing the optimal season length. [ABSTRACT FROM AUTHOR]

This paper considers a special class of transportation problems. There is a set of sources producing the same material with a fixed maximum capacity, and a set of users whose demands for the material are known. A cost is associated with the transportation of the material from each source to each user. Each user is to be supplied by one source only. The problem consists of finding the flow of the material from the sources to the users that satisfies their demands and minimizes the total transportation cost. The formulation of the problem is the same as the well-known Hitchcock problem with the further constraint that all the variables are binary. The paper proposes a search method, roughly resembling Balas's filter method, for the solution of the problem, and discusses it from a computational point of view. Finally, it describes an application of the model to a real industrial problem. [ABSTRACT FROM AUTHOR]

In order to discuss scheduling algorithms for time-sharing computer systems, this paper analyzes the M/G/1 queue under the well known round-robin (RR) discipline. Three models are considered: the constant-quantum RR model, the processor-shared (or zero-quantum RR) model, and the variable-quantum RR model. The paper proposes an effective calculating method for obtaining the expected response time under an arbitrary processing-time distribution with overhead. By the theoretical analysis, one can show how the response time is affected by the scheduling and processing-time distributions, as is demonstrated by some typical examples. [ABSTRACT FROM AUTHOR]

Certain jobs in large projects do not have a unique 'location' in the critical-path network; they may be moved into certain slack intervals, for example, or may even be divisible into smaller subtasks, and 'tucked in' at several locations. A previous paper gave an analysis of a model in which a single job can be divided up in any manner among an arbitrary number of locations; the resulting algorithm was of the optimal-network-flow type, which can be simply and efficiently solved using available computer codes. The first part of the present paper extends this model to multiple jobs of divisible type. The general approach is via the decomposition method of linear programming; however, the resulting algorithm is again fairly simple. Optimal cost-time solutions, possibly infinite (or optimal network flow solutions, possibly infeasible) are generated by known algorithms. The resulting schedules or cuts are then combined in a simple, special structure linear program whose dimensionality is equal to the number of divisible groups. Bounds on the nonintegrality of the final allocations can also be determined. When these special jobs can only be moved about the network in their entirety, or in certain indivisible modules, the problem takes on the form of an integer program. The second part of the paper gives a branch-and-bound procedure for the problem of movable activities, together with efficient heuristics for arbitrating and bounding these locations, using only the ordinary critical-path algorithm. Examples are given for both models. [ABSTRACT FROM AUTHOR]

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 develops a new algorithm for solving the general nonlinear programming problem that melds the flexible simplex search of NELDER AND MEAD with various additional rules to take care of equality and/or inequality constraints. The set of violated inequalities and equalities is lumped into one inequality constraint loosely satisfied during the early progress of the optimization and more closely satisfied during its final stages. To permit this type of search, the method sets up a special tolerance criterion, a function that does not depend on either the values of the objective function or the values of the constraints. The new algorithm has solved successfully a number of problems that have been proposed in the literature as test problems. Finally, to indicate the algorithm's capabilities, the paper describes an example composed of a linear objective function of twenty-four variables subject to fourteen nonlinear equalities and thirty inequalities. [ABSTRACT FROM AUTHOR]

This paper seeks here a minimum cost production plan over a finite number of time periods. There is a known demand requirement (stated in production hours) to be met in each period from current and previous hours of production (stored as inventory). A production policy consists of scheduled amounts of hours, some of which are costed at regular-time wage rates, the remainder costed at overtime rates. Expansion or contraction of the work force (stated in production hours) is charged against the period-to-period variations in regular-time employment. The fluctuations in overtime production do not incur such hiring and firing costs. The amount of overtime used, however, is constrained not to exceed a specified fraction of regular-time utilized in any period. We describe algorithms for finding an optimal policy under the assumption that all costs are described by linear functions and where demands are either monotonic increasing or decreasing in time. In addition to presenting the algorithms, we also examine certain planning horizon results implied by these algorithms. Specifically, we ascertain when optimal first period decisions can be made without knowing the precise values of all future demands and costs. [ABSTRACT FROM AUTHOR]

This paper approaches the assembly-line balancing problem as a sequencing problem involving precedence constraints that prohibit the occurrence of certain orderings. This approach permits the formulation of a dynamic programming algorithm for the exact solution of small assembly-line balancing problem. A generalization of this algorithm combined with a successive approximations technique is used for the solution of large problems. In addition, certain combinatorial problems associated with partially ordered sets are formulated and discussed in detail. These problems arise whenever sequencing problems with precedence constraints are treated by dynamic programming techniques. [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 presents a new approach to determining the optimal facility locations for uncapacitated location problems in two stages. First, it is shown that a subset of all solutions to the uncapacitated public facility location problem can be obtained by considering a closely related private location problem. The exact nature of the problem is established using the Generalised Lagrange Multiplier results given by Everett. In the second section of the paper a particularly efficient parametric decomposition algorithm, which is based on the results of the first section, is presented. Computational results are given which summarize the current level of experience with the algorithm. [ABSTRACT FROM AUTHOR]

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 purpose of this paper is to furnish a computational scheme for a class of programming problems with nonlinear constraints. The algorithm is sequential in nature, producing a sequence of feasible solutions whose limit points are optimal solutions of the original problem. Further, with a view to accelerating convergence we suggest two variants of the solution procedure. [ABSTRACT FROM AUTHOR]