HTML Archive

INFORMS Research Paper Archive - Browsable Listing

Papers are stored at author sites. Hence, when down-loaded, they will be retrieved directly from those sites.
Click here to go to the INFORMS Research Paper Archive Home Page.

A Capacitated Production-Inventory Model with Periodic Demand
     Keywords:  Capacitated Production-Inventory Model, Stochastic Models, Optimal Policy, Simulation based Optimization
     Author:        Kapuscinski, Roman, Sridhar,Tayur
     Download:   Postscript  (01-01-1996)
     Abstract:

For a single product, single-stage capacitated production-inventory model with stochas- tic, periodic (cyclic) demand, we find the optimal policy and characterize some of its properties. We study the finite-horizon, the discounted infinite-horizon and the infinite- horizon average cases. A simulation based optimization method is provided to compute the optimal parameters. Based on a numerical study, several insights into the model are also provided.

A Class of Shot Noise Models for Financial Applications
     Author:        Samorodnitsky, G.
     Download:   Postscript  (01-01-1996)
     Abstract:

We describe a class of non-Markov shot noise processes that can be used as models for rates of return on securities, exchange rate processes and other processes in finance. These are continuous time processes that can exhibit heavy tails that become lighter when sampling interval increases, clustering and long memory.

A Column-Generation Based Decomposition Algorithm for a Parallel Machine Just-In-Time Scheduling Problem
     Keywords:  Parallel machine scheduling; Just-in-time; Set partitioning; Dantzig-Wolfe decomposition; Column generation; Branch and bound
     Author:        Chen, Z.-L., Powell, W.B.
     Download:   PDF  (10-01-1997)
     Abstract:

We propose a column generation based exact decomposition algorithm for the problem of scheduling n jobs with an unrestrictively large common due date on m identical par- allel machines to minimize total weighted earliness and tardiness. We rst formulate the problem as an integer program, then reformulate it, using Dantzig-Wolfe decomposition, as a set partitioning problem with side constraints. Based on this set partitioning for- mulation, a branch and bound exact solution algorithm is developed for the problem. In the branch and bound tree, each node is the linear relaxation problem of a set partition- ing problem with side constraints. This linear relaxation problem is solved by column generation approach where columns represent partial schedules on single machines and are generated by solving two single machine subproblems. Our computational results show that this decomposition algorithm is capable of solving problems with up to 60 jobs in reasonable cpu time.

A Comparison of Formulations for the Single-Airport Ground Holding Problem with Banking Constraints
     Keywords:  optimization, integer programming, transportation problem, ground delay program, air traffic flow management, stochastic programming, collaborative d
     Author:        Hoffman, R., Ball, M.
     Download:   PDF  (07-01-1998)
     Abstract:

Both the single-airport ground-holding problem (GH) and the multi-airport ground-holding problem can be extended by the addition of banking constraints to accommodate the hubbing operations of major airlines. These constraints enforce the desire of airlines to land certain groups of flights, called banks, within fixed time windows, thus preventing the propagation of delays throughout their entire operation. GH can be formulated as a transportation problem and readily solved. But in the presence of banking constraints, GH becomes a difficult integer programming problem. In this paper, we construct five different models of the single-airport ground holding problem with banking constraints (GHB). The models are evaluated both computationally and analytically. For two of the models, we show that the banking constraints induce facets of the convex hull of the set of integer solutions. In addition, we explore a linear transformation of variables and a branching technique.

A Computationally Efficient Feasible Sequential Quadratic Programming Algorithm
     Keywords:  optimization, algorithms, optimization, numerical optimization, feasible iterates, sequential quadratic programming
     Author:        Lawrence, C., Tits, A.
     Download:   PDF  (07-01-1998)
     Abstract:

A Sequential Quadratic Programming (SQP) algorithm generating feasible iterates is described and analyzed. What distinguishes this algorithm from previous feasible SQP algorithms proposed by various authors is a drastic reduction in the amount of computation required to generate a new iterate while the proposed scheme still enjoys the same global and fast local convergence properties. A preliminary implementation has been tested and some promising numerical results are reported.

A Computer Program for Sample Size and Power Calculations in the Design of Multi-arm and Factorial Clinical Trials with Survival Time Endpoints
     Author:        Natarajan, R., Turnbull, B.W. , Slate, E.H. and Clark,L.C.
     Download:   Postscript  (07-01-1995)
     Abstract:

