73 results
Search Results
2. 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
3. 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
4. A Dynamic Lot-Sizing Model with Demand Time Windows.
- Author
-
Chung-Yee Lee, Çetinkaya, Sila, and Wagelmans, Albert P. M.
- Subjects
ECONOMIC lot size ,DYNAMIC programming ,MATHEMATICAL optimization ,INVENTORY control ,PRODUCTION control ,ALGORITHMS ,MATHEMATICAL models ,MANAGEMENT science ,ECONOMIC demand - Abstract
One of the basic assumptions of the classical dynamic lot-sizing model is that the aggregate demand of a given period must be satisfied in that period. Under this assumption, if backlogging is not allowed, then the demand of a given period cannot be delivered earlier or later than the period. If backlogging is allowed, the demand of a given period cannot be delivered earlier than the period, but it can be delivered later at the expense of a backordering cost. Like most mathematical models, the classical dynamic lot-sizing model is a simplified paraphrase of what might actually happen in real life. In most real-life applications, the customer offers a grace period--we call it a demand time window--during which a particular demand can be satisfied with no penalty. That is, in association with each demand, the customer specifies an acceptable earliest and a latest delivery time. The time interval characterized by the earliest and latest delivery dates of a demand represents the corresponding time window. This paper studies the dynamic lot-sizing problem with demand time windows and provides polynomial time algorithms for computing its solution. If backlogging is not allowed, the complexity of the proposed algorithm is O(T²) where T is the length of the planning horizon. When backlogging is allowed, the complexity of the proposed algorithm is O(T³). [ABSTRACT FROM AUTHOR]
- Published
- 2001
- Full Text
- View/download PDF
5. Improving Discrete Model Representations via Symmetry Considerations.
- Author
-
Sherali, Hanif D. and Smith, J. Cole
- Subjects
MATHEMATICAL models ,INTEGER programming ,MATHEMATICAL programming ,SYMMETRY ,MATHEMATICAL reformulation ,ALGORITHMS ,MATHEMATICAL optimization ,BRANCH & bound algorithms ,TELECOMMUNICATION systems ,COMPUTER networks ,MANAGEMENT science - Abstract
In this paper, we focus on a useful modeling concept that is frequently ignored while formulating discrete optimization problems. Very often, there exists a natural symmetry inherent in the problem itself that, if propagated to the model, can hopelessly mire a branch-and-bound solver by burdening it to explore and eliminate such alternative symmetric solutions. We discuss three applications where such a symmetry arises: a telecommunications network design problem, a noise pollution problem, and a machine procurement and operation problem. For each case, we identify the indistinguishable objects in the model that create the problem symmetry and show how imposing certain decision hierarchies within the model significantly enhances its solvability, while using a popular modern-day commercial branch-and-cut software (CPLEX 6.5). [ABSTRACT FROM AUTHOR]
- Published
- 2001
- Full Text
- View/download PDF
6. IMPROVED COMBINATORIAL PROGRAMMING ALGORITHMS FOR A CLASS OF ALL-ZERO-ONE INTEGER PROGRAMMING PROBLEMS.
- Author
-
Pierce, John F. and Lasky, Jeffery S.
- Subjects
MATHEMATICAL programming ,COMBINATORIAL optimization ,ALGORITHMS ,MODIFICATIONS ,DYNAMIC programming ,NONLINEAR programming ,INTEGER programming ,MANAGEMENT science ,MATHEMATICAL optimization ,PROBLEM solving - Abstract
In an earlier paper [20] combinatorial programming procedures were presented for solving a class of integer programming problems in which all elements are zero or one. By representing the problem elements in a binary computer as bits in a word and employing logical "and" and "or" operations in the problem-solving process, a number of problems involving several hundred integer variables were solved in a matter of seconds. In the present paper a number of improvements in these earlier algorithms are presented, including a new search strategy, methods for reducing the original problem, and mechanisms for feasibility filtering in multi-word problems. With these improvements problem-solving efficiency has been increased in many instances by an order of magnitude. In addition, the present paper contains computational experience obtained in solving problems for the k-best solutions. [ABSTRACT FROM AUTHOR]
- Published
- 1973
- Full Text
- View/download PDF
7. DETERMINING OPTIMAL REORDER INTERVALS IN CAPACITATED PRODUCTION-DISTRIBUTION SYSTEMS.
- Author
-
Jackson, Peter L., Maxwell, William L., and Muckstadt, John A.
- Subjects
PRODUCTION scheduling ,PRODUCTION (Economic theory) ,PHYSICAL distribution of goods ,NONLINEAR programming ,INTEGER programming ,ALGORITHMS ,MANAGEMENT science ,OPERATIONS research ,MATHEMATICAL optimization ,LAGRANGE equations - Abstract
The problem of determining consistent and realistic reorder intervals in complex production-distribution environments was formulated as a large scale, nonlinear, integer programming problem by Maxwell and Muckstadt (1985). They show how the special structure of the problem permits its solution by a standard network flow algorithm. In this paper, we review the Maxwell-Muckstadt model, provide necessary and sufficient conditions that characterize the solution, and show that the optimal partition of nodes in the production-distribution network is invariant to an arbitrary scaling of the set-up and holding cost parameters. We consider two capacitated versions of the model: one with a single constrained work center, and the other with multiple constrained work centers. For single constraint problems, the invariance corollary provides a simple closed-form solution. For the multiple work center problem, the invariance corollary is exploited in the development of a Lagrange multiplier method of solution. The technique is illustrated by means of a small example problem and a problem taken from a real industrial setting. [ABSTRACT FROM AUTHOR]
- Published
- 1988
- Full Text
- View/download PDF
8. ON THE SINGLE MACHINE SCHEDULING PROBLEM WITH QUADRATIC PENALTY FUNCTION OF COMPLETION TIMES: AN IMPROVED BRANCHING PROCEDURE.
- Author
-
Gupta, Sushil K. and Sen, Tapan
- Subjects
PRODUCTION scheduling ,PRODUCTION planning ,SCHEDULING ,PRODUCTION control ,MANAGEMENT science ,BRANCH & bound algorithms ,ALGORITHMS ,MATHEMATICAL optimization ,A priori ,TIME study - Abstract
This paper gives optimality conditions to obtain a priori precedence relationships among some of the jobs in a single machine scheduling problem so as to curtail the enumeration while using branch-and-bound technique. The objective is to minimize a quadratic (or generalized quadratic) penalty function of job completion times. [ABSTRACT FROM AUTHOR]
- Published
- 1984
- Full Text
- View/download PDF
9. AN ALGORITHM FOR DEPLOYING A CRIME DIRECTED (TACTICAL) PATROL FORCE.
- Author
-
Chelst, Kenneth
- Subjects
RESOURCE allocation ,POLICE patrol ,CRIMINAL justice system ,LEGITIMACY of governments ,STOCHASTIC processes ,ALGORITHMS ,MATHEMATICAL optimization ,CRIME analysis ,PROBABILITY theory ,MANAGEMENT science - Abstract
This paper presents an algorithm for deploying a crime directed patrol force. The optimization problem is formulated as the allocation of N patrol units among R high crime regions so as to maximize the weighted probability of a patrol intercept of a crime. The algorithm has full sensitivity analysis capabilities. This capability is critical because the model's input parameters include (1) crime weights, which in general will have a subjective component, (2) crime descriptive data, which are difficult to estimate, and (3) crime frequency data, which are likely to change with time. The paper presents an illustrative application of the algorithm. The resultant allocation is compared to a strategy which allocates patrol units in direct proportion to each region's total crime rate. The optimal allocation significantly increased the probability of an intercept. [ABSTRACT FROM AUTHOR]
- Published
- 1978
- Full Text
- View/download PDF
10. AN EFFICIENT ONE DIMENSIONAL SEARCH PROCEDURE.
- Author
-
Fox, R. L., Lasdon, L. S., Tamir, Arie, and Ratner, Margery
- Subjects
ALGORITHMS ,NONLINEAR programming ,MATHEMATICAL programming ,DYNAMIC programming ,SYSTEM analysis ,COMPUTER programming ,MATHEMATICAL optimization ,GRAPHIC methods ,MANAGEMENT science - Abstract
Many nonlinear programming algorithms utilize a one-dimensional search along directions generated by the algorithm. This paper describes a method for performing this search. The method finds 3 points which bracket the minimum, fits a quadratic through them to yield a fourth point, then fits successive cubics through 4 points, discarding one each time, until certain stop criteria are met. No gradient evaluations are required. Detailed flow charts of this procedure are given, and its performance is compared with that of 2 other algorithms. Eight test problems are used in this comparison, each solved using both exterior and interior penalty functions. The Davidon-Fletcher-Powell method is used to generate the search directions. Results show that the proposed procedure requires about ½ to ¾ the computer time of its nearest competitor, a procedure designed to be especially efficient when applied to penalty functions, and about &frac13 the time of the other competitor, the 2 point cubic search using derivatives. [ABSTRACT FROM AUTHOR]
- Published
- 1975
- Full Text
- View/download PDF
11. A SIMPLIFIED ALGORITHM FOR OBTAINING APPROXIMATE SOLUTIONS TO ZERO-ONE PROGRAMMING PROBLEMS.
- Author
-
Toyoda, Yoshiaki
- Subjects
PROBLEM solving ,DECISION making ,ALGORITHMS ,INTEGER programming ,APPROXIMATION theory ,MATHEMATICAL variables ,MATHEMATICAL optimization ,COMPUTERS ,MANAGEMENT science - Abstract
This paper is intended to present a simple and quick method for obtaining approximate solutions to large scale zero-one programming problems. The method does not use enumeration. Instead, it assigns measures of preferability to zero-one variables that change the values of the variables from zero to one. The method yields very good approximate solutions to zero-one programming problems in dramatically short computation time. Even for problems involving more than a thousand zero-one variables the computation time is of little concern. The method is applicable not only to those problems associated with obtaining the optimal package of variables with the value one but also to a great variety of binary choice ("Yes-No") problems. [ABSTRACT FROM AUTHOR]
- Published
- 1975
- Full Text
- View/download PDF
12. 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
13. A CLASS OF INSIDE-OUT ALGORITHMS FOR GENERAL PROGRAMS.
- Author
-
Gould, F. J.
- Subjects
ALGORITHMS ,STOCHASTIC convergence ,NONLINEAR programming ,MATHEMATICAL programming ,MATHEMATICAL optimization ,GEOMETRICAL constructions ,MANAGEMENT science ,MATHEMATICAL models ,MATHEMATICAL analysis ,OPERATIONS research ,MATHEMATICAL functions ,PROBLEM solving - Abstract
In this paper the Fiacco-McCormick SUMT technique is embedded in a class of inside-out algorithms. Convergence is demonstrated for the nonlinear programming problem under fairly general conditions and the algorithms are interpreted in a geometric structure. [ABSTRACT FROM AUTHOR]
- Published
- 1970
- Full Text
- View/download PDF
14. 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
15. NOTES ON THE THEORY OF DYNAMIC PROGRAMMING-- TRANSPORTATION MODELS.
- Author
-
Bellman, Richard
- Subjects
TRANSPORTATION management system ,DYNAMIC programming ,MATHEMATICAL optimization ,MATHEMATICAL programming ,ALGORITHMS ,SYSTEMS engineering ,MANAGEMENT science ,ORGANIZATIONAL structure ,PROBLEM solving ,BUSINESS communication ,MATHEMATICAL models in business ,MATHEMATICAL models of industrial management - Abstract
The purpose of this paper is to illustrate some applications of the functional equation technique of the theory of dynamic programming to a general class of problems arising in the study of networks, particularly those arising in transportation theory. [ABSTRACT FROM AUTHOR]
- Published
- 1958
- Full Text
- View/download PDF
16. ON THE LINEAR COMPLEMENTARITY PROBLEM.
- Author
-
Rao, Arza K.
- Subjects
LINEAR complementarity problem ,FEASIBILITY studies ,MATRICES (Mathematics) ,MATHEMATICAL programming ,ALGORITHMS ,VECTOR algebra ,MATHEMATICAL optimization ,OPERATIONS research ,MANAGEMENT science - Abstract
Consider the linear complementarity problem given in the system: (1) W = MZ + q (2) W ≥ 0, Z ≥ 0 (I) (3) Z[sup T] W = 0 where, W, Z and q are vectors of dimension n. M is a matrix of order n x n and Z[sup T] is the transpose of Z. Any (Z, W) satisfying (1), (2), and (3) is a complementary feasible solution to system (I). In the literature, a class of matrices is defined such that if M belongs to this class, then existence of a feasible solution to system (I) implies the existence of a complementary feasible solution to system (I) with W = 0. In this paper, a new class of matrices M is developed. It is shown that membership of a matrix M in M is equivalent to the property; for any q existence of a feasible solution to system (I) implies the existence of a complementary feasible solution to system (I) for that q with W = 0. This new class of matrices is not contained in any one of the known classes, namely, copositive plus, positive definite or semidefinite, P-matrices, P-matrices, Z-class, etc. [ABSTRACT FROM AUTHOR]
- Published
- 1975
- Full Text
- View/download PDF
17. An Exact Algorithm for Constrained Two-Dimensional Two-Staged Cutting Problems.
- Author
-
Hifi, Mhand and M'Hallah, Rym
- Subjects
CUTTING stock problem ,ALGORITHMS ,MATHEMATICAL optimization ,OPERATIONS research ,MANAGEMENT science - Abstract
The constrained two-dimensional cutting (C_TDC) problem consists of determining a cutting pattern of a set of n small rectangular piece types on a rectangular stock plate S with length L and width W, to maximize the sum of the profits of the pieces to be cut. Each piece type i, i = 1, ..., n, is characterized by a length l
i , a width wi , a profit (or weight) ci , and an upper demand value bi . The upper demand value is the maximum number of pieces of type i that can be cut on S. In this paper, we study the two-staged C_TDC problem, noted C_2TDC. It is a classical variant of the C_TDC where each piece is produced, in the final cutting pattern, by at most two cuts. We solve the C_2TDC problem using an exact algorithm that is mainly based on a bottom-up strategy. We introduce new lower and upper bounds and propose new strategies that eliminate several duplicate patterns. We evaluate the performance of the proposed exact algorithm on problem instances extracted from the literature and compare it to the performance of an existing exact algorithm. [ABSTRACT FROM AUTHOR]- Published
- 2005
- Full Text
- View/download PDF
18. Bounding Option Prices by Semidefinite Programming: A Cutting Plane Algorithm.
- Author
-
Jun-ya Gotoh and Hiroshi Konno
- Subjects
PRICES of securities ,PRICING ,MARKETING ,ALGORITHMS ,MATHEMATICAL programming ,MATHEMATICAL optimization ,PRICES ,OPTIONS (Finance) ,MANAGEMENT science - Abstract
In a recent article, Bertsimas and Popescu showed that a tight upper bound on a European-type call option price, given the first n moments of the distribution of the underlying security price, can be obtained by solving an associated semidefinite programming problem (SDP). The purpose of this paper is to improve and extend their results. We will show that a tight lower bound can be calculated by solving another SDP. Also, we will show that these problems can be solved very quickly by a newly developed cutting plane algorithm when n is less than six or seven. [ABSTRACT FROM AUTHOR]
- Published
- 2002
- Full Text
- View/download PDF
19. Bandwidth Packing: A Tabu Search Approach.
- Author
-
Laguna, Manuel and Glover, Fred
- Subjects
BANDWIDTHS ,PROBLEM solving ,TELECOMMUNICATION ,ALGORITHMS ,PROFIT maximization ,MANAGEMENT science ,MATHEMATICAL optimization ,INTEGER programming ,HEURISTIC ,MATHEMATICAL programming - Abstract
The bandwidth packing (BWP) problem is a combinatorially difficult problem arising in the area of telecommunications. The problem consists of assigning calls to paths in a capacitated graph, such that capacities are not violated and the total profit is maximized. In this paper we discuss the development of a tabu search (TS) method for the BWP problem. The method makes use of an efficient implementation of the k-shortest path algorithm, that allows the identification of a controlled set of feasible paths for each call. A tabu search is then performed to find the best path assignment for each call. The TS method developed here incorporates a number of features that have proved useful for obtaining optimal and near optimal solutions to difficult combinatorial problems. We establish the effectiveness of our approach by comparing its performance in speed and solution quality to other specialized heuristics and to a standard optimization package applied to a 0-1 integer programming formulation of the problem. [ABSTRACT FROM AUTHOR]
- Published
- 1993
- Full Text
- View/download PDF
20. PERFORMANCE OF SHORTEST PATH ALGORITHMS IN NETWORK FLOW PROBLEMS.
- Author
-
Divoky, James J. and Hung, Ming S.
- Subjects
BUSINESS networks ,ALGORITHMS ,TOPOLOGY ,MANAGEMENT science ,PROBLEM solving ,DECISION theory ,DECISION making ,STRATEGIC planning ,MATHEMATICAL optimization - Abstract
It is known that minimum cost flow problems can be solved by successive augmentations along shortest paths. In this paper the issues of implementing shortest path algorithms in this context are examined. Of particular interest is the dynamic topology that the flow networks exhibit. We develop a network generator capable of emulating such topology. Strategies for exploiting the special structures in such networks are discussed. A set of 9000 test problems is offered, from which a particular strategy/algorithm combination is shown to consistently produce superior results when compared to the other combinations. [ABSTRACT FROM AUTHOR]
- Published
- 1990
- Full Text
- View/download PDF
21. ASYMPTOMATIC METHODS IN THE PROBABILISTIC ANALYSES OF SEQUENCING AND PACKING HEURISTICS.
- Author
-
Coffman Jr., E.G., Lueker, G.S., and Kan, A.H.G. Rinnooy
- Subjects
PROBABILITY theory ,HEURISTIC ,MANAGEMENT science ,INTEGER programming ,MATHEMATICAL programming ,OPERATIONS research ,ALGORITHMS ,MATHEMATICAL optimization ,HEURISTIC programming - Abstract
Recently there has been considerable interest in the average-case performance of heuristics. This paper pursues that interest, where it concerns sequencing and packing problems. In particular, we survey the methods that have been used to obtain formal probabilistic analyses of heuristics for makespan scheduling and one-dimensional bin packing. In so doing, we present many of thc key results in these research areas. [ABSTRACT FROM AUTHOR]
- Published
- 1988
- Full Text
- View/download PDF
22. HEURISTICS WITH CONSTANT ERROR GUARANTEES FOR THE DESIGN OF TREE NETWORKS.
- Author
-
Altinkemer, Kemal and Gavish, Bezalel
- Subjects
HEURISTIC ,OPERATIONS research ,MANAGEMENT science ,NP-complete problems ,COMPUTATIONAL complexity ,ALGORITHMS ,MATHEMATICAL programming ,MATHEMATICAL optimization ,NETWORK analysis (Planning) - Abstract
A tree network is a collection of trees rooted at a common central node. Several types of network design problems can be viewed as requiring the formation of a spanning tree network of minimum length, subject to a bound on the sum of "weights" on the nodes of any component tree. Such problems are NP-complete, and experience has shown that only small examples can be solved to optimality. This paper describes an efficient heuristic algorithm based on partitioning of a traveling salesman tour. When all the nodes have a unit weight and the bound is K, the heuristic finds a solution whose cost is at most 3 - 2/K times the minimum; in the general case the error bound is 4. [ABSTRACT FROM AUTHOR]
- Published
- 1988
- Full Text
- View/download PDF
23. EXTENDING PLANNING LANGUAGES TO INCLUDE OPTIMIZATION CAPABILITIES.
- Author
-
Roy, Asim, Lasdon, L. S., and Lordeman, J.
- Subjects
PROGRAMMING languages ,DECISION support systems ,MANAGEMENT information systems ,ALGORITHMS ,MATHEMATICAL optimization ,MATHEMATICAL analysis ,OPERATIONS research ,NONLINEAR programming ,DECISION making ,ELECTRONIC spreadsheets ,MATHEMATICAL models ,MANAGEMENT science - Abstract
Planning languages and spreadsheet systems are very popular, and the number of new users is increasing dramatically. On larger computers, IFPS, System W, and FCS-EPS are among the most widely used systems; while on personal computers, Multiplan and 1-2-3 enjoy great popularity. Currently, such languages operate mainly as simulators, evaluating specific cases. In this paper, we propose methodology which is useful in designing an optimization capability for these languages. This capability permits the user to designate certain model variables as decisions, constraints, and the objective. Upper and lower limits on the decisions and constraints are also specified. The optimization interface then diagnoses the problem as linear or nonlinear, computes first partial derivatives needed by the solution algorithms, and invokes the appropriate "solver." Information regarding the optimal solution is obtained using the reporting and graphics capabilities of the planning language. Sensitivity analysis and "what if" features permit easy modification of the problem for further analysis. These ideas have been implemented in a system called IFPS/OPTIMUM, which provides an optimization capability to users of the widely-used planning language IFPS. A simple IFPS/OPTIMUM example is presented, and two applications are described. Endowing planning languages with an optimization capability promises to increase dramatically the use of optimization. There are already hundreds of thousands of users of planning languages and spreadsheet systems, most of whom are unfamiliar with optimization models or methods. Making optimization a natural extension of systems they understand and find very useful holds great promise, both for applications and for teaching optimization concepts. [ABSTRACT FROM AUTHOR]
- Published
- 1986
- Full Text
- View/download PDF
24. LARGE-SCALE PORTFOLIO OPTIMIZATION.
- Author
-
Perold, Andre F.
- Subjects
PORTFOLIO management (Investments) ,INVESTMENTS ,ALGORITHMS ,MATRICES (Mathematics) ,NONDIFFERENTIABLE functions ,MATHEMATICAL optimization ,OPTIMAL designs (Statistics) ,ANALYSIS of variance ,QUADRATIC programming ,TRANSACTION costs ,ANALYSIS of covariance ,MANAGEMENT science - Abstract
This paper describes a practical algorithm for large-scale mean-variance portfolio optimization. The emphasis is on developing an efficient computational approach applicable to the broad range of portfolio models employed by the investment community. What distinguishes these from the "usual" quadratic program is (i) the form of the covariance matrix arising from the use of factor and scenario models of return, and (ii) the inclusion of transactions limits and costs. A third aspect is the question of whether the problem should be solved parametrically in the risk-reward trade off parameter, &lamda;, or separately for several discrete values of &lamda;. We show how the parametric algorithm can be made extremely efficient by "sparsifying" the covariance matrix with the introduction of a few additional variables and constraints, and by treating the transaction cost schedule as an essentially nonlinear nondifferentiable function. Then we show how these two seemingly unrelated approaches can be combined to yield good approximate solutions when minimum trading size restrictions ("buy or sell at least a certain amount, or not at all") are added. In combination, these approaches make possible the parametric solution of problems on a scale not heretofore possible on computers where CPU time and storage are the constraining factors. [ABSTRACT FROM AUTHOR]
- Published
- 1984
- Full Text
- View/download PDF
25. ON "OPTIMIZING FIELD REPAIR KITS BASED ON JOB COMPLETION RATE"
- Author
-
March, Salvatore T. and Scudder, Gary D.
- Subjects
ALGORITHMS ,INVENTORY control ,MAINTENANCE ,REPAIRING ,SYSTEM downtime ,INDUSTRIAL costs ,HOLDING cost ,SPARE parts ,CONTRACTUAL penalties ,OPTIMAL designs (Statistics) ,MANAGEMENT science ,MATHEMATICAL optimization - Abstract
In a recent paper, Mamer and Smith (1982) presented a formulation for determining the optimal kit of parts and tools for on-site equipment repairs under a job completion criterion. The optimal kit minimizes the sum of expected broken job costs plus the annual inventory holding cost for those parts stocked. A broken job occurs whenever a repair cannot be completed because one or more of its required parts are not included in the field repair kit. Assuming equal penalties for all broken jobs, an algorithm developed by Eisner and Severance (1976) in a different context can be used to determine a set of optimal policies and a range on the penalty cost for which each policy is optimal. The ranges cover all penalty costs from 0 to ∞. This is significant for the repair kit problem since the actual penalty cost of broken jobs may be difficult to determine exactly. [ABSTRACT FROM AUTHOR]
- Published
- 1984
- Full Text
- View/download PDF
26. A LOWER MULTINOMIAL BOUND FOR THE TOTAL OVERSTATEMENT ERROR IN ACCOUNTING POPULATIONS.
- Author
-
Plante, Robert, Neter, John, and Leitch, Robert A.
- Subjects
POPULATION ,NONLINEAR programming ,MATHEMATICAL programming ,ALGORITHMS ,MATHEMATICAL optimization ,OPTIMAL designs (Statistics) ,BRANCH & bound algorithms ,ACCOUNTING ,ACCOUNTS receivable ,INVENTORY control ,MANAGEMENT science ,ERROR analysis in mathematics - Abstract
A lower bound on the total error in an accounting population is required, in conjunction with the point estimate of the total error amount and the upper bound, when adjusting an account to determine the amount of the adjustment. This paper extends the multinomial methodology for obtaining an upper bound on the total overstatement (or understatement) error in an accounting population to the determination of a lower bound on the total overstatement (or understatement) error. The methodology for obtaining a lower multinomial bound differs in several important respects from that for obtaining an upper bound. The proposed lower bound may be computed for up to 25 errors in the sample and provides tighter limits than the widely used Stringer bound. [ABSTRACT FROM AUTHOR]
- Published
- 1984
- Full Text
- View/download PDF
27. 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
28. A POLYNOMIALLY BOUNDED ALGORITHM FOR A NONLINEAR NETWORK ALLOCATION PROBLEM.
- Author
-
Elken, T. R., Freedman, H. T., and Gibson, A. E.
- Subjects
RESOURCE allocation ,ALGORITHMS ,MANAGEMENT science ,OPERATIONS research ,TELEPHONE systems ,RATE of return ,BUSINESS mathematics ,LAGRANGE equations ,ECONOMIC demand ,MATHEMATICAL optimization ,RESOURCE management ,NONLINEAR programming - Abstract
This paper presents an algorithm for determining the optimal allocation to demand points when the distribution system is a capacitated arborescence of N arcs and the cost (return) functions are convex (concave). It is proved that the algorithm generates an optimal solution by solving at most N(N + 1)/2 single-constraint subproblems. If the cost functions allow the Lagrange multiplier for the subproblems to be evaluated in polynomial time, then this is a polynomial algorithm. The analysis is motivated by the problem of allocating spare capacity in the loop plant portion of telephone networks. [ABSTRACT FROM AUTHOR]
- Published
- 1981
- Full Text
- View/download PDF
29. CLUSTER ANALYSIS: AN APPLICATION OF LAGRANGIAN RELAXATION.
- Author
-
Mulvey, John M. and Crowder, Harlan P.
- Subjects
CLUSTER analysis (Statistics) ,ALGORITHMS ,INDUSTRIAL location ,HEURISTIC programming ,STATISTICAL correlation ,MULTIVARIATE analysis ,MATHEMATICAL optimization ,RELAXATION methods (Mathematics) ,ITERATIVE methods (Mathematics) ,INDUSTRIAL clusters ,MANAGEMENT science - Abstract
This paper presents and tests an effective optimization algorithm for clustering homogeneous data. The algorithm iteratively employs a subgradient method for determining lower bounds and a simple search procedure for determining upper bounds. The overall objective is to assign n objects to m mutually exclusive "clusters" such that the sum of the distances from each object to a designated cluster median is minimum. The model represents a special case of the uncapacitated facility location and m-median problems. The technique has proven efficient for examples with n ≤ 200 (i.e., the number of 0-1 variables ≤ 40,006); computational experiences with 10 real-world clustering applications are provided. A comparison with a hierarchical agglomerative heuristic, the minimum squared error method, is included. It is shown that the optimization algorithm is an effective solution technique for the homogeneous clustering problem, and also a good method for providing tight lower bounds for evaluating the quality of solutions generated by other procedures. [ABSTRACT FROM AUTHOR]
- Published
- 1979
- Full Text
- View/download PDF
30. 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
31. STRONGER INEQUALITIES FOR 0, 1 INTEGER PROGRAMMING USING KNAPSACK FUNCTIONS.
- Author
-
Kianfar, Ferydoon
- Subjects
INTEGER programming ,KNAPSACK problems ,MATHEMATICAL programming ,MANAGEMENT science ,MATHEMATICAL optimization ,ALGORITHMS - Abstract
In deriving the well known cuts for cutting-plane methods in 0, 1 integer programming, the integer points outside the 0, 1 space can limit the parallel movement of the hyperplane of the cut toward the solution set. Furthermore it is unnecessarily restrictive to limit the movement of this hyperplane to parallel translations. This paper removes these two limitations in order to derive stronger cuts and reduce the total number of cuts required. Thus, it describes a method based on a special case of the knapsack function that replaces each cut or original constraint by a new inequality whose hyperplane passes through as many integer points in 0, 1 space as possible. [ABSTRACT FROM AUTHOR]
- Published
- 1971
- Full Text
- View/download PDF
32. GROUP THEORETIC ALGORITHMS FOR THE INTEGER PROGRAMMING PROBLEM II: EXTENSION TO A GENERAL ALGORITHM.
- Author
-
Shapiro, Jeremy F.
- Subjects
MANAGEMENT science ,ALGORITHMS ,DYNAMIC programming ,NONLINEAR programming ,INTEGER programming ,MATHEMATICAL optimization - Abstract
The main result of this paper is a group theoretic algorithm (GTIP2) for the integer programming problem. This algorithm is an extension of an algorithm from an earlier paper (part I). The algorithm in part I solves a group optimization problem derived from a given integer programming problem. The optimal solution to the group problem thereby obtained is an optimal solution to the integer programming problem if it is feasible. Unfortunately, an optimal solution to the group problem may yield an infeasible integer solution. The algorithm GTIP2 of this paper is an extension of the method of part I when it fails. In particular, GTIP2 employs a search procedure to find an optimal solution to the integer programming problem. The extent of the search is bounded by procedures derived from a variety of relevant group problems that are solved by the algorithm of part I. There is a discussion of the class of problems for which GTIP2 is primarily intended and the relation of GTIP2 to other algorithms is indicated. A numerical example and some partial computational results are included. [ABSTRACT FROM AUTHOR]
- Published
- 1968
- Full Text
- View/download PDF
33. AN ALGORITHM FOR SEPARABLE NONCONVEX PROGRAMMING PROBLEMS.
- Author
-
Falk, James E. and Soland, Richard M.
- Subjects
ALGORITHMS ,NONCONVEX programming ,COMPUTATIONAL complexity ,FOUNDATIONS of arithmetic ,MATHEMATICAL models in business ,MATHEMATICAL programming ,MANAGEMENT science ,BRANCH & bound algorithms ,INTEGER programming ,COMPUTER programming ,MATHEMATICAL optimization ,BUSINESS mathematics - Abstract
In this paper we present an algorithm for solving mathematical programming problems of the form: Find x = (x[sub 1], ..., x[sub n]) to minimize Σφ[sub i] (x[sub i]) subject to x ε G and I ≤ x ≤ L. Each φ[sub i] is assumed to be lower semicontinuous, possibly nonconvex, and G is assumed to be closed. The algorithm is of the branch and bound type and solves a sequence of problems in each of which the objective function is convex. These problems correspond to successive partitions of the feasible set. Two different rules for refining the partitions are considered; these load to convergence of the algorithm under different requirements on the problem functions. Examples are given, and computational considerations are discussed. [ABSTRACT FROM AUTHOR]
- Published
- 1969
- Full Text
- View/download PDF
34. TECHNIQUES FOR REMOVING NONBINDING CONSTRAINTS AND EXTRANEOUS VARIABLES FROM LINEAR PROGRAMMING PROBLEMS.
- Author
-
Thompson, Gerald L., Tonge, Fred M., and Zionts, Stanley
- Subjects
LINEAR programming ,MATHEMATICAL programming ,MATHEMATICAL optimization ,ALGORITHMS ,CONSTRAINT programming ,METHODOLOGY ,SIMPLEXES (Mathematics) ,MANAGEMENT science ,MATRICES (Mathematics) ,FUNCTIONAL equations - Abstract
In formulating linear programming problems, analysts tend to include constraints that are not binding at the optimal solution for fear of excluding necessary constraints. The inclusion of such constraints does not alter the optimum solutions, but may require many additional iterations to be taken, as well as increase the computational difficulties encountered. Most of the methods proposed to date for identification of redundant and non-binding constraints are not warranted in practice because of the excessive computations required to implement them. These methods are reviewed in the present paper, and some of them are extended. A number of additional methods are also considered. Two of these new methods are not only practical, but have proven to be powerful in solving a number of problems. These methods may be incorporated in a variant of the simplex method. After each simplex iteration is made, constraints and variables are tested and, when identified as non-binding, are eliminated. The procedure is continued, with the problem size dwindling as the algorithm progresses, until the optimum is reached. Then the values of the eliminated variables are computed by substitution into the eliminated constraints. Early evidence shows that a size reduction for small problems (having 25-30 constraints) of 50 percent is not unusual. It is hoped that the results on larger problems will be even more significant.(n4) [ABSTRACT FROM AUTHOR]
- Published
- 1966
- Full Text
- View/download PDF
35. Probabilistic analyses and practical algorithms for the vehicle routing problem with time windows.
- Author
-
Bramel, Julien and Simchi-Levi, David
- Subjects
ROUTE choice ,VEHICLES ,ALGORITHMS ,MATHEMATICAL optimization ,CONSUMERS ,HEURISTIC ,OPERATIONS research ,MANAGEMENT science ,MATERIALS handling - Abstract
In the Vehicle Routing Problem with Time Windows, a set of customers are served by a fleet of vehicles of limited capacity, initially located at a central depot. Each customer provides a period of time in which they require service, which may consist of repair work or loading/unloading the vehicle. The objective is to find tours for the vehicles, such that each customer is served in its time window, the total load on any vehicle is no more than the vehicle capacity, and the total distance traveled is as small as possible. In this paper, we present a characterization of the asymptotic optimal solution value for general distributions of service times, time windows, customer loads and locations. This characterization leads to the development of a new algorithm based on formulating the problem as a stylized location problem. Computational results show that the algorithm is very effective on a set of standard test problems. [ABSTRACT FROM AUTHOR]
- Published
- 1996
- Full Text
- View/download PDF
36. Tabu search and ejection chains--application to a node weighted version of the cardinality...
- Author
-
Cao, Buyang and Glover, Fred
- Subjects
SALES personnel ,MANAGEMENT science ,CITIES & towns ,ALGORITHMS ,FOUNDATIONS of arithmetic ,HEURISTIC ,COMBINATORIAL optimization ,MATHEMATICAL optimization ,THEORY of constraints - Abstract
A cardinality-constrained TSP (CC-TSP) problem requires the salesman to visit at least L and at most U cities, represented by nodes of a graph. The objective of this problem is to maximize the sum of weights of nodes visited, in this paper we propose a tabu search method based on ejection chain procedures, which have proved effective for many kinds of combinatorial optimization problems. Computational results on a set of randomly generated test problems with various implementations of the algorithm are reported. [ABSTRACT FROM AUTHOR]
- Published
- 1997
- Full Text
- View/download PDF
37. Parametric solution for linear bicriteria knapsack models.
- Author
-
Eben-Chaime, Moshe
- Subjects
MULTIPLE criteria decision making ,MATHEMATICAL models ,KNAPSACK problems ,STATISTICAL weighting ,DECISION making ,ALGORITHMS ,MANAGEMENT science ,LINEAR programming ,MATHEMATICAL optimization - Abstract
Linear weighing is a common approach to handle multiple criteria and the "knapsack" is a well-known combinatorial optimization problem. A knapsack problem with two linearly weighted, objective criteria is considered in this paper. For better support, it is important to provide the decision maker with information that covers the whole range of alternatives. Toward this goal, an algorithm for the construction of a parametric solution to the problem, i.e., for any combination of weights, is developed, which is based on finding a longest path in a network which compactly represents all feasible solutions to the knapsack problem. Exploiting the special structure of the knapsack model, the algorithm efficiently constructs the parametric solution in time that is linear in the product of the number of variables, the resource limit (right-hand side of the constraint), and the (finite) number of vectors which constitute the solution. The amount of memory required is linear in the product of the number of variables and the resource limit. Results of computational study are reported. The results are used to assess the efficiency of the algorithm and characterize its behavior with respect to the parameter values. [ABSTRACT FROM AUTHOR]
- Published
- 1996
- Full Text
- View/download PDF
38. A fast algorithm for a class of generalized fractional programs.
- Author
-
Gugat, Martin
- Subjects
DECISION making ,ALGORITHMS ,FRACTIONAL calculus ,STOCHASTIC convergence ,MULTIPLE criteria decision making ,MATHEMATICAL optimization ,MATHEMATICAL models ,MANAGEMENT science ,FRACTIONAL powers - Abstract
In many decision problems, criteria occur that can be expressed as ratios. The corresponding optimization problems are nonconvex programs of fractional type. In this paper, an algorithm for the numerical solution of these problems is introduced that converges always at superlinear speed. Numerical examples are presented. [ABSTRACT FROM AUTHOR]
- Published
- 1996
- Full Text
- View/download PDF
39. A Decomposition Method for Quadratic Zero-One Programming.
- Author
-
Chardaire, Pierre and Sutter, Alain
- Subjects
MATHEMATICAL optimization ,DECOMPOSITION method ,QUADRATIC programming ,BRANCH & bound algorithms ,LAGRANGIAN functions ,ALGORITHMS ,MATHEMATICAL programming ,NETWORK analysis (Planning) ,CALCULUS of variations ,MANAGEMENT science - Abstract
This paper proposes a decomposition method to compute a lower bound for unconstrained quadratic zero-one minimization. First, we show that any quadratic function can be expressed as a sum of particular quadratic functions whose minima can be computed by a simple branch and bound algorithm. Then, assuming some hypothesis, we prove that, among all possible decompositions, the best one can be found by a Lagrangian decomposition method. Moreover, we show that our algorithm gives at least the roof dual bound and should give better results in practice. Eventually, computational results and comparisons with Pardalos and Rodgers' algorithm demonstrate the efficiency of our method for medium size problems (up to 100 variables). [ABSTRACT FROM AUTHOR]
- Published
- 1995
- Full Text
- View/download PDF
40. THE USE OF OPTIMIZATION MODELS IN PUBLIC-SECTOR PLANNING.
- Author
-
Brill Jr., E. Downey
- Subjects
MATHEMATICAL optimization ,CREATIVE ability ,ALGORITHMS ,MATHEMATICAL analysis ,MULTIPLE criteria decision making ,DECISION making ,BUSINESS planning ,MANAGEMENT science ,COST effectiveness ,POLICY analysis ,INDUSTRIAL efficiency ,BUSINESS models - Abstract
When applied to public-sector planning, traditional least-cost optimization models and their offspring, contemporary multiobjective models, have often been developed under the optimistic philosophy of obtaining "the answer." Frequently, such models are not very useful because there is a multitude of local optima, which result from wavy indifference functions, and because important planning elements are not captured in the formulations. Omitted elements, in fact, may imply that an optimal planning solution lies within the inferior region of a multiobjective analysis instead of along the noninferior frontier. The role of optimization methods should be re-thought in full recognition of these limitations and of the relevant planning process. They should be used to generate planning alternatives and to facilitate their evaluation and elaboration; they should also be used to provide insights and serve as catalysts for human creativity. As illustrated by recent examples, these roles may require the use of several models as well as new types of optimization formulations and modified algorithms and computer codes. [ABSTRACT FROM AUTHOR]
- Published
- 1979
- Full Text
- View/download PDF
41. ACCELERATION OF LAGRANGIAN COLUMN-GENERATION ALGORITHMS BY PENALTY FUNCTION METHODS.
- Author
-
O'Neill, Richard P. and Widhelm, William B.
- Subjects
LAGRANGIAN functions ,MATHEMATICAL optimization ,ALGORITHMS ,STOCHASTIC convergence ,MANAGEMENT science ,CONVEX functions ,COMPUTER programming ,MATHEMATICAL models ,LAGRANGE equations ,OPERATIONS research - Abstract
A Lagrangian column-generation procedure is developed which retains the original problem functions for column generation but uses transformed penalty functions in the Lagrangian optimization. The class of penalty functions considered maintains the original order of differentiability and often enhances the optimization operation. Convergence is proven for convex problems and limited computational experience cited where the new procedure converges two to four times faster than the standard method. Certain modifications of these techniques to attack nonconvex problems are also presented. [ABSTRACT FROM AUTHOR]
- Published
- 1976
- Full Text
- View/download PDF
42. FRACTIONAL PROGRAMMING. II, ON DINKELBACH'S ALGORITHM.
- Author
-
Schaible, Siegfried
- Subjects
MATHEMATICAL programming ,ALGORITHMS ,DUALITY theory (Mathematics) ,MANAGEMENT science ,STOCHASTIC convergence ,MATHEMATICAL optimization ,MATHEMATICAL analysis ,CONVEX programming ,OPERATIONS research - Abstract
Dinkelbach's algorithm [2] solving the parametric equivalent of a fractional program is investigated. It is shown that the algorithm converges superlinearly and often (locally) quadratically. A priori and a posteriori error estimates are derived. Using those estimates and duality as introduced in Part I, a revised version of the algorithm is proposed. In addition, a similar algorithm is presented where, in contrast to Dinkelbach's procedure, the rate of convergence is still controllable. Error estimates are derived also for this algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 1976
- Full Text
- View/download PDF
43. A PRIMAL-DUAL TRAFFIC ASSIGNMENT ALGORITHM.
- Author
-
Petersen, E. R.
- Subjects
ASSIGNMENT problems (Programming) ,TRANSPORTATION problems (Programming) ,ALGORITHMS ,RAILROADS ,TRAFFIC engineering ,TRAFFIC flow ,RAILROAD engineering ,TRANSPORTATION engineering ,INDUSTRIAL efficiency ,MATHEMATICAL optimization ,MANAGEMENT science - Abstract
A new algorithm for solving the traffic assignment problem is presented. This is a primal-dual algorithm which utilizes a flow augmentation primal and a shortest path dual procedure. At each iteration a feasible solution is known together with a measure of "goodness" of the solution. It is shown that the algorithm converges to an optimal solution. Experience with the algorithm suggests that this convergence is very rapid. [ABSTRACT FROM AUTHOR]
- Published
- 1975
- Full Text
- View/download PDF
44. BOUNDS FOR PREFERENCE FUNCTION ASSESSMENT.
- Author
-
Bradley, Stephen P. and Frey, Jr., Sherwood C.
- Subjects
PREFERENCES (Philosophy) ,UTILITY theory ,RISK aversion ,MATHEMATICAL models of decision making ,DECISION theory ,LINEAR programming ,MATHEMATICAL functions ,PROBABILITY theory ,MATHEMATICAL optimization ,ALGORITHMS ,MANAGEMENT science - Abstract
It is well known that when an individual assesses a preference (utility) function, the set of assessed gambles and certainty equivalents is often inconsistent and, if consistent, many preference functions may satisfy the assessments. Mathematical programming is employed to examine properties that might be useful in a sequential determination of the individual's preference function. Specifically, given a consistent set of assessments, if an additional gamble were to be assessed, upper and lower bounds can be found for the probability of the better consequence of the gamble when the certainty equivalent is specified and also bounds for the certainty equivalent of the gamble when the probabilities are specified such that the augmented set of specifications remains consistent. The results are given for general, as well as risk averse preference functions. [ABSTRACT FROM AUTHOR]
- Published
- 1975
- Full Text
- View/download PDF
45. M/M/1 QUEUES WITH SWITCHING COSTS AND HYSTERETIC OPTIMAL CONTROL.
- Author
-
Kitaev, M. Yu. and Serfozo, Richard F.
- Subjects
QUEUING theory ,PRODUCTION scheduling ,STOCHASTIC processes ,ALGORITHMS ,MATHEMATICAL optimization ,MANAGEMENT science - Abstract
This paper considers an M/M/1 queueing system with dynamically controlled arrival and service rates. At each arrival or service completion epoch, a decision maker chooses a pair of arrival and service rates from a finite set, and the system operates under these rates until the next arrival or service completion. There is a switching cost for changing the rates, and there is a cost per unit time of holding customers and using the arrival and service rates. The results describe natural conditions on the costs under which an optimal policy for either the discounted-cost or average-cost criterion is a hysteretic policy. Such a policy increases the service rate and decreases the arrival rate as the queue length increases. Furthermore, the control exhibits a stickiness or resistance to change, called hysteresis, due to the switching costs. [ABSTRACT FROM AUTHOR]
- Published
- 1999
- Full Text
- View/download PDF
46. DYNAMIC PROGRAMMING ALGORITHMS FOR THE INTEGER PROGRAMMING PROBLEM-I: THE INTEGER PROGRAMMING PROBLEM VIEWED AS A KNAPSACK TYPE PROBLEM.
- Author
-
Shapiro, Jeremy F.
- Subjects
INTEGER programming ,DYNAMIC programming ,MATHEMATICAL optimization ,ALGORITHMS ,MATHEMATICAL programming ,KNAPSACK problems ,SYSTEMS engineering ,MANAGEMENT science - Abstract
GOMORY has transformed the integer programming problem into a related group optimization problem which can be more easily solved. An optimal solution to the group problem is optimal for the integer programming problem from which it is derived if the solution is feasible. An algorithm (IP Algorithm I) for solving the group optimization problem is developed, and sufficient conditions on its use are given. The usefulness of IP Algorithm I is extended by amending it to find alternative optima. In a subsequent paper, this algorithm is extended to an algorithm that can solve any integer programming problem. [ABSTRACT FROM AUTHOR]
- Published
- 1968
- Full Text
- View/download PDF
47. Global Optimality Conditions for Discrete and Nonconvex Optimization--With Applications to Lagrangian Heuristics and Column Generation.
- Author
-
Larsson, Torbjörn and Patriksson, Michael
- Subjects
PROBLEM solving ,MANAGEMENT science ,MATHEMATICAL optimization ,FEASIBILITY studies ,ALGORITHMS ,CONVEX programming - Abstract
The well-known and established global optimality conditions based on the Lagrangian formulation of an optimization problem are consistent if and only if the duality gap is zero. We develop a set of global optimality conditions that are structurally similar but are consistent for any size of the duality gap. This system characterizes a primal-dual optimal solution by means of primal and dual feasibility, primal Lagrangian ε-optimality, and, in the presence of inequality constraints, a relaxed complementarity condition analogously called δ-complementarity. The total size ε + δ of those two perturbations equals the size of the duality gap at an optimal solution. Further, the characterization is equivalent to a near-saddle point condition which generalizes the classic saddle point characterization of a primal-dual optimal solution in convex programming. The system developed can be used to explain, to a large degree, when and why Lagrangian heuristics for discrete optimization are successful in reaching near-optimal solutions. Further, experiments on a set-covering problem illustrate how the new optimality conditions can be utilized as a foundation for the construction of new Lagrangian heuristics. Finally, we outline possible uses of the optimality conditions in column generation algorithms and in the construction of core problems. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
48. An Algorithm for Portfolio Optimization with Transaction Costs.
- Author
-
Best, Michael J. and Hlouskova, Jaroslava
- Subjects
PORTFOLIO management (Investments) ,ALGORITHMS ,ASSETS (Accounting) ,TRANSACTION costs ,MATHEMATICAL optimization ,PROBLEM solving ,MANAGEMENT science ,MATHEMATICAL models of decision making ,PRACTICAL reason - Abstract
We consider the problem of maximizing an expected utility function of n assets, such as the mean-variance or power-utility function. Associated with a change in an asset's holdings from its current or target value is a transaction cost. This cost must be accounted for in practical problems. A straightforward way of doing so results in a 3n-dimensional optimization problem with 3n additional constraints. This higher dimensional problem is computationally expensive to solve. We present a method for solving the 3n-dimensional problem by solving a sequence of n-dimensional optimization problems, which accounts for the transaction costs implicitly rather than explicitly. The method is based on deriving the optimality conditions for the higher-dimensional problem solely in terms of lower-dimensional quantities. The new method is compared to the barrier method implemented in Cplex in a series of numerical experiments. With small but positive transaction costs, the barrier method and the new method solve problems in roughly the same amount of execution time. As the size of the transaction cost increases, the new method outperforms the barrier method by a larger and larger factor. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
49. Approximating Multiobjective Knapsack Problems.
- Author
-
Erlebach, Thomas, Kellerer, Hans, and Pferschy, Ulrich
- Subjects
KNAPSACK problems ,APPROXIMATION theory ,LINEAR programming ,MATHEMATICAL optimization ,INTEGER programming ,MATHEMATICAL analysis ,PROFIT ,ALGORITHMS ,MANAGEMENT science - Abstract
For multiobjective optimization problems, it is meaningful to compute a set of solutions covering all possible trade-offs between the different objectives. The multiobjective knapsack problem is a generalization of the classical knapsack problem in which each item has several profit values. For this problem, efficient algorithms for computing a provably good approximation to the set of all nondominated feasible solutions, the Pareto frontier, are studied. For the multiobjective one-dimensional knapsack problem, a practical fully polynomial-time approximation scheme (FPTAS) is derived. It is based on a new approach to the single-objective knapsack problem using a partition of the profit space into intervals of exponentially increasing length. For the multiobjective m-dimensional knapsack problem, the first known polynomial-time approximation scheme (PTAS), based on linear programming, is presented. [ABSTRACT FROM AUTHOR]
- Published
- 2002
- Full Text
- View/download PDF
50. Representing and Solving Decision Problems with Limited Information.
- Author
-
Lauritzen, Steffen L. and Nilsson, Dennis
- Subjects
DECISION making ,MARKOV processes ,ALGORITHMS ,MATHEMATICAL optimization ,PROBLEM solving ,MEMORY ,THEORY of constraints ,MANAGEMENT science ,STRATEGIC planning - Abstract
We introduce the notion of Limited Memory Influence Diagram (LIMID) to describe multistage decision problems in which the traditional assumption of no forgetting is relaxed. This can be relevant in situations with multiple decision makers or when decisions must be prescribed under memory constraints, such as in partially observed Markov decision processes (POMDPs). We give an algorithm for improving any given strategy by local computation of single policy updates and investigate conditions for the resulting strategy to be optimal. [ABSTRACT FROM AUTHOR]
- Published
- 2001
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.