bluuebunny/crossref_metadata_2025 huggingface dataset:
Performance Characteristics of the Jacobi and the Gauss-Seidel Versions of the Auction Algorithm on the Alliant FX/8
Authors: Kempka David N. , Kennington Jeffery L. , Zaki Hossam A.
Published: October 2008

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

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Using State Reduction for Computing Steady State Probabilities of Queues of GI/PH/1 Types
Authors: Kao Edward P. C.
Published: October 2008

This paper presents two state reduction based algorithms for computing steady state probabilities of the embedded Markov chains of GI/PH/1 types of queues. The first algorithm generalizes the phase-substitution approach proposed by E.P.C. Kao and C. Lin for QBD (quasi-birth-and-death process) types of queues. The second one uses the general ideas proposed by Grassmann and Heyman in their new state reduction procedure. We show both algorithms are quite efficient for solving GI/PH/1 types of queues. We give two numerical examples at the end.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Product Automaton Formalism for Hierarchical, Modular, Discrete Simulation
Authors: Portier Frederick J. , Haymond Robert E.
Published: October 2008

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

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Optimizing Interconnections of Local Area Networks: An Approach Using Simulated Annealing
Authors: Fetterolf Peter C. , Anandalingam G.
Published: October 2008

The problem of selecting minimum cost topologies for the interconnection of Local Area Networks (LANs) with transparent bridges is addressed. A graph theoretic model for a LAN internetwork is developed and an algorithm for calculating internetwork flows is presented. The flow algorithm accounts for O-D flows due to hosts and overhead flows due to the bridge learning algorithm. Internetwork delays are examined and standard queueing models are used to approximate the delay of a packet traversing multiple LANs and bridges. A mathematical program minimizing system cost subject to internetwork flow constraints and delay constraints is formulated. The resulting optimization problem is a complex nonlinear integer program; it is solved using a simulated annealing heuristic algorithm. Numerical experiments have showed the heuristic to be within 0.8% of the optimum for small problems. For large problems the annealing algorithm is evaluated using a statistical technique and results indicate excellent performance.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Some Convergence Results for Probabilistic Tabu Search
Authors: Faigle Ulrich , Kern Walter
Published: October 2008

During recent years, much work has gone into the exploration of general fundamental principles underlying local search strategies for combinatorial optimization. Many of these strategies can be subsumed under the general framework of Tabu Search, which introduces mechanisms of guidance and control based on flexible memory processes, broadening the range of strategic possibilities beyond those incorporated in memoryless search heuristics such as Simulated Annealing. We consider some examples of such memory based strategies for modifying both the generation and acceptance probabilities and investigate their impact on convergence results. It turns out that several Tabu Search ideas can be subjected to mathematical analyses similar to those applied to Simulated Annealing, making it possible to establish corresponding convergence properties based on a broader foundation.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Matroid Applications and Algorithms
Authors: Lee Jon , Ryan Jennifer
Published: October 2008

Matroid theory provides a set of modeling tools with which many combinatorial and algebraic problems may be treated. Generic algorithms for the resulting matroid problems can be used to solve problems from a variety of application areas including engineering, scheduling, mathematics, and mathematical programming. In this paper, we give an introduction to matroid theory and algorithms, and a survey of algorithmic applications.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Implementations of Affine Scaling Methods: Approximate Solutions of Systems of Linear Equations Using Preconditioned Conjugate Gradient Methods
Authors: Mehrotra Sanjay
Published: October 2008

The conjugate gradient method has been proposed for solving system of linear equations arising at each iteration of interior point methods. This paper studies several problems associated with developing such implementations. This includes development of a termination criteria, computation of an effective preconditioner, and the lack of positive definiteness of the matrix.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Parallel Decomposition of Multicommodity Network Flows Using a Linear-Quadratic Penalty Algorithm
Authors: Pinar Mustafa C. , Zenios Stavros A.
Published: October 2008

