bluuebunny/crossref_metadata_2025_split huggingface dataset:
Applying an Architecture for General Intelligence to Reduce Scheduling Effort
Authors: Prietula Michael J. , Hsu Wen-Ling , Steier David , Newell Allen 
Published: October 2008

A system called Merle-Soar is described which demonstrates how a specific architecture for general intelligence and learning (Soar) can be used to reduce scheduling effort when solving simple scheduling problems. In particular, we describe how Merle-Soar schedules sequences of jobs on a single bottleneck machine in a job shop. The knowledge of dispatching, acquired from examining how a human expert performs the task, is cast as search rules. A study was conducted which examined the extent to which learning could contribute to decreases in scheduling effort; specifically, the contribution of learning within-tasks was explored—the change in reasoning effort while solving a particular scheduling problem as knowledge is accumulated from successive trials. The results indicated that dramatic reductions in scheduling effort (in terms of the Soar architecture) were obtained. Knowledge gained early in the scheduling task was subsequently applied later in the task to reduce deliberation, and knowledge gained from one trial successfully reduced deliberation effort in subsequent trials. Additionally, the reduction exhibited the general power law of learning documented in psychological studies of skill acquisition. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A GRG2-Based System for Training Neural Networks: Design and Computational Experience
Authors: Subramanian Venkat , Hung Ming S. 
Published: October 2008

Artificial neural networks is a very active area of research in artificial intelligence. They are better than existing methods for many problems in pattern recognition and pattern matching. They are trained through examples rather than being programmed. Training neural networks is a nonlinear minimization problem. The currently popular algorithm for training neural networks is called back-propagation, a form of steepest descent technique. This paper presents a new training system based on GRG2, a widely distributed nonlinear optimization software. Comparisons with back-propagation based upon three benchmark problems suggest not only that the GRG2-based system is much faster, more robust and offers solutions with better quality, but also offers better scalability to larger problems. This paper is thus a clear example of the kinds of contributions that optimization theory can make to artificial intelligence. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Network Reoptimization Algorithms: A Statistically Designed Comparison
Authors: Amini Mohammad M. , Barr Richard S. 
Published: October 2008

Statistical design and analysis of experiments is a cornerstone methodology for scientific exploration and verification that is rarely employed in reporting mathematical software testing. This approach is used to study the relative effectiveness of three key algorithms for the reoptimization of network flow problems primal simplex, dual method, and out-of-kilter. Carefully designed experimentation with state-of-the-art codes accompanied by a rigorous statistical analysis isolates the most efficient method(s) for commonly encountered reoptimization problems, and identifies the effect on solution time of problem class, problem size, type of change (bounds, costs, or node requirements), degree and number of changes in parameters, and number of problems in the reoptimization series. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Bayesian Approach to Database Query Optimization
Authors: Seppi Kevin D. , Barnes J. Wesley , Morris Carl N. 
Published: October 2008

The focus of this paper is the application of Bayesian concepts to database query optimization. In relational database systems users retrieve data by describing the desired data. The description of the desired data takes the form of statements which specify operations on “relations” (as defined by set theory). In a relational database system a “query optimizer” determines how the desired data is to be found. The optimizer may have access to several potential algorithms for each step in the query. Each algorithm has a unique effect on the cost of evaluating the query. No single algorithm is best in all cases. To choose among the possible alternatives, the optimizer uses summary statistics of the data stored in the database to estimate the cost associated with the use of each alternative algorithm. Given the summary nature of the statistics typically collected, the true cost of the use of a given algorithm can be only estimated. As such, the query optimizer must choose algorithms in the presence of uncertainty. As will be illustrated later with a simple model, cases exist where the expected improvement in decision quality more than offsets the cost of sampling the database to gathering additional, more accurate, information. These cases are identified before such sampling is performed by using Bayesian pre-posterier analysis. When sample information is expected to have significant net value to the decision making process, sampling should be performed. In database query optimization readily available summary information is sufficient for the decision making process in some cases, in other cases, it is wholly inadequate. Examples of each of these cases will be identified. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Error Bound of a Heuristic for the Common Due Date Scheduling Problem
Authors: Liman Surya Danusaputro , Lee Chung-Yee 
Published: October 2008

