Search

This paper describes a two-person zero-sum game in function space concerning the optimal allocation of a homogenous defense force on different levels of readiness. The second player, the attacker, wants to determine the time for the attack such that the cost is minimized. As the defense is subject to attrition, a delay is preferable for the attacker. This is balanced, however, by a delay cost which increases with time. The existence of a solution consisting of a pure defense strategy and a mixed strategy for the attack time is proved elsewhere. This paper mainly treats an approximation of the game with a time-discrete version for which an algorithm is derived. Arbitrarily close upper and lower bounds of the value of the original game can be obtained by the algorithm, as well as feasible defense and attacker strategies that realize these value estimates. Computational results are given for two simple problems, one of which is also solved analytically. [ABSTRACT FROM AUTHOR]

This paper develops a methodology to evaluate various aspects of logistics supply support of space bases. It is assumed that there exists at the space base a schedule of operations that reflects the day-to-day living, build-up, and scientific experimental activities that are to be carried on. These activities, in turn, set a series of demands or requirements for products over a time spectrum. The supply system must deliver products so as to meet the amounts and times of the product requirements. Each product or module has an earliest and latest time by which it must be delivered. A mathematical model is developed that plans a series of trips, the dates at which each is to be sent, and the composition of the cargoes on each trip that satisfy the series of requirements over a time spectrum imposed by the activities at the space base. The series of trips are an expression of an efficient plan that simultaneously considers demands for different products at different future times and observes the various constraints of the system (e.g., cargo capacity of spaceships). The mathematical formulation of this scheduling problem is a simple non- linear discrete programming problem. An algorithm has been developed for its solution, and a description thereof is presented. The model is illustrated by showing how it would supply a long-term lunar base. Various uses of the model are described. [ABSTRACT FROM AUTHOR]

Following a line of approach recently applied to the 0-1 integer programming problem with some success by EGON BALAS, the algorithm of this paper is based upon an underlying tree-search structure upon which a series of tests is superimposed to exclude large portions of the tree of all possible 0-1 solutions from examination. In our method, the specific design of the enumeration and tests, supplemented by the use of a special type of constraint called a 'surrogate constraint,' results in an algorithm that appears to be quite efficient in relation to other algorithms currently available for solving the 0-1 integer programming problem. Early indications of efficiency must, however, be regarded as suggestive rather than conclusive, due to the limited range and size of problems so far examined. Following the analytical development of the method, three example problems are solved in detail with the Multiphase-Dual Algorithm to illustrate various aspects of its application. An extension of the algorithm to the general integer programming problem in bounded variables is briefly sketched in a concluding section. [ABSTRACT FROM AUTHOR]

This paper summarizes experimental results from applying several computational methods for solving the classic three-machine scheduling model. The basic mathematical problem is to select an optimal permutation of a items, where the objective function employed is the total amount of processing time elapsing for the completion of all n items on three machines. The methods tested are integer linear programming, ordinary linear programming with answers rounded to integers, a heuristic algorithm, and random sampling. Throughout the experimentation n=6. A dual integer programming code is tested on six trial problems. Consideration is given to studying the phenomenon of input-form sensitivity. The results are not encouraging and confirm previous experimental evidence as to the strong effect of varying the input form. However, the addition of a powerful bound on the objective function has a significant beneficial effect on the convergence of the dual algorithm. A sampling study of the statistical characteristics of this model is made with 100 sets of data randomly generated. Frequency distributions of minimum and mean total processing time are tabulated and analyzed. On this same set of problems, a linear programming approach is examined for effectiveness in producing nearly optimal schedules. Such an approach tends to give answers that are better than would be obtained by a single permutation drawn at random, but the LP rounded solutions average about an 11 per cent increase over the optimal processing time. A heuristic algorithm based on Johnson's method is tested on 20 of the 100 eases and gives excellent results. Finally attention is turned to the method of randomly sampling the permutations, possibly applying a simple heuristic gradient method to improve each sampled schedule. A feature of this method is that elementary probability theory can be applied to yield corresponding statements about the accuracy guaranteed by the approach. [ABSTRACT FROM AUTHOR]

Because the payload that an airplane can carry is a function of the longest segment of its route and differs from route to routes the usual algorithms of network flow theory will not yield the optimum flow of payload. In this paper two network algorithms are described. They determine the route of maximum payload flow per hour of flight time and the maximum steady- state payload flow through a network with capacity constraints on the nodes,. [ABSTRACT FROM AUTHOR]

