bluuebunny/crossref_metadata_2025_split huggingface dataset:
Generating Markov-Chain Transitions Quickly: I
Authors: Fox Bennett L. 
Published: October 2008

We give a way to generate transitions directly from a compact representation of the generator of a continuous-time Markov chain corresponding to a class that includes many queueing networks and reliability problems. Under specified conditions, this is (provably) faster than generating these transitions via a future-event schedule. Under weaker (specified) conditions, a variant is never slower but, when the original conditions hold, will be faster. This increases efficiency of certain simulations by an order of magnitude. We show that the acceptance-complement method is not competitive in our context. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Parallel Solution of Sparse One-Dimensional Dynamic Programming Problems
Authors: Nicol David M. 
Published: October 2008

Parallel computation offers the potential for quickly solving large computational problems. However, it is often a non-trivial task to effectively use parallel computers. Solution methods must sometimes be reformulated to exploit parallelism; the reformulations are often more complex than their slower serial counterparts. We illustrate these points by studying the parallelization of sparse one-dimensional dynamic programming problems, those which do not obviously admit substantial parallelization. We propose a new method for parallelizing such problems, develop analytic models which help us to identify problems which parallelize well, and compare the performance of our algorithm with existing algorithms on a multiprocessor. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Manipulation and Visualization of Sparse Matrices
Authors: Alvarado Fernando L. 
Published: October 2008

An open architecture software environment for handling sparse matrices and interchanging sparse matrix data is proposed. The proposed educational and research environment includes tools for the visualization of sparse matrices. A prototype implementation of these ideas called the Sparse Matrix Manipulation System is described. Two applications of these ideas are illustrated. The first application is to a comparative study of linear least squares methods, the second to the graphic description of the properties of partitioned sparse A−1 methods. The proposed system is built around three concepts: matrices, permutation vectors and partition vectors. Each concept is implemented as a stream of ASCII data. These streams are operated upon by filters (commands that accept data from standard input and direct output to standard output). Examples of commands include: permutations, addition of fills, factorization, computation of condition number and many others. Other commands generate sparse matrices and display topology maps and factorization path trees. This system permits interchanging information among programs written by different programmers, in different languages, possibly in different computers at different sites. The linear least squares example not only illustrates a practical use of the system, but underscores in a graphic manner the advantage of blocking algorithms to improve computational requirements and condition numbers in linear least squares problems. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Computing Steady-State Probabilities of a Nonpreemptive Priority Multiserver Queue
Authors: Kao Edward P. C. , Narayanan Kumar S. 
Published: October 2008

We consider a nonpreemptive priority exponential queue with multiple servers and two classes of customers—each with its own arrival and service rates. Our focus is on the computation of steady-state probabilities for problems in which the marginal distribution for the number of high priority customers in the system has a short tail. The model is formulated as a quasi-birth-and-death process and is solved by applying several variants of state reduction. The variants are designed to reduce the computation and storage requirements for handling problems of moderate size. A few numerical-examples are given at the end. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Decomposition Strategy for Global Optimum Search in the Pooling Problem
Authors: Floudas Christodoulos A. , Aggarwal Avanish 
Published: October 2008

Modeling of refinery and petrochemical processes that involve pooling of streams often results in nonconvex nonlinear relationships. In a number of cases these nonlinearities can make it difficult to determine the global optimum. A new search technique is presented in this paper that involves the decomposition of the original nonconvex problem into two specially structured subproblems. A series of these subproblems is then solved in an attempt to determine the global optimum. Suitable transformations can be combined with a judicious decomposition scheme leading to subproblems which can attain their respective global optimum solutions at each iteration. The effectiveness of the proposed approach is demonstrated using two small examples of the pooling problem proposed by C. A. Haverly in 1978 and one larger separation/blending/pooling problem. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Robustness of Rootfinding in Single-Server Queueing Models
Authors: Chaudhry Mohan L. , Harris Carl M. , Marchal William G. 
Published: October 2008

