Search

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.

Although the earliest discussions of linear programming date back to the 1930's, to the work of German and Austrian mathematicians and economists, the mathematics has been extensively developed only in the past six or eight years. Because of the relative newness of the subject, the literature is widely scattered and it is rather difficult for one just starting to learn about linear programming to know where to begin. Because of human limitations, the bibliography is necessarily incomplete. All papers and books that could be acquired that seemed to deal with the subject were perused and, if applicable, included. No extensive effort was made, however, to include papers dealing more or less exclusively with closely related topics, for example, the problem of determination of value and optimal strategies in a zero-sum, two-person game, the pure inequalities problem with no optimization, the subjects of convex functions and convex polyhedra, unless they also relate these topics directly to linear programming.

This paper introduces an efficient branch and bound algorithm for a special class of mixed integer programming problems called the warehouse location problem. A set of branching decision rules is proposed for selecting warehouses to be constrained open and closed from any node of the branch and bound tree. These rules are tested for their efficiency in reducing computation times and storage requirements to reach optimal solutions. An improved method of solving the linear programming problems at the nodes which substantially reduces the computations is also introduced in this paper. [ABSTRACT FROM AUTHOR]

In an earlier paper [5], we generalized and extended Beckmann's results [1] for a production and inventory problem with proportional smoothing costs and demands being random variables. Our previous results concerned the finite horizon nonstationary case. Here we consider the infinite horizon stationary case. Two curves in the plane determine an optimal policy. They are shown to have slopes between minus one and zero, to be differentiable, and to be bounded by two straight lines with a slope Of minus one. These results are used (a) to accelerate each iteration of a successive approximations algorithm and (b) to formulate a linear programming problem from whose solution an optimal policy can be determined. [ABSTRACT FROM AUTHOR]

The paper presents a method for solving the linear programming problems, which is itself a step towards the generalization of the classical Simlex Method. It replaces two basic variables by two non-basic variables at each iteration. Naturally this will reduce the total number of steps to reach the final solution. The paper also includes the solution of one example to illustrate the applicability of the method. [ABSTRACT FROM AUTHOR]

A mathematical program with a maximin objective function is defined as an optimization problem of the following type: Maxz=min[sub i] c[sub i]x[sub i], subject to AX = b, X * (This character cannot be converted in ASCII text) O. Although the c[sub i] can be in the interval (-- ∞, ∞), the paper discusses the more common practical case where all c[sub t] * (This character cannot be converted in ASCII text) 0. It shows that problems of this type arise in a variety of applications where it is required to maximize a production function of the 'fixed proportion' type subject to a set of linear constraints. Although it is well known that the solution to this type of problem can be found by linear programming, this paper shows that, if the existence of a certain condition can be demonstrated, then a simplified method can be used to determine the optimum solution. Many problems of practical interest can be solved by this simplified method; an example involving the readiness of a ship is presented. [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]

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]

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 presents an approach, similar to penalty functions, for solving arbitrary mathematical programs. The surrogate mathematical program is a lesser constrained problem that, in some cases, may be solved with dynamic programming. The paper deals with the theoretical development of this surrogate approach. [ABSTRACT FROM AUTHOR]

This paper considers the problem of partitioning N entities into M disjoint and nonempty subsets (clusters). Except when both N and N--M are very small, a search for the optimal solution by total enumeration of all clustering alternatives is quite impractical. The paper presents a dynamic programming approach that reduces the amount of redundant transitional calculations implicit in a total enumeration approach. A comparison of the number of calculations required under each approach is presented in Appendix A. Unlike most clustering approaches used in practice, the dynamic programming algorithm will always converge on the best clustering solution. The efficiency of the dynamic programming approach depends upon the rapid-access computer memory available. A numerical example is given in Appendix B. [ABSTRACT FROM AUTHOR]

This paper describes a stochastic game in which the play terminates in a finite number of steps with probability 1. The game is called a terminating stochastic game. When the play terminates at any step, the play is regarded to reach to an absorbing state in the Markov chain under consideration. Hence, the terminating stochastic game is a nonstationary Markov chain with rewards in which our concern is the transient behavior before absorption. In particular, when one of the players is a dummy, the stochastic game reduces to a Markovian decision process of special type. This paper discusses such games. We introduce a new concept of rewards and formulate three problems arising in the games by linear programming. Finally, numerical examples are presented. [ABSTRACT FROM AUTHOR]

