bluuebunny/crossref_metadata_2025_split huggingface dataset:
Modeling Networks with Dynamic Topologies
Authors: Moose Robert L. 
Published: October 2008

Dynamic hierarchical networks represent an architectural strategy for employing adaptive behavior in applications sensitive to highly variable external demands or uncertain internal conditions. The characteristics of such architectures are described, and the significance of adaptive capability is discussed. The necessity for assessing cost/benefit tradeoffs leads to the use of queueing network models. The general model, a network of M/M/1 queues in a random environment, is introduced and then is simplified so that the links may be treated as isolated M/M/1 queues in a random environment. This treatment yields a formula for approximate mean network delay by combining matrix-geometric results (mean queue length and mean delay) for the individual links. A discrete event simulation model is defined as a basis for cross-validation of the analytic model. Conditions under which the analytic model is considered valid are identified through comparison of the two models. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Continuous Models for Capacity Design of Large Packet-Switched Telecommunication Networks
Authors: LeBlanc Larry J. , Simmons Ronald V. 
Published: October 2008

We formulate nonlinear programming models for design of large-scale packet-switched telecommunication networks. In these models, the network’s link capacities and source-destination message routes are chosen simultaneously. Although leased communication lines are available only in discrete units of capacity, public telephone lines with high-speed modems can be used to augment them, thus effectively obtaining fractional equivalents of leased-line capacity. Therefore, our network-design models contain continuous link-capacity variables. These continuous models can be solved for ϵ-optimal solutions, even for networks with hundreds or thousands of nodes. We examine conventional link delay functions used by previous researchers and suggest an alternative class of convex delay functions. Using computer simulation to analyze link delays, we compare the convex delay function to the conventional one. We conclude, for our assumed message-length distribution, that the convex delay function predicts the simulated delays more accurately than the conventional one when flow-capacity ratios larger than or equal to 0.80 are ignored. However, the conventional delay function fits the simulated delays more accurately than the convex one when these high-congestion ratios are considered. Thus, in network-design models in which flow-capacity ratios must be less than 80%, our convex model can be more accurate than the nonconvex conventional one. Computational results show that our models give very good solutions for different size networks with up to 100 nodes. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Editor's Introduction
Authors: Greenberg Harvey J. 
Published: October 2008

Dedication to deceased distinguished leaders in the field: Darwin D. Klingman and William Orchard-Hays. Brief overview of papers published in the issue. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Identifying Minimally Infeasible Subsystems of Inequalities
Authors: Gleeson John , Ryan Jennifer 
Published: October 2008

Given an infeasible system of linear inequalities, we show that the problem of identifying all minimally infeasible subsystems can be reduced to the problem of finding all vertices of a related polyhedron. This results in a shorter enumeration than that performed by previous method to solve this problem. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
On Valuation and Optimization Problems in Fuzzy Graphs: A General Approach and Some Particular Cases
Authors: Delgado Miguel , Verdegay Jose L. , Vila Maria-Amparo 
Published: October 2008

This deals with the problem of valuation and optimization in fuzzy graphs in a general manner. Valuations are defined as functions depending on membership levels. A general solution procedure is developed for optimization problems on the basis of α-cut representation. Finally, this procedure is applied to a classical problem: to find the minimal path in a fuzzy graph. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
An Introduction to Graph-Based Modeling Systems, Part I: Overview
Authors: Jones Christopher V. 
Published: October 2008

Attributed graphs are a widely used paradigm for representing management science models. Examples include vehicle routing, production planning, simulation and decision trees. With the proliferation of computer graphics, direct manipulation interfaces have been created for many of these models. Although such systems can facilitate modeling and analysis, they generally prove quite expensive to develop. Since all of these models can be represented using an attributed graph, one can exploit that commonality to develop tools and techniques to facilitate developing computer graphics interfaces for such models. This paper discusses the concept of such a graph-based modeling system (GBMS) and a prototype implementation (Networks) that facilitates the creation of computer graphics interfaces for models that can be represented as attributed graphs. This study is divided into two parts; part I presents an overall introduction to the concepts; part II will discuss these concepts in detail. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Using Simulated Annealing to Solve Controlled Rounding Problems
Authors: Kelly James , Golden Bruce , Assad Arjang 
Published: October 2008

