bluuebunny/crossref_metadata_2025_split huggingface dataset:
Feature Article—Parallel Discrete Event Simulation: Will the Field Survive?
Authors: Fujimoto Richard M. 
Published: October 2008

Despite over a decade and a half of research and several successes, technologies to use parallel computers to speed up the execution of discrete event simulation programs have not had a significant impact in the general simulation community. Unless new inroads are made in reducing the effort and expertise required to develop efficient parallel simulation models, the field will continue to have limited application, and will remain a specialized technique used by only a handful of researchers. The future success, or failure, of the parallel discrete event simulation field hinges on the extent to which this problem can be addressed. Moreover, failure to meet this challenge will ultimately limit the effectiveness of discrete event simulation, in general, as a tool for analyzing and understanding large-scale systems. Basic underlying principles and techniques that are used in parallel discrete event simulation are briefly reviewed. Taking a retrospective look at the field, several successes and failures in utilizing this technology are discussed. It is noted that past research has not paid adequate attention to the problem of developing simulation models for efficient parallel execution, highlighting the need for future research to pay more attention to this problem. A variety of approaches to make parallel discrete event simulation an effective tool are discussed. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Feature Article—Interior Point Methods for Linear Programming: Computational State of the Art
Authors: Lustig Irvin J. , Marsten Roy E. , Shanno David F. 
Published: October 2008

A survey of the significant developments in the field of interior point methods for linear programming is presented, beginning with Karmarkar's projective algorithm and concentrating on the many variants that can be derived from logarithmic barrier methods. Full implementation details of the primal-dual predictor-corrector code OB1 are given, including preprocessing, matrix orderings, and matrix factorization techniques. A computational comparison of OB1 with a state-of-the-art simplex code using eight large models is given. In addition, computational results are presented where OB1 is used to solve two very large models that have never been solved by any simplex code INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Commentary—Theory and Practice for Interior-Point Methods
Authors: Todd Michael J. 
Published: October 2008

The last decade has been a fascinating time for researchers interested in linear programming and its extensions. It opened with Narendra Karmarkar's theoretical paper on the computational complexity of linear programming problems and his claims that his method solved problems 50 times faster than the simplex method. After 10 years of development in both interior-point and simplex methods, we are now at a point at which both approaches can handle problems that seemed intractable before, but where interior-point methods seem to be superior to simplex algorithms for many very large-scale sparse linear programming problems. Lustig, Marsten, and Shanno (LMS) provide an excellent overview of these advances, particularly with respect to their computational significance. Of course, they have been major contributors to the development of interior-point algorithms as well as of sophisticated implementations with their OB1 code. Their experience leads to many interesting insights and also raises some questions: why does the primal-dual method allow such long steps (99.95% of the way to the whereas primal or dual affine-scaling methods seem limited to, say, 95%)? Do the primal and dual “help each other?” And why does the primal-dual affine-scaling algorithm perform poorly, while even tiny centering components render it highly efficient? In these remarks I want to try to indicate the interplay between theory and computational practice, highlight theoretical developments with (potentially) important consequences and point out some major remaining tasks. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Commentary—Interior-Point Methods: Algorithms and Formulations
Authors: Vanderbei Robert J. 
Published: October 2008

The paper by Lustig, Marsten, and Shanno (LMS) gives an excellent presentation of the current state of the art for interior-point methods (as represented by their OB1 code) as it compares to the current state of the art for the simplex method (represented by OSL). The paper is well organized and thoughtful. The results of their experiments clearly indicate that for large problems interior-point methods offer a serious alternative to the simplex method. In these comments, we will try to clarify the relation among some of the algorithms discussed in LMS. In addition, we will compare the implementation strategy described in LMS, which is based on solving the so-called normal equations, to an alternative implementation strategy based on solving the so-called reduced Karush-Kuhn-Tucker (KKT) system. We will show that for many problems the two approaches yield virtually identical results but, for certain classes of challenging problems, the reduced KKT approach yields a much more efficient code. Also, we will argue that the reduced KKT system approach is more easily extended to quadratic and convex optimization problems. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Complexity of Hierarchical Trees in Evidence Theory
Authors: Dugat Vincent , Sandri Sandra 
Published: October 2008

