Search

The main purpose of this paper is to delineate an algorithm for fractional programming with nonlinear as well as linear terms in the numerator and denominator. The algorithm presented is based on a theorem by Jagannathan [7] concerning the relationship between fractional and parametric programming. This theorem is restated and proved in a somewhat simpler way. Finally, it is shown how the given algorithm can be related to the method of Isbell and Marlow [6] for linear fractional programming and to the quadratic parametric approach by Ritter [10]. The Appendix contains a numerical example. [ABSTRACT FROM AUTHOR]

Commentary is presented for an article published in the July 1960 issue of "Management Science," written by L. V. Kantorovich with an introductory note by T. C. Koopmans. According to the author, in his introduction Koopmans addresses in particular a linear programming problem and a matrix game presented by Kantorovich. Also presented is an interpretation of the article's treatment of decision variables and mathematical optimization. The author notes that the article presents algorithms that have been improved from their contemporary presentations.

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

This paper studies the linear programming problem in which all coefficients (even those of the stipulations matrix) are rational functions of a single parameter t called ‘time,’ and provides an algorithm that can serve problems of the following two types: (1) Steady-state behavior [the algorithm can be used to determine the functional form x(t) of the optimal solution as a function of t, this form being valid for all ‘sufficiently large’ values of t], and (2) sensitivity analysis [if a value t0 of ‘time’ is given, the algorithm can be used to determine the two possible functional forms of the optimal solution for all values of t ‘sufficiently dose’ to t0 (the first functional form valid for t«t0, the second for t»t0)]. In addition, the paper gives certain qualitative information regarding steady-state behavior, including the following result: If for some one of the properties of consistency, boundedness, or bounded constraint set, there exists a sequence tn↗+∞ such that the linear program at tn has this property for all n, then the program has this property for all ‘sufficiently large’ values of t. [ABSTRACT FROM AUTHOR]

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

The multi-index transportation problem is defined and a summary of the algorithm described in an earlier paper is given. This paper discusses the theorems justifying the use of the algorithm and gives a necessary condition for the existence of a solution. It also describes the formulation of three special-structure linear-programming problems as examples of multi-index problems. The three problems discussed are the capacitated Hitchcock problem, transportation where there is more than one method of transport available, and the transformation of one type of multi-index problem into another. A final section describes problems that have restrictions in the form of inequalities. [ABSTRACT FROM AUTHOR]

This paper investigates the optimal allocation of the marketing budget within the marketing-mix decision variables so that sales (or profit) is maximized in a planning horizon. Since the influence of marketing mix variables upon sales are, in reality, nonlinear and interactive, a geometric programming algorithm is used that solves this problem. A procedure to estimate a functional of sales on the marketing mix and environmental variables utilizing the experienced judgments of the firm's executives and the raw data is provided. The derived functional is later optimized by the Geometric Programming algorithm under a constraint set consisting of budget and strategy restrictions imposed by a firm's marketing environment, and conditions under which the optimal solution is either local or global are identified. An empirical application for a large midwestern brewery is provided which utilizes and illustrates both the estimation an optimization procedures. [ABSTRACT FROM AUTHOR]

This paper deals with systems (such as electronic devices and corporations) that are designed to accomplish multiple goals and whose internal structures are characterized by networks of interacting component parts. Each component of such a system is typically associated with a probability of failure, while each system goal is associated with a reward value. Failure of any network component may ultimately result in the inability to achieve one or more goals and force the forfeiture of the associated rewards. A basic problem in component-system design is to determine how the expectation of total reward may be maximized through the cost-limited acquisition of redundant (backup) components. This paper provides a formal statement of this redundancy-optimization problem and argues that the problem may not be solved easily by standard linear or integer programming techniques. It introduces an algorithm to solve this problem, proves its convergence, and presents computational results taken from a battery of test problems and an algorithm-efficiency study based on these tests. [ABSTRACT FROM AUTHOR]

This paper develops a new cutting plane for primal integer programming. This cut, when it exists and is used as pivot row, has the property that the minimum of the simplex evaluators of the next tableau is strictly larger (by an integer) than the minimum for the current tableau. The paper gives a sufficient condition in the form of a linear program for the existence of such a cut, and proposes an algorithm for generating such cuts. It also presents two additional sufficient conditions. The process of cut generation is then imbedded into a convergent primal algorithm to be used in an attempt to overcome the proof-of-optimality problem experienced with the primal algorithm. [ABSTRACT FROM AUTHOR]

Copyright of INFOR is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

This paper gives a detailed description of an algorithm for the solution of a specialized Linear Programming model, to be called the Machine Loading model. It is a generalization of the Transportation Problem, in that weighting factors are applied to the individual elements which form the row and column sums. For the Machine Loading model, the simplex method reduces to a specialized algorithm which generalizes the stepping stone method of the Transportation Problem [2], [3]. With the resulting generalized stepping stone method, it becomes practicable to solve many large-scale problems for which the direct application of the simplex method would be impracticable. The present paper is restricted to a discussion of the following topics: (I) the general characteristics of the model and its topological features; (ii) a detailed solution algorithm, including a consideration of degenerate cases and the use of a computer; (iii) a more restrictive capacitated model and the corresponding modifications to the solution algorithm; and (iv) the complete illustrative solution of a numerical example. The purpose is to aid interested readers in gaining familiarity with the algorithm and facility in the solution of numerical problems. No derivations or proofs will be included. [ABSTRACT FROM AUTHOR]