The central theme of this paper is the design and evaluation of a parallel decomposition algorithm for multicommodity network flow problems based on the notion of piecewise linear-quadratic penalty (LQP) functions. The algorithm induces separability of both the constraint set and the objective function by commodity during the subproblem phase. Hence it is suitable for implementations on coarse grain parallel architectures. A master problem, of significantly smaller dimension than the original problem, uses dense linear algebra computations. Hence it exploits a vector architecture, but is also suited for parallel implementation and can be executed using Basic Linear Algebra (BLAS) subroutines. Computational results on a CRAY Y-MPE264 supercomputer with a set of large multicommodity network flow problems drawn from a military application are presented and analyzed.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Alternative Approaches to Feasibility in Projective Methods for Linear Programming
Authors: Fraley Chris , Vial Jean-Philippe
Published: October 2008

This paper concerns further developments in primal projective methods based on the potential function of De Ghellinck and Vial. Their method is unique in that feasibility and optimality are approached simultaneously from an interior starting point, without the addition of an artificial variable to handle feasibility, and without penalty or barrier terms. This behavior is obtained by incorporating the infeasibilities within the potential function. The primal algorithm requires an initial optimal objective estimate, and results are given demonstrating sensitivity of its value. We show that, by choosing a different initial search direction, feasibility and optimality can be treated in separate phases. Results are given, indicating that the two-phase method is often superior to the original single-phase method. We also describe a variant that selects the search direction on the basis of potential reduction, and a technique that allows the use of estimates that are not necessarily lower bounds for the optimal objective value.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Simulated Annealing with a Temperature Dependent Penalty Function
Authors: Stern Julio M.
Published: October 2008

We formulate the problem of permuting a matrix to block angular form as the combinatorial minimization of an objective function. We motivate the use of simulated annealing (SA) as an optimization tool. We then introduce a heuristic temperature dependent penalty function in the simulated annealing cost function, to be used instead of the real objective function being minimized. Finally we show that this temperature dependent penalty function version of simulated annealing consistently outperforms the standard simulated annealing approach, producing, with smaller running times, better solutions. We believe that the use of a temperature dependent penalty function may be useful in developing SA algorithms for other combinatorial problems.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Solving the Steiner Tree Problem on a Graph Using Branch and Cut
Authors: Chopra Sunil , Gorres Edgar R. , Rao M. R.
Published: October 2008

In this paper we report computational experience with a branch and cut solver for the Steimer tree problem on a graph. The problem instances include complete graphs, randomly generated sparse graphs and grid graphs. The edge weights are either randomly generated or are the Euclidean distance between the endnodes that are placed at random on the plane. The effect of changing various problem parameters on solution time is studied.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Numerical Experiments with Iteration and Aggregation for Markov Chains
Authors: Stewart William J. , Wu Wei
Published: October 2008

This paper describes an iterative aggregation/disaggregation method for computing the stationary probability vector of a nearly completely decomposable Markov chain. The emphasis is on the implementation of the algorithm and on the results that are obtained when it is applied to three modeling examples that have been used in the analysis of computer/communication systems. Where applicable, a comparison with standard iterative and direct methods for solving the same problems, is made.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Heuristic Algorithm for the Guillotine Constrained Cutting Stock Problem
Authors: Ghandforoush Parviz , Daniels John J.
Published: October 2008

This paper presents a heuristic algorithm, programmed in PROLOG (a rule-based programming language) and run on a personal computer with 4.77 MHz CPU, for determining the packing of identical rectangles (boxes) onto a larger rectangle (pallet) such that the amount of waste is minimized. The algorithm has the additional property of producing solutions which satisfy the guillotine cut constraint. The rule-based approach takes advantage of the recursive and backtracking properties to expedite the matching operations. The algorithm is tested using 7500 randomly generated test cases and is compared to other cutting stock algorithms. Test results for one set of problems indicate that the rule-based method generates layout solutions that are within one box of the optimal solution 85% of the time.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Efficient Algorithms for the Capacitated 1-Median Problem
Authors: ElGindy Hossam , Keil J. Mark
Published: October 2008

The 1-median problem is to locate a service facility so as to minimize the sum of the distances from a given set of demand destinations. In this paper, we develop a data storage scheme which is useful for dealing with sums of rectilinear (L1) distances in space and travel distances along the edges of a tree network. We then use this scheme to provide efficient algorithms to various capacitated 1-median problems.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Monotone Pieces of Chains
Authors: Chandru V. , Rajan V. T. , Swaminathan R.
Published: October 2008