Controlled rounding is a procedure whereby tabular data gathered from respondents is perturbed in such a way as to preserve the anonymity of the respondents while maintaining the integrity of the data. This paper describes an algorithm for solving three-dimensional controlled rounding problems which is based on simulated annealing, linear programming, and binary search procedures. Numerical results obtained from processing 32,500 randomly generated tables and 292 real-life tables have demonstrated that this algorithm can efficiently find controlled roundings, provided they exist. The algorithm is significantly faster than any previously known solution procedure for this class of problems. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Backbone Network Design Tools with Economic Tradeoffs
Authors: Gavish Bezalel , Altinkemer Kemal 
Published: October 2008

This paper studies the problem of assigning capacities to the links in a backbone network and determining the primary routes used by messages for each origin-destination communicating pair in the network. The topology of the backbone network is assumed to be known and the end to end traffic requirements are given. The problem is to find the least cost design where the system costs are composed of connection costs which depend on link capacities and queueing costs which are incurred by users due to the limited capacities of links. The goal is to determine the routing and link capacities simultaneously. The problem is formulated and lower bounds are obtained by Lagrangean relaxation embedded in a subgradient optimization procedure. Cut constraints which are redundant in the original formulation are introduced, they improve the lower bounds. A heuristic method based on the Lagrangean solution is described. Extensive computational results are reported. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Path Planning in 0/1/∞ Weighted Regions with Applications
Authors: Gewali Laxmi P. , Meng Alex C. , Mitchell Joseph S. B. , Ntafos Simeon 
Published: October 2008

We consider the terrain navigation problem in a two-dimensional polygonal subdivision with three types of regions: obstacles, “free” regions (in which one can travel at no cost), and regions in which cost is proportional to distance traveled. We present an algorithm whose running time is O(E + nlog n), where n is the number of vertices representing the subdivision, and E is bounded above by the size of the visibility graph induced by the set of obstacles and free regions, which is no worse than quadratic (O(n2)). In addition, we present algorithms to solve a variety of important generalizations and applications: (1) an O(n2) algorithm for constructing a critical graph of size O(n2) (which can be searched in time O(n2log n) for shortest paths) for the case in which linear features (roads) are added, thereby allowing arbitrary weights on the edges of the subdivision; (2) similar time bounds for the case in which the linear features include a possible “cost of crossing”; (3) an O(n2W) algorithm for finding lexicographically shortest paths in weighted regions (with W different weights); (4) an O(k2n2) algorithm for planning least-risk paths in a simple polygon that contains k line-of-sight threats (this becomes O(k4n4) in polygons with holes); and (5) an O(k2n3) algorithm for finding least-risk watchman routes in simple rectilinear polygons (a watchman route is such that each point in the polygon is visible from at least one point along the route). INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Computing Sparse LU Factorizations for Large-Scale Linear Programming Bases
Authors: Suhl Uwe H. , Suhl Leena M. 
Published: October 2008

This paper discusses the computation of LU factorizations for large sparse matrices with emphasis on large-scale linear programming bases. We present new implementation techniques which reduce the computation times significantly. Numerical experiments with large-scale real life test problems were conducted. The software is compared with the basis factorization of MPSX/370, IBM's commercial LP system. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Discrete Event Simulation Model Decomposition by Principal Components Analysis
Authors: Bauer Kenneth W. , Kochar Bipin , Talavage Joseph J. 
Published: October 2008

A solution is offered to the simulation model decomposition problem. Discrete-event simulation models as described by condition specifications (CS) are cast as cluster interaction graphs (CIGs). These CIGs are analyzed using rotated principal component solutions. The loading patterns of these solutions provide a suggested decomposition. The method is demonstrated on a small CS of a harbor simulation model, as well as a larger CS of a flexible manufacturing system (FMS) simulation. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
On Finding Primal- and Dual-Optimal Bases
Authors: Megiddo Nimrod 
Published: October 2008

We show that if there exists a strongly polynomial time algorithm that finds a basis which is optimal for both the primal and the dual problems, given an optimal solution for one of the problems, then there exists a strongly polynomial algorithm for the general linear programming problem. On the other hand, we give a strongly polynomial time algorithm that finds such a basis, given any pair of optimal solutions (not necessarily basic) for the primal and the dual problems. Such an algorithm is needed when one is using an interior point method and is interested in finding a basis which is both primal- and dual-optimal. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Unique Names Violations, a Problem for Model Integration or You Say Tomato, I Say Tomahto
Authors: Bhargava Hemant K. , Kimbrough Steven O. , Krishnan Ramayya 
Published: October 2008