This paper presents a computer program for use in the design of long-term clinical trials with multiple treatment arms in which the primary outcome variables are censored survival times. The treatment arms may be structured as a one-way or multi-way factorial design. It is assumed that patients are entered and randomized to a treatment arm during an accrual period. The patients are then followed for a fixed period during which there may be dropouts. Various distributional assumptions can be used to model the survival times. These include an option in which there is an effect of treatment only after a lag or delay time. The program then computes the power of various statistical tests of hypotheses concerning treatment differences, interactions and trends. The power computations are ``exact`` in that they use the Monte Carlo method to obtain Type I and II error probabilities. However the program also outputs the normal approximations for comparison, although they are typically not accurate in these situations. Fisher`s LSD method is used to adjust for the multiple comparisons. By comparing the power for various sets of design parameters, such as sample size, numbers of factor levels, patient accrual rate, and length of followup, an appropriate design can be constructed. Two examples are provided. The first is a simple one-way layout with multiple treatment arms; the second a two-way factorial design for a proposed large scale cancer chemoprevention trial.

A Convergent Cutting Plane and Partial Sampling Algorithm for Multistage Linear Programs
     Keywords:  Multistage stochastic programming; Cutting plane; Sampling; Convergence
     Author:        Chen, Z. L., Powell, W. B.
     Download:   PDF  (08-01-1999)
     Abstract:

We propose an algorithm for multistage stochastic linear programs with recourse where ran- dom quantities in dierent stages are independent. The algorithm successively approximates expected recourse functions by building up valid cutting planes to support these functions from below. In each iteration, for the expected recourse function in each stage, one cutting-plane is generated using the dual extreme points of the next-stage problem that have been found so far. We prove that the algorithm is convergent with probability one.

A Faster Algorithm for the Quickest Transshipment Problem
     Author:        Fleischer, L.
     Download:   Postscript  (03-15-1997)
     Abstract:

A transshipment problem with demands that exceed network capacity can be solved by sending flow in several waves. How can this be done using the minimum number of iterations? This is the question tackled in the quickest transshipment problem. Hoppe and Tardos describe the only known polynomial time algorithm that finds an integral solution to this problem. Their algorithm repeatedly minimizes submodular functions using the ellipsoid method, and is therefore not at all practical. I present an algorithm that finds a fully integral quickest transshipment with a polynomial number of maximum flow computations. When there is only one sink, the quickest transshipment problem is significantly easier. For this case, I show how the algorithm can be sped up to return an integral solution using O(k) maximum flow computations, where k is the number of sources. Hajek and Ogier describe an algorithm that finds a fractional solution to the single-sink quickest transshipment problem on a network with n nodes using O(n) maximum flow computations. They actually solve the universally quickest transshipment--a dynamic flow that minimizes the amount of supply left in the network at every moment of time. In this paper, I show how to solve this problem in the same asymptotic time as one maximum flow computation.

A Framework for Routing and Congestion Control for Multicast Information Flows
     Keywords:  queueing networks, Multicast
     Author:        Sarkar, S., Tassiulas, L.
     Download:   PDF  (07-22-1998)
     Abstract:

We propose a new multipurpose multicast routing and scheduling algorithm (MMRS). The routing policy load balances amongst various possible routes between the source and the destinations, relying its decisions on the message queue lengths at the source node. The scheduling amongst various sessions sharing links is devised such that the flow of a session depends on the congestion of the next hop links. MMRS is throughput optimal and computationally simple. The algorithm can be implemented in a distributed, asynchronous manner. It has several parameters which can be suitably modified to control the end-to-end delay, packet loss in a topology specific manner. These parameters can be adjusted to offer limited priorities to some desired sessions. MMRS is expected to play a significant role in end-to-end congestion control in the multicast scenario.

A fully Automated Bandwidth Selection Method for Fitting Additive Models
     Author:        Opsomer, J., Ruppert, D.
     Download:   Postscript  (02-01-1996)
     Abstract:

This article describes a fully automated bandwidth selection method for additive models that is applicable to the widely used backfitting algorithm of Buja, Hastie and Tibshirani (1989) and does not rely on cross-validation. The proposed plug-in estimator is an extension of the local linear regression estimator of Ruppert, Sheather and Wand (1996) and is shown to achieve the same Op(n-2/7) relative convergence rate for bivariate additive models. If more than two covariates are present, theoretical justification of the method requires independence of the covariates, but simulation experiments show that in practice the method is very robust to violations of this assumption. The behavior of the method is demonstrated on a real dataset.

A Genetic Algorithm for a Minimax Network Design Problem
     Keywords:  algorithms, manufacturing, genetic algorithms, network design, robust discrete optimization
     Author:        Herrmann, J.
     Download:   PDF  (07-01-1999)
     Abstract:

This paper considers the problem of designing a network to transport material from sources of supply to sites where demand occurs. However, the demand at each site is uncertain. We formulate the problem as a robust discrete optimization problem. The minimax objective is to find a robust solution that has the best worst-case performance over a set of possible scenarios. However, this is a difficult optimization problem. This paper describes a two-space genetic algorithm that is a general technique to solve such minimax optimization problems. This algorithm maintains two populations. The first population represents solutions. The second population represents scenarios. An individual in one population is evaluated with respect to the individuals in the other population. The populations evolve simultaneously, and they converge to a robust solution and a worst-case scenario. Experimental results show that the two-space genetic algorithm can find robust solutions to the minimax network design problem. Since robust discrete optimization problems occur in many areas, the algorithm will have a wide variety of applications.

A Genetic Algorithm for Minimax Optimization
     Keywords:  algorithms, optimization, plant layout, robust design
     Author:        Herrmann, J.
     Download:   PDF  (02-22-1997)
     Abstract:

This paper describes a two-space genetic algorithm that finds solutions to minimax optimization problems. The genetic algorithm maintains two populations and searches both simultaneously. Each individual is evaluated with respect to the individuals in the other population. Preliminary experimental results confirm that the algorithm can find good solutions to minimax optimization problems.

A Heavy Traffic Limit Theorem for Workload Processes with Heavy Tailed Service Requirements
     Author:        Resnick, S., Samorodnitsky, G.
     Download:   Postscript  (10-09-1998)
     Abstract:

A system with heavy tailed service requirements under heavy load having a single server, has an equilibrium waiting time distribution which is approximated by the Mittag-Leffler distribution. This fact is understood by a direct analysis of the weak convergence of a sequence of negative drift random walks with heavy right tail and the associated all time maxima of these random walks. This approach complements the recent transform view of Boxma and Cohen (1997).

A Hybrid Genetic/Optimization Algorithm for a Task Allocation Problem
     Keywords:  genetic algorithms,scheduling
     Author:        Hadj-Alouane, Atidel, Bean, James C. and Murty, K.G.
     Download:   PDF  (01-01-1990)
     Abstract:

We consider the problem of designing a distributed computing system for handling a set of repetitive tasks on a periodic basis. Tasks assigned to different processors need communication link capacity, tasks executing on the same proces- sor do not. The aim is to develop a design of minimum total cost that can handle all the tasks. We compare the performances of a genetic algorithm, a commercial 0-1 integer programming software and a hybrid approach from the literature, in solving real instances of the problem.

A Markovian Dual-Source Production-Inventory Model with Order Bands
     Author:        Scheller-Wolf, Alan, Sridhar,Tayur
     Download:   Postscript  (02-01-1998)
     Abstract:

We present a Markovian model of a single firm engaging in a periodic review inventory policy to procure goods from two alternate suppliers. Each supplier quotes a state-dependent minimum order quantity, maximum order quantity, and unit price

A Markovian Storage Model
     Author:        Pacheco, A., Prabhu, N.U.
     Download:   Postscript  (11-01-1993)
     Abstract:

We investigate a storage model where the input and demand are additive functionals on a Markov chain . The storage policy is to meet the largest possible portion of the demand. We first derive results for the net input process embedded at the epochs of transitions of , which is a Markov random walk. Our analysis is based on a Wiener-Hopf factorization for this random walk; this also gives results for the busy period of the storage process. The properties of the storage level and the unsatisfied demand are then derived.

A Multi-Objective Integer Programming Framework For Product Design
     Author:        Trichur, V., Ball, M.
     Download:   PDF  (07-22-1998)
     Abstract:

This paper describes a modeling framework for product design that facilitates the incorporation of both engineering and strategic considerations at the design stage. We first develop an abstract representation of a generic product, an AND/OR tree, that is context-independent and can be used to model a wide variety of products in different application settings. We show how this representation leads naturally to a mathematical model and discuss some of the properties of this model. Next, we show how the AND/OR tree can be employed in different settings; specifically, we describe applications to printed circuit assembly and microwave module industries. These applications result in multiobjective integer programming formulations. We discuss the properties of these formulations, develop appropriate solution procedures, and report our computational experience. One of the advantages of the framework that we describe is the ease with which it can be extended to incorporate additional considerations. We indicate some some possible extensions that might find ready applicability in industry.

A Multiplier Adjustment Method for Dynamic Resource Allocation Problems
     Author:        Carvalho, T., Powell, W.B.
     Download:   PDF  (12-23-1998)
     Abstract:

Dynamic fleet management problems (with a homogeneous eet) are classically formulated as dy- namic networks, or linear programs with side constraints. Recently, a new dynamic control approach was introduced called a logistics queueing network. Instead of a large linear program, the problem is decomposed into small subproblems, that are guided by two control variables that push these local problems to produce a solution that is close to a global optimum. In prior work, these control variables were updated using a subgradient approximation. In this paper, we propose a multiplier adjustment method for solving the same problem. Numerical experiments show that this method produces better solutions with greater stability. The new method is somewhat slower, and is more dicult to implement. We believe that both methods will represent reasonable choices for solving the problem.

A New Direction in Group Support System Theory: An Evolutionary Approach to Group Decision-Making
     Keywords:  Group Decision Support Systems (GDSS), Genetic Algorithms, Computational Modeling and Markov Models.
     Author:        Rees, J., Koehler, G. J.
     Download:   PDF  (07-29-1999)
     Abstract:

We propose modeling Group Support System (GSS) search tasks with Genetic Algorithms. Using explicit mathematical models for Genetic Algorithms, (GAs), we how how to estimate the underlying GA parameters from an observed GSS solution path. Once these parameters are estimated, they may be related to GSS variables such as group composition and membership, leadership presence, the specific GSS tools available, incentive structure, and organizational culture. The estimated Genetic Algorithm parameters can be used with the mathematical models for GAs to compute or simulate expected GSS process outcomes.

A New Stopping Criterion for Genetic Algorithms
     Keywords:  Genetic Algorithms, Stopping Condition, First Passage Times, Markov Chains
     Author:        Aytug, H., Koehler, G. J.
     Download:   Postscript  (01-01-1996)
     Abstract:

Genetic Algorithms have been successfully applied in a wide variety of problems. Although widely used, there are few theoretical guidelines for determining when to terminate the search. One result by Aytug and Koehler provides a loose bound on the number of GA generations needed to see all populations (and hence, an optimal solution) with a specified probability. In this paper we derive a tighter bound. This new bound is on the number of iterations required to achieve a level of confidence to guarantee that a Genetic Algorithm has seen all strings (and, hence, an optimal solution.)

A Performance Evaluation of Online Warehouse Update Algorithms
     Keywords:  data warehouses, update algorithms, online
     Author:        Labrinidis, A., Roussopoulos, N.
     Download:   PDF  (07-22-1998)
     Abstract:

Data warehouse maintenance algorithms usually work off-line, making the warehouse unavailable to users. However, since most organizations require continuous operation, we need to be able to perform the updates online, concurrently with user queries. To guarantee that user queries access a consistent view of the warehouse, online update algorithms introduce redundancy in order to store multiple versions of the data objects that are being changed. In this paper, we present an online warehouse update algorithm that stores multiple versions of data as separate rows (vertical redundancy). We compare our algorithm to another online algorithm that stores multiple versions within each tuple by extending the table schema (horizontal redundancy). We have implemented both algorithms on top of an Informix Dynamic Server and measured their performance under varying workloads, focusing on their impact on query response times. Our experiments show that, except for a limited number of cases, vertical redundancy is a better choice, with respect to storage, implementation overhead, and query performance.

A Population-Based Search from Genetic Algorithms through Thermodynamic Operation
     Keywords:  artificial intelligence, chemical process control, mathematical modeling, neural networks, optimization, algorithms, optimization
     Author:        Sun, R., Dayhoff, J. and Weigand, W.
     Download:   PDF  (01-23-1994)
     Abstract:

The guided random search techniques, genetic algorithms and simulated annealing, are very promising strategies, and both techniques are analogs from physical and biological systems. Through genetic algorithms, the simulation of evolution for the purposes of parameter optimization has generally demonstrated itself to be a robust and rapid optimization technique. The simulated annealing algorithm often finds high quality candidate solutions. Limitations, however, occur in performance because optimization may take large numbers of iterations or final parameter values may be found that there are not at global minimum (or maximum) points. In this paper we propose a population-based search algorithm that combines the approaches from genetic algorithms and simulated annealing. The combined approach, called GASA, maintains a population of individuals over a period of generations. In the GASA technique, simulated annealing is used in choices regarding a subset of individuals to undergo crossover and mutation. We show that the GASA technique performs superior to a genetic algorithm on the Bohachevsky function, an objective function with m any local minima. The methodology and the test results on function optimization are given and compared with classical genetic algorithms.

A Primal-Dual Interior-Point Method for Nonconvex Optimization with Multiple Logarithmic Barrier Parameters and with Strong Convergence Properties
     Keywords:  optimization, algorithms, optimization
     Author:        Urban, T., Tits, A. and Lawrence, C.
     Download:   PDF  (07-01-1998)
     Abstract:

It is observed that an algorithm proposed in the 1980s for the solution of nonconvex constrained optimization problems is in fact a primal-dual logarithmic barrier interior-point method closely related to methods under current investigation in the research community. Its main distinguishing features are judicious selection and update of the multiple barrier parameters (one per constraint), use of the objective function as merit function, and careful bending of the search direction. As a payoff, global convergence and fast local convergence ensue. The purpose of this short note is to describe the algorithm in the interior-point framework and language and to provide a preliminary numerical evaluation. The latter shows that the method compares well with algorithms recently proposed by other research groups.

A Simple quadratically convergent Interior Point Algorithm for Linear Programming and Convex quadratic Programming
     Keywords:  linear programming, quadratic programming, global convergence, quadratic convergence
     Author:        Tits, A., Zhou, J.
     Download:   PDF  (01-23-1993)
     Abstract:

An algorithm for linear programming (LP) and convex quadratic programming (CQP) is proposed, based on an interior point iteration introduced more than ten years ago by J. Herskovits for the solution of nonlinear programming problems. Herskovits` iteration can be simplified significantly in the LP/CQP case, and quadratic convergence from any initial point can be achieved. Interestingly the resulting algorithm is closely related to a popular scheme, proposed in 1989 by Kojima et al. independently of Herskovits` work.

A Simple Roughness Penalty Approach to Regression Spline Estimation
     Author:        Ruppert, D., Carroll, R.J.
     Download:   Postscript  (08-01-1996)
     Abstract:

A regression spline is a piecewise polynomial function whose highest order nonzero derivative takes jumps at fixed ``knots.`` Usually regression splines are smoothed by deleting nonessential knots, or equivalently setting the jumps at those knots to zero. A method that is simpler to implement and has lower computational cost is to shrink the jumps at all knots towards zero by using a penalty function. The method is widely applicable, e.g., to multivariate regression, interaction models, and semiparametric estimators. We also consider a Bayesian approach with a new type of nonparametric prior.

A Stochastic Formulation of the Dynamic Assignment Problem, with an Application to Truckload Motor Carriers
     Author:        Powell, W. B.
     Download:   PDF  (05-01-1995)
     Abstract:

The dynamic assignment problem arises in a number of application areas in transporta- tion and logistics. Taxi drivers have to be assigned to pick up passengers, police have to be assigned to emergencies, and truck drivers have to pick up and carry loads of freight. All of these problems are characterized by demands that arrive continuously and randomly throughout the day, and require a dispatcher to assign a driver to handle a specic demand. We use as our motivating application the load matching problem that arises in long-haul truckload trucking, where we have to assign drivers to loads on a real-time basis. A hybrid model is presented that handles the detailed assignment of drivers to loads, as well as handling forecasts of future loads. Numerical experiments demonstrate that our stochastic, dynamic model outperforms standard myopic models that are widely used in practice.

A Storage Equation on Continuous Time
     Author:        Pacheco, A.
     Download:   Postscript  (04-01-1994)
     Abstract:

We solve the continuous time storage equation for storage models with cadlag net input whose policy is to meet the largest possible portion of the demand. This is an important equation which has been considered in the literature for several particular cases, including the workload process in a M/G/1 system with infinite capacity. In some instances the equation has been defined on a recursive way using Lindley-type equations, such as by Gani and Pyke [1960]. We give conditions under which these recursive definitions coincide with ours. Using order relations, we study the effect that changing the net input has on the storage level and the unsatisfied demand. Finally we give some examples of applications of our results, including priority systems and networks with storage nodes with incoming flow from other nodes or from the exterior.

A study of search directions in primal-dual interior-point methods for semidefinite programming
     Author:        Todd, M. J.
     Download:   Postscript  (10-16-1997)
     Abstract:

We discuss several different search directions which can be used in primal-dual interior-point methods for semidefinite programming problems and investigate their theoretical properties, including scale invariance, primal-dual symmetry, and whether they always generate well-defined directions. Among the directions satisfying all but at most two of these desirable properties are the Alizadeh-Haeberly-Overton, Helmberg-Rendl-Vanderbei-Wolkowicz/Kojima-Shindoh-Hara/Monteiro, Nesterov-Todd, Gu, and Toh directions, as well as directions we will call the MTW and Half directions. The first five of these appear to be the best in our limited computational testing also

A Study of Sequencing Heuristics for Periodic Production Environments
     Author:        Rao, U. S.
     Download:   Postscript  (11-01-1993)
     Abstract:

This paper considers the identical jobs, single end-item cyclic scheduling problem (CSP) of determining good schedules for repetitive production systems with a flexible manufacturing capability. The goal is to optimize system throughput and work in process inventory by determining the efficient trade-off frontier between cycle length and flow times. We present a new, tighter integer programming formulation of CSP corresponding to a network flow problem with some non-network capacity constraints. Since CSP is computationally intractable, we consider several heuristic approaches some of which use subproblems which we have considered in previous research. The five heuristics we examine fall into two generic categories: Myopic methods for schedule generation/improvement (the Graves et al method and a new push/pull heuristic) and truncated exponential search strategies (beam search/truncated branch and bound, simulation annealing algorithms and a new gambling procedure). Our computational tests comparing the heuristics indicate that the quick, myopic push/pull approach and the relatively slow, enumerative beam search generate reasonably good (near optimal) solutions which dominate the other methods.

A test for nonlinearity of time series with infinite variance
     Author:        Resnick, S., Berg, E.
     Download:   Postscript  (10-09-1998)
     Abstract:

A heavy tailed time series that can be represented as an infinite moving average has the property that the sample autocorrelation function (ACF) at lag h converges in probability to a constant , although the mathematical correlation typically does not exist. For many nonlinear heavy tailed models, however, the sample ACF at lag h converges in distribution to a nondegenerate random variable. In this paper, a test for (non)linearity of a given infinite variance time series is constructed, based on subsample stability of the sample ACF. The test is applied to several real and simulated datasets.

Activity periods of an infinite server queue and performance of certain heavy tailed fluid queues
     Author:        Resnick, S., Samorodnitsky, G.
     Download:   Postscript  (09-15-1997)
     Abstract:

A fluid queue with ON periods arriving according to a Poisson process and having a long-tailed distribution has long range dependence. As a result, its performance deteriorates. The extent of this performance deterioration depends on a quantity determined by the average values of the system parameters. In the case when the the performance deterioration is the most extreme, we quantify it by studying the time until the amount of work in the system causes an overflow of a large buffer. This turns out to be strongly related to the tail behavior of the increase in the buffer content during a busy period of the queue feeding the buffer. A large deviation approach provides a powerful method of studying such tail behavior.

Adaptive Labeling Algorithms for the Dynamic Assignment Problem
     Author:        Powell, W. B., Snow, W. and Cheung, R. K.-M.
     Download:   PDF  (08-24-1997)
     Abstract:

We consider the problem of dynamically routing a driver to cover a sequence of tasks (with no consolidation), using a complex set of driver attributes and operational rules. Our motivating application is dynamic routing and scheduling problems, which require fast response times, the ability to handle a wide range of operational concerns, and the ability to output multiple recommendations for a particular driver. A mathematical formulation is introduced that easily handles real{world operational complexities. Two new algorithms are described, one giving faster performance and the second providing somewhat higher solution quality. Comparisons to optimal solutions are provided, which measures the quality of the solutions that our algorithms provide. Experimental tests show that our algorithms provide high quality solutions, and are fast enough to be run in real{time applications.

Adaptive Labeling Algorithms for the Dynamic Assignment Problem
     Author:        Powell, W. B., Snow W. and Cheung R.K.-M.
     Download:   PDF  (08-24-1997)
     Abstract:

Adaptive Nonlinear Approximation Algorithms for Multiattribute Resource Scheduling Problems
     Author:        Powell, W. B., Sarma, S.
     Download:   PDF  (05-30-1998)
     Abstract:

In this paper we develop a new method for solving Dynamic Resource Allocation Problems (DRAP) that occur in the operation of freight transportation systems. Such problems involve the allocation of resources to perform tasks over a discrete-time, dynamic network. Our particular interest is in ultra-large scale problems, that involve managing thousands of resources (such as drivers or vehicles). We focus on problems with dynamic attributes, where the characteristics of the resource may change as it handles each task. We provide a general and very exible formulation, and provide a solution based on the principle of dynamic programming. A newly proposed linearization approximation is shown to provide high quality solutions with reasonable execution times. The technique is illustrated in the context of the driver management problem for a large motor carrier.

All 0-1 Polytopes are Traveling Salesman Polytopes
     Author:        Billera, L.J., Sarangarajan, A.
     Download:   Postscript  (06-01-1994)
     Abstract:

We study the facial structure of two important permutation polytopes in Rn2, the Birkhoff or assignment polytope Bn, defined as the convex hull of all permutation matrices, and the asymmetric traveling salesman polytope Tn, defined as the convex hull of those permutation matrices corresponding to n-cycles. using an isomorphism between the face lattice of Bn and the lattice of elementary bipartite graphs, we show, for example, that every pair of vertices of Bn is contained in a cubical face, showing faces of Bn to be fairly special 0-1 polytopes. On the other hand, we show that Tn has every 0-1 d-polytope as a face, for D = log n, by showing that every 0-1 d-polytope is the asymmetric traveling salesman polytope of some directed graph with n nodes. The latter class of polytopes is shown to have maximum diameter .

AMRoute: Adhoc Multicast Routing Protocol
     Keywords:  IP Multicast, Mobile Ad-Hoc Networks, Network Protocols, Routing
     Author:        Liu, M., Talpade, R. , McAuley, A. and Bommaiah, E.
     Download:   PDF  (07-01-1999)
     Abstract:

The Adhoc Multicast Routing Protocol (AMRoute) presents a novel approach for robust IP Multicast in mobile adhoc networks by exploiting user-multicast trees and dynamic logical cores. It creates a bi-directional, shared tree for data distribution using only group senders and receivers as tree nodes. Unicast tunnels are used as tree links to connect neighbors on the user-multicast tree. Thus, AMRoute does not need to be supported by network nodes that are not interested/capable of multicast, and group state cost is incurred only by group senders and receivers. Also, the use of tunnels as tree links implies that tree structure does not need to change even in case of a dynamic network topology, which reduces the signaling traffic and packet loss. Thus AMRoute does not need to track network dynamics; the underlying unicast protocol is solely responsible for this function. AMRoute does not require a specific unicast routing protocol; therefore, it can operate seamlessly over separate domains with different unicast protocols. Certain tree nodes are designated by AMRoute as logical cores, and are responsible for initiating and managing the signaling component of AMRoute, such as detection of group members and tree setup. Logical cores differ significantly from those in CBT and PIM-SM, since they are not a central point for data distribution and can migrate dynamically among member nodes. Simulation results demonstrate that AMRoute signaling traffic and join latency remain at relatively low levels for typical group sizes. The results also indicate that group members receive a high proportion of data multicast by a sender, even in the case of a dynamic network.

An Algorithm for Multistage Dynamic Networks with Random Arc Capacities, with an Application to Dynamic Fleet Management
     Author:        Cheung, R. K.-M., Powell, W.B.
     Download:   PDF  (09-01-1995)
     Abstract:

We consider the class of multistage dynamic networks with random arc capacities, a framework that is well suited to model dynamic eet management problems. We propose a successive convex approximation approach that produces an approximation to the expected recourse function which captures the future eects of current decisions under uncertainty. This method decomposes the network in each stage into tree subproblems, whose expected recourse functions are easy to obtain. We also compare this method with two alternative methods on a set of dynamic eet management problems. The numerical results show that this method is superior than the two alternative methods.

An Evolutionary Approach to Computer-Supported Groups: An Examination of Communications Channel and Leadership Presence
     Keywords:  Group Decision Support Systems (GDSS), Genetic Algorithms, Computational Modeling and Markov Models
     Author:        Rees, J., Koehler, G. J.
     Download:   PDF  (07-29-1999)
     Abstract:

An Infeasible-Interior-Point Potential-Reduction Algorithm for Linear Programming
     Author:        Tutuncu, R.
     Download:   Postscript  (11-01-1995)
     Abstract:

This paper studies a new potential-function and an infeasible-interior-point method based on this function for the solution of linear programming problems. This work is motivated by the apparent gap between the algorithms with the best worst-case complexity and their most successful implementations. For example, analyses of the algorithms are usually carried out by imposing several regularity assumptions on the problem, but implementations can solve problems which do not satisfy these assumptions. Furthermore, most state-of-the-art implementations incorporate heuristic tricks, but these modifications are rarely addressed in the theoretical analysis of the algorithms. The method described here and its analysis have the flexibility to integrate any heuristic technique for implementation while maintaining the important polynomial complexity feature.

An Integrated Model for Manufacturing Shop Design
     Keywords:  manufacturing, plant layout, manufacturing systems, material handling, vehicle routing, integer programming
     Author:        Ioannou, G., Minis, I.
     Download:   PDF  (01-23-1995)
     Abstract:

This paper presents an integer programming formulation for the manufacturing shop design problem, which integrates decisions concerning the layout of the resource groups on the shop floor with the design of the material handling system. The model reflects critical practical design concerns including the capacity of the flow network and of the transporters, and the tradeoff between fixed (construction and acquisition) and variable (operational) costs. For realistic industrial cases, the size of the problem prevents the solution through explicit or implicit enumeration schemes. The paper addresses this limitation by decomposing the global model into its natural components. The resulting submodels are shown to be standard problems of operations research. The decomposition approach provides ways to solve the integrated shop design problem in an effective manner.

An Investigation of GA Performance Results for Different Cardinality Alphabets
     Keywords:  Genetic Algorithm
     Author:        Rees, J., Koehler, G. J.
     Download:   Postscript  (01-01-1997)
     Abstract:

Theoretical and empirical results give mixed advice for choosing the cardinality for GA representation. Using GA models that capture the exact expected behavior of both the binary and higher cardinality cases, the determination of which representation is best for a given GA can be made. De Jong et al. and Spears and De Jong presented how the exact model for the binary genetic algorithm can give important insights to transient GA behavior. This paper uses a similar approach to study the impact of different cardinalities using the Koehler-Bhattacharyya-Vose general cardinality model.

An SQP Algorithm for Finely Discretized Continuous Minimax Problems and Other Minimax Problems with Many Objective
     Keywords:  continuous miminax, semi-infinite programming, many constraints, sequential quadratic programming, discretization, global convergence.
     Author:        Zhou, J., Tits, A.
     Download:   PDF  (01-23-1993)
     Abstract:

A common strategy for achieving global convergence in the solution of semi-infinite programming (SIP) problems, and in particular of continuous minimax problems, is to (approximately) solve a sequence of discretized problems, with a progressively finer discretization mesh. Finely discretized minimax and SIP problems, as well as other problems with many more objectives/constraints than variables, call for algorithms in which successive search directions are computed based on a small but significant subset of the objectives/constraints, with ensuing reduced computing cost per iteration and decreased risk of numerical difficulties. In this paper, an SQP-type algorithm is proposed that incorporates this idea in the particular case of minimax problems. The general case will be considered in a separate paper. The quadratic programming subproblem that yields the search direction involves only a small subset of the objectives functions. This subset is updated at each iteration in such a way that global convergence is insured. Heuristics are suggested that take advantage of a possible close relationship between �adjacent objective functions. Numerical results demonstrate the efficiency of the proposed algorithm.

Another derivation of the Karmarkar direction for linear programming
     Author:        Todd, M. J.
     Download:   Postscript  (12-01-1991)
     Abstract:

This paper provides another derivation of the Karmarkar direction for linear programming. It is strongly motivated by derivations of Gonzaga, but we show how the direction can be viewed as a steepest descent direction in the original feasible region corresponding to a metric different from the Euclidean one. We show that a fixed decrease in the potential function can be obtianed by taking a step in this direction, as long as a certain assumption holds. We give an example showing that such a restriction is necessary, and discuss two ways to remove it.

Anticipated behavior of long�step algorithms for linear programming
     Keywords:  Linear Programming, interior point algorithms, path�following algorithms, potential reduction algorithms.
     Author:        Mizuno, S., Todd, M. J. and YE, Y.
     Download:   Postscript  (10-28-1997)
     Abstract:

We provide a probabilistic analysis of the second order term that arises in path� following algorithms for linear programming. We use this result to show that two such methods, algorithms generating a sequence of points in a neighborhood of the central path and in its re� laxation, require a worst�case number of iterations that is O(nL) and an anticipated number of iterations that is O(log(n)L). The second neighborhood spreads almost all over the feasible region so that the generated points are close to the boundary rather than the central path. We also propose a potential reduction algorithm which requires the same order of number of iterations as the path�following algorithms.

Application of Perturbation Analysis to the Design and Analysis of Control Charts
     Keywords:  discrete event dynamical systems DEDS, perturbation analysis, Monte Carlo simulation, statistical quality control, control charts, average run length,
     Author:        Fu, M., Hu, J.
     Download:   PDF  (07-22-1997)
     Abstract:

The design of control charts in statistical quality control addresses the optimal selection of the design parameters such as the sampling frequency and the control limits; and includes sensitivity analysis with respect to system parameters such as the various process parameters and the economic costs of sampling. The advent of more complicated control chart schemes has necessitated the use of Monte Carlo simulation in the design process, particularly in the evaluation of performance measures such as average run length. In this paper, we apply perturbation analysis to derive gradient estimators that can be used in gradient-based optimization algorithms and in sensitivity analysis when Monte Carlo simulation is employed. We illustrate the technique on a simple Shewhart control chart and on a more complicated control chart that includes the exponentially- weighted moving average control chart as a special case.

Approximation Algorithms for Steiner and Directed Multicuts
     Author:        Klein, P., Plotkin, S. Rao, S. and Tardos,E.
     Download:   Postscript  (02-01-1995)
     Abstract:

In this paper we consider the steiner multicut problem. This is a generalization of the minimum multicut problem where instead of separating node pairs, the goal is to find a minimum weight set of edges that separates all given sets of nodes. A set is considered separated if it is not contained in a single connected component. We show an approximation algorithm for the steiner multicut problem, where k is the number of sets and t is the maximum cardinality of a set. This improves the bound that easily follows from the previously known multicut results. We also consider an extension of multicuts to directed case, namely the problem of finding a minimum-weight set of edges whose removal ensures that none of the strongly connected components includes one of the prespecified k node pairs. In this paper we describe an approximation algorithm for this directed multicut problem. If , this represents and an improvement over the approximation algorithm that is implied by the technique of Seymour.

Approximations for the Disjoint Paths Problem in High-Diameter Planar Networks
     Author:        Kleinberg, J., Tardos, E.
     Download:   Postscript  (03-01-1995)
     Abstract:

We consider the problem of approximating the maximum number of distinguished terminal pairs in a graph that can be simultaneously connected via edge-disjoint paths. This is a classical NP-complete problem for which no general approximation techniques are known; it has recently been brought into focus in papers discussing applications to admission control in high-speed networks and to routing in all-optical networks. We provide an -approximation for the class of nearly-Eulerian, uniformly high-diameter planar graphs, which includes two-dimensional meshes and other common planar interconnection networks. We also give an -approximation to the minimum number of wavelengths needed to route a collection of terminal pairs in the ``optical routing`` model considered by Raghavan and Upfal, and others; this improves on an -approximation for the special case of the mesh obtained by Aumann and Rabani. Our algorithm makes use of a number of new techniques, including the construction of a ``crossbar`` structure in any nearly-Eulerian planar graph, and develops some connections with classical matroid algorithms.

Asymptotic Behavior of Hill`s Estimator for Autoregressive Data
     Author:        Resnick, S., Starica, C.
     Download:   Postscript  (08-01-1996)
     Abstract:

Consider a stationary, pth order autoregression satisfying ___whose innovation sequence is iid with regularly varying tail probabilities of index . From observations ____, one may estimate__by applying Hill`s estimator to___. Alternatively, a second procedure is to use__to get estimates of the autoregressive coefficients and then to estimate the residuals by ___and then to apply Hill`s estimator to the estimated residuals. We show that from the point of asymptotic variance, the second procedure is superior.

Brainstorming, Negotiating and Learning in Group Decision Support Systems: An Evolutionary Approach
     Keywords:  Group Decision Support Systems (GDSS), Genetic Algorithms, Computational Modeling and Markov Models
     Author:        Rees, J., Koehler, G. J.
     Download:   PDF  (07-29-1999)
     Abstract:

Certain tasks undertaken by groups using Group Decision Support Systems (GDSS) can be viewed as search problems. These tasks involve arriving at a solution or decision where the problem is complex enough to warrant the use of computerized decision support tools. For these types of GDSS tasks, we propose to model the brainstorming, negotiating and learning processes undertaken by the group as a simple genetic algorithm. The simple genetic algorithm is a generalized search technique that is based on the principles of evolution and natural selection. Simply put, the best points in the current population are more likely to be selected and combined through genetic operators to determine new points. We propose that groups using GDSS to address certain tasks behave like a simple genetic algorithm in the manner in which possible solutions are generated, enhanced and altered in attempting to reach a decision or consensus. simple genetic algorithm. Hirokawa and Johnson proposed that the group decision-making process is itself an evolutionary process. Hence, the idea that groups undergo change and that the initial ideas or proposals submitted during a brainstorming session are subject to adaptation is not a new idea but has not been formally incorporated into analytical models for GDSS. This paper will describe an analytical model for groups using GDSS using a simple genetic algorithm (GA) as the basis of the model. We test this model using experimental data and will present the results of tests of hypotheses linking GA parameters to one specific set of GDSS variables.

