Search

In public policy decision making and in capital planning fractional criterion functions occur. For a given set of desirable target values (goals) τi, this paper develops an algorithm for solving a nonconvex programming problem of the type: Minx∈S Maxi{&phii(fi(x)/gi(x) - τi), i = 1,..., m} where fi are convex functions, gi, are concave functions over the convex subset S of Rn and φi are nondecreasing gauge functions. Here φi(&middot) is the penalty incurred whenever the fractional objective fi/gi deviates from the target value τi, the problem is then to choose an x that minimizes the maximum penalty incurred. [ABSTRACT FROM AUTHOR]

This paper combines two rival preference modeling techniques in a new approach to multi-attribute decision making. Currently existing multi-attribute procedures use either global or local preference modeling. In the global modeling technique, a single preference function is constructed in the large; its maximum is the optimal alternative. In the local procedure, sequential approximations of the preference function are constructed in the small. Each approximation generates a trial solution. Under suitable conditions, each trial solution is preferred to its predecessor, so the trial sequence eventually reaches the optimum. Each technique has advantages and disadvantages; this paper combines the desirable features of both techniques in a new improved method. This new method, called the proxy approach, uses the advantages of one technique to overcome the disadvantages of the other. This paper first develops the theoretical aspects of the proxy approach and then compares it to existing procedures. Finally, the proxy algorithm is applied to a curriculum planning problem and numerous insights are gained. [ABSTRACT FROM AUTHOR]

Expert judgment is frequently used to assess parameter values of quantitative management science models, particularly in decision-making contexts. Experts can, however, only be expected to assess observable quantities, not abstract model parameters. This means that we need a method for translating expert assessed uncertainties on model outputs into uncertainties on model parameter values. This process is called probabilistic inversion. The probability distribution on model parameters obtained in this way can be used in a variety of ways, but in particular in an uncertainty analysis or as a Bayes prior. This paper discusses computational algorithms that have proven successful in various projects and gives examples from environmental modelling and banking. Those algorithms are given a theoretical basis by adopting a minimum information approach to modelling partial information. The role of minimum information is two-fold: It enables us to resolve the problem of nonuniqueness of distributions given the information we have, and it provides numerical stability to the algorithm by guaranteeing convergence properties. [ABSTRACT FROM AUTHOR]

Compound option valuation formulae give rise to the summation of a series of multinormal distribution functions. This paper presents an identity on sums of nested multinormal distributions of arbitrary dimension. We show that this identity generalizes some well-known low order identities for the multinormal distribution. We present three applications of the new identity to contingent claims valuation problems. The first and second applications show that by reducing significantly the number of integrals to be evaluated, faster and more accurate algorithms can be developed for implementing the Geske-Johnson American put valuation formula and the Roll-Geske-Whaley American call formula; the third gives new economic insights into the valuation of disaggregated coupon bonds. [ABSTRACT FROM AUTHOR]

This paper extends recent work on finding the stochastic queue median (SQM) on a network. The SQM is the optimal location of a single mobile server, when idle, who travels to customers in response to requests for service. Customer demands are limited to the nodes of the network and their requests for service arrive according to a time homogeneous Poisson process, independently from each node. When a service request finds the server busy with a previous customer, it is entered into an M/G/1 queue that is depleted in a first-in, first-out (FIFO) manner. The SQM is the point on the network at which the sum of mean queueing delay and mean travel time is minimized. In this paper the transportation network is restricted to be a tree. By discovering and exploiting convex properties of the objective function and related functions, an efficient finite-step algorithm is found for locating the SQM on a tree. [ABSTRACT FROM AUTHOR]

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]

This paper considers optimization problems with a nonlinear-additive objective function and a single linear constraint. Such models have numerous direct applications and serve as subproblems in procedures for more complex problems. Some important portfolio selection problems can be expressed in this form, and the problem also arises in economic theory. Several authors have noticed independently that special cases and variants of the problem can be solved exactly by surprisingly simple, finite algorithms. The major purpose of this paper is to present these results in a unified framework, which then permits substantial generalizations and extensions. The results lend themselves to an appealing managerial interpretation, similar to the rate-of-return cutoff rules of capital budgeting. [ABSTRACT FROM AUTHOR]

