bluuebunny/crossref_metadata_2025 huggingface dataset:
A Virtual Clustering Approach for Routing Problems in Telecommunication Networks
Authors: Bartolacci Michael R. , Wu S. David
Published: October 2008

We propose an adaptable routing scheme for telecommunication networks based on the notion of virtual clustering. Virtual clustering logically reconfigures the network topology in a periodic basis according to the traffic requirements in the network. This temporary topology configuration imposes restrictions on the potential paths between certain groups of source—destination node pairs, thus regulating and balancing the global network traffic while maintaining sufficient local flexibility for real-time routing. The proposed routing scheme can be implemented in an established telecommunication environment where the actual routing of network traffic is conducted by an existing dynamic routing algorithm, while the routing tables are preprocessed by the current virtual clustering configuration. We develop a virtual clustering algorithm using problem space search proposed by Storer, Wu and Vaccari (1992. New Search Spaces for Sequencing Problems with Applications to Job Shop Schedule, Management Science 38, 1495–1509; 1996. Local Search in Problem and Heuristic Space for Job Shop Scheduling, ORSA Journal on Computing 7, 453–465). The algorithm iteratively evaluates clustering solutions and its potential impact to routing performance by perturbation of the traffic requirement matrix. The proposed routing scheme is tested through intensive computational experiments on randomly generated geometric networks, and on PREPNET, a real-world subnetwork on the Internet. Using Monte Carlo simulation, we compare the proposed routing scheme to centralized routing and decentralized asynchronous routing. Computational results show that the proposed approach significantly outperforms these traditional schemes under dynamic traffic fluctuation.
On the Application of Explanation-Based Learning to Acquire Control Knowledge for Branch and Bound Algorithms
Authors: Realff Matthew J. , Stephanopoulos George
Published: October 2008

The goal of this article is to present a methodology for the automatic acquisition of new control knowledge in the form of dominance and equivalence conditions, using an explanation-based learning algorithm from artificial intelligence. The acquisition of new control knowledge proceeds through the following stages: 1) Analysis of the problem-solving activity, generated from the application of a branch and bound algorithm on specific instance(s) of a class of problems. 2) Interpretation of the problem-solving activity and synthesis of new control knowledge, which can lead to more efficient solution of future problems. The generated control knowledge is provably correct within the theory of the given class of problems and the employed branch and bound strategy. Consequently, the number of nodes evaluated by a specific branch and bound algorithm is guaranteed to be reduced, as new control knowledge is continuously acquired from the solution of specific problems. The article presents the theoretical foundations for the handling of the above two tasks. It concludes with an application of the proposed approach to a mixed integer linear programming formulation of a batch scheduling problem.
Complexity of Simulation Models: A Graph Theoretic Approach
Authors: Yücesan Enver , Schruben Lee
Published: October 2008

In this article, we introduce complexity measures for simulation models. The framework of simulation graphs sets the context. A quantifiable measure of complexity is useful in an a priori evaluation of proposed simulation studies that must be completed within a specified budget. They can also be useful in classifying simulation models to obtain a thorough test bed of models to be used in simulation methodology research. The metrics introduced in this article have a rigorous theoretical, as well as empirical, grounding in software engineering. As such, simulation modeling and analysis represent a new area of application. Some surrogate measures of run time complexity are also developed. In particular, we provide estimates for the size of the future events list (or the pending event set). The proposed metrics are illustrated and compared through a limited set of examples. Limitations of the current approach as well as directions for future research are discussed.
Solving the Orienteering Problem through Branch-and-Cut
Authors: Fischetti Matteo , González Juan José Salazar , Toth Paolo
Published: October 2008

In the Orienteering Problem (OP), we are given an undirected graph with edge weights and node prizes. The problem calls for a simple cycle whose total edge weight does not exceed a given threshold, while visiting a subset of nodes with maximum total prize. This NP-hard problem arises in routing and scheduling applications. We describe a branch-and-cut algorithm for finding an optimal OP solution. The algorithm is based on several families of valid inequalities. We also introduce a family of cuts, called conditional cuts, which can cut off the optimal OP solution, and propose an effective way to use them within the overall branch-and-cut framework. Exact and heuristic separation algorithms are described, as well as heuristic procedures to produce near-optimal OP solutions. An extensive computational analysis on several classes of both real-world and random instances is reported. The algorithm proved to be able to solve to optimality large-scale instances involving up to 500 nodes, within acceptable computing time. This compares favorably with previous published methods.
Variance Reduction and Objective Function Evaluation in Stochastic Linear Programs
Authors: Higle Julia L.
Published: October 2008