The tomato-tomahto problem (known as the synonymy problem in the database literature) arises in the context of model management when different names are used in different models for what should be identical variables, and these different models are to be integrated or combined into a larger model. When this problem occurs, it is said that the unique names assumption has been violated. We propose a method by which violations of the unique names assumption can be automatically detected. The method relies on declaring four kinds of information and modeling variables: dimensional information, laws relating dimensional expressions, information (called the quiddity) about the intended interpretation of the variables, and laws relating quiddity expressions. We present and discuss the method and the principles and theory behind it, and we describe our (prototype) implementation of the method, as an additional function of an existing model management system. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Locating Minimal Infeasible Constraint Sets in Linear Programs
Authors: Chinneck John W. , Dravnieks Erik W. 
Published: October 2008

With ongoing advances in hardware and software, the bottleneck in linear programming is no longer a model solution, it is the correct formulation of large models in the first place. During initial formulation (or modification), a very large model may prove infeasible, but it is often difficult to determine how to correct it. We present a formulation aid which analyzes infeasible LPs and identifies minimal sets of inconsistent constraints from among the perhaps very large set of constraints defining the problem. This information helps to focus the search for a diagnosis of the problem, speeding the repair of the model. We present a series of filtering routines and a final integrated algorithm which guarantees the identification of at least one minimal set of inconsistent constraints. This guarantee is a significant advantage over previous methods. The algorithms are simple, relatively efficient, and easily incorporated into standard LP solvers. Preliminary computational results are reported. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Book Review
Authors: Ryan Jennifer 
Published: October 2008

Review of: D. E. Goldberg, 1989. Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading, MA. Reviewed by: Jennifer Ryan. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Optimal Partial-Match Hashing Design
Authors: Jagannathan Raj 
Published: October 2008

This paper suggests a method for determining an optimal hashing design for answering a partial-match query. Solution methods are suggested for the knapsack-type model, derived under the assumption that the attributes in a query are specified independently. It is further shown that the same nonlinear knapsack-type model holds even when the independence assumption is relaxed. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Pruning Procedure for Exact Graph Coloring
Authors: Sager Thomas J. , Lin Shi-Jen 
Published: October 2008

The graph coloring problem can be stated: “Given an undirected graph, using a minimal number of colors, assign each vertex a color so that if two vertices are connected by an edge then they are not assigned the same color.” Graph coloring can be used to solve scheduling problems with constraints of the form: events e and e' cannot be scheduled together. Graph coloring is an NP-hard problem. Generally, large problems are solved heuristically, although some of the better heuristic algorithms use an exact graph coloring algorithm to finish coloring a graph after first reducing it heuristically to manageable size. Exact graph coloring is important both in its own right and as a component of heuristic coloring. We present an improved exact graph coloring algorithm which runs, in the mean, over 20% faster than the DSATUR algorithm on some classes of random graphs. The improvement over DSATUR stems from the ability to prune the search tree by detecting, in certain instances, the existence of a complete subgraph of cardinality equal to the number of colors used in the best coloring found so far. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Approaches to Diagnosing Infeasible Linear Programs
Authors: Greenberg Harvey J. , Murphy Frederic H. 
Published: October 2008

This paper addresses the problem of diagnosing an infeasible linear program. In practice, there are several approaches one may take, most generally using the Phase I dual variables as an initial guide. Other approaches, however, have emerged to complement the traditional ones. These and new approaches are presented here with the aim of building a toolkit for automatic reasoning when an LP expert is not available. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Bounding Synchronization Overhead for Parallel Iteration
Authors: Downey Peter J. 
Published: October 2008