There has been frequent controversy over the years regarding the use of numerical rootfinding for the solution of queueing problems. It has been said that such problems quite often present computational difficulties. However, it turns out that rootfinding in queueing is so well structured that problems rarely occur. There are fundamental properties possessed by the well-known queueing models that eliminate classical rootfinding problems. Most importantly, we show that distinctness of roots is common within simply determined regions in the complex plane and provide conditions under which the characteristic equations for the G/EK/1 and EK/G/1 models have easily found, distinct roots. Furthermore, we show that the characteristic equation for the more general G/GEK/1 model has a collection of real and complex roots which are effectively distinct and located in clearly defined regions of the complex domain. Extensive computational results are given to support our contentions. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Model Libraries: Knowledge Representation and Reasoning
Authors: Mannino Michael V. , Greenberg Betsy S. , Hong Sa Neung 
Published: October 2008

We propose a knowledge representation and operators for large, diverse model libraries. The knowledge representation distinguishes between model types that are classes of models defined by a collection of assumptions and model templates and instances that instantiate model types through decomposition and specialization of components. Underlying the knowledge representation are inheritance to represent the level of generalization and multiple levels of instantiation to represent the level of details among models. For inheritance, we define partial order relations for models and their components including domains, classes, units, assumptions, metrics, and constraints. For instantiation, we define constraints on transformations between model types, templates, and instances. The inexact search operators support content-based retrieval especially when it is difficult for a user to exactly specify the characteristics of models of interest. The operators use similarity functions to measure the closeness of a match between a search atom and the value of a model attribute. The explanation operators are designed to enhance users' understanding about the symbols, assumptions, components, and relationships among models. A prototype system has been implemented in Prolog to demonstrate the essential features of the model library system. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Further Development of a Primal-Dual Interior Point Method
Authors: Choi In Chan , Monma Clyde L. , Shanno David F. 
Published: October 2008

The paper continues the development of a primal-dual interior point algorithm for linear programming. The topics studied include simple bounds on primal variables, incorporation of Lustig's phase 1 algorithm and the use of Schur complements to handle dense columns. Extensive numerical results demonstrate the efficiency of the resulting algorithm. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Knowledge Modularization for Adaptive Decision Modeling
Authors: Chakravarty Amiya K. , Sinha Diptendu 
Published: October 2008

Existing research has shown that theorem proving techniques of predicate calculus can be used as effective tools for query resolution in decision support systems. Implementation of these techniques however require searching large axiom sets leading to dead ends and backtracking. In this paper we use a mathematical programming approach to partition axiom sets into modules for efficient query resolution. The method is based on a two-stage analysis of the domain specific knowledge regarding queries types. The first stage analyzes the queries to determine the information requirement on the axiom set. The second stage determines the optimal modularization of the axiom set using this information. The advantage of our approach is that by selecting the appropriate modules for query resolution only a subset of axioms are considered in the resolution process. This approach works significantly better than the traditional methods when the axiom set can be partitioned into non-overlapping modules based on the commonality of a given query set. In the case of module overlap, the math program assigns the axioms to one of the overlapping modules maximizing overall query resolution efficiency of the system. An adaptive component performs dynamic reorganization of the modules when the query set is time variant. Real time issues of query resolution with modularized axiom set are briefly discussed. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
An Algorithm for Network Reliability Bounds
Authors: Yang Che-Liang , Kubat Peter 
Published: October 2008

We provide a new algorithm for assessing network reliability (and performability, the more general case). As in some well-known approaches, the algorithm identifies most probable states in iterations and provides converging upper and lower bounds after each iteration. The algorithm distinguishes itself by providing superior bounds after the same number of iterations. In some instances, the algorithm can even find the exact reliability in a small number of iterations. The time complexity for each iteration, excluding the time for computing the performance value of a generated state, is only O(n) (where n is the number of components), which is the same as any existing optimal algorithm for enumerating most probable states. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Book Reviews
Authors: Saltzman Matthew J. , McCurley Kevin S. 
Published: October 2008

Review of: Nielsen, Jakob (ed.) (1989) Coordinating User Interfaces for Consistency, Academic Press, San Diego, CA. Reviewed by: Matthew J. Saltzman. Review of: Wolfram, Stephen (1988) Mathematica: A System for Doing Mathematics by Computer, Addison Wesley Publishing Co., Redwood City, CA. Reviewed by: Kevin S. McCurley. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Approximation of Some Markov-Modulated Poisson Processes
Authors: Sitaraman H. 
Published: October 2008

