bluuebunny/crossref_metadata_2025_split huggingface dataset:
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.