Capacitated Inventory Problems with Fixed Order Costs: Some Optimal Policy Structure
     Keywords:  Inventory, Stochastic processes
     Author:        Gallego, Guillermo,, Alan Scheller-Wolf
     Download:   Postscript  (01-22-1998)
     Abstract:

Using a generalization of Scarf`s K-convexity, we are able to show that the optimal policy for the periodic review inventory problem with fixed ordering costs and finite capacity has an (s; S)-like structure. In particular, we are able to divide the parameter space into four regions. In two of these regions the optimal policy is completely specified. In the other two, it is partially specified.

Capacity-Driven Acceptance of Customer Orders for a Multi-Stage Batch Manufacturing System: Models and Algorithms
     Author:        Cakanyildirim, M., Chen, D. , Chen, P. , Roundy, R., Freimer , M.B. and Melkonian, V.
     Download:   Postscript  (02-01-1999)
     Abstract:

An automotive parts manufacturer produces a wide variety of parts in a job-shop environment. Many of the manufacturing operations have substantial setups. When a client phones in an order, the manufacturer must decide quickly whether or not it has the capacity required to accept the order. We develop a simplified formulation of the order acceptance problem. We formulate the discrete-time version as an integer program. The problem is NP-hard, but in 60 out of 60 small test problems the LP relaxation is tight. For larger problems we test several heuristics. Three of the heuristics look promising - simulated annealing, a genetic algorithm, and an LP-based heuristic.

Casino Gambling on the Internet: Scope, Issues, and Opportunities
     Keywords:  Blackjack
     Author:        Conway, D., Koehler, G. J.
     Download:   PDF  (04-21-1999)
     Abstract:

Online gaming has arrived. In this paper we discussed two implementations, IslandCasino`s and Casino Royale`s. These two illustrate what is common to online casinos (deposits, withdrawals and games available). They also illustrate the wide variety of environments and opportunities. IslandCasino offers a superior interface based on Java applets. They also offer more opportunities for sophisticated players. Online casinos differ from traditional casinos in a number of ways. We reviewed a number of these differences. Perhaps most noteworthy is the fact that online casinos can minimize player cheating yet increase their own opportunity to cheat. We address this issue by performing a number of statistical tests to detect casino cheating. In no case were we able to detect cheating.

Caveat Mercator in Electronic Commerce: A Gaming Example
     Keywords:  Optimal Blackjack, Markov Decision Process, Agent-based player
     Author:        Conway, D., Koehler, G. J.
     Download:   PDF  (09-26-1998)
     Abstract:

Electronic commerce has opened new opportunities for buyers and sellers. Consumers can do things in an on-line environment that are simply not possible in face-to-face transactions. In this paper we examine a novel setting where consumers can gain a dramatic advantage over a seller of an on-line service. Recently on-line casino gaming has appeared on the Internet. One game offered is blackjack - a game known to have a positive expected value for the player if played optimally. In on-line casino gambling, one can employ computer-assisted play and optimal betting with impunity, both of which are not permitted in real casinos. This paper formulates and solves the optimal blackjack betting problem - a problem not adequately solved in the literature. This problem is exceedingly hard to solve for realistic settings. We propose and test a number of solution strategies.

Centralized and competitive inventory models with demand substitution.
     Keywords:  Substitution, inventory, retail, stochastic model, newsvendor, single period, Nash equilibrium, game theory
     Author:        Nils Rudi, Serguei Netessine
     Download:   PDF  (12-20-1999)
     Abstract:

It is common for customers to substitute a commodity product with a similar one if stock-out occurs. Previous research indicates that by jointly setting stocking levels of substitutable products retailers can achieve sizable profit increases. In this paper we consider a very general substitution problem with any number of products and any substitution structure. We propose a simple and intuitive way to obtain a tractable analytical solution for this case thus extending the results of a number of papers in this area. Two main scenarios are considered: with centralized inventory control and with competition among retailers selling substitute goods. We prove concavity of the objective function in the non-competitive case and existence and uniqueness of the Nash equilibrium in the competitive case. The paper also provides simple bounds for the optimal inventory levels.

Cliques and Clustering: A Combinatorial Approach
     Author:        Mehrotra, Anuj, Trick , M.
     Download:   Postscript  (05-01-1997)
     Abstract:

We use column generation and a specialized branching technique for solving con- strained clustering problems. We also develop and implement an innovative com- binatorial method for solving the pricing subproblems. Computational experiments comparing the resulting branch-and-price method to competing methodologies in the literature are presented and suggest that our technique yields a significant improvement on the hard instances of this problem.

Computation of the Exact Solution from a Near Optimum Solution for Convex QP
     Author:        Mizuno, S., Murty, K.G.
     Download:   Postscript  (10-01-1992)
     Abstract:

Consider a convex quadratic program of size L involving m inequality constraints and possibly some equality constraints in n variables. Given a feasible solution whose objective value is within 2-2L of the optimum objective value, we discuss a procedure that finds a true optimum solution in at most m iterations, where each iteration involves minimizing the quadratic objective function on an affine space (this takes at most n conjugate gradient steps).

Computing Near-Optimal Solutions to Combinatorial Optimization Problems
     Author:        Shmoys, D. B.
     Download:   Postscript  (01-01-1990)
     Abstract:

In the past few years, there has been significant progress in our understanding of the extent to which near-optimal solutions can be efficiently computed for NP-hard combinatorial optimization problems. This paper surveys these recent developments, while concentrating on the advances made in the design and analysis of approximation algorithms, and in particular, on those results that rely on linear programming and its generalizations.

Computing Optimal Stock Levels for Common Components in an Assembly System
     Keywords:  Assembly systems; component commonality; stochastic program; simulation; derivative estimation; dual simplex; sensitivity analysis.
     Author:        Sridhar, Tayur
     Download:   Postscript  (01-01-1994)
     Abstract:

Managing component inventories effectively in assembly systems with several products that share many common components can lead to improved customer service. We consider a two-level, finite-horizon assembly problem with multiple end-products that have random demands and share several common components. The objective is to minimize the total cost which comprises of holding excess components and paying a penalty on backlogged demand of the end-products. We model this problem as a multi-period stochastic program. We show that it can be de- composed into a set of nested stochastic programs, each similar in structure to a one-period problem. We show that the problem is convex. We develop a simulation-based method for estimating the derivatives of costs with respect to component stock levels. These deriva- tive estimates are then used in an optimization procedure to obtain optimal values. Our estimation algorithm takes advantage of special structure in the imbedded linear programs. Experiments suggest that our algorithm converges to good values on industrial size problems in reasonable time. Extensions to compute derivatives with respect to demand parameters, executing our algorithm in a rolling horizon, solving an infinite horizon stationary problem and taking advantage of special demand structures are also discussed.

Controlled Markov Processes on the Infinite Planning Horizon: Weighted and, Overtaking Cost Criteria
     Keywords:  controlled Markov processes, infinite planning horizon, weighted , overtaking cost criteria
     Author:        Fernandez-Gaucherand, E., Ghosh, M. and Marcus, S.
     Download:   PDF  (01-01-1993)
     Abstract:

Stochastic control problems for controlled Markov processes models with an infinite planning horizon are considered, under some non-standard cost criteria. The classical discounted and average cost criteria can be viewed as complementary, in the sense that the former captures the short-time and the latter the long-time performance of the system. Thus, we study a cost criterion obtained as weighted combinations of these criteria, extending to a general state and control space framework several recent results by Feinberg and Shwartz, and by Krass et al. In addition, a functional characterization is given for overtaking optimal policies, for problems with countable state spaces and compact control spaces; our approach is based on qualitative properties of the optimality equation for problems with an average cost criterion.

Convexity and Sensitivity Properties of (R,T) Inventory Control Policies for Stochastic Demand Models
     Author:        Rao, U. S.
     Download:   Postscript  (11-01-1993)
     Abstract:

In this paper we show that, for two commonly used stochastic demand models, the exact long-run average cost function for the (R,T) inventory policy is jointly convex in the order-up-to-level, R, and the reorder interval, T. Consequently, the optimal control variables can be efficiently determined using a simple search routine such as Golden Section for minimization of convex functions. We also demonstrate the following sensitivity results for the continuous demand case: (a) The optimal cost is relatively insensitive to the choice of T, provided the optimal R corresponding to the chosen T is used. (b) The optimal reorder interval, T, and the corresponding long-run average inventory costs, for the stochastic (R,T) model are greater than that for the deterministic model, although the corresponding ordering costs are lower. (c) The relative percentage increase in costs from using the optimal reorder interval obtained by a deterministic analysis instead of the optimal from a stochastic model is no more than 12.5%. (d) The relative increase in long-run average cost resulting from use of an (R,T) policy instead of an (r,Q) policy has a provable worst-case bound of 1.0. Some numerical experiments are conducted to evaluate the computational issues, sensitivity and near-optimality of the (R,T) policy. In particular, we identify special situations in which the (R,T) policy has a less significant cost disadvantage relative to the (r,Q) poicy.

Current Research on Manufacturing Shop and Material Handling System Design
     Author:        Ioannou, G., Minis, I.
     Download:   PDF  (01-23-1995)
     Abstract:

The importance of the manufacturing shop design in the successful operation of a production system is well known and as a result, significant research has been devoted to this area. This paper reviews important literature in various aspects of manufacturing shop design including layout, material flow path design, and transporter fleet sizing and routing. In addition, the paper focuses on contributions to integration issues such as the design for operation of material handling systems, and the concurrent design of the shop layout and the transportation system. Research studies in these areas are critically examined, and emerging opportunities for research are identified.

Cyclic Schedules as part of a JIT implementation at a laminate plant
     Author:        Sridhar, Tayur
     Download:   Postscript  (08-01-1996)
     Abstract:

We briefly describe a Just-In-Time (JIT) implementation where cyclic schedules play a critical role. Central to the implementation is a clear understanding of the interactions between scheduling, due date quotation, capacity allocation, variability in production and demand, inventory management and customer service. Furthermore, a novelty of this imple- mentation is that we used the new technology of simulation based optimization to compute certain inventory levels. The goal of this paper is to communicate a successful implemen- tation of stochastic cyclic schedules that has had a significant impact at the plant level, as well as provide details of the entire implementation (as several changes have been made at the shop floor, the plant and the supply chain levels).

Design of a PBC (MRP Lot For Lot) planning system for cellular manufacturing
     Keywords:  time bucket length, bom structure, cellular manufacturing
     Author:        J. Riezebos
     Download:   PDF  (01-04-2001)
     Abstract:

The design of a special type of MRP system is studied: a Period Batch Control system. In cellular manufacturing, this type of system is rather popular, as it leads to short and reliable throughput times and low inventories. The study shows that two design parameters, the length of the time bucket and the number of levels in the planning bill of material, have a high impact on the performance of the system. Using simulation, other factors, such as scheduling rules applied, are tested as well. The study provides a decision support model to support decisions in the design of an effective planning system.

Design of Material Flow Networks in Manufacturing Facilities
     Keywords:  algorithms, manufacturing, plant layout
     Author:        Herrmann, J., Ioannou, .G, Minis, I. , Nagi, R. and Proth, J.
     Download:   PDF  (01-23-1994)
     Abstract:

In this paper we consider the design of material handling flow paths in a discrete parts manufacturing facility. A fixed-charge capacitated network design model is presented and two efficient heuristics are proposed to determine near-optimal solutions to the resulting NP- hard problem. The heuristics are tested against an implicit enumeration scheme used to obtain optimal solutions for small examples. For more realistic cases, the solutions of the heuristics are compared to lower bounds obtained by either the linear programming relaxation of the mixed integer program, or an iterative dual ascent algorithm. The results obtained indicate that the heuristics provide good solutions in reasonable time on the average. The proposed methodology is applied to design the flow paths of an existing manufacturing facility. The role of the flow path network problem in the integrated shop design is also discussed.

Development of a Rapid-Response Supply Chain at Caterpillar
     Author:        Rao, Uday, Scheller-Wolf, Alan and Sridhar ,Tayur
     Download:   Postscript  (02-01-1999)
     Abstract:

As part of its growth strategy, Caterpillar Inc. plans to launch a new P2000 product line of `compact` construction equipment and work tools. In anticipation of this, they asked the authors to construct and analyze potential P2000 supply chain configurations. Through the use of decomposition, and results from network flow theory, inventory theory, and simulation theory, we were able to provide a set of solutions to this problem, corresponding to different supply chain scenarios (provided by Caterpillar). Based on our recommendations, Caterpillar made their decision regarding the P2000 supply chain configuration.

Diagonalizing the Simple GA Mixing Matrix - Part 1
     Keywords:  Congruence transform, Walsh matrix, Genetic Algorithm
     Author:        Koehler, G. J.
     Download:   Postscript  (11-15-1995)
     Abstract:

The simple GA mixing matrix, M, is diagonalized by a congruence transformation involving a lower-triangular matrix, L. L is sparse. Several applications using L are given. One application gives the rank of M under various choices of GA parameter values. A second application shows how L might prove useful in studying the GA Fixed Point Problem. In this problem L is used to change a quadratic equation having terms to one having no cross terms and only squared terms.

Diagonalizing the Simple GA Mixing Matrix - Part 2
     Keywords:  Congruence transform, Walsh matrix, Genetic Algorithm
     Author:        Koehler, G. J.
     Download:   Postscript  (11-15-1995)
     Abstract:

Diagonalizing the Simple GA Mixing Matrix - Part 3
     Keywords:  Congruence transform, Walsh matrix, Genetic Algorithm
     Author:        Koehler, G. J.
     Download:   Postscript  (11-15-1995)
     Abstract:

Discussion of the Danish Data on Large Fire Insurance Losses
     Author:        Resnick, S.
     Download:   Postscript  (12-01-1996)
     Abstract:

Alexander McNeil`s (1996) study of the Danish data on large fire insurance losses provides an excellent example of the use of extreme value theory in an important application context. We point out how several alternate statistical techniques and plotting devices can buttress McNeil`s conclusions and provide flexible tools for other studies.

Disjoint Paths in Densely Embedded Graphs
     Author:        Kleinberg, J., Tardos,E.
     Download:   Postscript  (06-01-1995)
     Abstract:

We consider the following maximum disjoint paths problem (MDPP) We are given a large network, and pairs of nodes that wish to communicate over paths through the network -- the goal is to simultaneously connect as many of these pairs as possible in such a way that no two communication paths share an edge in the network. This classical problem has been brought into focus recently in papers discussing applications to routing in high-speed networks, where the current lack of understanding of the MDPP is an obstacle to the design of practical heuristics. We consider the class of densely embedded, nearly-Eulerian graphs, which includes the two-dimensional mesh and many other planar and locally planar interconnection networks. We obtain a constant-factor approximation algorithm for the maximum disjoint paths problem for this class of graphs; this improves on an O(log n)-approximation for the special case of the two-dimensional mesh due to Aumann-Rabani and the authors. For networks that are not explicitly required to be `high-capacity,` this is the first constant-factor approximation for the MDPP in any class of graphs other than trees. We also consider the MDPP in the on-line setting, relevant to applications in which connection requests arrive over time and must be processed immediately. Here we obtain an asymptotically optimal O(log n)-competitive on-line algorithm for the same class of graphs; this improves on an O(log n log log n)-competitive algorithm for the special case of the mesh due to Awerbuch, Gawlick, Leighton, and Rabani.

Distribution tails of sample quantiles and subexponentiality
     Author:        Braverman, M., Samorodnitsky, G.
     Download:   Postscript  (07-05-1997)
     Abstract:

We show that subexponentiality is not sufficient to guarantee that the distribution tail of a sample quantile of an infinitely divisible process is equivalent to the ``tail`` of the same sample quantile under the corresponding L�vy measure. However, such an equivalence result is shown to hold under either an assumption of an appropriatly slow tail decay or an assumption on the structure of the process.

Distribution Theory of Group Sequential t, chi-square and F Tests for General Linear Mixed Models
     Author:        Jennison, C., Turnbull, B. W.
     Download:   Postscript  (01-15-1997)
     Abstract:

We derive the joint distribution of the sequence of estimates of the parameter vector in a normal general linear model when data accumulate over a series of analyses. This sequence of estimates has a remarkably simple covariance structure, even when observations are correlated, allowing standard group sequential tests to be applied in very general settings. If variances and covariances of the observations depend on an unknown scale factor , the joint distribution of the sequence of estimates of and is required in order to construct sequential t-tests. We show that this joint distribution has a simple form, again even in the case of correlated observations, and a general treatment of group sequential t-tests can be obtained. Our results also provide a basis for group sequential and F-tests appropriate to the cases of known and unknown variance, respectively.

Distributions arising in the modelling of environmental processes
     Author:        Samorodnitsky, G., Rachev, S.T.
     Download:   Postscript  (05-01-1990)
     Abstract:

We study certain stochastic processes arising in probabilistic modelling. We discuss the limit behavior of these processes and estimate the rate of convergence to the limit.

Domains of attraction for exponential families
     Author:        Balkema, A.A., Kluppelberg, C. and Resnick, S.
     Download:   Postscript  (03-18-1999)
     Abstract:

With the df F of the rv X we associate the natural exponential family of df`s__where _____for . Assume___does not lie in__. Let__, then non-degenerate limit laws for the normalized distributions___are the normal and gamma distributions. Their domains of attractions are determined. Applications to saddlepoint and gamma approximations are considered.