The Markov-modulated Poisson process (MMPP) is a doubly stochastic Poisson process in which the arrival rate varies according to a finite state irreducible Markov process. In many applications of MMPPs, the point process is constructed by superpositions or similar constructions, which lead to modulating Markov processes with a large state space. Since this limits the feasibility of numerical computations, it is important to approximate an MMPP represented by a large Markov process by one with fewer states. In particular, we focus attention on approximating a simple but useful special case of the MMPP, the Birth and Death Modulated Poisson process. At the validation stage, the quality of the approximation is examined in relation to the MMPP/G/1 queue. The aggregation algorithm is the main contribution of this paper; it has applications in analyzing the performance of a statistical multiplexer for which the input is the superposition of packetized voice processes. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Mass Production Technique to Speed Multiple-Query Optimization and Physical Database Design
Authors: Helman Paul , Rosenthal Arnon 
Published: October 2008

The logic of many query optimizers corresponds to searching a graph that contains all alternative intermediate results considered by the optimizer. We consider the problem, “Given a query Q, determine the cost of a best strategy that uses intermediate result v to compute Q, assuming that v is available at no cost.” Our main result is an algorithm that mass-produces such cost information for all intermediates v considered by the query optimizer, in time linear in the size of the graph. To illustrate potential applications for the algorithm, we describe rules for identifying and eliminating suboptimal alternatives in multiple query optimization and demonstrate how the algorithm rapidly computes the necessary cost bounds. We also describe applications of the algorithm to speeding physical database design. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Parallel Implementation of Lemke's Algorithm on the Hypercube
Authors: De Leone Renato , Ow Terence T.-H. 
Published: October 2008

A simple but very effective method for parallelizing Lemke's algorithm for the solution of linear complementarity problems is presented. Implementation details on a 32-node Intel iPSC/2 hypercube for problems of dimension up to 1000 are discussed. A speedup efficiency as high as 76% is achieved with 32 processing nodes for a problem with 500 variables and 250,000 nonzero elements. By combining the effects of concurrency and vectorization the computing time on the Intel iPSC/2 in some cases is reduced by a factor of 100. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Improving LP-Representations of Zero-One Linear Programs for Branch-and-Cut
Authors: Hoffman Karla L. , Padberg Manfred 
Published: October 2008

We present various techniques for automatically improving the LP-representation of general zero-one linear programming problems. These include detection of redundant rows and blatant infeasibilities, coefficient reduction using the Euclidean algorithm, optimality fixing and variable elimination. Extensions to the case where special-ordered-set constraints are present are discussed as well. A summary of the branch-and-cut approach to general zero-one problems (including flowcharts) is given. We report numerical experiments to test the effect of such preprocessing within a branch-and-cut algorithm for eleven large-scale real-world zero-one linear-programming problems. An illustrative example is included in the Appendix. 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 the Job-Shop Scheduling Problem
Authors: Applegate David , Cook William 
Published: October 2008

The job-shop scheduling problem is a notoriously difficult problem in combinatorial optimization. Although even modest sized instances remain computationally intractable, a number of important algorithmic advances have been made in recent years by J. Adams, E. Balas and D. Zawack; J. Carlier and E. Pinson; B. J. Lageweg, J. K. Lenstra and A. H. G. Rinnooy Kan; and others. Making use of a number of these advances, we have designed and implemented a new heuristic procedure for finding schedules, a cutting-plane method for obtaining lower bounds, and a combinatorial branch and bound algorithm. Our optimization procedure, combining the heuristic method and the combinatorial branch and bound algorithm, solved the well-known 10×10 problem of J. F. Muth and G. L. Thomson in under 7 minutes of computation time on a Sun Sparcstation 1. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Technical Note—Least-Squares Image Registration
Authors: Zikan Karel 
Published: October 2008

Two-dimensional image registration estimates how one set of k 2-dimensional points is rotated, scaled, and translated into a second set of 2-dimensional points. We give an exact algorithm to solve the “least-squares” formulation of the problem. On average, the algorithm requires k2 pivots; it can be viewed as a refinement of the O(k3) approximation method proposed by K. Zikan and T. M. Silberberg. The approach can be extended to the registration of images of different cardinalities. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
SOFTWARE SECTION—RANDMOD: A System for Randomizing Modifications to an Instance of a Linear Program
Authors: Greenberg Harvey J. 
Published: October 2008