The most popular approach to developing mathematical models of organizational decision processes, the decomposition approach, begins with a mathematical statement of an ideal organizational problem and follows a process of decomposition to derive sub-problems solved by separate units at (possibly) different levels of the organization. Conversely, the composition approach starts with mathematical statements of the subproblems solved by the separate units and proceeds to develop a solution algorithm as a means of coordinating the activities of the separate units. A process of composition must then be followed if one is to discover the derived, organizational problem actually solved. This paper offers an operational definition of an organizational decision process and relates this process to the anatomy of mathematical models purported as being representative of it. Implications regarding the potential of the decision process models as tools of organizational design are explored. [ABSTRACT FROM AUTHOR]

This paper presents a systematic procedure for obtaining the optimum packaging frequencies for a number of items which are manufactured jointly but packaged individually immediately after manufacture. The method described in the paper is equally applicable to those problems where the optimum purchasing policy is to be obtained for a number of items procured from a single supplier. An example involving twenty jointly replenished items is solved to illustrate the procedure given in the paper. [ABSTRACT FROM AUTHOR]

This paper describes a practical algorithm based on Monte Carlo simulation for the pricing of multi- dimensional American (i.e., continuously exercisable) and Bermudan (i.e., discretely exercisable) options. The method generates both lower and upper bounds for the Bermudan option price and hence gives valid confidence intervals for the true value. Lower bounds can be generated using any number of primal algorithms. Upper bounds are generated using a new Monte Carlo algorithm based on the duality representation of the Bermudan value function suggested independently in Haugh and Kogan (2004) and Rogers (2002). Our proposed algorithm can handle virtually any type of process dynamics, factor structure, and payout specification. Computational results for a variety of multifactor equity and interest-rate options demonstrate the simplicity and efficiency of the proposed algorithm. In particular, we use the proposed method to examine and verify the tightness of frequently used exercise rules in Bermudan swaption markets. [ABSTRACT FROM AUTHOR]

In this paper, we consider an integer convex optimization problem where the objective function is the sum of separable convex functions (that is, of the form ∑[sub(i,j)∈Q]F[subij](W[subij])+∑[subi∈P]B[subi](µ[subi])), the constraints are similar to those arising in the dual of a minimum cost flow problem (that is, of the form µ[subi]-µ[subj]≤w[subij],(i,j)∈Q) with lower and upper bounds on variables. Let n =|P| m =|Q|, and U be the largest magnitude in the lower and upper bounds of variables. We call this problem the convex cost integer dual network flow problem. In this paper, we describe several applications of the convex cost integer dual network flow problem arising in a dial-a-ride transit problem, inverse spanning tree problem, project management, and regression analysis. We develop network flow-based algorithms to solve the convex cost integer dual network flow problem. We show that using the Lagrangian relaxation technique, the convex cost integer dual network flow problem can be transformed into a convex cost primal network flow problem where each cost function is a piecewise linear convex function with integer slopes. Its special structure allows the convex cost primal network flow problem to be solved in O(nmlog(n²/m)log (nU) time. This time bound is the same time needed to solve the minimum cost flow problem using the cost-scaling algorithm, and is also is best available time bound to solve the convex cost integer dual network flow problem. [ABSTRACT FROM AUTHOR]

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]

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]

The bond portfolio problem is viewed as a multistage decision problem in which buy, sell, and hold decisions are made at successive (discrete) points in time. Normative models of this decision problem tend to become very large, particularly when its dynamic structure and the uncertainty of future interest rates and cash flows are incorporated in the model. In this paper we present a multiple period bond portfolio model and suggest a new approach for efficiently solving problems which are large enough to make use of as much information as portfolio managers can reasonably provide. The procedure utilizes the decomposition algorithm of mathematical programming and an efficient technique developed for solving subproblems of the overall portfolio model. The key to the procedure is the definition of subproblems which are easily solved via a simple recursive relationship. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for finding the K loopless paths that have the shortest lengths from one node to another node in a network. The significance of the new algorithm is that its computational upper bound increases only linearly with the value of K. Consequently, in general, the new algorithm is extremely efficient as compared with the algorithms proposed by Bock, Kantner, and Haynes [2], Pollack [7], [8], Clarke, Krikorian, and Rausan [3], Sakarovitch [9] and others. This paper first reviews the algorithms presently available for finding the K shortest loopless paths in terms of the computational effort and memory addresses they require. This is followed by the presentation of the new algorithm and its justification. Finally, the efficiency of the new algorithm is examined and compared with that of other algorithms. [ABSTRACT FROM AUTHOR]