The problem of decomposing a general polygonal chain, open or closed, into a minimum number of monotone subchains is studied in this paper. We show that this geometric optimization problem can be solved in linear time (in the number of edges) by a strategy related to the selection of a minimum cardinality cover of a circle by a subset of its arcs. We also introduce a special class of polygonal chains, called stable configurations. These stable configurations are certificates of when a greedy procedure is guaranteed to be optimal for the monotone chain decomposition problem. The greedy procedure translates to a very simple linear-time algorithm. Further, the presence of the stable-configuration-certificate in any given polygonal chain can also be recognized in linear time.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Commentary—The “Tar Baby” of Computing: Performance Analysis
Authors: Gustafson John L.
Published: October 2008

It looks so easy. To find the speed of a computer, just take a job and time it. To compare two speeds, or try to establish speed in some type of universal unit, well…. Reporting performance is the “tar baby” of computing, and many authors and researchers have attacked this issue only to find themselves stuck in a mess of shaky logic and shakier assumptions. The more scientific one tries to be, the more difficult the problem is. Barr and Hickman have aimed their efforts at this issue, and have generated some thought-provoking ideas.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Feature Article—Reporting Computational Experiments with Parallel Algorithms: Issues, Measures, and Experts' Opinions
Authors: Barr Richard S. , Hickman Betty L.
Published: October 2008

Accompanying the increasing availability of parallel computing technology is a corresponding growth of research into the development, implementation, and testing of parallel algorithms. This paper examines issues involved in reporting on the empirical testing of parallel mathematical programming algorithms, both optimizing and heuristic. We examine the appropriateness of various performance metrics and explore the effects of testing variability, machine influences, testing biases, and the effects of tuning parameters. Some of these difficulties were explored further in a survey sent to leading computational mathematical programming researchers for their reactions and suggestions. A summary of the survey and proposals for conscientious reporting are presented.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Commentary—Parallel Reporting Guidelines Are on Target
Authors: Loshin H. David , Vasilevsky Alex
Published: October 2008

The prevalent theme of Barr and Hickman's article is the multitude of methods for reporting parallel speedup and the difficulty in interpreting results of reported speedup. In fact, the general supercomputing community is plagued by too many terms and phrases for comparing runtime, efficiency, speedup, etc. The authors of the article are very much on target with their observations, as can be demonstrated by a discussion of another metric that is commonly used for comparison of machine performance.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Commentary—Speedups and Insights
Authors: Lusk Ewing L.
Published: October 2008

It is a pleasure to be invited to participate in the discussion of this thoughtful paper, “Reporting Computational Experiments with Parallel Algorithms: Issues, Measures, and Experts' Opinions” by Richard S. Barr and Betty L. Hickman. As one who has published many a table of speedups, I feel very much in the authors' audience, perhaps even in their crosshairs. Their paper focuses attention on an issue faced by every reader as well as writer of articles that report the results of experiments with parallel programs running on real parallel machines. I believe the paper can contribute to more accurate communication in the parallel processing community through a heightened awareness of the issues surrounding reporting of experiments. The survey is a novel addition to the discussion, and seems to indicate that the field's participants are seriously grappling with this problem, although no consensus has developed.

What I hope to contribute here are a few opinions on why there is still a quite legitimate variation in what results are reported and how they are measured and presented, as well as some experiences in my own research that might reinforce some of the conclusions in the paper.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Rejoinder—Using Parallel Empirical Testing to Advance Algorithm Research
Authors: Barr Richard S. , Hickman Betty L.
Published: October 2008

The panel of commentators provided eloquent and insightful comments, which we found to be thoughtful as well as thought-provoking. We welcome this opportunity to respond to their remarks, and to expand on some of the issues that they brought forth. This paper is organized around two topics mentioned by Lusk: (1) the varying purposes of computational testing, and (2) using parallel testing to advance algorithmic research.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Barrier Method for Large-Scale Constrained Optimization
Authors: Nash Stephen G. , Sofer Ariela
Published: October 2008