The 'explosion' problem is the problem of determining the required components from knowledge of demand for finished products. The 'netting' problem IS the problem of determining the net requirements of these components, for purposes of production or procurement from outside the firm, based on available inventory. This paper presents a simple algorithm which yields the 'netted explosion. 'The algorithm is suitable for digital computation in case of large inventories. [ABSTRACT FROM AUTHOR]

This paper studies the close relation between the Gass-Saaty parametric programming algorithm and the `primal-dual' procedures recently exploited by DANTZIG, FORD, AND FULKERSON lit is shown that the two procedures are equivalent The possibility of eliminating the two-phase character of the simplex method using these techniques is discussed Finally, the application of the techniques to problems with special structure is considered [ABSTRACT FROM AUTHOR]

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]

In their paper [1], Doulliez and Rao present algorithms that solve two flow problems for a single source, multi-terminal network. The first problem that they solve is the construction of a flow that maximizes the value of t, where the demand at each sink is a nondecreasing, linear function of t. Given such a flow, the second problem that they solve is the construction of a flow that maximizes the value of t when the capacity of an arc is reduced. This paper supplies a finiteness proof for the first algorithm and sketches a finiteness proof for the second algorithm. The proofs are based on the well-known fact that a network possesses only a finite number of different spanning trees. [ABSTRACT FROM AUTHOR]

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

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

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

This paper presents an in-depth computational comparison of the basic solution algorithms for solving transportation problems. The comparison is performed using "state of the art" computer codes for the dual simplex transportation method, the out-of-kilter method, and the primal simplex transportation method (often referred to as the Row-Column Sum Method or M O D I method). In addition, these codes are compared against a state of the art large scale LP code, O P H E L I E/LP. The study discloses that the most efficient solution procedure arises by coupling a primal transportation algorithm (embodying recently developed methods for accelerating the determination of basis trees and dual evaluators) with a version of the Row Minimum start rule and a "modified row first negative evaluator" rule. The resulting method has been found to be at least 100 times faster than OPHELIE, and 9 times faster than a streamlined version of the SHARE out-of-kilter code. The method's median solution time for solving 1000 X 1000 transportation problems on a CDC 6600 computer is 17 seconds with a range of 14 to 22 seconds. Some of the unique characteristics of this study are (1) all of the fundamental solution techniques are tested on the same machine and the same problems, (2) a broad spectrum of problem sizes are examined, varying from 10 X 10 to 1000 X 1000; (3) a broad profile of nondense problems are examined ranging from 100 percent to 1 percent dense; and (4) additional tests using the best of the codes have been made on three other machines (IBM 360/65, UNIVAC 1108, and CDC 6400), providing surprising insights into conclusions based on comparing times on different machines and compilers. [ABSTRACT FROM AUTHOR]

A multi-stage linear program is defined with linking variables that connect consecutive stages. Optimality conditions for the composite problem are partitioned into local and linking conditions. When the Dantzig-Wolfe decomposition scheme is applied with the first stage as the master, the subproblem is also a MLP with one less stage. The same decomposition is then applied to the subproblem, giving rise to a nested decomposition scheme, in which each stage acts as a master for the following stage and a subproblem for the preceding. Optimizing a single stage problem results in satisfying the "local" optimality conditions. A very general rule is given for selecting the next subproblem to optimize, and finite convergence to a solution satisfying all linking conditions is demonstrated. Procedures for extracting the optimal primal solution at the end of the main algorithm and for initialization are given. Particular rules for selecting the next subproblem and for generating additional proposal vectors are discussed. Finally, it is shown how a variety of problems may be restructured as multi-stage linear programs to which this algorithm may be applied, and some computational experience is reported. [ABSTRACT FROM AUTHOR]

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

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

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

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

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

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

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

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

The multiparametric linear programming (MLP) problem for the right-hand sides (RHS) is to maximize z = cT x subject to Ax = b (λ), x ≧ 0, where b(λ) can be expressed in the form b(λ) = b* + Fλ, where F is a matrix of constant coefficients, and λ is a vector-parameter. The multiparametric linear programming (MLP) problem for the prices or objective function coefficients (OFC) is to maximize z = cT (v)x subject to Ax = b, where x ≧ 0, where c(v) can be expressed in the form c(v) = c* + Hv, and where H is a matrix of constant coefficients, and v a vector-parameter. Let Bi be an optimal basis to the MLP-RHS problem and Ri be a region assigned to Bi such that for all λ Ri the basis, Bi is optimal. Let K denote a region such that K = ui Ri , provided that the Ri for various i do not overlap. The purpose of this paper is to present an effective method for finding all regions Ri that cover K and do not overlap. This method uses an algorithm that finds all nodes of a finite connected graph. An analogous method is presented for the MLP-OFC problem. [ABSTRACT FROM AUTHOR]

This paper reports on an application of computer technology to a significant and costly school administration problem: the transportation of students between home and school. The problem, as it is generally thought of, has been complicated by the consideration of attempting racial balance via busing. We present an algorithm to find a feasible solution which tends to minimize the number of required routes and mileage. After setting down the basic approach used and the results of an application, we will present possible extensions of the approach to school location planning, bus fleets composition and timing conditions on particular bus stops. [ABSTRACT FROM AUTHOR]

This paper presents the results of comparing experimentally the performance of four of the more promising computer algorithms for the plant layout problem. CDC 3600 computer programs are tested with twenty-six test problems. The resulting solutions are evaluated in respect to both computer time requirements and objective function values. The experiment shows how these two performance measures vary with the algorithm used and various test problem characteristics. With the exception of two studies [4], [8], information on comparative performances of layout algorithms is very limited. [ABSTRACT FROM AUTHOR]

In this paper we apply the concept of generalized Lagrange multipliers, introduced by Everett [4], to the development of an algorithm for a one-period multiproduct production model, where the objective is to maximize profit subject to constraints on aggregate regular time and overtime production. We assume no difference between the cost of idle time and regular time labor, so that the regular time cost is fixed. Overtime cost is variable. The price for each product is constant (independent of quantity sold), and everything produced can be sold. The optimum production schedule (maximum profit) will depend upon revenues, overtime costs, setup times, and productivities. [ABSTRACT FROM AUTHOR]

The objective of this paper is the construction of a branch-and-bound algorithm for computing minimum cost flows in capacitated networks when the cost of passing a flow over an arc is concave. The method is based on the equivalence of the general network flow problem to a network flow problem in a bipartite network of a special form. An optimal flow is found by implicit enumeration of the set of extremal flows in that network. [ABSTRACT FROM AUTHOR]

This paper presents a method for taking into account dependency among certain activities in PERT networks. The method presented can be used with the reduction algorithm presented by Hartley and Wortham [1]. The addition of dependency among the completion times for certain types of activities should be a valuable aid in sensitivity analyses of PERT networks. [ABSTRACT FROM AUTHOR]

This paper gives efficient methods for solving four specially structured network problems that arise in connection with certain integer programming methods developed by Cook and Cooper, Hillier, and Glover. Such problems have also independently been studied in inventory theory by Ignall and Veinott, who have developed extensive qualitative (nonalgorithmic) implications of their structures. In the integer programming context, special subclasses of these network problems are generated and solved as part of a strategy for solving more general integer linear programs. By providing particularly efficient methods for accommodating somewhat broader network structures, our results enable the development of related integer programming solution strategies that generate more complex subproblems. We show that the first of the four network problems can be solved by a procedure that assigns each variable a value exactly once, without subsequent revision. Properties of optimal solutions for the remaining problems are developed that enable the algorithm for the first to be extended to the second and then, by suitable transformation of variables, to the third and last problems as well. Moreover, while the last three problems involve an additional linear constraint that nullifies the "integer extreme point property", we show that optimal integer solutions to these problems can nevertheless easily be obtained from the optimal continuous solutions. [ABSTRACT FROM AUTHOR]

In this paper the solution to the problem of placing n connected points (or nodes) in r-dimensional Euclidean space is given. The criterion for optimality is minimizing a weighted sum of squared distances between the points subject to quadratic constraints of the form X'X = 1, for each of the r unknown coordinate vectors. It is proved that the problem reduces to the minimization of a sum or r positive semidefinite quadratic forms which, under the quadratic constraints, reduces to the problem of finding r eigenvectors of a special "disconnection" matrix. It is shown, by example, how this can serve as a basis for cluster identification. [ABSTRACT FROM AUTHOR]

This paper describes a simple algorithm for the solution of very large sequence problems without the use of a computer. It produces approximate solutions to the n job, m machine sequencing problem where no passing is considered and the criterion is minimum total elapsed time. Up to m-1 sequences may be found. [ABSTRACT FROM AUTHOR]

The general practice in mixed model assembly line balancing is to assign work to stations in a manner that each station has an equal amount of work on a daily or shift basis. This paper shows how a modification to mixed model line balancing algorithms can be used so that the stations are loaded more consistently on a model by model basis as well. In addition, the modification now allows mixed model line balancing to become a plausible tool for hatched assembly line processes. The procedure is general in nature and is applicable to most line balancing algorithms. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for the solution of the knapsack problem. The method involves searching the nodes of a tree along a single branch at a time. The algorithm eliminates the computational drawbacks inherent in the usual branch and bound schemes. [ABSTRACT FROM AUTHOR]

If the constraint matrix of a linear program has special structure it may be possible to speed computation. Techniques have been developed to take advantages of such special structures as generalized networks, generalized upper bounding, and decomposition. For these matrix structures, it is shown in this paper how to extend the techniques to Zangwill's mathematical programming algorithm, the convex simplex method. [ABSTRACT FROM AUTHOR]

This paper considers an n-server queueing system with m customer classes distinguished by the reward associated with serving customers of that class. Our objective is to accept or reject customers so as to maximize the expected value of the rewards received over an infinite planning horizon. By making the assumptions of Poisson arrivals and a common exponential service time this problem can be formulated as an infinite horizon continuous time Markov decision problem. In §3 we customize the general algorithm for solving continuous time Markov decision problems to our queueing model. In §4 we obtain qualitative results about the form of the optimal policy. §6 reports the results of simulation tests which compare heuristic policies for our model when the service times associated with each customer class have arbitrary distributions. The ‘winning’ policy is based on a rather intricate theorem whose proof comprises §6. [ABSTRACT FROM AUTHOR]

There exists computational experience to the effect that search algorithms of the type introduced by Balas are frequently ineffective because of being tied to a rigid "natural" search origin. In this paper the dynamic relocation of the search origin to possibly more appropriate points is advocated. Details of such a procedure are given for the Simple Plant Location Problem. Computational improvements of, sometimes, a striking nature are presented. [ABSTRACT FROM AUTHOR]

This paper extends the algorithm developed by Hartley and Wortham [2] for the calculation of the c.d.f. of the critical time in a PERT network. Additional first order crossed networks and their operators are given. In addition, a technique for developing an integral operator for any PERT network is presented. [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]

In this paper we present an algorithm for solving mathematical programming problems of the form: Find x = (x[sub 1], ..., x[sub n]) to minimize Σφ[sub i] (x[sub i]) subject to x ε G and I ≤ x ≤ L. Each φ[sub i] is assumed to be lower semicontinuous, possibly nonconvex, and G is assumed to be closed. The algorithm is of the branch and bound type and solves a sequence of problems in each of which the objective function is convex. These problems correspond to successive partitions of the feasible set. Two different rules for refining the partitions are considered; these load to convergence of the algorithm under different requirements on the problem functions. Examples are given, and computational considerations are discussed. [ABSTRACT FROM AUTHOR]

During a pre-Christmas campaign in which daily sales are generally increasing, it is important to achieve a proper balance in advertising allocation between the final days of heavy sales and the earlier days of the campaign when sales are lighter but advertising might affect sales farther into the future. This paper presents a model of such a problem for two competing firms, an algorithm for solution of the model, numerical examples, and a proof of the algorithm. An equilibrium solution is found in which each firm applies the same proportioning vector to distribute its total advertising budget over the N days. [ABSTRACT FROM AUTHOR]

The article proposes an improvement on A.L. Gutjahr and G.L. Nemhauser's algorithm for the assembly line balancing problem. Gutjahr and Nemhauser have contributed an interesting and useful algorithm for the assembly line balancing problem. The two stages of their method are outlined, including the state generation--where all possible sets or combinations of work elements that are feasible first station assignments without regard to the cycle tune are listed, and the shortest route calculations--where arcs linking appropriate sets are generated. Several examples of the utilization of this method are presented.

This paper presents a method, called the convex simplex method, for minimizing a convex objective function subject to linear inequality constraints. The method is a true generalization of Dantzig's linear simplex method both in spirit and in the fact that the same tableau and variable selection techniques are used. With a linear objective function the convex simplex method reduces to the linear simplex method. Moreover, the convex simplex method actually behaves like the linear simplex method whenever it encounters a linear portion of a convex objective function. Many of the sophisticated techniques designed to enhance the efficiency of the linear simplex method are applicable to the convex simplex method. In particular, as an example, a network transportation problem with a convex objective function is solved by using the standard transportation tableau and by only slightly modifying the usual procedure for a linear objective function. [ABSTRACT FROM AUTHOR]

The Chebyshev problem is to determine a point χα which solves maxα min i = 1, ···, N{gi(χ)}. By exploiting generalized inverses an algorithm is developed for determining χα. It is also shown that in a certain sense the Chebyshev problem is equivalent to the concave programming problem. Moreover, for the programming problem generated by the Chebyshev problem, the Kuhn-Tucker conditions are proven to be sufficient even though the feasible region may not be convex. [ABSTRACT FROM AUTHOR]

It is generally recognized that reinforcement, over an extended period of time of a given subject matter taught, enhances the student's mastery and subsequent retention of knowledge and/or skills. Recent major studies of curricula have concentrated on the content and method of presentation but have not made any significant strides towards the systematic exploitation of the potential contribution to the learning process of reinforcement through proper sequencing of subject matter presentation. This paper outlines a mathematical model of the established and industrially validated learning and forgetting theories and presents a computer executed heuristic algorithm for the selection of the best schedule for subject presentation. Applications of this methodology can be made at all levels of our educational system; from the elementary grades through graduate school, in highly academic as well as vocational training programs. [ABSTRACT FROM AUTHOR]

Large graphs for which the calculation of the shortest distances between all vertices is required often consist of several parts with limited interconnections. This paper shows how this characteristic may be used to reduce computer storage for a matrix type calculation, to reduce calculational labour, and to provide results in a form which is particularly convenient if a subsequent assignment of commodity flow to shortest paths is needed. The technique presented here allows the partition to be arbitrary, save for a single, easily achieved, condition. [ABSTRACT FROM AUTHOR]

The general linear programming problem is considered in which the coefficients of the objective function to be maximized are assumed to be random variables with a known multinormal distribution. Three deterministic reformulations involve, respectively, maximizing the expected value, the α,-fractile (α fixed, 0 < α < ½), and the probability of exceeding a predetermined level κ of payoff. In this paper the author's previous work on "hi-criterion programs" is specialized to give an algorithm for routinely and efficiently solving the second and third reformulations. A by-product of the calculations in each ease is the tradeoff-curve between the criterion being maximized and expected value. The intimate relationships between all three reformulations are illuminated, with the cumulative effect of considerably lessening the burden on the decision-maker to preselect with finality a particular value of α or κ. [ABSTRACT FROM AUTHOR]

The technique described in this paper was devised for sequencing jobs on individual machines having characteristics of: (1) high job changeover costs; (2) small backlogs (10-20 jobs); (3) occasional "rush" orders. The algorithm starts with four-job sequences and from these constructs five-job sequences; from the five-job sequences, six-job sequences are constructed, and so on. At each stage, a large fraction of sequences are eliminated from further consideration. This elimination process makes the computation feasible because the number of all possible sequences becomes unmanageably large, even for small problems. The technique always provides a minimum cost sequence. It also permits determination of optimum sequences of backlog sub-sets; thus, rush orders can be accommodated and anticipated changes in the job backlog can be recognized. [ABSTRACT FROM AUTHOR]

A wide variety of branch and bound algorithms have recently been described in the literature. This paper provides a generalized description of such algorithms. An objective is to demonstrate the wide applicability of branch and bound to combinatorial problems in general. Two existing algorithms are used as illustrations and a discussion of computational efficiency is included. [ABSTRACT FROM AUTHOR]

This paper discusses the problem of assigning locations to indivisible facilities and its relation to the quadratic assignment problem. It also develops two suboptimal algorithms, one dealing with the general quadratic assignment problem and the other with an interesting special case. Qualitative and quantitative comparisons with existing suboptimal algorithms are presented. [ABSTRACT FROM AUTHOR]