Suppose m stochastically identical iterative processes are run in parallel. Each iteration of the process runs for a random time X, distributed identically and independently for each iteration. At the end of each iteration, each process checks a shared variable to see whether some global event has occurred; if it has, the process terminates and instantly joins a rendezvous with the other processes that have detected the event. The synchronization overhead is the time R(m)(t) needed to complete the rendezvous, measured from the time t of occurrence of the event (t is assumed to be independent of the m processes). It is not true (for general X) that ER(m)(t)≤EX, because t will more probably occur during a long iteration than a short one, and because R(m)(t) is an extreme value of a sample of size m. In renewal theory the random variable R(1)(t) is called the excess at t, and R(m)(t) will be the extreme of m i.i.d. excesses. While exact expressions for ER(m)(t) are impossible to obtain in practice, we give useful upper bounds. The bounds get tighter depending on information known about the underlying distribution of X. Results include: (1) a general bound valid for any X having finite third moment, (2) a better bound valid if X is dominated by an exponential in stochastic variability ordering, (3) an even better bound if X has bounded mean residual life, and (4) a bound valid when X has decreasing failure rate. The results are applied to searching a table in parallel and to on-line makespan scheduling. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
TES: A Class of Methods for Generating Autocorrelated Uniform Variates
Authors: Melamed Benjamin 
Published: October 2008

This paper introduces a class of methods called TES (Transform-Expand-Sample) for generating autocorrelated variates with uniform marginals and Markovian structure. TES methods are readily implemented on a computer and have generation complexity comparable to that of the i.i.d. uniform sequence which they transform to an autocorrelated uniform sequence. For any prescribed correlation coefficient ρ, there is a TES method generating a uniform sequence with the 1-lag autocorrelation ρ, and the resultant autocorrelation is monotonic quadratic in two structural TES parameters. A simulation study reveals that TES methods give rise to autocorrelation functions with monotone decreasing as well as oscillating magnitude, bounded by monotone envelopes. The structural parameters were found to control the “amplitude” and “frequency” of the resultant autocorrelation function. A third parameter can be used to transform a TES sequence into more continuous-looking versions and to control the skewness of sample path cycles. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Linear Discriminant Functions Determined by Genetic Search
Authors: Koehler Gary J. 
Published: October 2008

This paper studies a genetic algorithm that determines linear discriminant functions. The objective is to minimize the number of misclassifications and then to minimize the number of used attributes. The algorithm produces results that are significantly better than Fisher's method for minimizing the probability of misclassification but not significantly different than those that exactly minimize the number of misclassifications. The algorithm has the added benefit that the solutions obtained are more parsimonious than these exact algorithms since two objectives could be considered simultaneously. In our empirical studies, the algorithm routinely found the optimal solution while taking significantly less time than exact algorithms which must both find and prove optimality. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Preprocessing in Stochastic Programming: The Case of Linear Programs
Authors: Wallace Stein W. , Wets Roger J-B. 
Published: October 2008

The purpose of this paper is to investigate different preprocessing procedures for stochastic linear programs. The procedures are meant to be of use mostly for the modeler, but there are important computational implications as well. We discuss how to check if the problem under investigation is overspecified, i.e have options (columns) that can never be in an optimal solution, if the problem is tight or loose in terms of feasibility, and we demonstrate how to achieve relatively complete recourse in a number of cases. Computational results are detailed. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
The Vehicle Routing Problem with Time Windows: Minimizing Route Duration
Authors: Savelsbergh Martin W. P. 
Published: October 2008

We investigate the implementation of edge-exchange improvement methods for the vehicle routing problem with time windows with minimization of route duration as the objective. The presence of time windows as well as the chosen objective cause verification of the feasibility and profitability of a single edge-exchange to require an amount of computing time that is linear in the number of vertices. We show how this effort can, on the average, be reduced to a constant. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
The Ca/M/s/m Retrial Queue: A Computational Approach
Authors: Yang Tao , Posner Morton J. M. , Templeton James G. C. 
Published: October 2008

This paper considers a service station consisting of s identical, independent exponential servers and m buffers. Customers arrive according to a Coxian process with a stages. Blocked customers may either leave the system forever or return, after an exponentially distributed amount of time, to the service station to retry for services. An efficient algorithm is developed to evaluate system steady-state probabilities, and formulas for certain system performance measures are derived in terms of the steady-state probabilities. The computational complexity of the algorithm is shown to be O(4N), where N is the total number of state probabilities evaluated. The influence of the form of interarrival time distributions on system performance measures is examined through numerical results. Issues concerning numerical stability of the algorithm are also discussed. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.