The paper presents a new approach to solving a class of combinatorial economic allocation problems. One member of this class is known as the quadratic assignment problem. Besides presenting an algorithm to solve this problem, we will discuss in general terms the techniques for treating combinatorial problems. A novel feature of the paper is the development of the statistical properties of the criterion function. These statistical properties are used in conjunction with a general enumerative procedure to form the main parts of the algorithm. Using the idea of confidence level enumeration, an extension of the algorithm is proposed which should allow for the effective treatment of large scale combinatorial problems. Finally we present some computational results in order to illustrate the effectiveness of the general approach. [ABSTRACT FROM AUTHOR]

In this paper we study a model that minimizes the sum of production, employment smoothing, and inventory costs subject to a schedule of known demand requirements over a finite time horizon. The three instrumental variables are work force producing at regular-time, work force producing on overtime, and the total work force. Overtime is limited to be not more than a fixed multiple of regular time. The idle portion of the work force and the levels of inventory are resultant variables. We postulate the following shape characteristics for the cost functions production costs are convexlike, smoothing costs are V-shaped, and holding costs are increasing, both the production and holding cost functions need not be stationary. In this paper, we provide upper and lower bounds on the cumulative regular-time plus overtime work force for any sequence of demand requirements. We also give the form of an optimal policy when demands are monotone (either increasing or decreasing). Finally, we derive the asymptotic behavior of optimal policies when demands are monotone and the planning horizon becomes arbitrarily long. All of these results, which convey information about the numerical values of optimal policies, given specific demands and an initial level of inventory, depend only on the shape characteristics of the cost functions. Algorithmic techniques are discussed elsewhere. [ABSTRACT FROM AUTHOR]

This paper considers "critical path" networks which are used for the planning and scheduling of projects that consist of well defined sequences of individual activities. When the number of activities is large, it becomes difficult to prepare a network for the project as one unit, and it may also be difficult to store the network in the high speed memory of a digital computer. Also, in the cases where there are two or more independent projects, which are weakly inter-related by common activities, the problem of efficient scheduling of all the projects becomes quite difficult. This paper presents a method to "tear" or "decompose" a project network into several subnetworks, schedule the subnetworks and then to put the subnetworks back together. A computational algorithm is first given for time-only networks; then two computational formulations are given for cost-time network of project subnetworks. The latter essentially generalize the algorithm due to Fulkerson, in order to handle piecewise linear, convex, cost-time curves for some or all of the activities. [ABSTRACT FROM AUTHOR]

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

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

The minimum cost flow problem is to determine a least cost shipment of a commodity through a network G = (N, A) in order to satisfy demands at certain nodes from available supplies at other nodes. In this paper, we study a variant of the minimum cost flow problem where we are given a set R subset or is equal to A of arcs and require that each arc in R must carry the same amount of flow. This problem, which we call the simple equal flow problem, arose while modeling a water resource system management in Sardinia, Italy. We consider the simple equal flow problem in a directed network with n nodes, m arcs, and where all arc capacities and node supplies are integer and bounded by U. We develop several algorithms for the simple equal flow problem--the network simplex algorithm, the parametric simplex algorithm, the combinatorial parametric algorithm, the binary search algorithm, and the capacity scaling algorithm. The binary search algorithm solves the simple equal flow problem in O(log(nU)) applications of any minimum cost flow algorithm. The capacity scaling algorithm solves it in O(m(m + n log n) log (nU)) time, which is almost the same time needed to solve the minimum cost flow problem by the capacity scaling algorithm. These algorithms can be easily modified to obtain an integer solution of the simple equal flow problem. [ABSTRACT FROM AUTHOR]

In this paper we examine computational complexity issues and develop algorithms for a class of"shoreline" single-vehicle routing and scheduling problems with release time constraints. Problems in this class are interesting for both practical and theoretical reasons. From a practical perspective, these problems arise in several transportation environments. For instance, in the routing and scheduling of cargo ships, the routing structure is "easy" because the ports to be visited are usually located along a shoreline. However, because release times of cargoes at ports generally complicate the routing structure, the combined routing and scheduling problem is nontrivial. For the straight-line case (a restriction of the shoreline case), our analysis shows that the problem of minimizing the maximum completion time can be solved exactly in quadratic time by dynamic programming. For the shoreline case we develop and analyze heuristic algorithms. We derive data-dependent worst-case performance ratios for these heuristics that are bounded by constant. We also discuss how these algorithms perform on practical data. [ABSTRACT FROM AUTHOR]