A logarithmic barrier method is applied to the solution of a nonlinear programming problem with inequality constraints. An approximation to the Newton direction is derived that avoids the ill conditioning normally associated with barrier methods. This approximation can be used within a truncated-Newton method, and hence is suitable for large-scale problems; the approximation can also be used in the context of a parallel algorithm. Enhancements to the basic barrier method are described that improve its efficiency and reliability. The resulting method can be shown to be a primal-dual method when the objective function is convex and all of the constraints are linear. Computational experiments are presented where the method is applied to 1000-variable problems with bound constraints.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Toward a Programming Environment for Combinatorial Optimization: A Case Study Oriented to Max-Flow Computations
Authors: Gallo Giorgio , Scutellà Maria Grazia
Published: October 2008

In this paper, we try to move a few steps toward the definition of a programming environment oriented to the production and updating of algorithms for combinatorial optimization problems. Such an environment contains a certain number of basic blocks (data structures and routines) together with a set of rules for their use, which allow us to assemble the blocks into large and complex algorithmic architectures. The max-flow problem has been chosen for a case study which illustrates the main issues arising in the design of the programming environment. In order to develop such a study, a new general algorithm paradigm for the max-flow problem is proposed, from which most of the known algorithms can be derived by instantiation.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Duality-Based Algorithms for Scheduling Unrelated Parallel Machines
Authors: van de Velde S. L.
Published: October 2008

We consider the following parallel machine scheduling problem. Each of n independent jobs has to be scheduled on one of m unrelated parallel machines. The processing of job Ji on machine Mi requires an uninterrupted period of positive length pij. The objective is to find an assignment of jobs to machines so as to minimize the maximum job completion time. The objective of this paper is to design practical algorithms for this NP-hard problem. We present an optimization algorithm and an approximation algorithm that are both based on surrogate relaxation and duality. The optimization algorithm solves quite large problems within reasonable time limits. The approximation algorithm is based upon a novel concept for iterative local search, in which the search direction is guided by surrogate multipliers.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
An Implementation of the Generalized Basis Reduction Algorithm for Integer Programming
Authors: Cook William , Rutherford Thomas , Scarf Herbert E. , Shallcross David
Published: October 2008

In recent years many advances have been made in solution techniques for specially structured 0–1 integer programming problems. In contrast, very little progress has been made on solving general (mixed) integer problems. This, of course, is not true when viewed from the theoretical side: H. W. Lenstra (1983) made a major breakthrough, obtaining a polynomial-time algorithm when the number of integer variables is fixed. We discuss a practical implementation of a Lenstra-like algorithm, based on the generalized basis reduction method of L. Lovász and H. E. Scarf (1988). This method allows us to avoid the ellipsoidal approximations required in Lenstra's algorithm. We report on the solution of a number of small (but difficult) examples, with up to 100 integer variables. Our computer code uses the linear programming optimizer CPLEX as a subroutine to solve the linear programming problems that arise.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Empirical Studies on the Average Efficiency of Simplex Variants under Rotation Symmetry
Authors: Borgwardt Karl Heinz , Damm Renate , Donig Rudolf , Joas Gabriele
Published: October 2008

In this paper we study the average number of pivot steps required by the simplex algorithm for solving linear programs. For this purpose we perform numerical and empirical tests. The problems are generated randomly according to several rotation symmetric distribution models. We observe the influence of the distributions and the dimension. This evaluation is done for seven different, well known variants of the simplex algorithm. In addition, we test the shadow vertex algorithm. It should be remarked that only the shadow vertex variant and equivalent parametric methods could be analyzed theoretically so far under this or other stochastic models. Here we compare the empirical values with the theoretical bounds.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Graphical Interfaces for Network Modeling: A Model Management System Perspective
Authors: Steiger David , Sharda Ramesh , Leclaire Brian
Published: October 2008

This paper develops, based on the requirements of model management systems, the characteristics of a PC-based, graphical interface for networks which supports all phases of minimum cost flow network model development. The unique characteristics provided by such an interface include: 1) a nonmathematical environment for building network models via direct manipulation of model-specific, rule-based, arc-node icons, 2) the simultaneous display of multiple model views with instantaneous and transparent update of these views, 3) the functional power of modern algebraic modeling languages, and 4) an integrated, pictorial display of model structure, instantiating data and optimal flows for one or more related model instances. In addition, the paper describes a prototype implementation of such an interface. This prototype demonstrates how such a graphical interface system could change the way decision makers and model builders utilize optimization-based decision support models in a microcomputer environment.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Computation of Steady-State Probabilities for Infinite-State Markov Chains with Repeating Rows
Authors: Grassmann Winfried K. , Heyman Daniel P.
Published: October 2008