In this article we propose a structure called hierarchical tree to reduce the complexity of the Dempster's rule of combination in evidence theory. Our algorithm is bounded by O(22n−2) in the worst case versus O(22n) for the brute-force algorithm. We can hope for a better average complexity. Furthermore, we propose algorithms based on hierarchical trees to reduce the complexity of the computation of Bel, Pl and Q functions. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Primary and Secondary Route Selection in Backbone Computer Networks
Authors: Pirkul Hasan , Narasimhan Sridhar 
Published: October 2008

This paper addresses the problem of selecting primary and secondary routes for every pair of communicating nodes in a backbone computer network. A primary route and a secondary route constitute a route pair. The secondary route is node-disjoint (and hence also link-disjoint) from the primary route. A mathematical programming model is developed whose objective is to select routes to minimize the mean delay faced by messages. The model captures situations where a single link or node failure would divert traffic to the appropriate secondary routes. A solution procedure based on a relaxation of the problem is presented. Computational results indicate the effectiveness of the solution procedure. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Tabu Search for General Zero-One Integer Programs Using the Pivot and Complement Heuristic
Authors: Aboudi Ronny , Jörnsten Kurt 
Published: October 2008

Tabu search techniques have been applied to a wide class of optimization problems. Tabu search is a meta procedure that requires a subroutine to find local optima. In most examples of tabu search the subroutine used is problem specific. However, in order to apply tabu search successfully to general 0-1 integer programs, the subroutine must be general. The pivot and complement heuristic is a procedure that frequently finds feasible solutions for general 0-1 integer programs. In this paper we implement several elements of strategies proposed by tabu search method that result in general heuristics for 0-1 integer programs that could be included in an integer programming code. These heuristics employ the ZOOM/XMP implementation of the pivot and complement heuristic as a subroutine. Computational results indicate that these heuristics provide good bounds for many problems. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Numerical Factorization Methods for Interior Point Algorithms
Authors: Jung Ho-Won , Marsten Roy E. , Saltzman Matthew J. 
Published: October 2008

Interior point algorithms for linear programming achieve significant reductions in computer time over earlier methods for many large linear programming problems (LPs) and solve problems larger than previously possible. The most computationally intensive step in each iteration of any interior point algorithm is the numerical factorization of a sparse, symmetric, positive definite matrix. In large or relatively dense problems, 80–90% or more of computational time is spent in this step. This study describes our implementations of two algorithms for performing this factorization, the column Cholesky and the multifrontal methods, based on graph theory applied to sparse symmetric matrices. We use advanced techniques such as loop unrolling and equivalent sparse matrix reordering to improve the performance of the factorization step. Our studies are incorporated into an implementation of the primal-dual barrier algorithm. Computational experiments on relatively large LPs on a DEC station 3100 demonstrate that the primal-dual barrier algorithm using our advanced column Cholesky outperforms by 20–60% the same algorithm using a straightforward column Cholesky. Also, our multifrontal method using the loop unrolling technique in a partial inner product routine shows a 10–50% speedup compared with no loop unrolling. The two methods exhibit comparable overall performance. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
The Reactive Tabu Search
Authors: Battiti Roberto , Tecchiolli Giampietro 
Published: October 2008

We propose an algorithm for combinatorial optimization where an explicit check for the repetition of configurations is added to the basic scheme of Tabu search. In our Tabu scheme the appropriate size of the list is learned in an automated way by reacting to the occurrence of cycles. In addition, if the search appears to be repeating an excessive number of solutions excessively often, then the search is diversified by making a number of random moves proportional to a moving average of the cycle length. The reactive scheme is compared to a “strict” Tabu scheme that forbids the repetition of configurations and to schemes with a fixed or randomly varying list size. From the implementation point of view we show that the Hashing or Digital Tree techniques can be used in order to search for repetitions in a time that is approximately constant. We present the results obtained for a series of computational tests on a benchmark function, on the 0-1 Knapsack Problem, and on the Quadratic Assignment Problem. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Genetic Algorithms and Random Keys for Sequencing and Optimization
Authors: Bean James C. 
Published: October 2008