The linear programing algorithms available for optimizing the routing of shipments in multi-plant, multi-destination systems cannot, in the current state of knowledge, be applied directly to the more general problem of determining the number and location of regional warehouses in large-scale distribution networks. This paper outlines a heuristic computer program for locating warehouses and compares it with recently published efforts at solving the problem either by means of simulation or as a variant of linear programing. The heuristic approach outlined in this paper appears to offer significant advantages in the solution of this class of problems in that it (1) provides considerable flexibility in the specification (modeling) of the problem to be solved, (2) can be used to study large-scale problems, that is, complexes with several hundred potential warehouse sites and several thousand shipment destinations, and (3) is economical of computer time. The results obtained in applying the program to small scale problems have been equal to or better than those provided by the alternative methods considered. [ABSTRACT FROM AUTHOR]

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

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

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

The article presents comments on the management science paper "On Sequencing n Jobs on One Machine to Minimize the Number of Late Jobs," by William L. Maxwell. The paper focused on an integer programming formulation of a one-machine job shop problem. The author contends that Maxwell made in error in proving the validity of an optimal algorithm by applying cutting plane constraints to the problem. The author explains that the problem cannot be solved through traditional cutting plane procedures. The author provides a mathematical model in an attempt to correct the proof.

This paper considers fluid analogues for the standard linear programming problem and for a separable nonlinear programming problem. In the former case the usual duality results are demonstrated using the principle of minimum potential energy. In addition by examining the dynamics of the system a new method, referred to as the R-method, is derived for solving linear programmes, although it is not demonstrated that this has any computational advantages over the standard simplex method, except that degeneracy causes no problems. In the nonlinear case the weak Lagrangian principle is derived. The purpose of the paper is to demonstrate that analogue methods, while being impracticable as a physical method of solving optimisation problems, may give some insight into computational algorithms via dual energy concepts and/or dynamic behaviour. [ABSTRACT FROM AUTHOR]

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

A framework of concepts is developed which helps to unify a substantial portion of the literature on large-scale mathematical programming. These concepts fall into two categories. The first category consists of problem manipulations that can be used to derive what are often referred to as "master" problems; the principal manipulations discussed are Projection, Inner Linearization, and Outer Linearization. The second category consists of solution strategies that can be used to solve the master problems, often with the result that "subproblems" arise which can then be solved by specialized algorithms. The Piecewise, Restriction, and Relaxation strategies are the principal ones discussed. Numerous algorithms found in the literature are classified according to the manipulation/strategy pattern they can be viewed as using, and the usefulness of the framework is demonstrated by using it (see Part II of this paper) to rederive a representative selection of algorithms. The material presented is listed in the following order: The first section is introductory in nature, and discusses types of large-scale problems, the scope of discussion and the literature, and the notation used. The second section, entitled "Problem Manipulation: Source of 'Master' Problems" covers the subjects of projection, inner linearization and outer linearization. The third section, "Solution Strategies: Source of 'Subproblems'," discusses piecewise strategy, restriction and relaxation. The fourth section is entitled "Synthesizing Known Algorithms from Manipulations and Strategies," and is followed by a concluding section and an extensive bibliography. [ABSTRACT FROM AUTHOR]

The article presents an algorithm for solving a linear integer programming problem and describes the theoretical foundations for a new approach to integer programming. According to the authors, the approach may be described as an extension of the methods using enumeration, but by using a new, more powerful approach based on population statistics. The optimal solution to the integer programming problem in this paper is viewed as one of selecting the optimal function among a certain class of functions which map elements of one set into another. With this method in mind, the authors intend to view the different problems by characterizing the statistical structure of the associated finite class of maps.

The usefulness of integer programming as a tool of capital budgeting hinges on the development of an efficient solution technique. An algorithm based on partial enumeration has been developed by E. L. Lawler and M. D. Bell for solving integer linear programs with 0-1 decision variables; however their algorithm is not general enough to deal with all problems in which the objective function is quadratic. This paper extends Lawler and Bell's method so that it can be generally applied to integer quadratic programs. The new algorithm is illustrated by examples from capital budgeting. [ABSTRACT FROM AUTHOR]

The literature is replete with analyses of minimum cost flows in networks for which the cost of shipping from node to node is a linear function. However, the linear cost assumption is often not realistic. Situations in which there is a set-up charge, discounting, or efficiencies of scale give rise to concave functions. Although concave functions can be minimized by an exhaustive search of all the extreme points of the convex feasible region, such an approach is impractical for all but the simplest of problems. In this paper some theorems are developed which explicitly characterize the extreme points for certain single commodity networks. By exploiting this characterization algorithms are developed that determine the minimum concave cost solution for networks with a single source and a single destination, for acyclic single source multiple destination networks, and for acyclic single destination multiple source networks. An interesting theorem then establishes that for either single source or single destination networks the multi-commodity case can be reduced to the single commodity case. [ABSTRACT FROM AUTHOR]