Dynamic Control of Logistics Queueing Networks for Large Scale Fleet Management
     Keywords:  Fleet Management, driver scheduling
     Author:        Powell, W. B., Carvalho, T.
     Download:   PDF  (05-07-1999)
     Abstract:

Dynamic fleet management problems are normally formulated as networks over dynamic networks. Additional realism usually implies the inclusion of complicating constraints, typically producing exceptionally large integer programs. In this paper, we present for the first time the formulation of dynamic fleet management problems in an optimal control setting, using a novel formulation called a Logistics Queueing Network (LQN). This formulation replaces a single, large optimization problem with a series of very small problems that involve little more than solving a single sort at each point in space and time. We show that this approach can produce solutions that are within a few percent of a global optimum, but providing for considerably more exibility than standard linear programs.

Dynamic Control of Multicommodity Logistics Queueing Networks
     Author:        Carvalho, T., Powell, W.B.
     Download:   PDF  (09-25-1996)
     Abstract:

Dynamic fleet management problems with multiple equipment types and limited sub- stitution can be modeled as dynamic, multicommodity network ow problems. These problems are further complicated by the presence of time windows on task arcs (a task, or load, can be handled at dierent points in time) and the need for integer solutions. In this paper, we formulate the problem as a dynamic control problem, and show that we can produce solutions within four to five percent of a linear relaxation. In addition, we can solve the ultra-large problems that arise in certain applications; these problems are beyond the capabilities of state-of-the-art linear programming solvers.