The first part of this paper is concerned with the semi-infinite linear programs studied by Charnes, Cooper and Kortanek. A form of the Farkas lemma stated by Haar appears to apply to such programs and leads to a duality theorem. In this paper an example of a semi-infinite program is given which is consistent and which has a finite minimum. However the dual program is found to be inconsistent. With a variation of the example a situation is exhibited in which both the program and its dual are consistent and have finite extrema. In this case, however, the minimum of the former is not equal to the maximum of the latter. The existence of such a ‘duality gap’ indicates that Haar's statement needs qualification. In the second part of the paper a correct form of Haar's theorem is stated and proved. The proof invokes the infinite programming theory of Duffin and Kretschmer. The last part of the paper develops a new duality theory for infinite programs which, as a special case, insures a weak form of duality for programs typified by the examples. This new duality theory is somewhat simpler than previous theories of infinite programming. [ABSTRACT FROM AUTHOR]

When an underwriting syndicate submits a bid for a new issue of municipal bonds, one of the important decisions that it must make involves the scheduling of interest coupons to be placed on the bonds. Given the bid specifications stated by the issuing municipality and some prior decisions of the underwriters, it is shown that the determination of the optimal coupon schedule can be expressed as a linear programming problem. Since this LP problem has a special structure, a simple computational algorithm requiring less computation than the simplex method is derived. This paper goes beyond previous contributions to the literature in three important ways. First, simple formulas for obtaining the dual evaluators are developed; the marginal effect of shifts in the yield curve is also presented. Second, it is shown that in the non-integer year case both the conclusions of previous writers and the conventional heuristics of the market may be erroneous, whereas the general solution techniques developed in this paper remain valid. Finally, a direct analogy between the coupon schedule problem and the microeconomic theory of the firm is used in obtaining the special computational algorithm for this LP problem. [ABSTRACT FROM AUTHOR]

This paper explores methods for scheduling preventive maintenance by means of mathematical programming. Five integer linear programming models are posed, each based on a different optimality criterion dealing with manpower smoothing. By means of two hypothetical examples the models are tested for their computational properties. In addition to describing the experimental results of applying integer linear programming techniques to this class of problems, the paper also illustrates how effectively rounded linear programming solutions can be used as approximations to optimal solutions. [ABSTRACT FROM AUTHOR]

This paper is concerned with the solution of linear and linear goal programming problems in which the values of the right-hand side parameters are not fixed constants. Specifically, we are concerned with linear optimization problems in which the right-hand sides of the constraining equations are free to vary subject to a set of linear constraining equations. By formulating a relaxed linear program wherein the right-hand sides are treated as variables, we show how it is possible to solve one larger linear program that yields as a solution not only the optimal values for the decision variables, but also the optimal values for the right-hand sides. [ABSTRACT FROM AUTHOR]

This paper brings together two topics from regression analysis. One is the topic of stepwise regression, a set of commonly used procedures for exploring alternative formulations of the regression model. The other topic is regression by minimizing the sum of the absolute errors about the regression line (MSAE). This technique has been found, in a variety of circumstances, to be more attractive than the traditional least-squares method. The paper presents a procedure for selecting from among m regressors the best sets of k, k-1, ... and m regressors according to the MSAE criterion (k This character cannot be converted in ASCII text) m). Building upon the well known linear-programming formulation of the MSAE problem, the paper develops a partial enumerative search scheme, in which a set of distinct, but related, combinatorial optimization problems (corresponding to determination of 'best k,' 'best k+1,' etc.) are, in effect, solved simultaneously. [ABSTRACT FROM AUTHOR]

This paper develops an algorithm for pure integer programming problems. It first transforms the integer programming problem to an algebraically equivalent Hermite canonical problem, and then employs the Fourier-Motzkin elimination. These algebraic operations transform the problem into a form that leads to an efficient implicit enumeration scheme to calculate an optimal solution. The algorithm constructs, in a finite number of operations, an optimal solution to an integer program with n variables and n or n + 1 inequality constraints. If the original problem has more than n + 1 constraints, then the integer program with only the constraints that are binding at an optimal linear programming solution is solved in place of the original problem. Computational results are presented. [ABSTRACT FROM AUTHOR]