In this paper we consider Markov chains with these properties. The transition matrix is banded, and except for some boundary conditions, when the transition matrix is written in block form, the rows are identical except for a shift to the right. Some authors have used variants of the state reduction method to solve special cases. We present a general algorithm and some of the theoretical underpinnings of these methods. In particular, we give a rigorous proof of convergence. We also provide a simple method to norm the probabilities such that their sum is unity. We describe the connection between this new technique and the matrix-iterative methods of M. F. Neuts. The paper concludes with some numerical examples.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Applying an Architecture for General Intelligence to Reduce Scheduling Effort
Authors: Prietula Michael J. , Hsu Wen-Ling , Steier David , Newell Allen
Published: October 2008

A system called Merle-Soar is described which demonstrates how a specific architecture for general intelligence and learning (Soar) can be used to reduce scheduling effort when solving simple scheduling problems. In particular, we describe how Merle-Soar schedules sequences of jobs on a single bottleneck machine in a job shop. The knowledge of dispatching, acquired from examining how a human expert performs the task, is cast as search rules. A study was conducted which examined the extent to which learning could contribute to decreases in scheduling effort; specifically, the contribution of learning within-tasks was explored—the change in reasoning effort while solving a particular scheduling problem as knowledge is accumulated from successive trials. The results indicated that dramatic reductions in scheduling effort (in terms of the Soar architecture) were obtained. Knowledge gained early in the scheduling task was subsequently applied later in the task to reduce deliberation, and knowledge gained from one trial successfully reduced deliberation effort in subsequent trials. Additionally, the reduction exhibited the general power law of learning documented in psychological studies of skill acquisition.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A GRG2-Based System for Training Neural Networks: Design and Computational Experience
Authors: Subramanian Venkat , Hung Ming S.
Published: October 2008

Artificial neural networks is a very active area of research in artificial intelligence. They are better than existing methods for many problems in pattern recognition and pattern matching. They are trained through examples rather than being programmed. Training neural networks is a nonlinear minimization problem. The currently popular algorithm for training neural networks is called back-propagation, a form of steepest descent technique. This paper presents a new training system based on GRG2, a widely distributed nonlinear optimization software. Comparisons with back-propagation based upon three benchmark problems suggest not only that the GRG2-based system is much faster, more robust and offers solutions with better quality, but also offers better scalability to larger problems. This paper is thus a clear example of the kinds of contributions that optimization theory can make to artificial intelligence.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Network Reoptimization Algorithms: A Statistically Designed Comparison
Authors: Amini Mohammad M. , Barr Richard S.
Published: October 2008

Statistical design and analysis of experiments is a cornerstone methodology for scientific exploration and verification that is rarely employed in reporting mathematical software testing. This approach is used to study the relative effectiveness of three key algorithms for the reoptimization of network flow problems primal simplex, dual method, and out-of-kilter. Carefully designed experimentation with state-of-the-art codes accompanied by a rigorous statistical analysis isolates the most efficient method(s) for commonly encountered reoptimization problems, and identifies the effect on solution time of problem class, problem size, type of change (bounds, costs, or node requirements), degree and number of changes in parameters, and number of problems in the reoptimization series.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Bayesian Approach to Database Query Optimization
Authors: Seppi Kevin D. , Barnes J. Wesley , Morris Carl N.
Published: October 2008

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

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Error Bound of a Heuristic for the Common Due Date Scheduling Problem
Authors: Liman Surya Danusaputro , Lee Chung-Yee
Published: October 2008

In this paper, a simple heuristic for the n-job, one-machine nonpreemptive scheduling problem of minimizing the sum of absolute deviations of job completion times about a common due date is proposed. The heuristic, which has a complexity of O(n log n), is shown to have a tight relative worst case error bound of 0.5. A practical and systematic guideline for determining the posterior performance of the heuristic is also provided.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Commentary—Progress in Linear Programming
Authors: Bixby Robert E.
Published: October 2008

