Search

The problem of determining continuous flows of minimum cost in a network with convex cost functions is considered. The approach used is that of finding, for any given feasible flow, circuit flows of negative incremental costs. In the main theoretical result of this paper, it is proved that if at each stage, given a feasible nonoptimal flow X, the circuit flow with most negative incremental cost is added to X, linear convergence to the optimal solution will be obtained. In addition, this most negative incremental cost determines an upper bound on the difference in cost between the given feasible solution and the optimal. Based on these concepts, an algorithm, which preserves linear convergence, is presented to determine minimum cost flows in networks with convex costs in the arcs. Results of computer runs made for this algorithm are given. The special case of networks with linear costs is also considered. [ABSTRACT FROM AUTHOR]

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]

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 considers non-linear programming models in which randomized solutions are allowed. That is, we consider the minimization of the expected value of a non-linear function subject to constraints on the expectation of nonlinear functions, where the expectations are taken with respect to randomized decision strategies. Saddle-point and related optimality conditions similar to those given in [10] and [11] for convex functions are obtained with only very mild restrictions on the shape of the optimizing and constraint functions. We also consider when the optimal solution need not be randomized and how the notions of Lagrange multipliers and game theory are related to our results. We offer an economic interpretation of our solution. A few simple examples are given to illustrate the implications of randomized strategies. It is also pointed out how the results of this paper are related to the decomposition methods widely used to solve mathematical programming problems. [ABSTRACT FROM AUTHOR]

In a team decision problem there are two or more decision variables, and these different decisions can be made to depend upon different aspects of the environment, or information variables, the resulting payoff being a random variable. The choice of optimal rules for selecting information variables and for making decisions is the central problem of the economic theory of teams. This paper shows, by means of an example, how linear programming can be applied to obtain optimal team decision functions in the case in which the payoff to the team is a convex polyhedral function of the decision variables. [ABSTRACT FROM AUTHOR]

The main result proved in this paper is that the ratio of the square of a nonnegative convex function to a strictly positive concave function is convex over a convex domain. Some particular cases of this result and a few applications to mathematical programming are also considered. [ABSTRACT FROM AUTHOR]

In this paper we present an extension of the simplex procedure to deal with separable programming problems where the objective is composed of functions which are either convex or concave and where the feasible solution set is convex. [ABSTRACT FROM AUTHOR]

The stochastic cash balance problem is an inventory problem in which the stochastic cash (or inventory) change can either be positive or nonpositive, and in which decisions to increase or decrease the inventory are permitted at the beginning of each time period. The paper studies problems in which both fixed and proportional costs can be incurred whenever the inventory is changed in either direction. An example is used to demonstrate that when these costs are positive and the loss function is convex, a simple policy (analogous to a two-sided (s, S) policy) is not generally optimal. The example is also used to display the relations between the cash balance problem and inventory problems previously studied by Scarf and Veinott. When proportional costs of changing the inventory are zero, the two fixed costs are equal, the loss function is symmetric quasi-convex, and the problem's probability densities are quasi-concave a simple policy is shown to be optimal. For the cases in which simple policies are not optimal, the paper develops a technique which employs convex upper and lower bounds on the (nonconvex) cost functions partially to describe the optimal policy. It is suggested that this convex bounding technique may provide an approach to studying the cost implications of following simple, nonoptimal policies in inventory problems for which the optimal policy is complex. [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]

An important function which is neither concave nor convex often arises in production and inventory models. This function is herein called piecewise concave and can be considered to be a generalization of the concave function. Essentially it is the maximum of a collection of concave functions. Various properties of piecewise concave functions are explored in this paper. In particular, a theory is developed to locate the point at which such functions are minimized. A short discussion of applications is included. [ABSTRACT FROM AUTHOR]

In the generation of an additional constraint or cut for integer programming introduced by Ralph Gomory, there is a certain parameter whose value is customarily chosen so that one of the original variables has a zero coefficient in the cut-equation. In this paper we consider alternative values of the parameter and refer to any linear combination of the original source equation and this cut as a "generalised cut." Attention is then focused, as customary, on those cuts of this type for which the original variable has a zero coefficient. In particular, we show how to determine values for Gomory's parameter so that only a subset of the feasible solutions to the cuts used by Gomory's method of integer forms are feasible for the generalized cuts. [ABSTRACT FROM AUTHOR]

In this paper we consider a firm that must make a production decision and a capital decision at periodic intervals of time. The cost of production is assumed to be convex and the firm is allowed to hold inventories. For a class of inventory and capital costs the optimal production and capital decisions are obtained for an n-period problem. The optimality criterion used is minimization of the expected present value of costs in the n periods. [ABSTRACT FROM AUTHOR]

Evaluation of FIFO (= first in first out) versus LIFO (= last in first out) policies in stock depletion problems has hitherto been based on the classification of field life functions as convex and concave, the optimal policy for n > 2 units being determined when the optimal policy for n = 2 units is known. This paper suggests a test for selecting the optimal policy for the n = 2 system, for field life functions with a derivative equal or larger than -1, and by induction the conclusions are extended to n > 2. When the derivative is smaller than -1, LIFO is shown to be an optimal policy. [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]