This paper reviews some recent successes in the use of linear programming methods for the solution of discrete-variable extremum problems. One example of the use of the multistage approach of dynamic programming for this purpose is also discussed. [ABSTRACT FROM AUTHOR]

Randomly-generated linear programming problems of three different types and five different sizes were solved by the criss-cross method and by the simplex method. One hundred problems of each type and size were solved, and the results are overwhelmingly favorable to the criss-cross method. An improvement to the criss-cross method used in these tests is given, and the extension of the results of the paper to variations of the criss-cross and simplex methods is discussed. [ABSTRACT FROM AUTHOR]

The paper considers a class of optimization problems. The problems are linear programming problems: maximize ex subject to Ax = b with the additional constraint that x must also be an extreme point of a second convex polyhedron Dx = d. X ≥ 0. A cutting-plane algorithm for solving such problems is presented. Two numerical examples are also included. [ABSTRACT FROM AUTHOR]

Integer programs may have constraints which are redundant or else nonbinding. They may also have variables which are extraneous in the sense that there is some optimal program in which they are nonpositive. Thompson, Tonge and Zionts [1] have discussed the topics of redundant constraints and extraneous variables in linear programs. This paper extends their results to integer programs, and provides new proofs of the original results. [ABSTRACT FROM AUTHOR]

The aim of this paper is to construct sets of uniformly tighter linear constraints to replace a chance constraint, in order to be able to solve the chance-constrained programming problem by the simplex method. The chance constraints are first diagonalized by a linear orthonormal transformation. Uniformly tighter linear constraints can then be formed to replace the chance constraint. The developed multistage linear programming problem can also be solved using the Dantzig-Wolfe decomposition technique. Approximation errors of our method and one of Hillier's [8] are compared. [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]

Many people have proposed objective functions, or optimizers, which guide one to schedule a multi-product single stage production system. In this paper we present a whole new class of optimizers, or solution concepts, which generalizes most of the well-known optimizers to date. Our combinatoric formulations are related to a new class of solution concepts for n-person games developed by Charnes-Kortsnek. By constructing a combinatoric linear programming problem, where some of the variables are determined by an arbitrary set of permutations, we encompass classical optimizers in one formulation including such concepts as (1) minimizing maximum lateness or tardiness, (2) maximizing minimum lateness or tardiness, (3) minimizing mean lateness or flow time, and (4) random sequencing. More generally, we characterize a new class of optimizers as optimal solutions to specially constructed combinatoric programming problems, including optimizers which are integer in character. [ABSTRACT FROM AUTHOR]

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]

In this paper the dual method and the poly-ω technique are specialized for the generalized transportation problem. A simple procedure is obtained for solving the parametric version of this problem, i.e. for passing from a solution optimal for given values of the parameters, to solutions optimal for other values of the parameters. This procedure is then extended to the case when not only the parameters change, but additional constraints appear. Finally, the procedure may be used as a general method for solving the usual (non-parametric) generalized transportation problem, and for this case a way is described for finding an initial (dual-feasible) solution. [ABSTRACT FROM AUTHOR]

In linear programming under uncertainty the two-stage problem is handled by assuming that one chooses a first set of constrained decision variables; this is followed by observations of certain random variables after which another set of decisions must be made to adjust for any constraint violations. The objective is to optimize an expected value functional defined relative to the indicated choices. This paper shows how such problems may always be replaced with either constrained generalized medians or hypermedians in which all random elements appear only in the functional. The resulting problem is called a deterministic equivalent for the original problem since (a) the originally defined objective replaces all random variables by corresponding expected values and (b) the remaining constraints do not contain any random terms. Significant classes of cases are singled out and special attention is devoted to the structure of the constraint matrices for these purposes. Numerical examples are supplied and related to the previous literature. Other properties of these models are also examined and related to types of problems which are often of interest. For instance the hypermedian and generalized median formulations involve minimizations over absolute value terms in the functional. These, in turn, are developed for their possible pertinence in problems where minimizations are to be over the maximum of a set of functions under inequality constraints. Utilizing Moore-Penrose (generalized) inverses, other characterizations are also secured in which all relevant weights and coefficients are stated explicitly in terms of original data. [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]