In this paper we study the problem of coordinating the purchase and shipment of I items in a one-warehouse, N-retailer inventory system. The model includes positive echelon holding costs, fixed costs for ordering and shipping each item, and a fixed joint item order cost at each retailer. Demand for each item at each retailer is assumed to occur at a constant and continuous rate. A mathematical model is developed based on these assumptions and the assumption that a stationary nested policy is followed. An efficient algorithm is presented based on the problem's structure that involves only sorting and runs in O(NI log NI) time. The cost of the policy computed is proven to be within 6% of the cost of an optimal nested policy. An example is presented to illustrate the problem structure and the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper surveys models and algorithms dealing with partially observable Markov decision processes. A partially observable Markov decision process (POMDP) is a generalization of a Markov decision process which permits uncertainty regarding the state of a Markov process and allows for state information acquisition. A general framework for finite state and action POMDP's is presented. Next, there is a brief discussion of the development of POMDP's and their relationship with other decision processes. A wide range of models in such areas as quality control, machine maintenance, internal auditing, learning, and optimal stopping are discussed within the POMDP-framework. Lastly, algorithms for computing optimal solutions to POMDP's are presented. [ABSTRACT FROM AUTHOR]

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]

This article describes a modified algorithm for critical path method time-cost tradeoff. The algorithm suggests rules for choosing paths and minimizing the total cost of expediting activities in order to complete projects in the time desired. Several examples of the algorithm's usage are presented. The author observes that the algorithm presented in this paper provides the optimum solution to all the network problems he solved. Comparisons are made of the effectiveness of the critical path method time-cost tradeoff algorithm and other algorithms.

This paper explores the normative theory of simulation within the context of an optimization algorithm for a linear programming model of the experimental setting. The simulation is viewed as a random generalized mathematical function which provides an uncertain evaluation of any policy within a specified constraint set. A sequential experimental design aimed at identifying the feasible levels of the policy variables which provide the optimal level of expected response is presented and analyzed. The results of numerical tests of the proposed procedure are discussed. [ABSTRACT FROM AUTHOR]

This paper presents a new approach to determining the optimal facility locations for uncapacitated location problems in two stages. First, it is shown that a subset of all solutions to the uncapacitated public facility location problem can be obtained by considering a closely related private location problem. The exact nature of the problem is established using the Generalised Lagrange Multiplier results given by Everett. In the second section of the paper a particularly efficient parametric decomposition algorithm, which is based on the results of the first section, is presented. Computational results are given which summarize the current level of experience with the algorithm. [ABSTRACT FROM AUTHOR]

This part of the paper introduces some possible implementations of Self-Scaling Variable Metric algorithms based on the theory presented in Part I. These implementations are analyzed theoretically and discussed qualitatively. A special class of SSVM algorithms is introduced, which has the additional property of being invariant under scaling of the objective function or of the variables. Experimental results are provided for a particular case of this class. This case has been tested in comparison to the DFP algorithm on a variety of functions with up to 50 variables. The results indicate that the new method has substantial advantage for functions with a large number of variables. [ABSTRACT FROM AUTHOR]

This paper is concerned with the following problem in network synthesis. Suppose that we are given a network with real-valued capacities on each arc. There is a cost associated with each arc which is proportional to the magnitude of the arc capacity. We wish to determine new arc capacities such that the capacity of each cut in the new network differs from the capacity of the corresponding cut in the original network by a specified constant and such that the total cost is minimized. This problem is shown to be equivalent to solving a minimum cost flow problem on a related network. [ABSTRACT FROM AUTHOR]

The author responds to the paper "The Loading Problem," by Eilon and Christofides. He focuses on suggesting a solution to the problem. The recommended solution involves a heuristic algorithm that allegedly requires fewer computations than the one proposed by Eilon and Christofides. It is suggested that the simpler algorithm offered by the author reaches mathematical optimization as often as the aforementioned algorithm. It is further proposed that the algorithm presented by Eilon and Christofides cannot be used to solve multi-dimensional programming problems. The author goes on to discuss a numerical analysis that can be used for the allocation of industrial resources. Related mathematical models are discussed in detail. A table comparing the results of the two algorithms is also presented.

This paper presents a model for determining how a central government can most efficiently allocate resources among other levels of government. The model explicitly includes the fact that lower levels of government can make independent decisions once they have been given resources by the central government. A key feature of the model is the mathematical formulation of the central government's objective of distributing resources efficiently, while at the same time being as fair as possible to all those receiving allocations. An algorithm for solving the model is presented along with a numerical example. [ABSTRACT FROM AUTHOR]

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

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]