Planning under uncertainty requires the explicit representation of uncertain quantities within an underlying decision model. When the underlying model is a linear program, the representation of certain data elements as random variables results in a stochastic linear program (SLP). Precise evaluation of an SLP objective function requires the solution of a large number of linear programs, one for each possible combination of the random variables' outcomes. To reduce the effort required to evaluate the objective function, approximations, especially those derived from randomly sampled data, are often used. In this article, we explore a variety of variance-reduction techniques that can be used to improve the quality of the objective-function approximations derived from sampled data. These techniques are presented within the context of SLP objective-function evaluations. Computational results offering an empirical comparison of the level of variance reduction afforded by the various methods are included.
Connections Between Integer Linear Programming and Constraint Logic Programming—An Overview and Introduction to the Cluster of Articles
Authors: Williams H. Paul , Wilson John M.
Published: October 2008

The fields of integer linear programming and constraint logic programming have developed from different standpoints in mathematics and operations research, but offer synergy. This article will briefly review some aspects of their separate development that give rise to connections between the two fields and will describe some of these connections which appear to have potential for harnessing and for future research. The article will then introduce the other four articles in this cluster, which further explore and develop these interconnections.
Properties of Some Combinatorial Optimization Problems and Their Effect on the Performance of Integer Programming and Constraint Logic Programming
Authors: Darby-Dowman Ken , Little James
Published: October 2008

The comparative performance of Integer Programming (IP) and Constraint Logic Programming (CLP) is explored by examining a number of models for four different combinatorial optimization applications. Computational results show contrasting behavior for the two approaches, and an analysis of performance with respect to problem and model characteristics is presented. The analysis shows that tightness of formulation is of great benefit to CLP where effective search reduction results in problems that can be solved quickly. In IP, if the linear feasible region does not identify the corresponding integer polytope, the problem may be difficult to solve. The paper identifies other characteristics of model behavior and concludes by examining ways in which IP and CLP may be incorporated within hybrid solvers.
Interval Protection of Confidential Information in a Database
Authors: Gopal Ram D. , Goes Paulo B. , Garfinkel Robert S.
Published: October 2008

We deal with the question of how to maintain security of confidential information in a database while answering as many queries as possible. The database is assumed to operate in a query restriction (as opposed to perturbation) mode in which exact answers are given to those queries which, together with those already answered, will not compromise any confidential datum. Those which fail this criterion are not answered. We introduce the concept of interval disclosure where a datum is compromised if the answered queries provide enough information to establish that it is contained in a given interval even if the datum cannot be determined exactly. Models are presented for the problem of deciding whether to answer a query and three techniques, one based on linear programming, are developed and tested.
An Algorithm for Identifying the Frame of a Pointed Finite Conical Hull
Authors: Dulá J. H. , Helgason R. V. , Venugopal N.
Published: October 2008

We present an algorithm for identifying the extreme rays of the conical hull of a finite set of vectors whose generated cone is pointed. This problem appears in diverse areas including stochastic programming, computational geometry, and non-parametric efficiency measurement. The standard approach consists of solving a linear program for every element of the set of vectors. The new algorithm differs in that it solves fewer and substantially smaller LPs. Extensive computational testing validates the algorithm and demonstrates that for a wide range of problems it is computationally superior to the standard approach.
Feature Article—The World Wide Web: Opportunities for Operations Research and Management Science
Authors: Bhargava Hemant K. , Krishnan Ramayya
Published: October 2008

The World Wide Web has already affected OR/MS work in a significant way, and holds great potential for changing the nature of OR/MS products and the OR/MS software economy. Web technologies are relevant to OR/MS work in two ways. First, the Web is a multimedia communication system. Originally based on an information pull model, it is—critically for OR/MS—being extended for information push as well. Second, it is a large distributed computing environment in which OR/MS products—interactive computational applications—can be made available, and interacted with, over a global network. Enabling technologies for Web-based execution of OR/MS applications are classified into those involving client-side execution and server-side execution. Methods for combining multiple client-side and server-side technologies are critical to OR/MS's use of these technologies. These methods, and various emerging technologies for developing computational applications, give the OR/MS worker a rich armament for building Web-based versions of conventional applications. They also enable a new class of distributed applications working on real-time data. Web technologies are expected to encourage the development of OR/MS products as specialized component applications that can be bundled to solve real-world problems. Effective exploitation, for OR/MS purposes, of these technological innovations will also require initiatives, changes, and greater involvement by OR/MS organizations.
Commentary—Dynamic, Distributed, Platform Independent OR/MS Applications—A Network Perspective
Authors: Bradley Gordon H. , Buss Arnold H.
Published: October 2008