There is little doubt that barrier methods are now indispensable tools in the solution of large-scale linear programming problems. However, it is our opinion that the results of Lustig, Marsten, and Shanno (hereafter LMS) somewhat overstate the performance of these methods relative to the simplex method. We will present a slightly different view of progress in linear programming, one in which barrier methods do not dominate in the solution of large-scale problems.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Commentary—Major Cholesky Would Feel Proud
Authors: Saunders Michael A.
Published: October 2008

Probably more than any other group, authors Lustig, Marsten, and Shanno have led the way in demonstrating the effectiveness of interior methods for solving large, real-world linear programs. For several years they have written at length about things they have actually done. There are no pies in the sky, no secrets. They have explored a multitude of algorithmic ideas and implementation strategies, and they have done more than could be asked to share their experience with the rest of the world.

Here, the authors look back on a decade's events that revived barrier methods for constrained optimization and eventually led to their production LP solver OB1. The results reported are indeed impressive. In this commentary, we focus mostly on the “engine”—the Cholesky factorizer—that has made OB1 such a practical success.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Design of Performance Constrained Optic Fiber Multidrop Access Networks
Authors: Dewan Rajiv M.
Published: October 2008

Propagation delay may not be negligible in comparison to transmission times in high speed networks. As a consequence, design procedures for high speed networks, such as optic fiber based networks, must take propagation delay into account. The design problem for multidrop access networks that includes transmission and propagation delay times is modeled as a mixed integer program. The problem is shown to be NP Hard and a solution procedure is proposed. Experimentation reveals the effect of poll cycle time limits on topology and cost.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Staged Primal-Dual Algorithm for Finding a Minimum Cost Perfect Two-Matching in an Undirected Graph
Authors: Pekny Joseph F. , Miller Donald L.
Published: October 2008

We describe an algorithm for finding a minimum cost perfect two-matching in a weighted undirected graph, G = (V, E). The algorithm is based on a staged approach that sequentially applies increasingly more expensive steps until a solution is found. First, the degree constrained LP relaxation is posed as a bipartite two-matching problem and solved using a network flow algorithm. Next, the facet inducing two-matching cutset inequalities are activated selectively within a primal-dual framework that progressively eliminates half-integral values from the primal solution while maintaining dual feasibility. The algorithm is guaranteed to terminate in O(|V|2|E|) steps, although computational results suggest this upper bound to be pessimistic. The algorithm is experimentally shown to be effective on TSPLIB test problem[1] ranging in size from 17 to 11,849 vertices.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
From the Editor
Authors: Golden Bruce L.
Published: October 2008

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Computational Study of Local Search Algorithms for Job Shop Scheduling
Authors: Aarts E. H. L. , van Laarhoven P. J. M. , Lenstra J. K. , Ulder N. L. J.
Published: October 2008

We present a computational performance analysis of local search algorithms for job shop scheduling. The algorithms under Investigation are Iterative improvement, simulated annealing, threshold accepting, and genetic local search. Our study shows that simulated annealing performs best in the sense that it finds better solutions than the other algorithms within the same amount of running time. Compared to more tailored algorithms, simulated annealing still finds the best results but only under the assumption that running time is of no concern. Compared to tabu search, simulated annealing is outperformed especially with respect to running times.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
On the Complexity of the Policy Improvement Algorithm for Markov Decision Processes
Authors: Melekopoglou Mary , Condon Anne
Published: October 2008

We consider the complexity of the policy improvement algorithm for Markov decision processes. We show that four variants of the algorithm require exponential time in the worst case.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
SSS: Subrouting Set for Experimenting in Simulation Research
Authors: Pollatschek A. M.
Published: October 2008

SSS is a collection of routines that can be used in DOS-based systems with a Borland or Microsoft compiler. Simulations can be run within integrated environments, thus appreciably reducing turnover from concept of an idea until the experimental results are obtained. SSS provides nearly all the support found in well established simulation languages and is well suited to research and illustration of simulation principles.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Intelligent Objects in Simulation
Authors: Ozden Mufit
Published: October 2008