In this paper, it is shown that the "caterer" problem, a problem in mathematical economics and logistics which has been discussed by Jacobs, Gaddum, Hoffman and Sokolowsky, and Prager, can be reduced to the problem of determining the maximum of the linear form Ln = ∑I=1nv1, subject to a series of constraints of the form V1 ≦ b1, v1 +v2 ≦ b2, v1 + v2 +v3 ≦ b2, ߪ, v1 + v2 + … + vK ≦ bK, v2 + v3 + … + vK+1 ≦ bK+1, …, vb-h+1 + … + Vn ≦ bn, 0 ≦ rI, I = 1, 2, … , n, under an assumption concerning the nonaccumulation of dirty laundry. This maximization problem is solved explicitly, using the functional equation technique of dynamic programming. [ABSTRACT FROM AUTHOR]

This note points out some deficiencies in a recent paper [Opt. Res. 19 (1971), pages 1045–1050] concerning the classical derivation of optimality conditions in linear programming. [ABSTRACT FROM AUTHOR]

This paper shows that the final solutions to the executive and divisional programs in a linear fractional decomposition furnish the complete primal and dual solutions; it extends the proofs already presented for the linear decomposition problem. [ABSTRACT FROM AUTHOR]

Each of the main enumerative methods for zero-one programming has a drawback: the branch-and-bound (multi-branch) approach may require an inordinate amount of storage capacity and the backtrack implicit-enumeration (single-branch) approach circumvents this storage problem only by restricting the flexibility of the search. This paper outlines an implicit-enumeration scheme that, while maintaining a low storage requirement, allows the same flexibility in backward branching (backtracking is no longer mandatory) as we commonly have in forward branching. Preliminary computational results are presented. [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 article presents a response to an article discussing the majority rule under transitivity constraints, by V.J. Bowman and C.S. Colantoni, published in a previous issue. The authors say that the original papers' optimization model was a linear integer programming problem. They believe a quadratic assignment type of the optimization model is better suited to the problem.

The article presents a paper, which shows how to determine the optimal number and routings of containers used to move mail among several cities. This paper extends the above system to more than two cities, with different schedules on different days and with transfer of containers permitted throughout the system. A mathematical formulation is developed that can be readily solved by known linear programming techniques. Critical assumptions are (a) periodic demand patterns and linear transportation costs between each city-pair, and (b) constant fixed cost per container in the system. The optimization problem is transformed into a network flow linear program for which efficient solution methods are known. The researchers have investigated a system where containerized mail would be sent between two cities. The problem solved in reference was that of determining the best number of containers to be sent each day between the two cities, based on (a) the distribution of mail volumes going between the cities each day and (b) the costs for sending containers, full or empty, and for sending mail by other means in case of container shortage. Thus the original convex programming problem has been converted to an especially tractable type of linear program, namely the optimization of a network flow.

This paper presents a model for choosing the periodical collection in a reading room. The model consists of two stages. In the first stage the probability distribution of contacts by users with a given periodical is developed and employed to determine the utility of the periodical. In the second stage the problem of choosing an optimum periodical collection is formulated as a capital budgeting problem and solved with the aid of dynamic programming. The implementation of this model at the University of Connecticut is described in detail. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for the set-covering problem (that is, min c'y:Ey±e, y±0,y, integer, where E is an m by n matrix of 1's and O's, and e is an m-vector of 1's). The special problem structure permits a rather efficient, yet simple, solution procedure that is basically a (0, 1) search of the single-branch type coupled with linear programming and a suboptimization technique. The algorithm has been found to be highly effective for a good number of relatively large problems. Problems from 30 to 905 variables with as many as 200 rows have been solved in less than 16 minutes on an IBM 360 Model 50 computer. The algorithm's effectiveness stems from an efficient suboptimization procedure, which constructs excellent integer solutions from the solutions to linear-programming subproblems. [ABSTRACT FROM AUTHOR]

The convex hull of the feasible integer points to a given integer program is a convex polytope I. The feasible set obtained by relaxing the integrality requirements is another convex polytope L. Cutting-plane algorithms essentially try to remove part of L--I. Hence the more complicated the relationship between L and I, the more difficult (in some sense) the integer program. This paper shows one such complexity: specifically, we construct a series of programs such that I has arbitrarily many faces even though L is a triangle. We also indicate the existence of a large class of problems that exhibit the same behavior. [ABSTRACT FROM AUTHOR]

The special class of linear programs described as network flow problems includes many of the special structure optimization problems in such areas as assignment, transportation, catering, warehousing, production scheduling, etc Besides the physical motivation of the flow description, this class of problems possesses conceptually simple, and computationally elegant, solution techniques originated by DANTZIG, FORD, FULKERSON, ET AL This paper describes a generalization of this class of problems to 'process-flow networks,' or 'flow with gains,' in which flow in any branches of the network may be multiplied by an arbitrary constant, called the branch gain, before leaving the branch and flowing into the remainder of the network This generalization permits the description of networks in which different kinds of flow may be converted one to another, without 'constant returns to scale' Among other interesting problems, this model includes the metalprocessing problem, the machine-loading problem, financial budgeting, aircraft routing, warehousing with 'breeding' or 'evaporation,' the two-equation capacitated linear program, etc The solution method here described and proved is a natural extension of Ford and Fulkerson's technique (or specialization of the primal-dual method) and retains much of the physical motivation and easy computational aspect of their technique, a direct starting solution is usually available, and optimization of the imbedded linear program (the restricted primal problem) can be accomplished without the use of the simplex technique Conceptually, the solution procedure consists of the following steps (1) Find the inerementally cheapest loop in the network that will absorb flow (2) Establish as much additional flow into the network along this route as possible (3) Repeat Steps (1) and (2) until the desired flow is established, or until infeasibility is discovered The solution technique includes a maximal-flow procedure and produces a 'min-cut... [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for determining the minimum cost schedule of tasks in a critical path network in which task cost-time curves may be concave. A computer program for the case of cost-time curves that are piecewise linear in two segments is described, and a numerical example is presented. [ABSTRACT FROM AUTHOR]

Decomposable mathematical programming problems sometimes admit a certain degree of decentralization in the decision process. By an informative interplay between a central authority and a number of subdivisions one hopes to establish the overall best solution. This interplay can be organized in either of two ways: direct or indirect distribution. However, an absolute prerequisite for such procedures to be successful is the availability of an optimality criterion to the centre so as to know when to stop the iterative process. It is well known that for either of two cases the optimality conditions as derived from the Kuhn-Tucker conditions for the overall problem are not satisfactory. The present paper makes a comparison between the shortcomings of the two kinds of conditions. In the case of direct distribution this condition turns out to be necessary but unfortunately not sufficient and for indirect distribution the condition is sufficient but not necessary. The insufficiency in the direct and the absence of necessity in the indirect case, which are caused by eventual nonconvexities of the problem, are explored a bit further. A simple example is presented. [ABSTRACT FROM AUTHOR]

Mathematical programming as an aid to R&D project portfolio selection has been suggested by many authors, but few practical applications have been reported. This paper discusses some of the difficulties, associated with the application of the proposed models, and describes procedures for handling these problems. Problem areas considered are: Allowance for future opportunities in multi-period models, Generation of alternative risk-return solutions, Inclusion of projects not completed during the planning period, Comparison of linear and integer programming outputs. In the main, both the problems and methods of solution are clarified by means of numerical examples, and details of a practical case study are given. [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]

Several difficulties arise when multistage optimization problems with linear constraints are extended to an infinite horizon. For linear objectives the weak duality theorem fails, duality gaps exist, complementary slackness is not a sufficient condition for optimality, and the total reward may diverge. This paper presents verifiable conditions on the problem that guarantee the existence of optimal solutions and equilibrium prices for linear and nonlinear objectives. In addition, it is ascertained that the Kuhn-Tucker conditions are sufficient for optimality if additional restrictions are imposed. If the constraints are Leontief and the objective is convex (in a maximization problem), then the existence of an extreme point optimal solution can be verified. The decision taken in each period is an extreme point of the set of solutions that are feasible in that period. The Leontief case also yields a horizon theorem. All sufficiently long finite horizon problems produce a first decision that is optimal for the infinite horizon problem. [ABSTRACT FROM AUTHOR]

In this paper a process analysis model of production in the U. S. Steel Industry is developed and tested. A technology matrix, which represents recent industry input-output structure, is estimated using engineering and metallurgical information. This matrix together with detailed cost, sales and resource capacity data is then used in a linear programming model of short-run resource allocation for the industry as a whole. Linear programming solutions are obtained and compared with available industry statistics for each year in the period 1955-1968. Theil's U statistic is computed to indicate how well the model performs. We conclude that it performs "fairly well" and that it should prove useful in various economic applications. [ABSTRACT FROM AUTHOR]