Open Access. Powered by Scholars. Published by Universities.®
Business Administration, Management, and Operations Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Institution
- Publication Year
Articles 91 - 108 of 108
Full-Text Articles in Business Administration, Management, and Operations
An Efficient One-Dimensional Search Procedure For Barrier Function, Leon S. Lasdon, Richard L. Fox, Margery W. Ratner
An Efficient One-Dimensional Search Procedure For Barrier Function, Leon S. Lasdon, Richard L. Fox, Margery W. Ratner
Research Reports from the Department of Operations
Interior penalty functions are a popular approach for solving non-linear constrained optimization problems. Most current methods for minimizing such functions require a one-dimensional minimization along specified search directions, and this can be quite difficult, since the function approaches +∞ along the boundaries of the feasible set. A special purpose algorithm is described which alleviates this difficulty by using a simpler approximating function which also goes to infinity near the boundary. Numerical results are presented, showing that the number of function evaluations and computation time are reduced by factors of about three and two respectively. The ideas are easily extended to …
Algorithms For Stochastic Games: A Comparison Of Efficiency, Arvind Jain
Algorithms For Stochastic Games: A Comparison Of Efficiency, Arvind Jain
Research Reports from the Department of Operations
There are two convergent algorithms for the solution of two person zero sum nonterminating stochastic games. The first one is developed by Hoffman and Karp and the second one is recently developed by Nair, Rao and Chandrasekaran. This paper presents computer programs for the two algorithms and computational experiments for comparing the efficiency of the algorithms. The results show that the second algorithm requires fewer iterations and moreover, the computation time for each iteration in this is significantly lower. Further, the results show that the ratio of the computation of time of the first algorithms to that of the second …
A Faster Algorithm For Nonterminating Stochastic Games, K.P. K. Nair, S. Subba Rao, R. Chandrasekaran
A Faster Algorithm For Nonterminating Stochastic Games, K.P. K. Nair, S. Subba Rao, R. Chandrasekaran
Research Reports from the Department of Operations
In this paper a two person zero sum nonterminating stochastic game with a finite number of positions or states is considered. The movement of the game from state to state is jointly controlled by the two players depending on their choices of strategies from a finite number of alternatives in each state available to each player, respectively. Considering an infinite number of transitions, Hoffman and Karp have provided a convergent algorithm for the solution of this game. This paper presents a new convergent algorithm for the solution of the above game. The proof of convergence shows also the existence of …
Dynamic Programming And Fuzzy Allocation Processes, Augustine O. Esogbue, Vengalathur Ramesh
Dynamic Programming And Fuzzy Allocation Processes, Augustine O. Esogbue, Vengalathur Ramesh
Research Reports from the Department of Operations
The modeling and computational aspects of certain allocation processes are studied through a new concept in systems theory --- fuzzy decision making. The use of these concepts will generally provide models of better proximity to the systems modelled than the traditional deterministic and stochastic approaches. Some concepts of fuzzy systems theory are first introduced. Fuzzy dynamic programming models with their corresponding flow charts are then provided for an allocation problem arising in R&D systems. The computational problems in fuzzy algorithms are discussed. An extensive bibliography on fuzzy decision theory is included.
A Pseudo Dual All-Integer Algorithm For The Set Covering Problem, Harvey M. Salkin, Ronald D. Koncal
A Pseudo Dual All-Integer Algorithm For The Set Covering Problem, Harvey M. Salkin, Ronald D. Koncal
Research Reports from the Department of Operations
A modified linear programming method for the inequality or equality set covering problem (i.e., minimize cx subject to Ex ≥ b or Ex = b, where E is a zero-one matrix, b is a column of ones, and c is a nonnegative integral row) is presented. The "almost unimodular" property of the (zero-one) constraint matrix suggested an algorithm in which one performs (dual) simplex interactions whenever unit pivots are available and adjoin Gomory all-integer cuts when they are not. Finiteness, time reducing criteria, the elimination of roundoff errors, and applications to enumerative schemes are discussed. Preliminary computational experience, being very …
Non Iterative Algorithm Form Solving Special Types Of Transportation Problems, Benjamin Lev
Non Iterative Algorithm Form Solving Special Types Of Transportation Problems, Benjamin Lev
Research Reports from the Department of Operations
Many transportation problems are such that, when origins and destinations are suitably indexed, the cost matrix contains elements along the main diagonal, a band above it, and a band below it, while the other elements of the cost matrix are infinite. A procedure has been developed which yields optimal solution to such tridiagonal problems in n steps for a n-origin, n-destination problem. A second model has been solved for a tridiagonal and a coupling column of the cost matrix. A third model, a four-diagonal one, has been partially solved. We suggested and showed a method to solve any other model …
A Primal Method For Linear Programs With Coupling Rows And Columns, James K. Hartman
A Primal Method For Linear Programs With Coupling Rows And Columns, James K. Hartman
Research Reports from the Department of Operations
A considerable amount of work has been done in recent years on adapting the simplex method for linear programming to solving II large-scale specially structured linear programs. One class of methods which has proved to be quite useful in practice is the class of compact inverse methods ([16], Chapter 6). In these S methods, the special structure of the constraint matrix is 8 exploited to obtain a representation of the basis inverse matrix 1 which is more compact than the explicit inverse used in the revised simplex method. .Early proposals for this type of algorithm are found in [1] and …
A Generalized Upper Bounding Method For Doubly Coupled Linear Programs, James K. Hartman, Leon S. Lasdon
A Generalized Upper Bounding Method For Doubly Coupled Linear Programs, James K. Hartman, Leon S. Lasdon
Research Reports from the Department of Operations
The constraints of large linear programs can often be partitioned into independent subsets, except for relatively few coupling rows and coupling columns. The individual subsets may, for example, arise from constraints on the activity levels of subdivisions of a large corporation. Alternatively, such blocks may arise from activities in different time periods. The coupling rows may arise from limitations on shared resources or from combining the outputs of subdivisions to meet overall demands. The coupling columns arise from activities which involve different time periods (e.g storage), or which involve different subdivisions (e.g. transportation or assembly). The case with only coupling …
A Generalized Upper Bounding Algorithm For Multicommodity Network Flow Problems, James K. Hartman, Leon S. Lasdon
A Generalized Upper Bounding Algorithm For Multicommodity Network Flow Problems, James K. Hartman, Leon S. Lasdon
Research Reports from the Department of Operations
An algorithm for solving min cost or max flow multicommodity flow problems is described. It is a specialization of the simplex method, which takes advantage of the special structure of the multicommodity problem. The only non-graph or non-additive operations in a cycle involve the inverse of a working basis, whose dimension is the number of currently saturated arcs. Efficient relations for updating this inverse are derived.
A Special Case Of The Complementary Pivot Problem, R. Chandrasekaran
A Special Case Of The Complementary Pivot Problem, R. Chandrasekaran
Research Reports from the Department of Operations
This paper addresses a fundamental problem in linear programming, quadratic programming, and bimatrix games: solving a system involving vectors w and z, subject to complementarity and non-negativity constraints. Existing algorithms solve this problem when the matrix M meets specific properties such as being positive semi-definite, copositive-plus, or adequate. The paper extends the problem to a broader class of matrices, including L-matrices, which are not necessarily copositive-plus, adequate, or positive semi-definite. An efficient algorithm is introduced to solve the problem for this generalized class, and its steps and correctness are detailed.
Enumerative Algorithms For Integer And Mixed Integer Programs, Harvey M. Salkin
Enumerative Algorithms For Integer And Mixed Integer Programs, Harvey M. Salkin
Research Reports from the Department of Operations
This thesis presents two flexible zero-one integer programming (single branch enumerative) algorithms. It is shown that the first method, applicable to the general program (i.e., min.(c'y: Ay<=b, y_j=0 or 1) ), has the ability, via a new dynamic origin technique, to adapt to the problem data. Other pioneering features, which assist in curtailing the length of the search, are linear programming, post optimization, and criteria for selecting branches from feasible nodes. Using this approach as a foundation, an extension for the mixed integer program (i.e., min.(c'y+d'x: Ay+Dx<=b, x>=0, y_j=0 or 1) ) is discussed. The second algorithm, applicable to the set covering problem (i.e., min.(c'y: Ry>=e, y>=0, y integer); where R is a matrix of 0's and 1's, and e is a vector of 1's), basically obtains upper and lower bounds on the integer problem from the associated linear program. It is shown, by certain proved facts, that one can always obtain two (and sometimes three) integer feasible …
Efficient Methods For Unconstrained Minimization, Leon S. Lasdon
Efficient Methods For Unconstrained Minimization, Leon S. Lasdon
Research Reports from the Department of Operations
It is now well known that the most efficient methods for unconstrained minimization which do not require second derivatives are those which, when applied to a quadratic, generate conjugate directions [1-4]. This insures that a quadratic in n variables is minimized in n steps or less. Since a general twice differentiable function behaves like a positive semidefinite quadratic in the neighborhood of its minimum, methods which will minimize it efficiently must work well on a quadratic. Conjugate direction methods meet this requirement, do not require second derivatives, and can be constructed so that the function is reduced at each step. …
The Design Of Markovian Congestion Systems, Hillel Jeremy Kumin
The Design Of Markovian Congestion Systems, Hillel Jeremy Kumin
Research Reports from the Department of Operations
An algorithm is proposed for the design of a class of Markovian congestion systems. The class is characterized by almost triangular transition matrices. A feature of the algorithm is that it does not utilize closed-form expressions for the steady-state behavior of the system. Convergence is discussed, and the results of numerical experimentation are provided. A behavioral result is also obtained for this class of systems.
On The Budget Decrement Problem, T.S. Chidambaram
On The Budget Decrement Problem, T.S. Chidambaram
Research Reports from the Department of Operations
A model for dealing with the Army budget decrement problem is proposed. A simple algorithm is developed based on the assumption that the original allocation is optimal. Kuhn-Tucker theory in non-linear programming is used to show that this algorithm reaches the revised optimal solution in a finite number of iterations.
The Multidimensional Assignment Problem, William P. Pierskalla
The Multidimensional Assignment Problem, William P. Pierskalla
Research Reports from the Department of Operations
The multidimensional assignment problem is a higher dimensional version of the standard (two-dimensional) assignment problem in the literature. The higher dimensions can be thought of as time or space dimensions or both. An algorithm is proposed for the solution of the multi-index assignment problem. The algorithm is based on a tree search technique of the branch-and-bound variety. It uses dual subproblems to provide easily computed bounds for the primal assignment problem.
The Multi-Dimensional Assignment And Quadratic Assignment Problems, William P. Pierskalla
The Multi-Dimensional Assignment And Quadratic Assignment Problems, William P. Pierskalla
Research Reports from the Department of Operations
The multi-dimensional assignment problem is a higher dimensional version of the standard (two-dimensional) assignment problem in the literature. The higher dimensions can be though of as time or space dimensions or both. An algorithm is proposed for the solution of the multi-index assignment problem. The algorithm is based on a tree search technique of the branch and bound variety. It uses dual subproblems to provide easily computed bounds for the primal assignment problem. The same algorithm with appropriate modifications is used to find an optimal solution to the multi-dimensional quadratic assignment problem.
A Computational Algorithm For A Class Of Dynamic Programming Problems, B. Miller, Daniel Teichroew
A Computational Algorithm For A Class Of Dynamic Programming Problems, B. Miller, Daniel Teichroew
Research Reports from the Department of Operations
This paper describes an algorithm for finding the optimum value of a decision variable in the standard dynamic programming recurrence equation, when the state is described by one variable and the return function and state transition function are both linear one-to-one functions of the decision variable. The approach has been successfully programmed for a class of dynamic programming problems and has been found to be computationally much faster than searching over a set of possible decision values, even when the Fibonacci search method (the fastest search method available) is used. [Likely published circa 1966.]
Mathematical Programming With Joint Stochastic Constraints, Pierre J. Doulliez
Mathematical Programming With Joint Stochastic Constraints, Pierre J. Doulliez
Research Reports from the Department of Operations
In the present thesis, we want to show that a programming problem with joint stochastic constraints can be treated generally and under relatively simple conditions, as a quasi-concave programming problem. In some cases, the same problem may be equivalent to a concave programming problem after a logarithmic transformation. It has been shown by Charnes and Cooper that a stochastic programming problem where each constraint has to be achieved with a given probability, can be put under the form of a deterministic programming problem which is concave under some assumptions [1]. The "joint chance-constraint" formulation presented here is less restrictive and …