In this paper, a simple heuristic for the n-job, one-machine nonpreemptive scheduling problem of minimizing the sum of absolute deviations of job completion times about a common due date is proposed. The heuristic, which has a complexity of O(n log n), is shown to have a tight relative worst case error bound of 0.5. A practical and systematic guideline for determining the posterior performance of the heuristic is also provided. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Commentary—Progress in Linear Programming
Authors: Bixby Robert E. 
Published: October 2008

There is little doubt that barrier methods are now indispensable tools in the solution of large-scale linear programming problems. However, it is our opinion that the results of Lustig, Marsten, and Shanno (hereafter LMS) somewhat overstate the performance of these methods relative to the simplex method. We will present a slightly different view of progress in linear programming, one in which barrier methods do not dominate in the solution of large-scale problems. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Commentary—Major Cholesky Would Feel Proud
Authors: Saunders Michael A. 
Published: October 2008

Probably more than any other group, authors Lustig, Marsten, and Shanno have led the way in demonstrating the effectiveness of interior methods for solving large, real-world linear programs. For several years they have written at length about things they have actually done. There are no pies in the sky, no secrets. They have explored a multitude of algorithmic ideas and implementation strategies, and they have done more than could be asked to share their experience with the rest of the world. Here, the authors look back on a decade's events that revived barrier methods for constrained optimization and eventually led to their production LP solver OB1. The results reported are indeed impressive. In this commentary, we focus mostly on the “engine”—the Cholesky factorizer—that has made OB1 such a practical success. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Design of Performance Constrained Optic Fiber Multidrop Access Networks
Authors: Dewan Rajiv M. 
Published: October 2008

Propagation delay may not be negligible in comparison to transmission times in high speed networks. As a consequence, design procedures for high speed networks, such as optic fiber based networks, must take propagation delay into account. The design problem for multidrop access networks that includes transmission and propagation delay times is modeled as a mixed integer program. The problem is shown to be NP Hard and a solution procedure is proposed. Experimentation reveals the effect of poll cycle time limits on topology and cost. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Staged Primal-Dual Algorithm for Finding a Minimum Cost Perfect Two-Matching in an Undirected Graph
Authors: Pekny Joseph F. , Miller Donald L. 
Published: October 2008

We describe an algorithm for finding a minimum cost perfect two-matching in a weighted undirected graph, G = (V, E). The algorithm is based on a staged approach that sequentially applies increasingly more expensive steps until a solution is found. First, the degree constrained LP relaxation is posed as a bipartite two-matching problem and solved using a network flow algorithm. Next, the facet inducing two-matching cutset inequalities are activated selectively within a primal-dual framework that progressively eliminates half-integral values from the primal solution while maintaining dual feasibility. The algorithm is guaranteed to terminate in O(|V|2|E|) steps, although computational results suggest this upper bound to be pessimistic. The algorithm is experimentally shown to be effective on TSPLIB test problem[1] ranging in size from 17 to 11,849 vertices. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Computational Study of Local Search Algorithms for Job Shop Scheduling
Authors: Aarts E. H. L. , van Laarhoven P. J. M. , Lenstra J. K. , Ulder N. L. J. 
Published: October 2008

We present a computational performance analysis of local search algorithms for job shop scheduling. The algorithms under Investigation are Iterative improvement, simulated annealing, threshold accepting, and genetic local search. Our study shows that simulated annealing performs best in the sense that it finds better solutions than the other algorithms within the same amount of running time. Compared to more tailored algorithms, simulated annealing still finds the best results but only under the assumption that running time is of no concern. Compared to tabu search, simulated annealing is outperformed especially with respect to running times. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
On the Complexity of the Policy Improvement Algorithm for Markov Decision Processes
Authors: Melekopoglou Mary , Condon Anne 
Published: October 2008

We consider the complexity of the policy improvement algorithm for Markov decision processes. We show that four variants of the algorithm require exponential time in the worst case. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
SSS: Subrouting Set for Experimenting in Simulation Research
Authors: Pollatschek A. M. 
Published: October 2008