In this paper we present a general genetic algorithm to address a wide variety of sequencing and optimization problems including multiple machine scheduling, resource allocation, and the quadratic assignment problem. When addressing such problems, genetic algorithms typically have difficulty maintaining feasibility from parent to offspring. This is overcome with a robust representation technique called random keys. Computational results are shown for multiple machine scheduling, resource allocation, and quadratic assignment problems. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
On Exploiting Original Problem Data in the Inverse Representation of Linear Programming Bases
Authors: Gondzio Jacek 
Published: October 2008

A method for handling the inverse of linear programming bases is presented. The method extensively exploits the fact that the original problem data (i.e., the constraint matrix) must be stored anyway. It then builds the basis inverse representation of two matrices: an easily invertible submatrix of the constraint matrix (fundamental basis) and a Schur complement containing information on the difference between the fundamental and the current bases. Since the fundamental basis does not have to be stored, the memory space required by the method is limited to that for a small, dense Schur complement. Computational comparisons are made with advanced implementations of LU factorizations with Bartels-Golub updating. Tests performed on real-life linear programs from the Netlib collection indicate that the method may be used for solving large problems. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
CONOPT—A Large-Scale GRG Code
Authors: Drud Arne Stolbjerg 
Published: October 2008

CONOPT is a generalized reduced-gradient (GRG) algorithm for solving large-scale nonlinear programs involving sparse nonlinear constraints. The paper will discuss strategic and tactical decisions in the development, upgrade, and maintenance of CONOPT over the last 8 years. A verbal and intuitive comparison of the GRG algorithm with the popular methods based on sequential linearized subproblems forms the basis for discussions of the implementation of critical components in a GRG code: basis factorizations, search directions, line-searches, and Newton iterations. The paper contains performance statistics for a range of models from different branches of engineering and economics of up to 4000 equations with comparative figures for MINOS version 5.3. Based on these statistics the paper concludes that GRG codes can be very competitive with other codes for large-scale nonlinear programming from both an efficiency and a reliability point of view. This is especially true for models with fairly nonlinear constraints, particularly when it is difficult to attain feasibility. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Commentary—Visualization and Optimization: The Future Lies Together
Authors: Bell Peter C. 
Published: October 2008

Visualization and optimization are complementary approaches to problem solving, not rivals: a future involving closer integration promises to benefit both areas and to stimulate their development. Jones' important and extensive feature article highlights progress being made on many different dimensions from the perspective of the researcher and scholar. A recent paper by Greenberg[4] augments Jones' article. In order to provide a contrasting view with the objective of stimulating further debate and hopefully some new research, I will try to present the perspective of an important set of “customers” for optimization: senior decision makers who use optimization in solving important problems. After presenting a view of problem solving using optimization, I will attempt to make the case that visualization is very important to the future of optimization, and that the emergence of visualization presents important opportunities for further developments within optimization. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Consistency in Valuation-Based Systems
Authors: Shenoy Prakash P. 
Published: October 2008

This paper has three main results. First, we present a new computational technique for checking for inconsistencies in valuation-based systems. This technique is different from the implicit enumeration method of Davis-Putnam and its variants. Our technique uses the divide-and-conquer method of dynamic programming. The computational complexity of this technique depends on the sizes of the valuations and on the graphical structure of the valuation-based system. Second, if a valuation-based system is consistent, we describe a method for generating a model for the system, i.e., an assignment of values for each variable that is consistent with each valuation in the system. Third, if a valuation-based system is inconsistent, we describe a method for isolating a minimal inconsistent set of valuations. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Newton Based Radius Reduction Algorithm for Nearest Point Problems in Pos Cones
Authors: Al-Sultan Khaled S. 
Published: October 2008

We develop an interior point algorithm for finding the nearest point in Pos cones to a given point in Rn. The algorithm is based on constructing a sequence of spheres of reduced radii that intersect the cone until a sphere that just touches the cone is found in which case the problem is solved. Implementation of the algorithm and some preliminary computational experience are presented. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Numerical Method for Controlled Routing in Large Trunk Line Networks via Stochastic Control Theory
Authors: Kushner Harold J. , Yang Jichuan 
Published: October 2008