Dynamic Fleet Management as a Logistics Queueing Network.
     Author:        Powell, W. B., Carvalho, T., Godfrey, G. and Simao, H.
     Download:   PDF  (06-12-1995)
     Abstract:

This paper introduces a new framework for modeling and solving dynamic eet man- agement problems, which we call the Logistics Queueing Network (LQN). A variety of problems in logistics involve the combined problem of moving freight from origin to destination while simultaneously managing the capacity required to move this freight. Standard formulations for real-world problems usually lead to intractably large linear programs. The LQN approach can take into account more real world detail and is con- siderably faster than classical LP formulations. The solutions generated using the LQN approach are shown to be within a few percentage points of the LP optimal solutions depending on the size of the capacity eets.

Dynamic Management of Heterogeneous Resources
     Author:        Powell, W. B., Shapiro, J.
     Download:   PDF  (12-01-1998)
     Abstract:

Effective Heuristics for Multi-product Shipment Models
     Author:        Dawande, Milind, Srinagesh, Gavirnenei, and Sridhar, Tayur
     Download:   Postscript  (07-26-1996)
     Abstract:

We consider two shipment models (motivated by a real application) where multiple customers asking for sets of products are to be satisfied from inventory in the best man- ner possible. The restrictions posed by the customers include that the first shipment be at least a minimum fraction of the total demand, and that the second shipment (if any) should not be too small nor be further split. We first show that solving these prob- lems to optimality requires considerable computational effort. Thus, the performance of commercially available packages, applied directly on these problems, is unsatisfactory. Adapting the latest developments in computational integer programming, we are able to solve several instances to optimality. However, this can also require considerable computational effort with some instances not solvable within 10 hours. So we develop and analyze two heuristics: these are easy to implement, run very quickly and provide good solutions. In a test bed of 50 problems of industrial size, one heuristic solves Model 1 and Model 2 under 30 seconds and 10 seconds respectively, with an average error of 0.86% and 2.1%. The average relative error of the second heuristic is 0.18 % and 1.05 % for Model 1 and Model 2 respectively and solves these in an average of 142 seconds and 321 seconds.