The calculation of economic lot sizes with more than one constraint on the system is a recognized problem in inventory control theory. This paper presents a simplex like solution procedure. The algorithm as presented can be readily adapted to other constraints which may arise in a specific application. The essential conditions for application are that the non-linear constraints and/or objective function be differentiable, convex functions. [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]

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]

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.)

Several techniques in mathematical programming involve the constrained optimization of an extremal-value function. Such functions are defined as the extremal value of a related parameterized optimization problem. This paper reviews and extends the characterization of directional derivatives for three major types of extremal-value functions. The characterization for the completely convex case is then used to construct a robust and convergent feasible direction algorithm. Such an algorithm has applications to the optimization of large-scale nonlinear decomposable systems. [ABSTRACT FROM AUTHOR]

The paper deals with problems of maximizing a sum of linear or concave-convex fractional functions on closed and bounded polyhedral sets. It shows that, under certain assumptions, problems of this type can be transformed into equivalent ones of maximizing multiparameter linear or concave functions subject to additional feasibility constraints. The problems are transformed into those finding roots of monotone-decreasing convex functions. Where the objective function is separable, such a root is unique, and any local optimum is a global one, i.e., the objective function is quasiconcave. In problems involving separable linear fractional functions, under some additional assumptions, the parametric presentation results in a combinational property. Where the number of terms in the objective function is equal or less than three, this property leads to an efficient algorithm. [ABSTRACT FROM AUTHOR]

Consider the set of all vectors b such that the system g(x)≤ b has a solution, where g:D→R[supm], D⊆R[supn]. This paper presents necessary and sufficient conditions for this set to be closed, with special results on continuous and convex functions, and gives an application to mathematical programming. [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]

It is shown that minimax problems with convex-concave payoff and convex inequality constraints can be reduced to solving an equivalent constrained minimization problem. The objective function of the minimization problem is not convex, nor is the set of feasible solutions convex. Nevertheless, it is shown that any point which satisfies the first order necessary conditions for optimality must be a global minimum. [ABSTRACT FROM AUTHOR]

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 problem of locating economic facilities in such a manner as to minimize the cost of moving inputs from source points to the facilities and outputs from the facilities to subsequent destination points has had considerable attention in recent times. A wide and diverse variety of approaches which give reasonable but not necessarily optimal solutions to such problems has been suggested. This paper suggests a different approach to this familiar problem. For a single facility location problem, an algorithm is presented which produces optimal locations. For the case of locating several new facilities a computer search process is instituted which produces close to optimal locations. [ABSTRACT FROM AUTHOR]

It is shown that the modular design problem minimize Σ i=1 i=m Yi Σ j=1 j=n Zj, subject to Yi Zj ≧ rij, Yi Zj > 0,can be transformed into a problem of minimizing a separable convex function subject to linear equality constraints and nonnegativities. This transformation is effected by using a generalized inverse of the constraint matrix. Moreover the nature of the functional and the constraints of the separable problem are such that a good starting point for its solution can be obtained by solving a particular transportation problem. Several possible methods for solving the separable problem are discussed, and the results of our computational experience with these methods are given. It is also shown that the modular design problem can be viewed as a special case of a large class of general engineering design problems that have been discussed in the literature. [ABSTRACT FROM AUTHOR]

We extend a previous algorithm in order to solve mathematical programming problems of the form: Find x = (x[sub 1], ..., x[sub n]) to minimize Σ φ[sub i0] (x[sub I]) subject to and . Each φ[sub ij] 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. In case G is convex each problem in the sequence is a convex programming problem. The problems correspond to successive partitions of the set. Two different rules for refining the partitions are considered; these lead to convergence of the algorithm under different requirements on the problem functions. An example is given, and computational considerations are discussed. [ABSTRACT FROM AUTHOR]