RANDMOD is an interactive system to perform controlled randomization on an linear programming model. Its purpose is to enable statistical analysis of algorithm performance or model robustness while preserving structural realism of the underlying model. The basic operations are augmentation, perturbation, scaling and sign reversal. In addition, RANDMOD provides interactive query, session control and interfaces with other systems. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Performance Characteristics of the Jacobi and the Gauss-Seidel Versions of the Auction Algorithm on the Alliant FX/8
Authors: Kempka David N. , Kennington Jeffery L. , Zaki Hossam A. 
Published: October 2008

Recently, D. Bertsekas proposed a new method to solve the linear assignment problem that appears to be well suited for concurrent computation. The method, called the auction algorithm is a primal-dual iterative scheme that updates the dual solution by performing coordinate steps similar to those of the Jacobi and Gauss-Seidel (GS) methods for unconstrained optimization. Bertsekas noted that the GS version tends to converge a little faster on uniprocessor computers but is generally much less parallelizable. Consequently, several questions arise regarding the relative performance of these two versions: How will their performances be affected by changes in problem size, cost range, and problem data? How should one design an efficient implementation for each version that takes full advantage of novel computer hardware capabilities such as concurrency and vectorization? How does the concurrency of computations affect the sensitivity of the solution times to changes in the cost range for each version? Will Jacobi outperform Gauss-Seidel in a vector-concurrent computational environment? In this paper we address these questions and present insightful algorithmic and empirical comparisons between the two versions. Both versions have been tested on 224 randomly generated dense assignment problems with the number of variables ranging from 10,000 to 16 million and with cost ranges of [0, 10], [0, 100], [0, 1,000], and [0, 10,000]. The vector-concurrent computational environment used in this study is the one available on the Alliant FX/8 at Argonne National Laboratory. In our computational experiments the Jacobi version has exhibited higher speedups, less sensitivity to changes in cost ranges, and better solution times in vector-concurrent mode for cost ranges [0, 1,000] and [0,10,000]. However, for cost range [0, 100] the GS version can be up to five times faster and solved the one million variable problem in less than one second and the 16 million variable problem, in less than 7 seconds. In addition, the results of our experiments support the conjecture that the performance of both versions of the auction algorithm improves dramatically when the ratio of the problem size to the cost range is greater than a certain constant that is shown to be 6 for cost range [0, 100] and 8 for cost range [0, 50]. We also show that the variability in solution times due to changes in the cost range is moderated when the vector-concurrent capabilities of the Alliant FX/8 are invoked. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Using State Reduction for Computing Steady State Probabilities of Queues of GI/PH/1 Types
Authors: Kao Edward P. C. 
Published: October 2008

This paper presents two state reduction based algorithms for computing steady state probabilities of the embedded Markov chains of GI/PH/1 types of queues. The first algorithm generalizes the phase-substitution approach proposed by E.P.C. Kao and C. Lin for QBD (quasi-birth-and-death process) types of queues. The second one uses the general ideas proposed by Grassmann and Heyman in their new state reduction procedure. We show both algorithms are quite efficient for solving GI/PH/1 types of queues. We give two numerical examples at the end. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Product Automaton Formalism for Hierarchical, Modular, Discrete Simulation
Authors: Portier Frederick J. , Haymond Robert E. 
Published: October 2008

A formalism for discrete simulation allows one to specify a discrete simulation model in an unambiguous, mathematically precise manner. The DEVSM formalism, developed by B. Zeigler, is a well-known example. In this paper, we present a formalism that is very much related to the DEVSM formalism, the PA formalism. The most significant difference between the two approaches is the world view adopted by each of the formalisms. In the DEVSM case, components experience internal and external state transitions. Interaction is accomplished by the sending of signals from component to component; basically, a network view of the world. The PA formalism views the world as a hierarchy of components, each of which can experience conditional and unconditional state transitions. Interaction between components is accomplished through the coordinated passing of inputs down the hierarchy, an intrinsically top-down view of the world. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.