108 results
Search Results
2. A Primal-Dual Approach to Analyzing ATO Systems.
- Author
-
DeValve, Levi, Pekeč, Saša, and Wei, Yehua
- Subjects
LINEAR programming ,ALGORITHMS ,LINEAR statistical models ,COMPUTER simulation - Abstract
We study assemble-to-order (ATO) problems from the literature. ATO problems with general structure and integrality constraints are well known to be difficult to solve, and we provide new insight into these issues by establishing worst-case approximation guarantees through primal-dual analyses and linear programming (LP) rounding. First, we relax the one-period ATO problem using a natural newsvendor decomposition and use the dual solution for the relaxation to derive a lower bound on optimal cost, providing a tight approximation guarantee that grows with the maximum product size in the system. Then, we present an LP rounding algorithm that achieves both asymptotic optimality as demand grows large, and a 1.8 approximation factor for any problem instance. In addition to theoretical guarantees, we perform comprehensive numerical simulations and find that our rounding algorithm outperforms existing techniques and is close to optimal. Finally, we demonstrate that our one-period LP rounding results can be used to develop an asymptotically optimal integral policy for dynamic ATO problems with backlogging and identical component lead-times. This paper was accepted by Yinyu Ye, optimization. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
3. ON NONLINEAR FRACTIONAL PROGRAMMING.
- Author
-
Dinkelbach, Werner
- Subjects
FRACTIONAL integrals ,NONLINEAR programming ,LINEAR programming ,MATHEMATICAL programming ,ALGORITHMS ,PARAMETER estimation ,QUADRATIC programming ,CONCAVE functions ,CONVEX functions ,POLYHEDRAL functions ,NUMERICAL solutions to Lagrange equations - Abstract
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]
- Published
- 1967
- Full Text
- View/download PDF
4. ON SOME WORKS OF KANTOROVICH, KOOPMANS AND OTHERS.
- Author
-
Charnes, A. and Cooper, W. W.
- Subjects
INDUSTRIAL management ,MANAGEMENT science ,LINEAR programming ,GAME theory ,MANAGEMENT games ,DECISION making ,DECISION theory ,ALGORITHMS ,RANDOM variables - Abstract
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.
- Published
- 1962
- Full Text
- View/download PDF
5. A HYBRID METHOD FOR THE SOLUTION OF SOME MULTI-COMMODITY SPATIAL EQUILIBRIUM PROBLEMS.
- Author
-
Pang, Jong-Shi
- Subjects
ECONOMIC equilibrium ,COMMERCIAL products ,TRANSPORTATION ,MANAGEMENT science ,LINEAR programming ,MATHEMATICAL programming ,ALGORITHMS ,PROBLEM solving ,MATHEMATICAL models in business ,RELAXATION methods (Mathematics) ,DEMAND function ,MATHEMATICAL models of industrial management - Abstract
This paper describes a hybrid method for solving the multi-commodity transportation and transshipment spatial equilibrium models. The method is basically a specialization of the block successive overrelaxation method for solving a linear complementarity problem with certain block structure and consists of solving a sequence of subproblems of the single-commodity type. These subproblems are solved by a special-purpose principal pivoting algorithm developed in an earlier paper. Under some mild conditions, convergence of the proposed method is established. Finally, computational experience of solving some fairly large randomly generated problems by the proposed hybrid method is presented. [ABSTRACT FROM AUTHOR]
- Published
- 1981
- Full Text
- View/download PDF
6. LINEAR MULTIPLE OBJECTIVE PROBLEMS WITH INTERVAL COEFFICIENTS.
- Author
-
Bitran, Gabriel R.
- Subjects
MULTIPLE criteria decision making ,DECISION making ,BRANCH & bound algorithms ,STATISTICAL decision making ,VECTOR analysis ,LINEAR programming ,PROBLEM solving research ,TREE graphs ,INDUSTRIAL applications ,UTILITY theory ,MATHEMATICAL models ,ALGORITHMS - Abstract
In this paper we consider linear multiple objective programs with coefficients of the criteria given by intervals. This class of problems is of practical interest since in many instances it is difficult to determine precisely the coefficients of the objective functions. A subproblem to test if a feasible extreme point is efficient in the problem considered is obtained. A branch and bound algorithm to solve the subproblem as well as computational results are provided. Extensions are discussed. [ABSTRACT FROM AUTHOR]
- Published
- 1980
- Full Text
- View/download PDF
7. AN ALGORITHM FOR DERIVING THE CAPITAL MARKET LINE.
- Author
-
Alexander, Gordon J.
- Subjects
CAPITAL market ,CAPITAL budget ,RISK assessment ,MANAGEMENT of securities ,PORTFOLIO management (Investments) ,FINANCIAL management ,EFFICIENT market theory ,LINEAR programming ,MATHEMATICAL optimization ,ALGORITHMS ,MANAGEMENT ,ACCOUNTING - Abstract
This paper examines the problem of deriving the tangent (or market) portfolio from a given set of risky assets and a specified risk-free borrowing and lending rate. Deriving the tangent portfolio involves solving a mathematical programming problem which can be specified as the minimization of a quadratic objective function with linear constraints. The complementary pivot algorithm has previously been shown to be capable of deriving the optimal solution to certain quadratic programming problems, subject to a nonnegativity constraint. This paper demonstrates that the algorithm can be used to derive the tangent portfolio and that the nonnegativity constraint does not pose any serious handicap. Furthermore, it is shown that the algorithm can efficiently solve large-scale problems of this nature. [ABSTRACT FROM AUTHOR]
- Published
- 1977
- Full Text
- View/download PDF
8. FRACTIONAL PROGRAMMING. I, DUALITY.
- Author
-
Schaible, Siegfried
- Subjects
DUALITY theory (Mathematics) ,MATHEMATICAL analysis ,MANAGEMENT science ,MATHEMATICAL programming ,MATHEMATICAL optimization ,OPERATIONS research ,LINEAR programming ,CONVEX programming ,QUADRATIC programming ,ALGORITHMS - Abstract
This paper, which is presented in two parts, is a contribution to the theory of fractional programming, i.e. maximization of quotients subject to constraints. In Part 1, duality theory for linear and concave-convex fractional programs is developed and related to recent results by Bector, Craven-Mond, Jagannathan, Sharma-Swarup, et al. Basic duality theorems of linear, quadratic and convex programming are extended. In Part II Dinkelbach's algorithm solving fractional programs is considered. The rate of convergence as well as a priori and a posteriori error estimates are determined. In view of these results the stopping rule of the algorithm is changed. Also the starting rule is modified using duality as introduced in Part I. Furthermore a second algorithm is proposed. In contrast to Dinkelbach's procedure the rate of convergence is still controllable. Error estimates are obtained too. [ABSTRACT FROM AUTHOR]
- Published
- 1976
- Full Text
- View/download PDF
9. SOLVING THE "MARKETING MIX" PROBLEM USING GEOMETRIC PROGRAMMING.
- Author
-
Balachandran, V. and Gensch, Dennis H.
- Subjects
MARKETING mix ,GEOMETRIC programming ,BUSINESS planning ,MATHEMATICAL programming ,LINEAR programming ,MARKETING research ,ALGORITHMS ,MATHEMATICAL optimization ,REGRESSION analysis - Abstract
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]
- Published
- 1974
- Full Text
- View/download PDF
10. The Lagrangian Relaxation Method for Solving Integer Programming Problems.
- Author
-
Fisher, Marshall L.
- Subjects
INTEGER programming ,LAGRANGE equations ,LINEAR programming ,MANAGEMENT science ,THEORY of constraints ,ALGORITHMS ,RELAXATION methods (Mathematics) ,SCHEDULING ,MANAGEMENT ,BRANCH & bound algorithms - Abstract
One of the most computationally useful ideas of the 1970s is the observation that many hard integer programming problems can be viewed as easy problems complicated by a relatively small set of side constraints. Dualizing the side constraints produces a Lagrangian problem that is easy to solve and whose optimal value is a lower bound (for minimization problems) on the optimal value of the original problem. The Lagrangian problem can thus be used in place of a linear programming relaxation to provide bounds in a branch and bound algorithm. This approach has led to dramatically improved algorithms for a number of important problems in the areas of routing, location, scheduling, assignment and set covering. This paper is a review of Lagrangian relaxation based on what has been learned in the last decade. [ABSTRACT FROM AUTHOR]
- Published
- 2004
- Full Text
- View/download PDF
11. Selection, Provisioning, Shared Fixed Costs, Maximum Closure, and Implications on Algorithmic Methods Today.
- Author
-
Hochbaum, Dorit S.
- Subjects
MANAGEMENT science ,LINEAR programming ,OPERATIONS research ,INTEGER programming ,FREIGHT & freightage ,ALGORITHMS ,CONVEX functions ,BAYES' estimation ,MATHEMATICAL optimization ,MARKET segmentation ,RISK management in business ,PRICING - Abstract
Motivated by applications in freight handling and open-pit mining, Rhys, Balinski, and Picard studied the problems of selection and closure in papers published in Management Science in 1970 and 1976. They identified efficient algorithms based on linear programming and maximum-flow/minimum-cut procedures to solve these problems. This research has had major impact well beyond the initial applications, reaching across three decades and inspiring work on numerous applications and extensions. The extensions are nontrivial optimization problems that are of theoretical interest. The applications ranged from evolving technologies, image segmentation, revealed preferences, pricing, adjusting utilities for consistencies, just-in-time production, solving certain integer programs in polynomial time, and providing efficient 2-approximation algorithms for a wide variety of hard problems. A recent generalization to a convex objective function has even produced novel solutions to prediction and Bayesian estimation problems. This paper surveys the streams of research stimulated by these papers as an example of the impact of Management Science on the optimization field and an illustration of the far-reaching implications of good original research. [ABSTRACT FROM AUTHOR]
- Published
- 2004
- Full Text
- View/download PDF
12. THE GENERALIZED STEPPING STONE METHOD FOR THE MACHINE LOADING MODEL.
- Author
-
Eisemann, Kurt
- Subjects
LINEAR programming ,ALGORITHMS ,MATHEMATICAL programming ,SIMPLEXES (Mathematics) ,MATHEMATICAL models ,MATHEMATICAL models in business ,TOPOLOGY ,NUMERICAL analysis ,BUSINESS mathematics ,MANAGEMENT science ,SIMULATION methods & models - Abstract
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]
- Published
- 1964
- Full Text
- View/download PDF
13. A HEURISTIC PROGRAM FOR LOCATING WAREHOUSES.
- Author
-
Kuehn, Alfred A. and Hamburger, Michael J.
- Subjects
WAREHOUSES -- Location ,ALGORITHMS ,LINEAR programming ,HEURISTIC programming ,PHYSICAL distribution of goods ,SHIPMENT of goods ,LOCATION analysis ,METHODOLOGY ,INDUSTRIAL applications ,PROBLEM solving research ,FLOW charts ,COMPUTER software - Abstract
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]
- Published
- 1963
- Full Text
- View/download PDF
14. A COMMENT ON A PAPER OF MAXWELL.
- Author
-
Sidney, Jeffrey B.
- Subjects
JOB shops management ,INTEGER programming ,MATHEMATICAL programming ,PRODUCTION management (Manufacturing) ,ALGORITHMS ,LINEAR programming ,MATHEMATICAL optimization ,MATHEMATICAL models ,MANAGEMENT science research ,OPERATIONS research - Abstract
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.
- Published
- 1972
- Full Text
- View/download PDF
15. A TIGHT LINEARIZATION AND AN ALGORITHM FOR ZERO-ONE QUADRATIC PROGRAMMING PROBLEMS.
- Author
-
Adams, Warren P. and Sherali, Hanif D.
- Subjects
LINEAR programming ,PRODUCTION scheduling ,CAPITAL budget ,BUSINESS planning ,MATHEMATICAL programming ,ALGORITHMS ,QUADRATIC programming ,STRATEGIC planning ,RELAXATION methods (Mathematics) ,MANAGEMENT science - Abstract
This paper is concerned with the solution of linearly constrained zero-one quadratic programming problems. Problems of this kind arise in numerous economic, location decision, and strategic planning situations, including capital budgeting, facility location, quadratic assignment, media selection, and dynamic set covering. A new linearization technique is presented for this problem which is demonstrated to yield a tighter continuous or linear programming relaxation than is available through other methods. An implicit enumeration algorithm which uses Lagrangian relaxation, Benders' cutting planes, and local explorations is designed to exploit the strength of this linearization. Computational experience is provided to demonstrate the usefulness of the proposed linearization and algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 1986
- Full Text
- View/download PDF
16. SUCCESSIVE LINEAR PROGRAMMING AT EXXON.
- Author
-
Baker, Thomas E. and Lasdon, Leon S.
- Subjects
LINEAR programming ,MATHEMATICAL models of industrial management ,PETROLEUM chemicals industry management ,MATHEMATICAL optimization ,PRODUCTION (Economic theory) ,PRODUCTION management (Manufacturing) ,MATHEMATICAL programming ,PRODUCTION planning - Abstract
Successive Linear Programming (SLP) has been used extensively in the refining and petrochemical industries for over 20 years. This paper concentrates on some recent work at Exxon to unify the treatment of nonlinear terms in 'mostly linear' models. We first discuss the source of nonlinearities in refining and petrochemical problems and propose a multiplicative formulation for the linearized subproblems to be solved by SLP. We then describe a SLP algorithm which is shown to be related to the concept of trust regions. Finally, we present an example formulation and computational results for a series of large industrial applications. [ABSTRACT FROM AUTHOR]
- Published
- 1985
- Full Text
- View/download PDF
17. MULTIPLE OBJECTIVE LINEAR FRACTIONAL PROGRAMMING.
- Author
-
Kornbluth, Jonathan S. H. and Steuer, Ralph E.
- Subjects
SIMPLEXES (Mathematics) ,LINEAR programming ,ALGORITHMS ,MATHEMATICAL programming ,MANAGEMENT science ,PRODUCTION scheduling ,ALGEBRA ,MATHEMATICAL models in business ,FOUNDATIONS of arithmetic ,MATHEMATICAL models of industrial management ,CONVEX functions ,BUSINESS mathematics - Abstract
This paper presents a simplex-based solution procedure for the multiple objective linear fractional programming problem. By (1) departing slightly from the traditional notion of efficiency and (2) augmenting the feasible region as in goal programming, the solution procedure solves for all weakly efficient vertices of the augmented feasible region. The article discusses the difficulties that must be addressed in multiple objective linear fractional programming and motivates the solution algorithm that is developed. [ABSTRACT FROM AUTHOR]
- Published
- 1981
- Full Text
- View/download PDF
18. HEURISTIC 0-1 LINEAR PROGRAMMING: AN EXPERIMENTAL COMPARISON OF THREE METHODS.
- Author
-
Zanakis, Stelios H.
- Subjects
LINEAR programming ,HEURISTIC programming ,MATHEMATICAL programming ,REGRESSION analysis ,ANALYSIS of variance ,ALGORITHMS ,OPERATIONS research ,PROBLEM solving ,MATHEMATICAL models - Abstract
This paper examines the performance of three heuristic methods (Senju-Toyoda, Kochenberger et al., and Hillier) when applied to the 0-1 linear programming problem with nonnegative coefficients. Their effectiveness, measured in terms of computing time, error and relative error, is evaluated on a set of problems from the literature and randomly generated 0-1 test problems with nonnegative coefficients. Analysis of variance and stepwise regressions are employed to study the effect of the number of variables, number of constraints and degree of constraint slackness. The methods exhibited some similarities but also marked differences in their behavior. Interestingly enough, the larger the number of variables the better the accuracy of each method. Error differences among the three methods were significant (1:0.8:0.2) yet small (less than 2% on the average) for many practical situations. Hillier's algorithm was the most accurate but much slower and more core demanding than the other two, which makes it difficult or impossible to use for solving large 0-1 problems. Kochenberger's et al. heuristic was the fastest (most accurate) of the three in tightly (loosely) constrained problems. In general the Senju-Toyoda algorithm was the fastest, but least accurate on small and medium size problems. Suggestions are made for selecting the "best" heuristic based on the problem characteristics. [ABSTRACT FROM AUTHOR]
- Published
- 1977
- Full Text
- View/download PDF
19. A LINEAR PROGRAMMING ANALOGUE, A DUALITY THEOREM, AND A DYNAMIC ALGORITHM.
- Author
-
White, D.J.
- Subjects
DUALITY theory (Mathematics) ,LINEAR programming ,NONLINEAR programming ,ORGANIZATIONAL behavior ,MANAGEMENT science ,SIMPLEXES (Mathematics) ,ALGORITHMS ,COMPUTER simulation ,MANAGEMENT - Abstract
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]
- Published
- 1974
- Full Text
- View/download PDF
20. SOME EMPIRICAL TESTS OF THE CRISS-CROSS METHOD.
- Author
-
Zionts, Stanley
- Subjects
LINEAR programming ,MATHEMATICAL programming ,METHODOLOGY ,DYNAMIC programming ,MATHEMATICS ,ALGORITHMS ,SIMPLEXES (Mathematics) ,MATHEMATICAL optimization ,OPERATIONS research - Abstract
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]
- Published
- 1972
- Full Text
- View/download PDF
21. EXTREME POINT MATHEMATICAL PROGRAMMING.
- Author
-
Kirby, M. J. L., Love, H. R., and Swarup, Kanti
- Subjects
MATHEMATICAL optimization ,LINEAR programming ,MATHEMATICAL programming ,DYNAMIC programming ,PRODUCTION scheduling ,PRODUCTION management (Manufacturing) ,MANUFACTURING process management ,INTEGER programming ,ALGORITHMS ,MATHEMATICAL models of industrial management ,NUMERICAL analysis ,OPERATIONS research - Abstract
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]
- Published
- 1972
- Full Text
- View/download PDF
22. ELEMENTS OF LARGE-SCALE MATHEMATICAL PROGRAMMING PART I: CONCEPTS.
- Author
-
Geoffrion, Arthur M.
- Subjects
MATHEMATICAL programming ,MANAGEMENT science ,ALGORITHMS ,COMPUTER programming ,MATHEMATICAL optimization ,OPERATIONS research ,LINEAR programming ,LARGE scale systems ,BUSINESS mathematics ,MATHEMATICAL analysis ,MATHEMATICAL models - Abstract
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]
- Published
- 1970
- Full Text
- View/download PDF
23. A NEW APPROACH TO DISCRETE MATHEMATICAL PROGRAMMING.
- Author
-
Graves, G. and Whinston, A.
- Subjects
INTEGER programming ,LINEAR programming ,MANAGEMENT science ,PRODUCTION management (Manufacturing) ,DISCRETE mathematics ,POPULATION statistics ,MATHEMATICAL functions ,MATHEMATICAL programming ,INFINITE groups ,COMBINATORIAL enumeration problems ,OPERATIONS research ,ALGORITHMS ,OPTIMAL designs (Statistics) ,MATHEMATICAL mappings - Abstract
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.
- Published
- 1968
- Full Text
- View/download PDF
24. AN EXTENSION OF LAWLER AND BELL'S METHOD OF DISCRETE OPTIMIZATION WITH EXAMPLES FROM CAPITAL BUDGETING.
- Author
-
Mao, James C. T. and Wallingford, B. A.
- Subjects
CAPITAL budget ,ALGORITHMS ,MATHEMATICAL optimization ,LINEAR programming ,MANAGEMENT science ,CAPITAL investments ,INTEGER programming ,MATHEMATICAL programming ,OPERATIONS research - Abstract
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]
- Published
- 1968
- Full Text
- View/download PDF
25. MINIMUM CONCAVE COST FLOWS IN CERTAIN NETWORKS.
- Author
-
Zangwill, Willard I.
- Subjects
PRODUCTION planning ,NETWORK analysis (Planning) ,PRODUCT management ,MATERIALS management ,INVENTORY control ,ALGORITHMS ,PRODUCTION (Economic theory) ,LINEAR programming ,MATHEMATICAL programming ,CONCAVE functions ,CONVEX functions ,INDUSTRIAL costs ,MANAGEMENT - Abstract
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]
- Published
- 1968
- Full Text
- View/download PDF
26. ALGORITHMIC EQUIVALENCE IN LINEAR FRACTIONAL PROGRAMMING.
- Author
-
Wagner, Harvey M. and Yuan, John S.C.
- Subjects
ALGORITHMS ,LINEAR programming ,MATHEMATICAL variables ,HYPOTHESIS ,EQUIVALENCE relations (Set theory) ,MATHEMATICAL programming ,PROBLEM solving research ,MATHEMATICAL models ,EDUCATION - Abstract
This paper demonstrates the equivalence of several published algorithms for solving the so-called linear fractional programming problem. [ABSTRACT FROM AUTHOR]
- Published
- 1968
- Full Text
- View/download PDF
27. INTEGER PROGRAMMING: METHODS, USES, COMPUTATION.
- Author
-
Balinski, M.L.
- Subjects
INTEGER programming ,PROBLEM solving ,METHODOLOGY ,MATHEMATICAL programming ,LINEAR programming ,ALGORITHMS ,DISCRETE groups ,KNAPSACK problems ,COMBINATORIAL enumeration problems ,BRANCH & bound algorithms ,TRANSPORTATION ,OPERATIONS research - Abstract
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]
- Published
- 1965
- Full Text
- View/download PDF
28. A DYNAMIC PROGRAMMING ALGORITHM FOR EMBEDDED MARKOV CHAINS WHEN THE PLANNING HORIZON IS AT INFINITY.
- Author
-
de Cani, John S.
- Subjects
DYNAMIC programming ,ALGORITHMS ,MARKOV processes ,MATHEMATICAL models of industrial management ,MATHEMATICAL models in business ,MATHEMATICAL programming ,LINEAR programming ,STOCHASTIC processes ,BUSINESS planning ,DISTRIBUTION (Probability theory) ,MATHEMATICAL optimization ,BUSINESS mathematics - Abstract
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]
- Published
- 1964
- Full Text
- View/download PDF
29. A STRUCTURAL METHOD OF COMPUTING PROJECT COST POLYGONS.
- Author
-
Prager, William
- Subjects
LINEAR programming ,PRODUCTION scheduling ,NETWORK analysis (Planning) ,CONSTRUCTION industry planning ,ALGORITHMS ,MATHEMATICAL programming ,MATRICES (Mathematics) ,CRITICAL path analysis ,CIVIL engineering ,EDUCATION - Abstract
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]
- Published
- 1963
- Full Text
- View/download PDF
30. A LINEAR PROGRAMMING APPROACH TO THE CHEMICAL EQUILIBRIUM PROBLEM.
- Author
-
Dantzig, George, Johnson, Selmer, and White, Wayne
- Subjects
CHEMICAL equilibrium ,LINEAR programming ,DYNAMIC programming ,PRODUCTION scheduling ,MATHEMATICAL programming ,ALGORITHMS ,LINEAR free energy relationship ,APPROXIMATION theory ,CONVEX functions ,MANAGEMENT science ,SEPARABLE algebras ,CHEMICAL engineers - Abstract
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]
- Published
- 1958
- Full Text
- View/download PDF
31. ON A DYNAMIC PROGRAMMING APPROACH TO THE CATERER PROBLEM--I.
- Author
-
Bellman, Richard
- Subjects
DYNAMIC programming ,MATHEMATICAL programming ,MATHEMATICAL optimization ,MATHEMATICAL economics ,ECONOMICS methodology ,LINEAR programming ,CATERING services ,PRODUCTION scheduling ,INDUSTRIAL efficiency ,ALGORITHMS ,EQUATIONS ,ECONOMICS - Abstract
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 L
n = ∑I=1 n v1 , 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]- Published
- 1957
- Full Text
- View/download PDF
32. An Exact Algorithm for Finding Extreme Supported Nondominated Points of Multiobjective Mixed Integer Programs.
- Subjects
ALGORITHMS ,MATHEMATICAL optimization ,INTEGER programming ,KNAPSACK problems ,MATHEMATICAL programming ,LINEAR programming - Abstract
In this paper, we present an exact algorithm to find all extreme supported nondominated points of multiobjective mixed integer programs. The algorithm uses a composite linear objective function and finds all the desired points in a finite number of steps by changing the weights of the objective functions in a systematic way. We develop further variations of the algorithm to improve its computational performance and demonstrate our algorithm’s performance on multiobjective assignment, knapsack, and traveling salesperson problems with three and four objectives. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF
33. Reduce-and-Split Cuts: Improving the Performance of Mixed-Integer Gomory Cuts.
- Author
-
Andersen, Kent, Cornuéjols, Gérard, and Yanjun Li
- Subjects
LINEAR programming ,INTEGER programming ,HEURISTIC programming ,COMPUTER software ,ALGORITHMS ,BRANCH & bound algorithms ,MANAGEMENT ,COMPUTERS in management - Abstract
Mixed-integer Gomory cuts have become an integral part of state-of-the-art software for solving mixedinteger linear programming problems. Therefore, improvements in the performance of these cutting planes can be of great practical value. In this paper, we present a simple and fast heuristic for improving the coefficients on the continuous variables in the mixed-integer Gomory cuts. This is motivated by the fact that in a mixed-integer Gomory cut, the coefficient of an integer variable lies between 0 and 1, whereas for a continuous variable, there is no upper bound. The heuristic tries to reduce the coefficients of the continuous variables. We call the resulting cuts reduce-and-split cuts. We found that on several test problems, reduce-and-split cuts can substantially enhance the performance of a branch-and-bound algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
34. Pooling Problem: Alternate Formulations and Solution Methods.
- Author
-
Audet, Charles, Brimberg, Jack, Hansen, Pierre, Le Digabel, Sébastien, and Mladenovic, Nenad
- Subjects
PETROLEUM industry ,LINEAR programming ,PRODUCTION planning ,PRODUCTION control ,INDUSTRIAL management ,MANAGEMENT science ,MATHEMATICAL programming ,CONVEX functions ,ALGORITHMS ,CASH flow ,BRANCH & bound algorithms ,PRODUCT management - Abstract
The pooling problem, which is fundamental to the petroleum industry, describes a situation in which products possessing different attribute qualities are mixed in a series of pools in such a way that the attribute qualities of the blended products of the end pools must satisfy given requirements. It is well known that the pooling problem can be modeled through bilinear and nonconvex quadratic programming. In this paper, we investigate how best to apply a new branch-and-cut quadratic programming algorithm to solve the pooling problem. To this effect, we consider two standard models: One is based primarily on flow variables, and the other relies on the proportion of flows entering pools. A hybrid of these two models is proposed for general pooling problems. Comparison of the computational properties of flow and proportion models is made on several problem instances taken from the literature. Moreover, a simple alternating procedure and a variable neighborhood search heuristic are developed to solve large instances and compared with the well-known method of successive linear programming. Solution of difficult test problems from the literature is substantially accelerated, and larger ones are solved exactly or approximately. [ABSTRACT FROM AUTHOR]
- Published
- 2004
- Full Text
- View/download PDF
35. Effective Zero-Inventory-Ordering Policies for the Single-Warehouse Multiretailer Problem with Piecewise Linear Cost Structures.
- Author
-
Lap Mui Ann Chan, Muriel, Ana, Zuo-Jun Max Shen, Simchi-Levi, David, and Chung-Piaw Teo
- Subjects
BUSINESS logistics ,INDUSTRIAL management ,ALGORITHMS ,INVENTORY control ,PHYSICAL distribution of goods ,MANAGEMENT science ,TRUCKLOAD shipping ,LESS-than-truckload shipping ,DISCOUNT prices ,COST control ,LINEAR programming ,HEURISTIC - Abstract
We analyze the problem faced by companies that rely on TL (Truckload) and LTL (Less than Truckload) carriers for the distribution of products across their supply chain. Our goal is to design simple inventory policies and transportation strategies to satisfy time- varying demands over a finite horizon, while minimizing systemwide cost by taking advantage of quantity discounts in the transportation cost structures. For this purpose, we study the cost effectiveness of restricting the inventory policies to the class of zero-inventory-ordering (ZIO) policies in a single-warehouse multiretailer scenario in which the warehouse serves as a cross-dock facility. In particular, we demonstrate that there exists a ZIO inventory policy whose total inventory and transportation cost is no more than 4/3 (5.6/4.6 if transportation costs are stationary)times the optimal cost. However, finding the best ZIO policy is an NP-hard problem as well.Thus, we propose two algorithms to find an effective ZIO policy: An exact algorithm whose running time is polynomial for any fixed number of retailers, and a linear-programming-based heuristic whose effectiveness is demonstrated in a series of computational experiments. Finally, we extend the worst-case results developed in this paper to systems in which the warehouse does hold inventory. [ABSTRACT FROM AUTHOR]
- Published
- 2002
- Full Text
- View/download PDF
36. Generalized Column Generation for Linear Programming.
- Author
-
O>ilde;uz, Osman
- Subjects
LINEAR programming ,MATHEMATICAL variables ,ITERATIVE methods (Mathematics) ,MATHEMATICS ,ALGORITHMS ,ALGEBRA ,SIMPLEXES (Mathematics) ,TECHNOLOGY ,BUSINESS mathematics ,MANAGEMENT science - Abstract
Column generation is a well-known and widely practiced technique for solving linear programs with too many variables or constraints to include in the initial formulation explicitly. Instead, the required column information is generated at each iteration of the simplex algorithm. This paper shows that, even if the number of variables is low enough for explicit inclusion in the model with the available technology, it may still be more efficient to resort to column generation for some class of problems. [ABSTRACT FROM AUTHOR]
- Published
- 2002
- Full Text
- View/download PDF
37. Solving the Cell Suppression Problem on Tabular Data with Linear Constraints.
- Author
-
Fischetti, Matteo and Salazar, Juan José
- Subjects
DATA protection ,THEORY of constraints ,LINEAR statistical models ,LINEAR programming ,STATISTICS ,MATHEMATICAL optimization ,PROBLEM solving ,METHODOLOGY ,TABLES (Furniture) ,INTEGER programming ,ALGORITHMS ,HEURISTIC - Abstract
Cell suppression is a widely used technique for protecting sensitive information in statistical data presented in tabular form. Previous works on the subject mainly concentrate on 2-and 3-dimensional tables whose entries are subject to marginal totals. In this paper we address the problem of protecting sensitive data in a statistical table whose entries are linked by a generic system of linear constraints. This very general setting covers, among others, k -dimensional tables with marginals as well as the so-called hierarchical and linked tables that are very often used nowadays for disseminating statistical data. In particular, we address the optimization problem known in the literature as the (secondary) Cell Suppression Problem, in which the information loss due to suppression has to be minimized. We introduce a new integer linear programming model and outline an enumerative algorithm for its exact solution. The algorithm can also be used as a heuristic procedure to find near-optimal solutions. Extensive computational results on a test-bed of 1,160 real-world and randomly generated instances are resented, showing the effectiveness of the approach In particular, we were able to solve to proven optimality 4-dimensional tables with marginals as well as linked tables of reasonable size (to our knowledge, tables of this kind were never solved optimally by previous authors). [ABSTRACT FROM AUTHOR]
- Published
- 2001
- Full Text
- View/download PDF
38. A NOTE ON PARAMETRIC NETWORK FLOWS.
- Author
-
Minieka, Edward
- Subjects
ALGORITHMS ,COMPUTER algorithms ,COMPUTER networks ,NETWORK PC (Computer) ,LINEAR programming ,DATA flow computing ,MODULES (Algebra) ,MATHEMATICAL programming ,COMPUTER programming ,SPANNING trees - Abstract
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]
- Published
- 1973
- Full Text
- View/download PDF
39. ALGORITHMS FOR SCHEDULING A SINGLE MACHINE TO MINIMIZE THE WEIGHTED NUMBER OF LATE JOBS.
- Author
-
Potts, C. N. and van Wassenhove, L. N.
- Subjects
PRODUCTION scheduling ,SCHEDULING ,ALGORITHMS ,LINEAR programming ,DYNAMIC programming ,MATHEMATICAL optimization ,BRANCH & bound algorithms ,PRODUCTION control ,SYSTEMS engineering - Abstract
This paper considers the problem of scheduling n jobs, each having a processing time, a due date and a weight, on a single machine to minimize the weighted number of late jobs. An O(n log n) algorithm is given for solving the linear programming problem obtained by relaxing the integrality constraints in a zero-one programming formulation of the problem. This linear programming lower bound is used in a reduction algorithm that eliminates jobs from the problem. Also, a branch and bound algorithm that uses the linear programming lower bound is proposed. Computational results with branch and bound algorithms that use this and other lower bounds and with a dynamic programming algorithm for problems with up to 1000 jobs are given. [ABSTRACT FROM AUTHOR]
- Published
- 1988
- Full Text
- View/download PDF
40. THE EFFICIENCY OF THE SIMPLEX METHOD: A SURVEY.
- Author
-
Shamir, Ron
- Subjects
LINEAR programming ,MATHEMATICAL programming ,MATHEMATICAL optimization ,SIMPLEXES (Mathematics) ,MONTE Carlo method ,PROBABILITY theory ,ALGORITHMS ,MATHEMATICAL analysis ,MATHEMATICAL models ,NUMERICAL analysis ,PROBLEM solving - Abstract
The Linear Programming Problem is by far the most widely used optimization model. Its impact on economic and government modeling is immense. The Simplex Method for solving the Linear Programming (LP) Problem, due to George Dantzig, has been an extremely efficient computational tool for almost four decades. The method has been the subject of intense investigations for many years, but some major aspects of its behavior are not fully understood yet. The purpose of this paper is to survey the body of knowledge on the efficiency of the Simplex Method, from both practical and theoretical points of view. Adopting the number of iterations (pivot steps) as the yardstick for efficiency, we survey four aspects of the issue: 1. Reports on practical experience of the method's performance on real-life LP problems. 2. Results on controlled (Monte-Carlo) experiments solving LP problems which were randomly generated according to some predetermined distributions. 3. Complexity results, including theoretical analyses on both upper and lower bounds for the performance of the Simplex as well as non-Simplex algorithms for LP. 4. Results of recent theoretical studies using probabilistic analysis to derive bounds on the average behavior of the Simplex Method. We discuss the consequences and limitations of the various studies. Special emphasis is given to open questions. [ABSTRACT FROM AUTHOR]
- Published
- 1987
- Full Text
- View/download PDF
41. AN INTERACTIVE MULTIPLE OBJECTIVE LINEAR PROGRAMMING METHOD FOR A CLASS OF UNDERLYING NONLINEAR UTILITY FUNCTIONS.
- Author
-
Zionts, Stanley and Wallenius, Jyrki
- Subjects
UTILITY functions ,MATHEMATICAL models of decision making ,LINEAR programming ,MATHEMATICAL programming ,CONCAVE functions ,PRODUCTION scheduling ,PRODUCTION control ,MANAGEMENT science ,MATHEMATICAL optimization ,OPERATIONS research ,ALGORITHMS ,MATHEMATICAL models - Abstract
This paper develops a method for interactive multiple objective linear programming assuming an unknown pseudo concave utility function satisfying certain general properties. The method is an extension of our earlier method published in this journal [18]. Various technical problems present in predecessor versions have been resolved. In addition to presenting the supporting theory and algorithm, we discuss certain options in implementation and summarize our practical experience with several versions of the method. [ABSTRACT FROM AUTHOR]
- Published
- 1983
- Full Text
- View/download PDF
42. EFFICIENT HEURISTIC ALGORITHMS FOR POSITIVE 0-1 POLYNOMIAL PROGRAMMING PROBLEMS.
- Author
-
Granot, Frieda
- Subjects
HEURISTIC programming ,MATHEMATICAL programming ,INTEGER programming ,OPERATIONS research ,PROBABILITY theory ,POLYNOMIALS ,ALGORITHMS ,HEURISTIC ,RISK assessment ,EVALUATION ,LINEAR programming ,COMPUTATIONAL complexity - Abstract
We develop in this paper two types of heuristic methods for solving the positive 0-1 polynomial programming (PP) problem of finding a 0-1 vector x that maximizes c[SUPT]x subject to f(x) ⩽ b where c, b ⩾ 0 and f is an m-vector of polynomials with non-negative coefficients. The various heuristics were first tested on randomly generated sparse problems of up to 50 variables and 50 constraints, and their performance in terms of computational time and effectiveness was investigated. The results were very encouraging. Optimal solutions were consistently obtained by some of the heuristic methods in over 50% of the problems solved. The effectiveness was on the average better than 99% and no less than 96.5%. The computational time using these heuristics is on the average 5% of the time required to solve the PP problems to optimality. Some results for very sparse problems with up to 1000 variables and 200 constraints are also reported. [ABSTRACT FROM AUTHOR]
- Published
- 1982
- Full Text
- View/download PDF
43. SIMULATION OF DECENTRALIZED PLANNING IN TWO DANISH ORGANIZATIONS USING LINEAR PROGRAMMING DECOMPOSITION.
- Author
-
Christensen, John and Obel, Børge
- Subjects
DECENTRALIZATION in management ,LINEAR programming ,MATHEMATICAL decomposition ,MATHEMATICS ,PROBABILITY theory ,ALGORITHMS ,ORGANIZATIONAL structure ,BUSINESS planning ,SIMULATION methods & models ,MANAGEMENT science - Abstract
This paper describes the results of two studies where decentralized planning has been simulated. The coordination mechanisms employed were based on the Dantzig-Wolfe decomposition algorithm, and the Ten Kate decomposition algorithm, which are price directive and budget directive planning procedures, respectively. The importance of the results is that the data and the structure of the two planning problems come from real organizations--a cooperative slaughterhouse and a forecast model for Danish agriculture. Thus conclusions based on using a price-directive and a budget-directive planning method to simulate decentralized planning m these organizations have relevance to the potential value of using such methods in real organizations, The mare conclusions concern the importance of and the difficulties in finding good starting strategies for the two methods and the impact of the organizational structure on the rate of improvement for the methods. [ABSTRACT FROM AUTHOR]
- Published
- 1978
- Full Text
- View/download PDF
44. INTERACTIVE PREFERENCE OPTIMIZATION FOR UNIVERSITY ADMINISTRATORS.
- Author
-
Wehrung, Donald A., Hopkins, David S.P., and Massy, William F.
- Subjects
STRATEGIC planning ,FINANCIAL planning ,COLLEGE administrators ,PRIVATE universities & colleges ,UNIVERSITIES & colleges ,ALGORITHMS ,LINEAR programming ,MATHEMATICAL programming ,MATHEMATICAL optimization ,FINANCIAL management ,MATHEMATICAL models ,ECONOMICS - Abstract
This paper describes a long-range planning procedure for administrators in private universities. The procedure operates by generating a sequence of alternative future configurations of the university that satisfy several financial constraints and by helping an administrator to assess his preferences on them. A mathematical programming algorithm is used to structure the interactive identification/search procedure. It incorporates the strategy of restriction and linear programming methods to generate new configurations, and it relies upon the interactively assessed preferences of the administrator to guide the search process rather than a standard objective function. [ABSTRACT FROM AUTHOR]
- Published
- 1978
- Full Text
- View/download PDF
45. A MODIFIED BENDERS' PARTITIONING ALGORITHM FOR MIXED INTEGER PROGRAMMING.
- Author
-
McDaniel, Dale and Devine, Mike
- Subjects
ALGORITHMS ,INTEGER programming ,LINEAR programming ,MATHEMATICAL programming ,RELAXATION methods (Mathematics) ,NETWORK analysis (Planning) ,NUMERICAL analysis ,MATHEMATICAL models ,PROBLEM solving - Abstract
As applied to mixed-integer programming, Benders' original work made two primary contributions: (1) development of a "pure integer" problem (Problem P) that is equivalent to the original mixed-integer problem, and (2) a relaxation algorithm for solving Problem P that works iteratively on an LP problem and a "pure integer" problem. In this paper a modified algorithm for solving Problem P is proposed, in which the solution of a sequence of integer programs is replaced by the solution of a sequence of linear programs plus some (hopefully few) integer programs. The modified algorithm will still allow for taking advantage of any special structures (e.g. an LP subproblem that is a "network problem") just as in Benders' original algorithm. The modified Benders' algorithm is explained and limited computational results are given. [ABSTRACT FROM AUTHOR]
- Published
- 1977
- Full Text
- View/download PDF
46. A COMPUTATION STUDY ON START PROCEDURES, BASIS CHANGE CRITERIA, AND SOLUTION ALGORITHMS FOR TRANSPORTATION PROBLEMS.
- Author
-
Glover, Fred, Karney, D., Klingman, D., and Napier, A.
- Subjects
TRANSPORTATION problems (Programming) ,LINEAR programming ,GOVERNMENT policy ,ALGORITHMS ,STANDARD deviations ,ECONOMIC policy ,SIMPLEXES (Mathematics) ,COMPILERS (Computer programs) ,MANAGEMENT science - Abstract
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]
- Published
- 1974
- Full Text
- View/download PDF
47. NESTED DECOMPOSITION AND MULTI-STAGE LINEAR PROGRAMS.
- Author
-
Glassey, C. Roger
- Subjects
LINEAR programming ,MATHEMATICAL decomposition ,MATHEMATICAL programming ,MANAGEMENT science ,MATHEMATICAL optimization ,MATHEMATICAL models ,ALGORITHMS ,PRODUCTION scheduling ,MATHEMATICAL variables - Abstract
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]
- Published
- 1973
- Full Text
- View/download PDF
48. THE EQUIVALENCE OF INTEGER PROGRAMS TO CONSTRAINED RECURSIVE SYSTEMS.
- Author
-
Nanda, Patanjali S.
- Subjects
RECURSIVE programming ,INTEGER programming ,LINEAR programming ,MATHEMATICAL programming ,TRAVELING salesman problem ,ALGORITHMS ,MATHEMATICAL models ,OPERATIONS research ,MANAGEMENT education - Abstract
It has been established that integer programs with integral, recursive constraint matrices have integral extreme points for integral, nonnegative requirement vectors. In this paper, it is first shown that the assignment problem can be transformed to such a program, but with upper bounds on some variables. This equivalent program leads to additional results for solving the assignment problem. Algorithms are then delineated to transform matching, covering and travelling salesman problems to equivalent recursive programs of the aforementioned type, but with bounds on some variables. These results are extended to programs with special structure in their constraint matrices. [ABSTRACT FROM AUTHOR]
- Published
- 1973
- Full Text
- View/download PDF
49. CRITICAL PATH PROBLEMS WITH CONCAVE COST-TIME CURVES.
- Author
-
Falk, James E. and Horowitz, Joel L.
- Subjects
ALGORITHMS ,COST accounting ,CRITICAL path analysis ,PRODUCTION scheduling ,BUDGET ,COMPUTER software ,NUMERICAL analysis ,MATHEMATICAL optimization ,CONCAVE functions ,LINEAR programming - Abstract
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]
- Published
- 1972
- Full Text
- View/download PDF
50. MULTIPARAMETRIC LINEAR PROGRAMMING.
- Author
-
Gal, Tomas and Nedoma, Josef
- Subjects
LINEAR programming ,MATHEMATICAL programming ,MATHEMATICAL optimization ,VECTOR analysis ,MATRICES (Mathematics) ,PRICING ,ALGORITHMS ,PROBLEM solving ,MATHEMATICAL models - Abstract
The multiparametric linear programming (MLP) problem for the right-hand sides (RHS) is to maximize z = c
T 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]- Published
- 1972
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.