Search

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

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

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]

This paper presents an efficient algorithm for finding a minimum-weight generalized matching in a weighted bipartite graph. Computational evidence is given that indicates that the time required to find a least-cost assignment of n jobs to n workers goes roughly as n[sub2] for 10=

This paper describes an algorithm for a ship scheduling problem, obtained from a Swedish ship-owning company. The algorithm uses the Dantzig-Wolfe decomposition method for linear programming. The subprograms are simple network flow problems that are solved by dynamic programming. The master program in the decomposition algorithm is an LP problem with only zero-one elements in the matrix and the right-hand side. Integer solutions are not guaranteed, but generation and solution of a large number of problems indicates that the frequency of fractional solutions is as small as 1-2 per cent. Problems with about 40 ships and 50 cargoes are solved in about 2.5 minutes on an IBM 7090. In order to resolve the fractional cases, some integer programming experiments have been made. The results will be reported in a forthcoming paper. [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]

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]

This paper presents a grouping procedure which yields improved solutions to Bomberger's Lot Size Scheduling Problem [1]. The group definition is a generalization of the group definition proposed by Stankard and Gupta [3]. Moreover, the generalization leads to a pseudo dynamic programming procedure which is readily programmable. Computational experience has shown the procedure to be extremely efficient. [ABSTRACT FROM AUTHOR]

This paper extends the results of "Duality in Discrete Programming" [1] to the case of quadratic objective functions. The paper is, however, self-contained. A pair of symmetric dual quadratic programs is generalized by constraining some of the variables to belong to arbitrary sets of real numbers. Quadratic all-integer and mixed-integer programs are special cases of these problems. The resulting primal problem is shown, subject to a qualification, to have an optimal solution if and only if the dual has one, and in this case the values of their respective objective functions are equal. The dual of a mixed-integer quadratic program can be formulated as a minimax problem whose quadratic objective function is linear in the integer-constrained variables, and whose linear constraint set does not contain the latter. Based on this approach an algorithm is developed for solving integer and mixed-integer quadratic programs. [ABSTRACT FROM AUTHOR]

Two dynamic economic lot size production systems are analyzed in this paper, the first being a single product model with backlogging and the second a multi-echelon model. In each model the objective is to find a production schedule that minimizes the total production and inventory costs. A key conceptual difficulty is that the mathematically perplexing problem of minimizing a concave function is being considered, it is shown that both models are naturally represented via single source networks. The network formulations reveal the underlying structure of the models, and facilitate development of efficient dynamic programming algorithms for calculating the optimal production schedules. [ABSTRACT FROM AUTHOR]

This paper presents results which apply to convex programming problem in parametric form. The results secured are also related to the problem of fractional programming in a way which indicates computational possibilities for the latter class of problems. The results are extended to general non-linear programming problems with special reference to continuous criterion functions. As a particular case, the linear fractional programming problem is considered and, in conclusion, the results secured here are pointed up by reference to existing algorithms for the latter class of problems. [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]

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]

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]

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 presents an algorithm, based on the simplex routine, that provides a way to solve a problem in which the objective function is not linear, but rather is represented by a ratio of two linear functions. This algorithm has a computational advantage over two previous ones because it requires neither variable transformations nor the introduction of new variables and constraints. [ABSTRACT FROM AUTHOR]