This paper presents a grouping procedure which yields improved solutions to Bomberger's Lot Size Scheduling Problem [1]. The group definition is a generalization of the group definition proposed by Stankard and Gupta [3]. Moreover, the generalization leads to a pseudo dynamic programming procedure which is readily programmable. Computational experience has shown the procedure to be extremely efficient. [ABSTRACT FROM AUTHOR]

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]

Two dynamic economic lot size production systems are analyzed in this paper, the first being a single product model with backlogging and the second a multi-echelon model. In each model the objective is to find a production schedule that minimizes the total production and inventory costs. A key conceptual difficulty is that the mathematically perplexing problem of minimizing a concave function is being considered, it is shown that both models are naturally represented via single source networks. The network formulations reveal the underlying structure of the models, and facilitate development of efficient dynamic programming algorithms for calculating the optimal production schedules. [ABSTRACT FROM AUTHOR]

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

The topology of the Generalized Transportation Problem, at the end of each iteration of the stepping-stone method, is characterized by a variable number of loops to which are attached multiple branched side chains or trees. An efficient computer representation of this structure and methods for updating it are described in this paper. [ABSTRACT FROM AUTHOR]

This paper describes an algorithm for the solution of mathematical programming problems having a linear objective function and non-linear constraints. The algorithm is basically an adaptation of the simplex method to the case of non-linear constraints. Certain complications are, however, introduced through non-linearity in the constraints, and it is shown how these can be overcome. [ABSTRACT FROM AUTHOR]

We consider the resource-constrained project scheduling problem. The purpose of this paper is to direct the focus to a branch-and-bound concept that can, by simple adaptations, operate on a wide range of problem settings. The general approach can, e.g., deal with multimode problems, resource availability varying with time, and a wide range of objectives. Even the simple assembly line balancing problem of type-1 can be competitively approached with some modifications. Although the algorithm is the most general and simple one currently available for resource-constrained project scheduling, the computational performance can compete with the best approaches available for the single-mode problem. The algorithm uses far less memory than the state-of-the-art procedure, i.e., 256 KB versus 24 MB, for solving the standard benchmark set with projects consisting of 32 activities within comparable time. If both approaches are allowed to make limited use of memory, i.e., 256 KB, then more than 97% of the benchmark instances can be solved within fractions of the time required by the current state-of-the-art procedure. The truncated version of our algorithm achieves at 256 KB approximately the results of the truncated version of the state-of-the-art approach at 24 MB. Since in general the memory requirements exponentially grow with the number of activities the project consists of, memory will become a critical resource, and the strategy to access previously stored information will gain fundamental importance when solving larger projects. [ABSTRACT FROM AUTHOR]

This paper presents the results of an empirical study of the effects of coefficient correlation structure and constraint slackness settings on the performance of solution procedures on synthetic two-dimensional knapsack problems (2KP). The population correlation structure among 2KP coefficients, the level of constraint slackness, and the type of correlation (product moment or rank) are varied in this study. Representative branch-and-bound and heuristic solution procedures are used to investigate the influence of these problem parameters on solution procedure performance. Population correlation structure, and in particular the interconstraint component of the correlation structure, is found to be a significant factor influencing the performance of both the algorithm and the heuristic. In addition, the interaction between constraint slackness and population correlation structure is found to influence solution procedure performance. [ABSTRACT FROM AUTHOR]

This paper describes three approaches to assigning tasks to earth observing satellites (EOS). A fast and simple priority dispatch method is described and shown to produce acceptable schedules most of the time. A look ahead algorithm is then introduced that outperforms the dispatcher by about 12% with only a small increase in run time. These algorithms set the stage for the introduction of a genetic algorithm that uses job permutations as the population. The genetic approach presented here is novel in that it uses two additional binary variables, one to allow the dispatcher to occasionally skip a job in the queue and another to allow the dispatcher to occasionally allocate the worst position to the job. These variables are included in the recombination step in a natural way. The resulting schedules improve on the look ahead by as much as 15% at times and 3% on average. We define and use the "window-constrained packing" problem to model the bare bones of the EOS scheduling problem. [ABSTRACT FROM AUTHOR]

Routing problems appear frequently when dealing with the operation of communication or transportation networks. Among them, the message routing problem plays a determinant role in the optimization of network performance. Much of the motivation for this work comes from this problem which is shown to belong to the class of nonlinear convex multicommodity flow problems. This paper emphasizes the message routing problem in data networks, but it includes a broader literature overview of convex multicommodity flow problems. We present and discuss the main solution techniques proposed for solving this class of large-scale convex optimization problems. We conduct some numerical experiments on the message routing problem with four different techniques. [ABSTRACT FROM AUTHOR]