We are in the midst of, or perhaps at the beginning of, the development of a new concept of computing and computers that will significantly affect OR/MS. This development is summarized in the phrase “the network is the computer.” The focus and use is not an individual computer and its resources but a network of computers and resources, indeed, a network of all computers. This concept is closely tied to an evolving view about what a computer is; we now have an exploding number of ubiquitous devices with computational capacity, such as credit cards, cellular phones, and TV set-top boxes. We need to anticipate the impact of millions and then billions of programmable devices that are interconnected on a high bandwidth network accessible by millions and then billions of individuals. The sudden and fast moving development of computer networks and the wide distribution of powerful computing devices is revolutionizing not just OR/MS, but commerce, communications, and indeed, nearly all aspects of society.
Commentary—Predictions for Web Technologies in Optimization
Authors: Fourer Robert
Published: October 2008

In surveying the World Wide Web's potential in operations research and management science, Bhargava and Krishnan (H. K. Bhargava and R. Krishnan. The World Wide Web: Opportunities for Operations Research and Management Science. INFORMS Journal on Computing, Vol. 10, No. 4, 359–383, 1988) often use examples of applications in optimization or mathematical programming to explain connections between advances in optimization and in computer science.
Commentary—A New Horizon for OR/MS
Authors: Geoffrion Arthur M.
Published: October 2008

Commentary to the article by Bhargava and Krishnan (H. K. Bhargava and R. Krishnan. The World Wide Web: Opportunities for Operations Research and Management Science. INFORMS Journal of Computing, Vol. 10, No. 4, 359–383, 1988). The Web may prove to be the most important marriage of communications and computation yet devised by man. The average Web-user is likely to be most conscious of the communications aspect. The point is in emphasizing the aspect of the advantages to be gained by distributed implementation of OR/MS applications: It empowers dispersed practitioners and enables embedded applications.
]ary—The World Wide Web: It's the Customers
Authors: Trick Michael
Published: October 2008

The feature article by Bhargava and Krishnan does a wonderful job of outlining the current state of the Web and its future possibilities. The Web is an active and ever-changing place; providing a snapshot of the state of the art is not easy. In this commentary, I would like to concentrate on a group that the article does not cover in depth: the users of OR/MS. The number of users of OR/MS is vastly larger than the producers of OR/MS, and has been affected perhaps even more by the Web. I will concentrate on two types of users: those who do not know what OR/MS is but have found our community through the Web, and our students.
A Branch and Bound Algorithm for the Stability Number of a Sparse Graph
Authors: Sewell E. C.
Published: October 2008

We present a branch and bound algorithm for finding a maximum stable set in a graph. The algorithm uses properties of the stable set polytope to construct strong upper bounds. Specifically, it uses cliques, odd cycles, and a maximum matching on the remaining nodes. The cliques are generated via standard coloring heuristics, and the odd cycles are generated from blossoms found by a matching algorithm. We report computational experience on two classes of randomly generated graphs and on the DIMACS Challenge Benchmark graphs. These experiments indicate that the algorithm is quite effective, particularly for sparse graphs.
Appreciation to Referees
Authors: Golden Bruce L.
Published: October 2008

On behalf of the Editorial Board, Bruce L. Golden, Editor-in-Chief thanks the individuals listed for having acted as referees for papers considered for publication during 1998.
Packet Routing in Telecommunication Networks with Path and Flow Restrictions
Authors: LeBlanc Larry J. , Chifflet Jerome , Mahey Philippe
Published: October 2008