This paper demonstrates the equivalence of several published algorithms for solving the so-called linear fractional programming problem. [ABSTRACT FROM AUTHOR]

This paper attempts to present the major methods, successful or interesting uses, and computational experience relating to integer or discrete programming problems. Included are descriptions of general algorithms for solving linear programs in integers, as well as some special purpose algorithms for use on highly structured problems. This reflects a belief, on the author's part, that various clever methods of enumeration and other specialized approaches are the most efficacious means existent by which to obtain solutions to practical problems. A serious try at gathering computational experience has been made—but facts are difficult to uncover. The paper is written with intent to enable readers to read selected sections without having to read the whole. [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]

For a project that consists of numerous jobs subject to technological ordering restrictions the polygon representing project cost versus completion time is to be determined when the normal and crash completion times are known for each job and the cost of doing the job varies linearly between these times. A linear programming formulation of this problem was given by Keliey [1] and a network flow formulation by Fulkerson [2]. Since the traditional mathematical background of civil engineers includes neither linear programming nor network flow theory, these methods are not as widely used in the building industry as they deserve. This paper shows that Fulkerson's algorithm can be given a structural interpretation using concepts that are familiar to civil engineers. [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]

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]

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 generalized network problem and the closely related restricted dyadic problem occur frequently in applications of linear programming. Although they are next in order of computational complexity after pure network or distribution problems, the jump in degree of difficulty is such that, in the most general problem, there exist no algorithms comparable in speed to those for pure networks. In this paper we characterize the properties of a special class of generalized network problems that permit a dual feasible basic solution to be determined in one 'pass' through the network. In particular, this class includes the class of pure network problems for which no such procedure has previously existed. Our algorithm also makes it possible to apply LEMKE'S dual method and the poly-ω technique of CHARNES AND COOPER in an efficient manner to solve capacitated (pure) network problems. [ABSTRACT FROM AUTHOR]

This paper combines the theory of generalized Lagrange multipliers with a reformulation of the integer-programming problem due to group theory. The use of multipliers enhances the algorithmic efficiency of group theory in a variety of ways. One particular application is the approximation of generalized Lagrange multipliers by generalized linear programming as suggested by BROOKS AND GEOFFRION. This procedure is shown to be closely related to the cutting-plane method of GOMORY. [ABSTRACT FROM AUTHOR]

This paper proposes a new class of cutting planes for integer programming. A typical member of the class is generated as follows. Let X be the feasible set, and ... the optimal (noninteger) solution to the linear program associated with an integer program in n-space. Consider a unit hypercube containing 2, whose vertices are integer, and the hypersphere circumscribing the cube. This hypersphere is intersected in n independent points by the n hairlines originating at ... and containing the n edges of X adjacent to (if ... is degenerate, X is replaced by X' ⊃ X having exactly n edges adjacent to ...). The hyperplane through these n points of intersection defines a valid cut, the (spherical) intersection cut. The paper gives a simple formula for finding the equation of the hyperplane, discusses some ways of strengthening the cut, proposes an algorithm, and gives a finiteness proof. A straightforward extension of these geometric ideas yields an analogous (cylindrical) intersection cut for the mixed-integer case. A discussion of relations to other work (Young, Gomory) is followed by the introduction of some additional intersection cuts obtained from hypersurfaces other than the sphere or the cylinder. The message of this paper lies, not so much in the particular cuts that it proposes, as in the basically new approach to integer programming that these cuts typify. This approach is geometrically motivated and uses the 'local' properties (in the integer-programming sense) of the feasible set. [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 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]

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]

Linear programming models for media selection have limited application because the function describing the aggregate response to additional inputs of advertising effort is generally non-linear. The authors present a general media mix model which assumes linear response and illustrate how the model can be modified to accommodate non-linearity while still using the revised simplex method as a solution algorithm. [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]

It is known that prices only cannot usually be utilized to coordinate a linear economic system. This paper considers a linear economic system. formally represented as a linear programming model which is interpreted as a resource-allocation problem. An algorithm founded on the idea of associating with each resource a linearly increasing price schedule rather than a constant price is developed. The paper hence demonstrates that a mechanism rather similar to a pure price mechanism can be used both to find and sustain an optimal allocation of resources in a linear economic system. [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]

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]

Copyright of INFOR is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

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

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]

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]

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]

This paper presents an algorithm for yielding an improved initial dual solution of the transportation problem when the network flow algorithm of Ford and Fulkerson is used. (1) The algorithm is described. (2) It is demonstrated by means of a numerical example. (3) Computational experience is reported. 400 medium-sized (30 X 80; 50 X 60; 50 X 80) test problems with three different kinds of distance matrices and two different kinds of shipment quantity vectors were evaluated. The average improvement over the usual method was about 30%. [ABSTRACT FROM AUTHOR]