In a discrete-event simulation, the information related to the events scheduled to occur in the future is kept in a data structure called the future event set (FES). In this paper, we study the interaction hold model a popular stochastic model for FES performance analysis, corresponding to the superposition of a (fixed) number of renewal processes. The general state-space Markov chain formed by the discrete-time process that keeps track, at event times, of the residual lifetimes is shown here to be recurrent in the sense of Harris, and its stationary distribution is obtained. Linked lists and indexed lists, two popular FESs, are investigated using this model. For the interaction hold model, we make rigorous certain published results as well as introduce new ones. For example, we derive the distribution of the relative position of the event to be inserted in the data structure. In the exponential case, our analytic and empirical results confirm that when events with relatively short lifetimes often get regenerated upon their occurrence, it is better to scan a list (or sublist) from its head rather than tail. In the same context and for indexed lists with sublists with constant sizes, our results suggest that subsequent sublists should be of larger sizes, i.e., the first sublist should contain the smallest number of records, the second sublist the second smallest number of records, etc. [ABSTRACT FROM AUTHOR]

Approaches like finite differences with common random numbers, infinitesimal perturbation analysis, and the likelihood ratio method have drawn a great deal of attention recently as ways of estimating the gradient of a performance measure with respect to continuous parameters in a dynamic stochastic system. In this paper, we study the use of such estimators in stochastic approximation algorithms, to perform so-called "single-run optimizations" of steady-state systems. Under mild conditions, for an objective function that involves the mean system time in a G//G/1 queue, we prove that many variants of these algorithms converge to the minimizer. In most cases, however, the simulation length must be increased from iteration to iteration; otherwise the algorithm may converge to the wrong value. One exception is a particular implementation of infinitesimal perturbation analysis, for which the single-run optimization converges to the optimum even with a fixed (and small) number of ends of service per iteration. As a by-product of our convergence proofs, we obtain some properties of the derivative estimators that could be of independent interest. Our analysis exploits the regenerative structure of the system, but our derivative estimation and optimization algorithms do not always take advantage of that regenerative structure. In a companion paper, we report numerical experiments with an M/M/1 queue, which illustrate the basic convergence properties and possible pitfalls of the various techniques. [ABSTRACT FROM AUTHOR]

This paper concerns lot-sizing in a multistage and multifacility pure distribution network. A facility at the end of the distribution network experiences a deterministic and continuous demand. Each facility has an echelon holding cost rate for each item it distributes, and a facility-dependent set up cost. In this paper an algorithm is presented of complexity 0(rd log r) where r is the number of end facilities and d is the maximum depth of the distribution system. The algorithm exploits a lower bound obtained by decomposing the distribution network into facilities-in-series problems. Using a set up cost allocation procedure, the maximum of the continuous solution of the decomposed problem is obtained. This maximizing solution provides the lower bound which is used for solving the distribution problem. This gives a power-of-two heuristic with a worst case performance no more than 2% above optimal. [ABSTRACT FROM AUTHOR]

The paper presents a heuristic for determining the path that maximizes the expected utility of a stochastic acyclic network. The focus is on shortest route problems where a general, nonlinear utility function is used to measure outcomes. For such problems, enumerating all feasible paths is the only way to guarantee that the global optimum has been found. Alternatively, we develop a reduction algorithm based on stochastic dominance to speed up the computations. Monte Carlo simulation is used to evaluate the approach. In all, 70 test problems comprising 20 to 60 nodes are randomly generated and analyzed. The results indicate that the heuristic produces significant computational saving as the size of the network grows, and that the quality of the reduced network solutions are better than those obtained from the original formulation. [ABSTRACT FROM AUTHOR]

This paper presents a new approach to modeling, analyzing, and solving a class of environmental control problems dealing with sediment deposition. An efficient dynamic programming algorithm is designed to handle the spatial characteristics of soil movement through a watershed, and its ultimate impact on water channels and/or reservoirs. The model generates "sediment abatement cost frontiers" which summarize the trade-off information needed for watershed planning and management. This information can also be used to identify and target special-problem areas. The paper presents both results on the efficiency of the DP algorithm compared to other methods, and results on the application of the model to real world cases. [ABSTRACT FROM AUTHOR]

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]