SSS is a collection of routines that can be used in DOS-based systems with a Borland or Microsoft compiler. Simulations can be run within integrated environments, thus appreciably reducing turnover from concept of an idea until the experimental results are obtained. SSS provides nearly all the support found in well established simulation languages and is well suited to research and illustration of simulation principles. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Intelligent Objects in Simulation
Authors: Ozden Mufit 
Published: October 2008

In this paper, learning automata are incorporated as decision making agents (“intelligent objects”) to handle the discrete type of decisions in simulation models. The integrated simulation system is viewed as a continuously evolving, closed system in which operational and design decisions can be made automatically. In this learning paradigm, the simulation model serves as an environment which provides performance evaluations for the decision policies formulated in succession by the learning automata. As the automata revise the action probabilities at regular intervals on the basis of these performance evaluations, they improve their decision making process continuously. The approach can be an excellent tool for the analysis and design of complex systems under uncertainty. An application is demonstrated in a manufacturing setting in which due-dates and machine assignments of jobs are the decisions to be made by the automata so as to minimize a nonlinear function of job tardiness and earliness subject to random job arrivals and machine breakdowns. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Flexible Method for Estimating Inverse Distribution Functions in Simulation Experiments
Authors: Avramidis Athanassios N. , Wilson James R. 
Published: October 2008

To generate random variates from an unknown continuous distribution, we present procedure IDPF—a flexible technique for estimating the associated inverse distribution function from sample data and for generating variates from the fitted distribution by inversion. To motivate IDPF, first we examine a predecessor due to Hora, and we explain how Hora's method can fail in either the distribution-fitting or variate-generation stage of application. We apply IDPF as follows. After selecting an initial inverse distribution function by a standard technique, we estimate a polynomial “filter” for the random-number input by constrained nonlinear regression to achieve minimum “distance” between the empirical inverse distribution and the final fitted inverse distribution obtained by composition of the initial inverse distribution with the polynomial “filter.” The regression constraint ensures that the fitted inverse distribution function is nondefective and monotonically nondecreasing. A portable, public-domain implementation of IDPF is based on well-known techniques for selecting initial distributions from the Johnson translation system. A Monte Carlo study illustrates the effectiveness of IDPF. Compared to initial Johnson distributions selected by matching moments, IDPF-based fits are closer on the average to the corresponding empirical and theoretical inverse distribution functions. Similar conclusions apply to other initial distributions selected by other methods. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
The Application of Metamodeling to Interconnection Network Analysis
Authors: Shaw Wade H. , Davis Nathaniel J. , Raines Richard A. 
Published: October 2008

Metamodeling is demonstrated as a methodology to accurately and concisely characterize the behavior of parallel processing interconnection networks. A set of mathematical metamodels are derived from a discrete event simulation model and then used to predict and compare the performance of interconnection networks. To illustrate the development and the application of metamodels, models for the multistage cube network, the single stage cube network (hypercube), and the llliac IV mesh-type network are formulated. These models, validated using empirical data from earlier studies, provide compact mathematical relations between packet delay time, message load, and switch size for each interconnection architecture. This approach provides insight into the complexities of network performance and uses simulation as the experimental vehicle for theoretical development. We show the comparison of network performance and conclude that the use of simulation as a means to estimate mathematical models is beneficial and consistent with experimental evidence. Our metamodels for performance prediction establish a basis for future comparisons that can be directly applied by other researchers. The models give the designer of a parallel processing system additional insight for choosing the interconnection network which best suits the application needs. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Convergence Results for Harmonic Gradient Estimators
Authors: Jacobson Sheldon H. 
Published: October 2008

Sensitivity analysis of steady state simulation outputs typically involves estimating gradients. This paper presents convergence results for the harmonic gradient estimators. Sufficient conditions are formulated that validate the interchange of the derivative and the expectation operators for these estimators. The relationship between these estimators and finite differences gradient estimators is discussed. In particular, the harmonic estimators are shown to be variations of finite differences gradient estimators. Exploiting the orthogonal property of the trigonometric basis results in harmonic gradient estimation procedures requiring two simulation runs. Computational results with various queueing system simulation models are included to compare and illustrate the different estimators. These results suggest that the harmonic gradient estimation procedures requiring two simulation runs may be an alternative to forward (symmetric) finite differences gradient estimation procedures with common random number streams requiring p + 1 (2p) simulation runs. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Optimization of Simulation via Quasi-Newton Methods
Authors: Safizadeh M. Hossein , Signorile Robert 
Published: October 2008