The paper discusses a powerful approach to the routing problem in large networks of the trunk line type. The approximations are based on heavy traffic limit theorems. The sequence of suitably scaled available circuits converges to a reflected diffusion process as the network size grows, under reasonable conditions. This limit model contains the basic features of the original network, and provides a very useful basis for a good control strategy for the physical system. The optimal ergodic cost problem for a three (link) dimensional system is solved numerically via the Markov chain approximation method to get the optimal controls. These “three link” results can be approximated in such a way that they can be applied to a physical network of arbitrary size, using only “local” information. Indeed, the numerical approximations have the interpretation of a type of simplified or “aggregated” network, which allows the use of physical intuition in its application. The resulting polities are compared in simulations (on systems with hundreds of links) to other current approaches, and found to be quite competitive and have many advantages. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Perspectives on Simulation Research and Practice
Authors: Kelton W. David 
Published: October 2008

This paper discusses recent developments in simulation research, current directions, as well as how research interacts with practice and software development. Among the methodological research areas considered are modeling techniques, generation of random numbers and processes, and statistical design and analysis. Projections for future research are made, and ways in which practice can both benefit from research as well as help guide it are discussed. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Structured Expert System for Model Management in Inventory Control
Authors: Ghiaseddin Nasir , Matta Khalil , Sinha Diptendu 
Published: October 2008

The focus of this paper is on the expert system design for inventory control model management. The model selection procedure uses the knowledge of inventory theory as well as user-specific heuristics and approximation rules. The models available in the model base are represented in a model selection tree using information currently present in the inventory control literature. We explore the use of a structured design methodology through incorporating knowledge modules (i.e., sub-expert system) at the nodes of the model selection tree. The knowledge base is also modularized into selection, application, and solution knowledge bases in addition to a database, each with its unique and independent set of rules and/or storage requirements. This structured design reduces the knowledge representation complexity, facilitates the search process and allows for the use of backtracking procedures to select approximate models for the problem. Implementation of the system using the expert system shell GURU is discussed and sample consultation is provided 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 Satisfiability Algorithms for Propositional Logic
Authors: Harche F. , Hooker J. N. , Thompson G. L. 
Published: October 2008

We implement several recent algorithms for the satisfiabiiity problem in propositional logic and test them on a wide variety of benchmark problems. We focus on algorithms based on some kind of tree search, including three versions of the classical Davis-Putnam-Loveland method, the method of Jeroslow and Wang, the Horn Relaxation method of Gallo and Urbani, the branch and cut method of Hooker and Fedjki, and the column subtraction method of Harche and Thompson. We design experiments so as to identify the important factors that influence the performance of tree search algorithms. We find that the choice of which variable to branch on is a key factor. Methods based on weak relaxations (e.g., Horn relaxation) are best for easy problems, and the column subtraction method is clearly the most robust, as it was the only algorithm to solve the hardest problems. if Davis-Putnam-Loveland is properly implemented, it and the remaining methods generally excel on problems that are neither too easy nor too hard. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
An EP Algorithm for Computing a Minimum Weight Perfect Matching for a Set of Points on the Plane
Authors: Osiakwan Constantine K. N. , Akl Selim G. 
Published: October 2008

Given a graph induced by an even number of points on the plane, the minimum weight matching problem calls for finding a pairing of all the points such that the sum of the distances between the paired points is the smallest possible. In this paper, we propose a parallel algorithm for this problem. The algorithm is designed for the EREW PRAM model of parallel computation with p processors. For points on the Euclidean and manhattan planes, the algorithm executes in O((n2.5log4n)/p) time, where p ≤ n0.5. The algorithm provides an optimal speedup with respect to the fastest existing sequential algorithm. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Preprocessing and Probing Techniques for Mixed Integer Programming Problems
Authors: Savelsbergh M. W. P. 
Published: October 2008

In the first part of the paper, we present a framework for describing basic techniques to improve the representation of a mixed integer programming problem. We elaborate on identification of infeasibility and redundancy, improvement of bounds and coefficients, and fixing of binary variables. In the second part of the paper, we discuss recent extensions to these basic techniques and elaborate on the investigation and possible uses of logical consequences. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.