It is shown that for any feasible network flow model, there is a flow which simultaneously minimizes every d-Schur convex function of the flows emanating from a single distinguished node called the source. The vector of flows emanating from the source in the minimizing flow is unique and is the "least d-majorized" flow. This flow can be found by solving the problem for the Special Case where the d-Schur convex function is separable and quadratic. Once this flow is found, the solution of the dual problem is reduced to evaluating the conjugate of a function appearing in the dual objective function at the above flow. This Computation is extremely simple when the function is separable. These results are extended to situations in which the variables must be integers. An important Special case of the problem can be solved geometrically by choosing, from among all paths joining two points in the plane and lying between two given nonintersecting paths, the path with minimum euclidian length. Applications of the results are given to deterministic production-distribution models (e.g., the Modigliani-Hohn [30] production Smoothing model), certain of the stochastic inventory-redistribution models examined by Ignall and Veinott [27], a deterministic price speculation and storage model (including Cahn's warehouse problem [11]), and a zero lead time ease of the Clark-Scarf series multi-echelon model [13]. In addition, applications are given to several maximum likelihood estimation problems in which the parameters satisfy certain linear inequalities, e.g., those surveyed in Brunk [8], [9, pp. 1347-1349], and a few others. [ABSTRACT FROM AUTHOR]

The article extends work previously presented by Edmund Eisenberg, who characterized the set of supports of a convex function defined on a polyhedral convex cone. This work extended Farkas' Lemma and is useful in programming problems. This article seeks to enlarge that scope of work to include an even larger class of convex functions. A theory with supporting lemmas and proofs is provided.

Consider a stockpile consisting of n items where the ith item has a rating r[SUBi], i = 1, . . . , n. An item with rating r, if kept in stockpile until time t and then released to the field, will have a field life of rd(t). Thus it is assumed that for any t, the field life for issuance at time t is proportional to the time 0 field life. Items are to be issued one by one from the stockpile to the field until the stockpile is depleted. The ith issued item is placed in the field immediately upon the death in the field of the (i - 1)st issued item. Conditions for LIFO and FIFO optimality are obtained. [ABSTRACT FROM AUTHOR]

In this study we generalize the formulation of symmetric duality introduced by DANTZIG, EISENBERG, and COTTLE to include the case where the constraints of the inequality type are defined via closed convex cones and their polars. The new formulation retains the symmetric properties of the original programs. Under suitable convexity/concavity assumptions we generalize the known results about symmetric duality. The case where the function involved is strongly convex/strongly concave is also treated and KARAMARDIAN's result in this case is generalized. As a result, we show that every strongly convex function achieves a rain/mum value over any closed convex cone at a unique point. Some special cases of symmetric programs are then considered, leading to generalizations of Wolfe's duality as well as generalizations of quadratic and linear programming formulations. [ABSTRACT FROM AUTHOR]

Many theorems involving convex functions have appeared in the literature since the pioneering work of JENSEN. Recently some results have been obtained for a larger class of functions: quasi-convex. This review summarizes in condensed form results known to date, providing some refinements to gain further generality. An additional objective of this review is to clarify the structure underlying quasi-convex functions by presenting analogues to properties of convex functions, and by illustrating where dialogues do not exist. [ABSTRACT FROM AUTHOR]

To lease long-distance telecommunications facilities, the lessee submits, for billing purposes, a configuration of individual channels and bulk units of channels, called TELPAKS, that implements his requirements. The bulk rate charged for a TELPAK results in the cost being a piecewise linear function of the number of channels. This leads to a network-synthesis problem with a nonlinear cost function that is neither concave nor convex. We give a characterization of an optimal solution and present a method for obtaining a low-cost configuration when all requirements are to a single point. [ABSTRACT FROM AUTHOR]

A decomposition principle is developed for nonlinear optimization problems. This principle also allows certain classes of problems with convex objective functions subject to concave constraints to be transformed into a problem with convex objective function with convex constraints. [ABSTRACT FROM AUTHOR]

A standard inventory model is examined with a concave increasing ordering cost function rather than simply a linear one with a setup cost. A generalized (s, S) policy is shown to be optimal in the n-period problem. A generalization of K-convex and quasi-convex functions to quasi-K-convex functions is required in the process. The probability densities of demand must be one-sided Pólya densities. [ABSTRACT FROM AUTHOR]

A study is made of a dynamic inventory model with stochastic lead times. A probability model is developed for the arrival of outstanding orders in which it is assumed that orders do not cross in time and that the arrival probabilities are independent of the number and size of outstanding orders. With these assumptions, it is shown that the sequential multidimensional minimization problem normally associated with the random lead time model can be reduced to a sequence of one-dimensional minimizations. The minimizations are a function of a variable representing the sum of stock on hand plus all outstanding orders. Optimal ordering policies are characterized under the assumptions of convex expected holding and shortage costs, a linear ordering cost and a fixed setup cost (greater than or equal to zero) paid when the order is placed. These policies are shown to be quite similar to those obtained with deterministic lead times but some differences in the behavior of the single-period critical numbers (when the setup cost is zero) are noted. [ABSTRACT FROM AUTHOR]

A simple procedure is given for solving minimal cost flow problems in which feasible flows are maintained throughout. It specializes to give primal algorithms for the assignment and transportation problems. Convex cost problems can also be handled. [ABSTRACT FROM AUTHOR]

We consider the problem of choosing the amounts of a single product to produce in each of a finite number of time periods so as to minimize the (convex) production and (convex) inventory carrying costs over the periods while satisfying known requirement. The effect of changes in the various parameters, viz., the requirements and the production and inventory capacity limits, upon the optimal production levels is studied. The results obtained are exploited to provide simple and intuitive computational procedures for finding optimal production schedules for a range of parameter values. [ABSTRACT FROM AUTHOR]

The authors present commentary on their earlier article, "Inventory Depletion Management," published in the July 1958 issue of the periodical "Management Science." The authors identify the problem presented in their article: to determine the order of item issue that will yield a maximum for the total expected utility of the items while meeting a given demand schedule. According to the authors, in their previous article they demonstrated that for any distribution of ages and any schedule, the optimal policy is to issue the youngest item first, or the last in, first out policy.