We address packet-switched telecommunication networks, including ATM, SMDS, and X.25 services. We analyze important extensions of routing models by imposing restrictions on paths and flows. We then study how these modifications affect the computational requirements for solution. The restricted cases we examine are: 1) hop limits—the flow between each pair of nodes can take a maximum of h hops; 2) node and link capacity constraints—instead of traditional queuing delays, queuing is treated indirectly using penalty terms for “effective” capacity constraints; and 3) high- and low-priority flows—because of higher grade-of-service requirements for high-priority flows, additional capacity constraints are imposed on them. We discuss the importance of these restrictions and report results of computational testing using the flow-deviation algorithm. We also discuss the importance of limiting the number of routes used between node pairs and then analyze numerically how many distinct routes are typically used by the final solution from the flow-deviation algorithm when no route limits exist between node pairs.
Improved Constructive Multistart Strategies for the Quadratic Assignment Problem Using Adaptive Memory
Authors: Fleurent Charles , Glover Fred
Published: October 2008

Multistart constructive approaches operate by applying a local search procedure to start from different initial solutions produced by a repeated (variable) constructive process. The classical Random Restart procedure and the more recent GRASP procedure are prominent examples of such approaches. Adaptive memory strategies that are the heart of tabu search methods give a foundation for alternative, enhanced, multistart approaches. We demonstrate this by showing that a simple implementation of adaptive memory search principles, even when restricted to the constructive phases, can provide more effective multistart methods. Computational experiments for the quadratic assignment problem disclose that these methods improve significantly over previous multistart methods that do not incorporate such memory based strategies.
A Class of Hard Small 0-1 Programs
Authors: Cornuéjols Gérard , Dawande Milind
Published: October 2008

In this article, we consider a class of 0-1 programs that, although innocent looking, is a challenge for existing solution methods. Solving even small instances from this class is extremely difficult for conventional branch-and-bound or branch-and-cut algorithms. We also experimented with basis reduction algorithms and with dynamic programming without much success. The article then examines the performance of two other methods: a group relaxation for 0,1 programs, and a sorting-based procedure following an idea of Wolsey. Although the results with these two methods are somewhat better than with the other four when it comes to checking feasibility, we offer this class of small 0,1 programs as a challenge to the research community.
Optimizing Expert Systems: Heuristics for Efficiently Generating Low-Cost Information Acquisition Strategies
Authors: Mannino Michael V. , Mookerjee Vijay S.
Published: October 2008

We study the sequential information acquisition problem for rule-based expert systems as follows: find the information acquisition strategy that minimizes the expected cost to operate the system while maintaining the same output decisions. This problem arises for rule-based expert systems when the cost or time to collect inputs is significant and the inputs are not known until the system operates. We develop several “optimistic” heuristics to generate information acquisition strategies and study their properties. The heuristics provide choices concerning precision (i.e., how optimistic) versus computational effort. The heuristics are embedded into an informed search algorithm (based on AO*) that produces an optimal strategy and a greedy search algorithm. The search strategies are designed for situations in which rules can overlap and the cost of collecting an input may depend on the set of inputs previously collected. We study the properties of these approaches and simulate their performance on a variety of synthetic expert systems. Our results indicate that the heuristics are very precise, leading to near optimal results for greedy search and moderate search effort for optimal search.
Computing Laplace Transforms for Numerical Inversion Via Continued Fractions
Authors: Abate Joseph , Whitt Ward
Published: October 2008

It is often possible to effectively calculate probability density functions (pdf's) and cumulative distribution functions (cdf's) by numerically inverting Laplace transforms. However, to do so it is necessary to compute the Laplace transform values. Unfortunately, convenient explicit expressions for required transforms are often unavailable for component pdf's in a probability model. In that event, we show that it is sometimes possible to find continued-fraction representations for required Laplace transforms that can serve as a basis for computing the transform values needed in the inversion algorithm. This property is very likely to prevail for completely monotone pdf's, because their Laplace transforms have special continued fractions called S fractions, which have desirable convergence properties. We illustrate the approach by considering applications to compute first-passage-time cdf's in birth-and-death processes and various cdf's with non-exponential tails, which can be used to model service-time cdf's in queueing models. Included among these cdf's is the Pareto cdf.
Tabu Search—Part II
Authors: Glover Fred
Published: October 2008