This paper presents an iterative algorithm that allows the solution of the following problem to be obtained to any desired degree of accuracy: choose s,,A, for i=1, -.., rs to minimize &Sigma[supi−n][subi&minus1]c[subi](8[subi]) subject to Σ[supi;−n][subi−1]e[subi](8[subi])≥ ε for arbitrary given real ε c[subi], e[sub1], and finite A[subi], i=1, ..., n. In particular, the sets {(c[subi](ϒ), e[subi](ϒ)): ϒεA[subi] need not be convex. The procedure offers considerable computational advantage over alternative means of obtaining the desired solution. The technique uses a pair of Lagrange multipliers for the single constraint. This pair of Lagrangians induces a partial ordering among the set of all (8[sub1], ..., 8[subn]). The desired solution is found among the maximal elements under this ordering for appropriate choices of the multipliers, and possible improvement in the solution is bounded in terms of other maximal elements. The set of all maximal elements, under the partial ordering, is generated by dynamic programming. [ABSTRACT FROM AUTHOR]

This paper develops a model for the optimum allocation of fixed stockpiles of interceptors. Imbedded dynamic programming and successive approximations serve as the format for the computational scheme. This procedure leads to a local optimum solution in general and to the global optimum in certain instances. A method for determining upper bounds is included in the algorithm so that optimal stopping rules may be used to choose a final solution. [ABSTRACT FROM AUTHOR]

This paper considers the problem of determining the policy to be followed by each member of a team so as to optimize some over-all criterion function characterizing the objective of the team. The reasoning of dynamic programming is employed to formulate the optimization problem, and the discussion is couched in the terms of a classical network problem. The paper first formulates a simple bipartite network optimization and then presents a number of generalizations. Finally, it gives two slightly different computational solutions to an example bipartite optimization problem. [ABSTRACT FROM AUTHOR]

The main result of this paper is a group theoretic algorithm (GTIP2) for the integer programming problem. This algorithm is an extension of an algorithm from an earlier paper (part I). The algorithm in part I solves a group optimization problem derived from a given integer programming problem. The optimal solution to the group problem thereby obtained is an optimal solution to the integer programming problem if it is feasible. Unfortunately, an optimal solution to the group problem may yield an infeasible integer solution. The algorithm GTIP2 of this paper is an extension of the method of part I when it fails. In particular, GTIP2 employs a search procedure to find an optimal solution to the integer programming problem. The extent of the search is bounded by procedures derived from a variety of relevant group problems that are solved by the algorithm of part I. There is a discussion of the class of problems for which GTIP2 is primarily intended and the relation of GTIP2 to other algorithms is indicated. A numerical example and some partial computational results are included. [ABSTRACT FROM AUTHOR]

This paper develops a dynamic programming model for selecting an optimal combination of transportation modes over a multiperiod planning horizon. The formulation explicitly incorporates uncertainty regarding future requirements or demands for a number of commodity classes. In addition to determining the optimal modes to employ, the model assigns individual commodity classes to various modes, determines which supply points serve which destinations, and reroutes carriers from destinations to alternative sources where they will be most effective. The model is formulated as an optimal discrete time stochastic control problem where cost is quadratic and dynamic equations linear in the state and control variables. This model may be solved in closed form by an efficient dynamic programming algorithm that permits the treatment of relatively large scale systems. A iso developed is an alternative, generally suboptimal method of solution, based upon wiving a sequence of convex programming problems over time. This technique may be employed for a more general class of problems. In both methods the use of 'shadow prices' that arise is discussed. [ABSTRACT FROM AUTHOR]

This paper presents a version of Beale's Quadratic Programming Algorithm [1], [2] for solving a problem of maximizing a quadratic function under linear constraints. The modification discussed here makes it possible to retain the "inverse basis" tableau which has to be augmented by additional constraints to be called "auxiliary." The algorithm has been successfully tested on a computer. [ABSTRACT FROM AUTHOR]

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

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]

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]

In this paper we show that a bounded integer programming problem, with real data, can be replaced with another problem of the same dimension, with rational data, in such a way that the feasible solutions and optimal feasible solutions to the new problem are identical with those to the original problem. [ABSTRACT FROM AUTHOR]

GOMORY has transformed the integer programming problem into a related group optimization problem which can be more easily solved. An optimal solution to the group problem is optimal for the integer programming problem from which it is derived if the solution is feasible. An algorithm (IP Algorithm I) for solving the group optimization problem is developed, and sufficient conditions on its use are given. The usefulness of IP Algorithm I is extended by amending it to find alternative optima. In a subsequent paper, this algorithm is extended to an algorithm that can solve any integer programming problem. [ABSTRACT FROM AUTHOR]

In this paper (section 1) a two-phase procedure, the filter method or accelerated additive algorithm, is proposed for solving linear programs with zero-one variables. In Phase I an auxiliary problem is constructed that, in Phase II, is used to 'filter' the solutions to which the tests of the additive algorithm are to be applied. The filter method is then extended (section 2) by J. F. BENDERS' partitioning procedure to the mixed-integer zero-one case, as well as to general integer and mixed-integer programs. Finally, a specialized version of this method is used (section 3) to tackle a general machine-sequencing model, formulated as the problem of finding a mini-maximal path in a disjunctive graph. [ABSTRACT FROM AUTHOR]

