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 61 - 90 of 108
Full-Text Articles in Business Administration, Management, and Operations
Nonlinear Optimization Using The Generalized Reduced Gradient Method, Leon S. Lasdon, Richard L. Fox, Margery W. Ratner
Nonlinear Optimization Using The Generalized Reduced Gradient Method, Leon S. Lasdon, Richard L. Fox, Margery W. Ratner
Research Reports from the Department of Operations
Generalized Reduced Gradient methods are algorithms for solving nonlinear programs of general structure. This paper discusses the basic principles of GRG, and constructs a specific GRG algorithm. The logic of a computer program implementing this algorithm is presented by means of flow charts and discussion. A numerical example is given to illustrate the functioning of this program.
Computational Experience With An Enumerative Algorithm For The Set Covering Problem With Base Constraints, Harvey M. Salkin, Chien-Hua Lin
Computational Experience With An Enumerative Algorithm For The Set Covering Problem With Base Constraints, Harvey M. Salkin, Chien-Hua Lin
Research Reports from the Department of Operations
An algorithm for the classical set-covering problem with additional "base" constraints is presented. The "base" constrained set covering problem is: Minimize cx, subject to Ex ≥ e, xj = 0 or 1 (j = 1,...,n), and Bx ≤ d. Here E is an m by n matrix of zeros and ones, e is an m column of ones, c and d are nonnegative vectors, and B is a nonnegative array having row diagonal structure. The algorithm is basically a zero-one single branch enumeration with linear programming and other feasibility criteria. A "heuristic" is used which sometimes finds an initial solution …
Row Generalized Linear Programs, R. Chandrasekaran
Row Generalized Linear Programs, R. Chandrasekaran
Research Reports from the Department of Operations
A concept of row generalized linear programs is introduced. Illustrations of potential application for this concept are provided, along with methods for solving the row generalized linear program. The duality between row and column generalized linear programs is discussed.
The Complementarity Problem Of Mathematical Programming, Arie Tamir
The Complementarity Problem Of Mathematical Programming, Arie Tamir
Research Reports from the Department of Operations
We consider the nonlinear complementarity problem: Find x in R^n such that: x ≥ 0 , f(x) ≥ 0 (1) x^T(f(x))=0 (2) where f is a given mapping satisfying f(0) = 0 and q is a vector in R^n. We say that the problem is feasible if (1) has a solution. f is said to be a Q-function if (1)-(2) has a solution for each q in R^n, and it is a P-function if the solution is unique for each q. Classes of functions are defined using properties of the complementarity problem (1)-(2), and sufficient conditions which guarantee that a …
Optimal Flows In Networks With Positive Gains, Klaus Truemper
Optimal Flows In Networks With Positive Gains, Klaus Truemper
Research Reports from the Department of Operations
Simple, yet powerful non-simplex algorithms are developed for max flow and min-cost flow problems in networks with positive gains. It is shown that these algorithms are computationally better than existing non-simplex algorithms. A strong relationship between the min-cost flow problem in pure networks and the max flow problem in networks with positive gains is used to demonstrate how algorithms for one problem can be transformed into ones for the other problem.
One Machine Sequencing To Minimize Mean Flow Time With Minimum Number Tardy, Hamilton Emmons
One Machine Sequencing To Minimize Mean Flow Time With Minimum Number Tardy, Hamilton Emmons
Research Reports from the Department of Operations
The problem of sequencing n jobs on one machine is considered, under the multiple objective of minimizing mean flow time with the minimum number of tardy jobs. A simple procedure is first proposed to schedule for minimum flow time with a specified subset of jobs on time. This is used in conjunction with Moore's Algorithm in a simple heuristic producing good and often optimal schedules. A branch-bound algorithm is presented to produce the optimal schedule efficiently with the help of several theorems which eliminate much branching.
All-Integer Integer Programming Algorithms Applied To Tableaux With Rational Coefficients, Harvey M. Salkin, Shailesh J. Mehta, Pradip H. Shroff
All-Integer Integer Programming Algorithms Applied To Tableaux With Rational Coefficients, Harvey M. Salkin, Shailesh J. Mehta, Pradip H. Shroff
Research Reports from the Department of Operations
It is shown that an initial all integer tableau is not necessary to the convergence of primal all-integer integer programming algorithms. It is well known that an analogous result holds for Gomory's dual all integer method, where only the cost row is required to be integer. We also show that the cost row need not be integer for the convergence of Gomory's dual all integer method.
Integer Programming : Dual Fractional Mixed Integer Programming (Gomory [2]), Harvey M. Salkin
Integer Programming : Dual Fractional Mixed Integer Programming (Gomory [2]), Harvey M. Salkin
Research Reports from the Department of Operations
This work represents the fourth chapter of a forthcoming textbook “Integer Programming” to be written by Harvey M. Salkin and published by Addison-Wesley. The cutting plane algorithm for the mixed integer program, developed by Ralph Gomory in 1960 and presented in this chapter, is a direct extension of the integer programming algorithm discussed in Chapter 3. Again, the intent is to whittle the feasible region down to one whose optimal vertex has integer values for the integer-constrained variables. As before, the cutting plane technique utilizes the dual simplex method and allows fractional numbers in computation and is thus classified as …
Integer Programming : The Fixed Charge Problem The Plant Location Problem, Harvey M. Salkin
Integer Programming : The Fixed Charge Problem The Plant Location Problem, Harvey M. Salkin
Research Reports from the Department of Operations
This work represents the fourteenth chapter of a forthcoming textbook “Integer Programming” to be written by Harvey M. Salkin and published by Addison-Wesley. Contents: Algorithms: A branch and bound algorithm for the fixed charge problem; a branch and bound algorithm for the plant location problem.
Integer Programming : Dual Fractional Integer Programming (Gomory [10]), Harvey M. Salkin
Integer Programming : Dual Fractional Integer Programming (Gomory [10]), Harvey M. Salkin
Research Reports from the Department of Operations
This work represents the third chapter of a forthcoming textbook “Integer Programming” to be written by Harvey M. Salkin and published by Addison-Wesley. This chapter concerns itself with a cutting plane algorithm for the integer program which utilizes the dual simplex method and allows fractional numbers in computation - hence the "dual fractional" reference. We outline the basic approach for the integer program, extension to the mixed case appears in the next chapter.
Integer Programming : Dual All-Integer Integer Programming (Gomory [5]), Harvey M. Salkin
Integer Programming : Dual All-Integer Integer Programming (Gomory [5]), Harvey M. Salkin
Research Reports from the Department of Operations
This work represents the fifth chapter of a forthcoming textbook “Integer Programming” to be written by Harvey M. Salkin and published by Addison-Wesley. The cutting plane algorithm for the integer program presented in this chapter was developed by Ralph Gomory in 1960. Its similarity to the fractional method (Chapter 3) is principally due to the utilization of the lexicographic dual simplex method and to the maintenance of lexicographic positive columns in the tableau. The basic approach is, however, different from the fractional technique. There is no optimization, generating a constraint, reoptimization, etc. Rather, inequalities are generated at each iteration starting …
Integer Programming : The Set Covering Problem The Set Partitioning Problem, Harvey M. Salkin
Integer Programming : The Set Covering Problem The Set Partitioning Problem, Harvey M. Salkin
Research Reports from the Department of Operations
This work represents chapter 13 of a forthcoming book entitled “Integer Programming” to be written by Harvey M. Salkin and published by Addison-Wesley.
Integer Programming : Group Theory In Integer Programming, Harvey M. Salkin
Integer Programming : Group Theory In Integer Programming, Harvey M. Salkin
Research Reports from the Department of Operations
This work represents the eleventh chapter of a forthcoming textbook “Integer Programming” to be written by Harvey M. Salkin and published by Addison-Wesley.
Order-Preserving Allocation Of Jobs To Two Machines, Shailesh J. Mehta, R. Chandrasekaran, Hamilton Emmons
Order-Preserving Allocation Of Jobs To Two Machines, Shailesh J. Mehta, R. Chandrasekaran, Hamilton Emmons
Research Reports from the Department of Operations
In this paper, we consider the problem of minimizing the mean flow time of jobs to be processed on two machines. The jobs have a predetermined order, perhaps reflecting the order of arrival, and each job has a known processing time. We wish to assign the jobs to machines so as to minimize the mean flow time, with the constraint that the original order must be preserved within the subset of jobs assigned to each machine. An efficient algorithm based on dynamic programming is developed.
The Knapsack Problem: A Survey, Harvey M. Salkin, Cornelis A. De Kluyver
The Knapsack Problem: A Survey, Harvey M. Salkin, Cornelis A. De Kluyver
Research Reports from the Department of Operations
A unifying survey of the literature related to the knapsack problem; that is, maximize Σᵢvᵢxᵢ, subject to Σᵢwᵢxᵢ ≤ W, xᵢ ≥ 0, and xᵢ integer; where vᵢ, wᵢ and W are known positive integers. Various uses, including those in group theory and in other integer programming algorithms, as well as applications from the literature, are discussed. Dynamic programming, branch and bound, search enumeration, heuristic methods, and other solution techniques are presented. Computational experience, and extensions of the knapsack problem, such as to the multi-dimensional case, are also considered.
Set Covering: Uses, Algorithms, Results, Harvey M. Salkin, Jahar Saha
Set Covering: Uses, Algorithms, Results, Harvey M. Salkin, Jahar Saha
Research Reports from the Department of Operations
An up to date survey of the set covering literature. Applications, (useful) theoretical results, algorithms, computational experience, and existing computer programs are described. The relationships between set covering problems and graphs are also discussed. No attempt is made to detail proofs or algorithm development, but rather an understandable, somewhat brief, unifying survey is presented.
Results On Matroids, Blocking Systems And Convex Sets, Bradley Hull
Results On Matroids, Blocking Systems And Convex Sets, Bradley Hull
Research Reports from the Department of Operations
Two algorithms for matroids are presented, and relations between matroids and blocking systems are explored. A method is presented for removing an element of one of the dual pairs of clutters which comprise a blocking system. The problem of how to "chop off" a vertex from a convex polyhedron without creating new vertices is dealt with. Bounds on the number of cutting planes are determined.
School Bus Routing By Integer Programming, Dynamic Programming, And Composite Algorithms, Harvey M. Salkin, Patrice Breining
School Bus Routing By Integer Programming, Dynamic Programming, And Composite Algorithms, Harvey M. Salkin, Patrice Breining
Research Reports from the Department of Operations
This paper proposes several models, and outlines seemingly efficient techniques for the school bus routing problem. Given the number of schools, buses and their capacities, the number of children, their location and destination, and distances or times between stops, the problem is to design a "best" (several criteria are given) series of bus routes. An integer programming, a dynamic programming, and several composite models and algorithms are proposed. By making reasonable assumptions computer storage problems may be substantially alleviated and implementation is possible in each case. As the problem is usually enormous, emphasis is placed on producing "good" solutions to …
Binding Inequalities In Benders' Partitioning Algorithm, Harvey M. Salkin
Binding Inequalities In Benders' Partitioning Algorithm, Harvey M. Salkin
Research Reports from the Department of Operations
The mixed integer program is transformed to its equivalent integer program which has a vast number of "z inequality" constraints. A brief description of Benders' partitioning algorithm for the mixed integer program, which is suggested by the transformation, is then given. It is shown that unless a bounding constraint is explicitly introduced, a z inequality (hyperplane) that does not intersect an optimal solution to the integer program which appears in the algorithm cannot be dropped. Furthermore, if the bounding constraint is used in place of keeping not binding inequalities, the algorithm may converge at a slower rate. A small plant …
A Solution To A Special Class Of Flow Shop Scheduling Problems, Michael S. Salvador
A Solution To A Special Class Of Flow Shop Scheduling Problems, Michael S. Salvador
Research Reports from the Department of Operations
This research considers the most general type of "network" flow shop in which jobs pass through each of m > 2 stages, where the ith stage is composed of ni ≥ 1 identical processors. Jobs are processed on one processor at each stage in ascending order of stage numbers and the objective is minimization of makespan. The class of shops considered includes those where in-process inventory is prohibited and the sequence of jobs processed on a particular processor is required to be a subsequence of the jobs entering the shop; without these additional constraints, algorithmic solutions are available only for the …
Note On Finite Convergence Of Exterior Penalty Functions, Klaus Truemper
Note On Finite Convergence Of Exterior Penalty Functions, Klaus Truemper
Research Reports from the Department of Operations
It is shown that existence of a saddlepoint of the Lagrangian function in an optimization problem is sufficient to assure finite convergence of a special exterior penalty function. Also, an estimate of the penalty weight is given that yields finite e-convergence for the quadratic exterior penalty function. [Likely published circa 1972.]
Algorithms For Discounted Stochastic Games: A Comparison Of Efficiency, Vijaykumar V. Aggarwal
Algorithms For Discounted Stochastic Games: A Comparison Of Efficiency, Vijaykumar V. Aggarwal
Research Reports from the Department of Operations
There are two algorithms for the solution of two person zero sum stochastic games with a finite number of states or positions and where future payoffs are discounted. The first algorithm is on somewhat similar lines as that of Hoffman and Karp for the undiscounted case, and the second one is recently developed by Rao, Chandrasekaran and Nair. 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. …
A Dual All-Integer Algorithm (In Revised Simplex Form) For The Set Covering Problem, Harvey M. Salkin, Ronald D. Koncal
A Dual All-Integer Algorithm (In Revised Simplex Form) For The Set Covering Problem, Harvey M. Salkin, Ronald D. Koncal
Research Reports from the Department of Operations
In an earlier work ("A Pseudo Dual All-Integer Algorithm for the Set Covering Problem", Department of Operations Research Tech. Memo. No. 204, CWRU, Nov. 1970) the authors developed a composite dual simplex-Gomory all integer algorithm for the (inequality or equality) set covering problem (i.e., minimize cx subject to Ex >= e or Ex = e, xj = 0 or 1; where E is an m by n zero-one matrix, e is a column of ones, and c is a nonnegative integral row). Essentially the algorithm performs dual simplex iterations whenever unit pivots are available and it adjoins Gomory all integer …
Algorithms For Discounted Stochastic Games, S. Subba Rao, R. Chandrasekaran, K.P. K. Nair
Algorithms For Discounted Stochastic Games, S. Subba Rao, R. Chandrasekaran, K.P. K. Nair
Research Reports from the Department of Operations
In this paper, a two person zero sum stochastic game with a finite state space is considered. The movement of the game from state to state is jointly controlled by the two players depending on their choice of strategies from a finite number of alternatives available to each player in each of the states. Considering an infinite number of transitions, Hoffman and Karp provided a convergent algorithm for the solution of this game when the future payoffs are not discounted. Subsequently, the authors presented a proof for a faster algorithm available in literature for solving the same problem. This paper …
Reduction Of Dimensionality In Dynamic Programming Of Higher Dimensions: A Comparative Study And Analysis Of Computational Aspects, Augustine O. Esogbue, Amar J. Singh
Reduction Of Dimensionality In Dynamic Programming Of Higher Dimensions: A Comparative Study And Analysis Of Computational Aspects, Augustine O. Esogbue, Amar J. Singh
Research Reports from the Department of Operations
One of the noble aims of dynamic programming at its conception -- namely, that of developing an operational method for the numerical solution of various control problems, is often thwarted for meaningfully scaled systems, by the curse of dimensionality. By far the most important contribution to modern dynamic programming is the development of efficient algorithms capable of being used, with present-day computational devices, to solve problems of a large-scale nature. Consequently, a number of algorithms have appeared in the literature in recent times, each geared towards ameliorating the above curse. The purpose of this paper is to present a didactic …
The Optimal Choice Of Corporate Growth Plans Under Risk, Roy B. Larson
The Optimal Choice Of Corporate Growth Plans Under Risk, Roy B. Larson
Research Reports from the Department of Operations
This study develops a sequence of five progressively realistic computational models for optimizing corporate growth plans under risk, combining advancements in security evaluation and capital budgeting. The final model integrates investment, financing, and dividend policy alternatives to maximize firm market value using a mathematical programming approach. Supporting contributions include a review of corporate planning practices in U.S. firms, analysis of corporate objectives, and enhancements to Weingartner’s programming model for growth plan selection. The Sharpe index model for portfolio selection is extended to a multi-period risk framework, while novel algorithms, MIC(X) and PMIC(Xs, Xb), address mixed-integer convex nonlinear programming problems. These …
Integer Programming : Dual All-Integer Integer Programming (Gomory [2]), Harvey M. Salkin
Integer Programming : Dual All-Integer Integer Programming (Gomory [2]), Harvey M. Salkin
Research Reports from the Department of Operations
This work represents the sixth chapter of a forthcoming textbook “Integer Programming” to be written by Harvey M. Salkin. The cutting plane algorithm for the integer program presented in this chapter was developed by Ralph Gomory in 1960. Its similarity to the fractional method (Chapter 3) is principally due to the utilization of the (lexicographic) dual simplex method and the maintenance of (lexicographic) positive columns. The basic approach is, however, different from the fractional technique: there is no optimization, generating a constraint, reoptimization, etc. Rather, inequalities are generated at each iteration starting with the very first. Further, each of these …
Computational Experience With A Traveling Salesmen Algorithm, Joseph A. Svestka, Vaughn E. Huckfeldt
Computational Experience With A Traveling Salesmen Algorithm, Joseph A. Svestka, Vaughn E. Huckfeldt
Research Reports from the Department of Operations
A formulation of the traveling salesman problem with more than one salesman is offered. The particular formulation has computational advantages over other formulations. Experience is obtained with an exact branch and bound algorithm employing both upper and lower bounds (mean run time for 55 city problems is one minute). Due to the special formulation, certain subtours may satisfy the constraints, thus reducing the search. A very good initial tour and upper bound are employed. The determination of these as well as the pathology of the formulation and the algorithm are discussed. No increase in computation time over the one salesman …
Integer Programming : Dual Fractional Mixed Integer Programming (Gomory [2]), Harvey M. Salkin
Integer Programming : Dual Fractional Mixed Integer Programming (Gomory [2]), Harvey M. Salkin
Research Reports from the Department of Operations
This work represents the fourth chapter of a forthcoming textbook “Integer Programming” to be written by Harvey M. Salkin. The mixed integer programming algorithm developed by Ralph Gomory in 1960 and presented in this chapter is a direct extension of the integer programming algorithm discussed in Chapter 3. As before, the cutting plane technique utilizes the dual simplex method and allows fractional numbers in computation and is thus classified as "dual fractional." For ease of reference, we rewrite the basic approach.
Integer Programming : Dual Fractional Integer Programming (Gomory [3]), Harvey M. Salkin
Integer Programming : Dual Fractional Integer Programming (Gomory [3]), Harvey M. Salkin
Research Reports from the Department of Operations
This work represents the third chapter of a forthcoming textbook “Integer Programming” to be written by Harvey M. Salkin. This chapter concerns itself with a cutting plane algorithm for the integer program which utilizes the dual simplex method and allows fractional numbers in computation - hence the "dual fractional" reference. We outline the basic approach for the integer program extension to the mixed case appears in the next chapter.