This paper discusses the application of quasi-Newton methods to optimization of simulation. Specifically, it describes a general methodology that combines response surface methodology and other optimization techniques with quasi-Newton methods. Using quasi-Newton methods in the vicinity of the optimum speeds up the convergence rate of response surface methodology, the gradient, and search methods. From the class of quasi-Newton methods, we recommend BFGS and Davidon's methods. These methods are effective without exact line searches. Two examples demonstrate the effectiveness of the proposed methodology. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Branch and Bound Algorithm for Integer Quadratic Knapsack Problems
Authors: Bretthauer Kurt M. , Shetty Bala , Syam Siddhartha 
Published: October 2008

We present a branch and bound algorithm for solving separable convex quadratic knapsack problems with lower and upper bounds on the integer variables. The algorithm solves a series of continuous quadratic knapsack problems via their Kuhn-Tucker conditions. We also discuss reoptimization procedures for efficiently solving the continuous subproblems. Computational results for problems with up to 300 integer variables are reported. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
The Distribution Problem with Carrier Service: A Dual Based Penalty Approach
Authors: Diaby Moustapha , Ramesh R. 
Published: October 2008

The distribution problem with carrier service is an important optimization problem that often arises in vehicle routing. The problem arises in the distribution of commodities from a central facility to a set of geographically distributed locations. Each location has a certain demand, the distribution vehicle has a load capacity, and the entire operation should be completed within a certain time. An outside carrier is available for direct service of locations from the central facility. The problem is to determine a feasible tour for the company vehicle and the locations to be served by the outside carrier such that the total cost of the operations is minimized. We model this problem and develop a solution technique using valid inequalities. A key feature of the solution approach is that it can easily be extended to solve similar problems with any type and number of side constraints as encountered in the current model. The algorithm has been extensively tested and computational results for problems having up to 200 locations are presented. The results show that the proposed approach is efficient and viable for solving problems of medium to large size. We also present a real-world application, and show how the model is implemented within the framework of an order scheduling and vehicle routing system. We present performance results with real-world data and demonstrate the operational efficiency achieved by using the proposed approach. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Hulls and Efficient Sets for the Rectilinear Norm
Authors: Chhajed Dilip , Chandru Vijay 
Published: October 2008

Given a set of points on the plane, we study the structure of their rectilinear hull. We also consider the multiple objective decision of identifying a facility location that minimizes the rectilinear distance to each of these points. We show specific correspondences between the efficient (non-dominated) solutions to the location problem and the rectilinear hulls of point sets in the plane. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Disjoint Paths in the Plane
Authors: Liebling Th. M. , Margot F. , Müller D. , Prodon A. , Stauffer L. 
Published: October 2008

Given n pairs of points in the Euclidean plane, we address the problem of finding paths of minimum length linking the pairs that can be made disjoint by infinitesimal deformations. We present and compare several fast heuristics and their implementation. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Stability of p-Persistent CSMA/CD
Authors: Park June S. , Bartoszyński Robert , Rosenkrantz Walter A. 
Published: October 2008

A semi-Markovian model is developed for slotted p-persistent CSMA/CD with a finite population of buffered users. A subsequence of the queuing process at embedded Markov epochs is characterized as a multidimensional, nonnegative random walk which is spatially homogeneous and uniformly downward bounded. Sufficient conditions for ergodicity, recurrence and transience of the queuing process are obtained using multidimensional Lyapunov functions, and also by a supermartingale method of independent interest. For the CSMA/CD system with symmetric users, the stability conditions are evaluated in parameters based on an exact joint probability generating function of the random drift. Important properties of the queuing behavior and stability conditions are uncovered through a numerical analysis. In passing, we remark on queuing properties and stability conditions of slotted ALOHA for comparison with the CSMA/CD. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.