A specific type of all-integer integer programming problem which seems to arise frequently in capital budgeting and other areas involves a zero-one restriction on the problem variables. Approaches to solutions to such problems by the General Lagrange Multiplier Method are discussed. This procedure, because of its relative simplicity, has certain advantages over other direct methods such as the use of integer programming algorithms, especially in areas such as capital budgeting where the constraints are usually not binding to the degree indicated by the problem statement. Throughout this paper, the Lorie-Savage problem in capital budgeting is used as a basis for the discussion. [ABSTRACT FROM AUTHOR]

A recent and significant addition to the literature of partial enumeration methods for solving integer linear programming problems has been the work of Balas. This paper describes some computational experience with a version of the algorithm and discusses future avenues of research that may be undertaken. [ABSTRACT FROM AUTHOR]

The generalized network problem and the closely related restricted dyadic problem are two special model types that occur frequently in applications of linear programming. Although they are next in order after pure network or distribution problems with respect to ease of computation, the jump in degree of difficulty is such that, in the most general problem, there exist no algorithms for them comparable in speed or efficiency to those for pure network or distribution problems. There are, however, numerous examples in which some additional special structure leads one to anticipate the existence of algorithms that compare favorably with the efficiency of those for the corresponding pure cases. Also, these more special structures may be encountered as part of larger or more complicated models. In tins paper we designate by topological properties two special structures that permit evolution of efficient algorithms. These follow by extensions of methods of Charnes and Cooper and of Dijkstra for the corresponding pure network problems. We obtain easily implemented algorithms that provide an optimum in one `pass' through the network. The proofs provided for these extended theorems differ in character from those provided (or not provided) in the more special 'pure' problem algorithms published. [ABSTRACT FROM AUTHOR]

This paper presents a method for developing efficient timetables for the operation of fixed schedule common-carrier passenger transportation systems. The ability to compute such timetables is needed in the consideration of planning alternatives for future transportation systems and/or the efficient operation of existing systems. Here, time- table optimization is accomplished by maximizing an objective function consisting of three basic components: operating costs, revenues, and traveler benefits. Traveler benefits are computed using a consumer preference model that specifies a traveler's willingness to pay for alternative trips, based on the scheduling of those trips. The optimization is based on successive iterations of a dynamic programming algorithm that develops timetables for each vehicle in the system. Solutions are termed optimal to within a 'first-order passenger exchange! Examples are presented to illustrate the utilization of the methodology for computing information relevant to the development of system operating policies and to the consideration of planning alternatives. [ABSTRACT FROM AUTHOR]

We consider the optimal lot size problem for multi-stage assembly systems where each facility may have many predecessors but only a single successor. Assumptions include constant continuous final product demand, instantaneous production, and an infinite planning horizon. Costs at each facility consist of a fixed charge per lot and a linear holding cost. Under the constraint that lot sizes remain time invariant, it is proven that the optimal lot size at each facility is an integer multiple of the lot size at the successor facility. This fact is used in the construction of a dynamic programming algorithm for the computation of optimal lot sizes. The algorithm exploits the concept of echelon stock [1], [2]. [ABSTRACT FROM AUTHOR]

Problem-solving procedures based on the methods of combinatorial programming are presented for solving a class of integer programming problems in which all elements are zero or one. All of the procedures seek first a feasible solution and then successively better and better feasible solutions until ultimately one is discovered which is shown to be optimal. By representing the problem elements in a binary computer as bits in a word and employing logical "and" and "or" operations in the problemsolving process, a number of problems involving several hundred integer variables have been solved in a matter of seconds. [ABSTRACT FROM AUTHOR]

The article presents a reply to a comment made on the paper on one-dimensional space allocation (ODSA) in programming. In a recent paper, developing an algorithm for ODSA, the author proved a lemma that essentially amounts to the linear segments of length and weighting, which are to be ordered on a line. The arrangement that minimizes the objective function is obtained by ordering the segments so that the quotients, length/weighting, form a non-increasing sequence. Professor Richard L. Francis has pointed out that this lemma has previously occurred in production-scheduling and notes that the facilities-to-locations assignment problem can be solved by a dynamic programming algorithm.