This is the second half of a two part series devoted to the tabu search metastrategy for optimization problems. Part I introduced the fundamental ideas of tabu search as an approach for guiding other heuristics to overcome the limitations of local optimality, both in a deterministic and a probabilistic framework. Part I also reported successful applications from a wide range of settings, in which tabu search frequently made it possible to obtain higher quality solutions than previously obtained with competing strategies, generally with less computational effort. Part II, in this issue, examines refinements and more advanced aspects of tabu search. Following a brief review of notation, Part II introduces new dynamic strategies for managing tabu lists, allowing fuller exploitation of underlying evaluation functions. In turn, the elements of staged search and structured move sets are characterized, which bear on the issue of finiteness. Three ways of applying tabu search to the solution of integer programming problems are then described, providing connections also to certain nonlinear programming applications. Finally, the paper concludes with a brief survey of new applications of tabu search that have occurred since the developments reported in Part I. Together with additional comparisons with other methods on a wide body of problems, these include results of parallel processing implementations and the use of tabu search in settings ranging from telecommunications to neural networks.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Reliability Computations for Planar Networks
Authors: Whited David E. , Shier Douglas R. , Jarvis James P.
Published: October 2008

The two-terminal reliability problem for an undirected network involves calculating the probability that two distinguished sites are connected by a path of working edges. This problem is known to be NP-hard, even for the special case of planar systems. We present efficient data structures and algorithms for manipulating planar networks and for generating both paths an cutsets in such networks. A pseudopolynomial algorithm is then implemented, based on these generation procedures, to calculate two-terminal reliability for planar networks; that is, the algorithm's time complexity is polynomially bounded in the number of paths (or the number of cutsets). Computational experience with this implementation is also presented, showing that it provides a substantial improvement over previous implementations of the pseudopolynomial algorithm.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Worst-Case Analysis of Heuristics for Multidepot Capacitated Vehicle Routing Problems
Authors: Li Chung-Lun , Simchi-Levi David
Published: October 2008

We consider the multidepot capacitated vehicle routing problems and analyze the tour partitioning heuristics for different versions of the model. We prove that the worst-case ratios of the heuristics are bounded by some fixed numbers. Examples are provided to show that the worst-case bounds are tight or asymptotically tight for almost all versions.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Matrix Visualization in the Design of Numerical Algorithms
Authors: Tuchman Allan M. , Berry Michael W.
Published: October 2008

At the heart of much scientific computing are the algorithmic kernels often found in numerical software libraries. Numerical analysts and algorithm designers can be aided by various software tools in the design of their algorithms. We present a tool for matrix visualization and its application in the design and development of numerical algorithms for supercomputers. We discuss the development of the tool as an object-oriented distributed system and show examples of its use, including applications in linear algebra and performance monitoring. By using color computer graphics, one can gain insights into algorithm behavior, which can then be used to design more efficient numerical algorithms. In particular, we present a case study of the application of data structure visualization in the development of hybrid parallel algorithms for the singular value decomposition.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Neural Network Implementation of a Data Association Algorithm
Authors: Barker Allen L. , Brown Donald E. , Martin Worthy N.
Published: October 2008

In this paper we are concerned with a time varying set of entities located in a fixed field. These entities are sensed at discrete time instances with a single sensor modality. At a given time instant a collection of bivariate Gaussian sensor reports is produced, estimating the locations of a subset of the entities present in the field. A database of reports is maintained which should ideally contain exactly one report for each entity that has been sensed. Whenever a collection of sensor reports is received the database must be updated to reflect the new information. This updating requires correspondence processing between the database reports and the new sensor reports to determine which pairs of sensor and database reports correspond to the same entity. We present an algorithm for performing this correspondence processing under the assumptions that each new collection of sensor reports contains at most one report for any entity, and that the database can be reasonably assumed to contain at most one report for any entity. This algorithm is based on pairwise distance measures between Gaussian distributions. We consider several such distance measures, and present simulation results indicating that the divergence is a reasonable choice. A formulation of the divergence between two bivariate Gaussians as a scalar product is given. We describe a neural network implementation of our algorithm, along with a proof that the network will converge and, under certain restrictions, exactly compute our correspondence algorithm.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Matrix Balancing on a Massively Parallel Connection Machine
Authors: Zenios Stavros A.
Published: October 2008

Matrix balancing models find applications in economics, transportation, regional sciences, statistics, stochastic modeling and other areas. The iterative scaling algorithm RAS that is used for the solution of these problems is shown here to be suitable for data level parallelism on the Connection Machine (CM). We develop synchronous and asynchronous parallel versions of RAS and discuss designs for implementation of both dense and sparse problems on the CM. We report numerical experiences with matrices of dimension up to 1000 × 1000 and 990000 nonzero entries. Problems of this size are solved within seconds on a Connection Machine model CM-2 with 32K processing elements, and the algorithm achieves peak rate of computing in excess of 300μFLOPS.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
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.