In this paper, learning automata are incorporated as decision making agents (“intelligent objects”) to handle the discrete type of decisions in simulation models. The integrated simulation system is viewed as a continuously evolving, closed system in which operational and design decisions can be made automatically. In this learning paradigm, the simulation model serves as an environment which provides performance evaluations for the decision policies formulated in succession by the learning automata. As the automata revise the action probabilities at regular intervals on the basis of these performance evaluations, they improve their decision making process continuously. The approach can be an excellent tool for the analysis and design of complex systems under uncertainty. An application is demonstrated in a manufacturing setting in which due-dates and machine assignments of jobs are the decisions to be made by the automata so as to minimize a nonlinear function of job tardiness and earliness subject to random job arrivals and machine breakdowns.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Flexible Method for Estimating Inverse Distribution Functions in Simulation Experiments
Authors: Avramidis Athanassios N. , Wilson James R.
Published: October 2008

To generate random variates from an unknown continuous distribution, we present procedure IDPF—a flexible technique for estimating the associated inverse distribution function from sample data and for generating variates from the fitted distribution by inversion. To motivate IDPF, first we examine a predecessor due to Hora, and we explain how Hora's method can fail in either the distribution-fitting or variate-generation stage of application. We apply IDPF as follows. After selecting an initial inverse distribution function by a standard technique, we estimate a polynomial “filter” for the random-number input by constrained nonlinear regression to achieve minimum “distance” between the empirical inverse distribution and the final fitted inverse distribution obtained by composition of the initial inverse distribution with the polynomial “filter.” The regression constraint ensures that the fitted inverse distribution function is nondefective and monotonically nondecreasing. A portable, public-domain implementation of IDPF is based on well-known techniques for selecting initial distributions from the Johnson translation system. A Monte Carlo study illustrates the effectiveness of IDPF. Compared to initial Johnson distributions selected by matching moments, IDPF-based fits are closer on the average to the corresponding empirical and theoretical inverse distribution functions. Similar conclusions apply to other initial distributions selected by other methods.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
The Application of Metamodeling to Interconnection Network Analysis
Authors: Shaw Wade H. , Davis Nathaniel J. , Raines Richard A.
Published: October 2008

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

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Convergence Results for Harmonic Gradient Estimators
Authors: Jacobson Sheldon H.
Published: October 2008

Sensitivity analysis of steady state simulation outputs typically involves estimating gradients. This paper presents convergence results for the harmonic gradient estimators. Sufficient conditions are formulated that validate the interchange of the derivative and the expectation operators for these estimators. The relationship between these estimators and finite differences gradient estimators is discussed. In particular, the harmonic estimators are shown to be variations of finite differences gradient estimators. Exploiting the orthogonal property of the trigonometric basis results in harmonic gradient estimation procedures requiring two simulation runs. Computational results with various queueing system simulation models are included to compare and illustrate the different estimators. These results suggest that the harmonic gradient estimation procedures requiring two simulation runs may be an alternative to forward (symmetric) finite differences gradient estimation procedures with common random number streams requiring p + 1 (2p) simulation runs.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Optimization of Simulation via Quasi-Newton Methods
Authors: Safizadeh M. Hossein , Signorile Robert
Published: October 2008

This paper discusses the application of quasi-Newton methods to optimization of simulation. Specifically, it describes a general methodology that combines response surface methodology and other optimization techniques with quasi-Newton methods. Using quasi-Newton methods in the vicinity of the optimum speeds up the convergence rate of response surface methodology, the gradient, and search methods. From the class of quasi-Newton methods, we recommend BFGS and Davidon's methods. These methods are effective without exact line searches. Two examples demonstrate the effectiveness of the proposed methodology.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Branch and Bound Algorithm for Integer Quadratic Knapsack Problems
Authors: Bretthauer Kurt M. , Shetty Bala , Syam Siddhartha
Published: October 2008

We present a branch and bound algorithm for solving separable convex quadratic knapsack problems with lower and upper bounds on the integer variables. The algorithm solves a series of continuous quadratic knapsack problems via their Kuhn-Tucker conditions. We also discuss reoptimization procedures for efficiently solving the continuous subproblems. Computational results for problems with up to 300 integer variables are reported.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.