Efficient Continuous-Time Dynamic Network Flow Algorithms
     Author:        Fleischer, L., Tardos, E.
     Download:   Postscript  (08-01-1996)
     Abstract:

We extend the discrete-time dynamic flow algorithms presented by Ford and Fulkerson, Wilkinson, Minieka, and Hoppe and Tardos to solve the analogous continuous-time dynamic flow problems. These problems include finding maximum dynamic flows, quickest flows, universally maximum dynamic flows, lexicographically maximum dynamic flows, dynamic transshipments, and quickest transshipments in networks with capacities and transit times on the edges.

Empirical-bias Bandwidths for Local Polynomial Nonparametric Regression and Density Estimation
     Author:        Ruppert, D.
     Download:   Postscript  (11-01-1995)
     Abstract:

A data-based local bandwidth selector is proposed for nonparametric regression by local fitting of polynomials. The estimator, called the empirical-bias bandwidth selector (EBBS), is rather simple and easily allows multivariate predictor variables and estimation of any order derivative of the regression function. EBBS minimizes an estimate of mean square error consisting of a squared bias term plus a variance term. The variance term used is exact, not asymptotic, though it involves the conditonal variance of the response given the predictors that must be estimated. The bias term is estimated empirically, not from an asymptotic expression. Thus, EBBS is similar to the `double smoothing` approach of H�rdle, Hall, and Marron, but is developed here for a far wider class of estimation problems than what those authors consider. EBBS is tested on simulated data and its performance seems quite satisfactory. Local polynomial smoothing of a histogram is a highly effective technique for density estimation, and several of the examples involve density estimation by EBBS applied to binned data.

Erratum: Probabilistic Models for Linear Programming
     Author:        Todd, M. J.
     Download:   Postscript  (10-28-1997)
     Abstract:

In this paper, I proposed various models for generating random linear programming problems and investigated several properties of these models, including the probability that the feasible region is bounded, the distribution of the distance from a particular interior point to each constraint hyperplane, and some properties of the vertices of the feasible region. Unfortunately, one of the results about these vertices is incorrect, and this affects some of the corollaries. Here I describe what is invalid, and explain where the difficulty arises in the proof.

Estimating Performance Measures in Stochastic Cyclic Schedules
     Author:        Jackson, P., Rao, U.
     Download:   Postscript  (09-01-1993)
     Abstract:

This paper reviews a cyclic scheduling model of repetitive manufacturing environments consisting of flexible machines and multi-stage jobs. We explicitly model two system performance measures, throughput and flow time, while incorporating variability arising from uncertainty in operation processing times. We present an iterative approximation scheme to estimate the two moment behavior of our performance measures. The basic approach relies on Clark`s method for computing moments of the maximum of bivariate normals. The proposed algorithm, called the Cyclic Network Clark`s Algorithm, is illustrated via a simple flow shop example and subjected to extensive computational testing.

Estimating the Size of the Transitive Closure
     Author:        Huber, M.
     Download:   Postscript  (06-01-1996)
     Abstract:

In O(m) time it is possible to find the number of nodes reachable in a directed graph from a single node. The best known deterministic algorithm requires O(sm) time to find the number of nodes reachable from each node in a set of s nodes. We give an __time randomized algorithm which gives for every node v in the graph an estimate of the number of nodes reachable from v. All of these estimates will lie within a factor of__ of the true answer with probability 1-1/n. This is an improvement of the result of Cohen which also gave a__approximation, but required __time to be true with probability__

Estimation of Hidden Markov Models for Partially Observed Risk Sensitive Control Problems
     Keywords:  queueing networks, signal processing, optimization, discrete event dynamical systems , machine learning, purely theoretical, nonlinear stochastic
     Author:        Frankpitt, B., Baras, J.
     Download:   PDF  (02-01-1997)
     Abstract:

We look at the problem of estimation for partially observed, risk-sensitive control problems with finite state, input and output sets, and receding horizon. We describe architectures for risk sensitive controllers, and estimation, and we state conditions under which both the estimated model converges to the true model, and the control policy will converge to the optimal risk sensitive policy.

Fast approximation algorithms for fractional packing and covering problems
     Author:        Plotkin, S. A., Shmoys, D. and Tardos, E.
     Download:   Postscript  (02-01-1992)
     Abstract:

This paper presents fast algorithms that find approximate solutions for a general class of problems, which we call fractional packing and covering problems. The only previously known algorithms for solving these problems are based on general linear programming techniques. The techniques developed in this paper greatly outperform the general methods in many applications, and are extensions of a method previously applied to find approximate solutions to multicommodity flow problems. Our algorithm is a Lagrangean relaxation technique; an important aspect of our results is that we obtain a theoretical analysis of the running time of a Lagrangean relaxation-based algorithm. We give several applications of our algorithms. The new approach yields several orders of magnitude of improvement over the best previously known running times for algorithms for the scheduling of unrelated parallel machines in both the preemptive and the non-preemptive models, for the job shop problem, for the Held & Karp bound for the traveling salesman problem, for the cutting-stock problem, for the network embedding problem, and for the minimum-cost multicommodity flow problem.

Fast Approximation Algorithms for Multicommodity Flow Problems
     Author:        Leighton, T., Makedon, F. ,Plotkin, S. , Stein, C. ,Tardos, E. and Tragoudas,S.
     Download:   Postscript  (02-01-1995)
     Abstract:

All previously known algorithms for solving the multicommodity flow problem with capacities are based on linear programming. The best of these algorithms uses a fast matrix multiplication algorithm and takes time for the multicommodity flow problem with integer demands and at least time to find an approximate solution, where k is the number of commodities, n and m denote the number of nodes and edges in the network, D is the largest demand, and U is the largest edge capacity. Substantially more time is needed to find an exact solution. As a consequence, even multicommodity flow problems with just a few commodities are believed to be much harder than single-commodity maximum-flow or minimum-cost flow problems. In this paper, we describe the first polynomial-time combinatorial algorithms for approximately solving the multicommodity flow problem. The running time of our randomized algorithm is (up to log factors) the same as the time needed to solve k single-commodity flow problems, thus giving the surprising result that approximately computing a k-commodity maximum-flow is not much harder than computing about k single-commodity maximum-flows in isolation. In fact, we prove that a (simple) k-commodity flow problem can be approximately solved by approximately solving single-commodity minimum-cost flow problems. Our k-commodity algorithm runs in time with high probability. We also describe a deterministic algorithm that uses an O(k)-factor more time. Given any multicommodity flow problem as input, both algorithms are guaranteed to provide a feasible solution to a modified flow problem in which all capacities are increased by a -factor, or to provide a proof that there is no feasible solution to the original problem. We also describe faster approximation algorithms for multicommodity flow problems with a special structure, such as those that arise in the `sparsest cut` problems studied earlier if .

Feasible Sequential Quadratic Programming for Finely Discretized Problems from SIP
     Keywords:  optimal control, optimization
     Author:        Lawrence, C., Tits, A.
     Download:   PDF  (07-22-1998)
     Abstract:

A sequential Quadratic Programming algorithm designed to efficiently solve nonlinear optimization problems with many inequality constraints, e.g. problems arising from finely discretized Semi-Infinite Programming, is described and analyzed. The key features of the algorithm are (i) that only a few of the constraints are used in the QP sub-problems at each iteration, and (ii) that every iterate satisfies all constraints.

Finite Buffer Realization of Input-Output Discrete Event Systems
     Keywords:  discrete event dynamical systems , flexible manufacturing
     Author:        Kumar, R., Garg, V. and Marcus, S.
     Download:   PDF  (01-23-1994)
     Abstract:

Many discrete event systems (DESs) such as manufacturing systems, data base management systems, communication networks, traffic systems, etc., can be modeled as input-output discrete event systems (I/O DESs). In this paper we formulate and study the problem of stable realization of such systems in the logical setting. Given an input and an output language describing the sequences of events that occur at the input and the output, respectively, of an I/O DES, we study whether it is possible to realize the system as a unit consisting of a given set of buffers of finite capacity, called a dispatching unit. The notions of stable, conditionally stable, dispatchable and conditionally dispatchable units are introduced as existence of stable (or input-output bounded), and causal (or prefix preserving) input- output maps, and effectively computable necessary and sufficient conditions for testing them are obtained.

Fitting a Bivariate Additive Model by Local Polynomial Regression
     Author:        Opsomer, J., Ruppert, D.
     Download:   Postscript  (02-01-1996)
     Abstract:

While the additive model is a popular nonparametric regression method, its theoretical properties are not well understood, especially when the backfitting algorithm is used for computation of the the estimators. This article explores those properties when the additive model is fitted by local polynomial regression. Sufficient conditions guaranteeing the asymptotic existence of unique estimators for the bivariate additive model are given. Asymptotic approximations to the bias and the variance of a homoskedastic bivariate additive model with local linear terms are computed. This model is shown to have the same rate of convergence as that of (non-additive) local linear regression. The approach is generalized to local polynomials of arbitrary degree.

Fixed Point Approximation for Multirate Multihop Loss Networks with Adaptive Routing
     Keywords:  loss network, fix-point approximation, reduced load, blocking probability, adaptive routing
     Author:        Liu, M., Baras, J.
     Download:   PDF  (07-01-1999)
     Abstract:

In this paper, we consider a class of loss networks where multiple traffic classes are present, each has different bandwidth requirement, and each traffic stream is routed according to an adaptive routing scheme. The performance metric of interest is the end-to-end call blocking probability. Blocking probabilities in a loss network have been studied quite extensively but very few considered multiple traffic classes and rates together with adaptive/state dependent routing. We propose a fixed-point method, a.k.a. reduced load approximation, to estimate the end-to-end blocking probability in a multihop, multirate loss network with adaptive routing. Simulation results are provided to compare with that of approximations. The approximation scheme is shown to be asymptotically correct in a natural limiting regime, and it gives conservative estimates of blocking probabilities under heavy traffic load.

Flexible service capacity: optimal investment and the impact of demand correlation
     Keywords:  Capacity, investment, correlation, stachastic programming, newsvendor
     Author:        Netessine, Serguei, Gregory Dobson and Robert Shumsky
     Download:   PDF  (06-01-2000)
     Abstract:

We consider a firm that provides multiple services using both specialized and flexible capacity. The problem is formulated as a two-stage single-period stochastic program. The firm invests in capacity before the actual demand is known and optimally assigns capacity to customers when demand is realized. Sample applications include a car-rental company�s use of mid-sized cars to satisfy unexpectedly high demand for compact cars and an airline�s use of business-class seats to satisfy economy-class demand. We obtain an analytical solution for a particular case, when services may be upgraded by one class. The simple form of the solution allows us to compare the optimal capacities explicitly with a solution that does not anticipate flexibility. Given that demand follows a multivariate Normal distribution, we analytically characterize the effects of increasing demand correlation on the optimal solution. For the case with two customer classes, the effects of demand correlation are intuitive: increasing correlation induces a shift from flexible to dedicated capacity. When there are three or more classes, there are also adjustments in the resources not directly affected by the correlation change. These adjustments follow an alternating pattern, with every other resource rising, and the remaining resources falling. Finally, we suggest an efficient algorithm for finding numerically the optimal capacities.

Further Delay Moment Results for FIFO Multiserver Queues
     Author:        Scheller-Wolf, Alan
     Download:   Postscript  (01-01-1998)
     Abstract:

Using a new family of service disciplines, we provide sufficient conditions for finite stationary delay moments in FIFO multiserver queues. This extends the work in Sigman and Scheller-Wolf[1997], generalizing the weakening of the Kiefer and Wolfowitz

General Cardinality Genetic Algorithms
     Keywords:  Genetic Algorithms, Markov chain
     Author:        Koehler, G. J., Siddhartha Bhattacharyya and Michael D. Vose
     Download:   Postscript  (01-01-1995)
     Abstract:

A complete generalization of the Vose Genetic Algorithm model from the binary to higher cardinality case is provided. Boolean AND and EXCLUSIVE-OR operators are replaced by multiplication and addition over rings of integers. Walsh matrices are generalized with finite Fourier transforms for higher cardinality usage. Comparison of results to the binary case are provided.

Genetic Algorithm Heuristics for Finite Horizon Partially Observed Markov Decision Problems
     Keywords:  genetic algorithms, partially observed Markov decision processes
     Author:        Lin, Alex Z. Z., Bean, James C. and White, Chelsea C. III
     Download:   PDF  (01-01-1990)
     Abstract:

The partially observed Markov decision problem (POMDP) is a generalization of a Markov decision problem (MDP) that allows for noise corrupted and costly observations of the underlying system state. The value function of the POMDP is known to be piecewise affine and convex (PAC) in the probability mass vector (pmv) over the state space. Most exact solution procedures determine the minimal set of affine functions that describes the value function. This determination tends to require significant computational resources, and as a result these solution procedures can only solve small-scale problems. In this paper, we develop two heuristic approaches, dc-niche and spatial, for constructing suboptimal designs for the finite horizon POMDP and present error bounds. Both of these approaches use the genetic algorithm to construct approximations of the min