bluuebunny/crossref_metadata_2025_split huggingface dataset:
Using a Hop-Constrained Model to Generate Alternative Communication Network Design
Authors: Balakrishnan Anantaram , Altinkemer Kemal 
Published: October 2008

Designing the link topology and selecting capacities in a backbone network of a communication system involve complex tradeoffs between investment and operating costs and service considerations such as network reliability and vulnerability, delays, and blocking. Incorporating all these design criteria simultaneously in a comprehensive model results in a large-scale, nonlinear, discrete optimization problem that is intractable. This paper proposes an alternate optimization-based methodology to generate several cost-effective backbone network designs with varying cost and performance characteristics. Network planners can use this method together with detailed performance evaluation techniques to select a design that achieves the proper balance between conflicting objectives. To generate different configurations, the method parametrically varies a set of hop constraints that restrict the number of links over which messages can be transmitted. Reducing the maximum number of hops increases the number of alternate routes but incurs higher total cost for the communication system. For a given set of hop constraints, we develop a Lagrangian-based algorithm to identify a cost-minimizing network design that satisfies all internode traffic requirements. Our extensive computational tests using randomly generated networks demonstrate that, even for relatively large problems, the method identifies good heuristic solutions and tight lower bounds that confirm the near-optimality of the selected designs. Using a 25-node example, we illustrate how the model can be used to evaluate the cost versus performance tradeoff. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Technical Note—On Performance of Path Planning Algorithms in Unknown Terrains
Authors: Rao Nageswara S. V. 
Published: October 2008

We consider the problem of planning a collision-free path for a point robot R from its present position to a specified destination position through an unknown terrain, i.e., a terrain whose model is not known a priori. R is equipped with a sensor system that is capable of detecting all visible vertices and edges of the obstacles. Algorithms that plan a required path for R have been reported earlier in literature. In this paper, we investigate some trade-offs in the performance of such algorithms in terms of distance traversed, number of sensor operations and computational complexity. These trade-offs accrue as a result of the details of an underlying graph search algorithm, and in this sense are independent of the other properties of the terrain. We show that among a general class of these algorithms (a) depth-first implementations result in minimum computational complexity, (b) shortest-path implementations result in a globally shortest path in each step, and that (c) among a set of implementations that attempt to optimize the distance to the destination, the A* implementation results in minimum number of scan operations. We also present some interesting intermediaries between the algorithms of (a) and (b). INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A New Multiplier Adjustment Procedure for the Distributed Computation of Routing Assignments in Virtual Circuit Data Networks
Authors: Lin Frank Y. S. , Yee James R. 
Published: October 2008

In this paper, the routine problem in virtual circuit networks is considered. In virtual circuit networks, all of the packets in a session are transmitted over exactly one path established between the origin and the destination. We consider the problem of choosing a path for each origin-destination pair so as to minimize the average number of packets in the network. We consider the formulation of this problem as a nonlinear multicommodity flow problem with integer decision variables. The emphasis of this work is to develop a distributed algorithm to solve this optimization problem. The basic approach is Lagrangean Relaxation. We introduce a new multiplier update rule which facilitates the solution of the nonlinear integer programming problem using distributed computation. In computational experiments, our proposed distributed algorithm determines solutions that are within 1% of an optimal solution in less than 2 minutes of CPU time for networks with 26 to 61 nodes. In addition, the proposed multiplier adjustment procedure provides better bounds and is less sensitive to the algorithm parameters than the subgradient method. An analysis of the communication delays of the control messages needed to support a distributed implementation is given. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Implementing the Simplex Method: The Initial Basis
Authors: Bixby Robert E. 
Published: October 2008

This paper contains the first two parts of a planned series of papers on the CPLEXTM implementation of the simplex method. Part I is introductory. It gives an elementary description of the bounded-variable simplex method as well as a rather detailed discussion of some of the numerical characteristics of the netlib test problems. These problems form the basis for the computational tests in the subsequent parts. Part II contains the main results of this paper, a description of the method used by CPLEX for constructing an initial basis. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Numerical Issues in Computing Steady-State Queueing-Time Distributions of Single-Server Bulk-Service Queues: M/Gb/1 and M/Gd/1
Authors: Chaudhry Mohan L. 
Published: October 2008

This paper gives closed-form expressions in terms of the roots of certain equations, for the distributions of the queueing time, Wq, in the steady state for the queues M/Gb/1 and M/Gd/1. Whereas in the former system the server can serve customers up to its capacity b, in the latter system be serves several customers in batches of exactly size d. Essentially, the solution is obtained by first finding the roots of the denominators of the Laplace transforms of Wq and then resolving these transforms into partial fractions. Numerical examples are given that show that the algorithm discussed in the paper can be used effectively to find the required roots, even when there is a large number of such roots. With one exception, all the examples use service times with rational Laplace transforms. The remaining example demonstrates the fact that the quantities for the queues M/Db/1 and M/Dd/1 can be approximated by those from the queues M/Ekb/1 and M/Ekd/1 respectively, when k is large. Out of numerous computations, only representative results in the form of tables and graphs have been appended. It is hoped that the results presented here might be of use to practitioners or queueing theorists dealing with inequalities, bounds, et cetera. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Recognizing Voronoi Diagrams with Linear Programming
Authors: Hartvigsen David 
Published: October 2008

Let P = {P1, …, Pn} be a finite set of distinct points in ℝd and let Ri be the set of points whose distance from Pi is less than or equal to the distance from every other point in P. The collection of regions R1, …, Rn is called the Voronoi diagram generated by P. Our main result is a polynomial time algorithm for recognizing whether or not a given tessellation of ℝd into polyhedra is a Voronoi diagram. This is accomplished by describing a linear program that has a solution if and only if the given tessellation is a Voronoi diagram. As a consequence, for each Ri of a Voronoi diagram, the set of points in Ri contained in some generating set P is either a singleton or the interior of a polyhedron. We also give a polynomial time algorithm for describing this set for each Ri. Finally, this leads to a second algorithm for recognizing Voronoi diagrams; this algorithm also relies on linear programming but, for fixed dimension d, it is strongly polynomial and has linear time complexity. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
1-Segment Center Problems
Authors: Imai Hiroshi , Lee D. T. , Yang Chung-Do 
Published: October 2008

We consider a minimax facility location problem for n points such that the facility is a line segment of a given length. The general problem can be solved by case analysis in O(n4 log n) time. When the orientation of the segment is fixed, the problem is shown to be linear-time solvable by using the prune-and-search technique. Other variations of this problem are also discussed. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
“Lion and Man”: Upper and Lower Bounds
Authors: Alonso Laurent , Goldstein Arthur S. , Reingold Edward M. 
Published: October 2008

Given a lion and a man, their initial positions, and restrictions on their ranges and speeds, how quickly can the lion get within a given distance from the man? We consider the case in which the lion and man are restricted to the interior of a circle and each is limited to the same speed. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Commentary—The Role of Performance Metrics for Parallel Mathematical Programming Algorithms
Authors: Miller Donald L. , Pekny Joseph F. 
Published: October 2008

Parallel computing adds an extra dimension of complexity to the design of mathematical programming algorithms. This complexity complicates the comparison of algorithms and introduces an additional set of performance metrics. The paper by Barr and Hickman (BH) is well written as they have knitted together expert opinion and their own experience into a reasonable set of guidelines for avoiding the pitfalls that arise in the use of these metrics. BH motivate the guidelines with an insightful summary of fundamental parallel computer issues and how they relate to measuring algorithm effectiveness. Below we expand on those comments of BH which we have found especially relevant. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Commentary—Parallel Discrete Event Simulation: Fact or Fiction?
Authors: Abrams Marc 
Published: October 2008

Can a discrete event simulation model be executed in parallel? Fujimoto's article presents the challenges from the perspective of a parallel discrete event simulation (PDES) researcher. A somewhat different answer arises by reexamining the question from the viewpoint of simulation modelers that study complex systems. A simulationist in any simulation study faces the central concern of how to define a model. Often the choice of what to include versus exclude from a model is a significant intellectual accomplishment. Indeed, success in selecting a model maximizes the model's ability to meet the objectives of a simulation study, but minimizes the computation required, to the point that it may obviate the need for parallel simulation! The model is cast into a specification, and the specification is implemented as a program. The issues of verification—whether we are building the model right—and validation—whether we are building the right model—become paramount. An added complexity is designing a model that is maintainable over a lifetime of many years, during which the model may be adapted to new simulation study objectives, run on new hardware configurations or even a new computer architecture, and run on new system software releases. Therefore, conducting a successful simulation study using sequential simulation is already a taxing activity. What additional work must be done to use PDES? Fundamentally, for the PDES programmer, the chief intellectual problem is algorithm design—to devise an operational view of model execution that can be partitioned into an efficient program for the target computer architecture. The efficiency of the algorithm chosen and its match to the target architecture are overriding decisions. In selecting the parallel simulation algorithm used for execution, the PDES programmer will assess whether assumptions required by different algorithms are met by the model. This raises the question of whether a model can be modified to allow use of a more efficient PDES algorithm. In particular, the modeler may have made arbitrary design decisions which do not affect the validity of the model but do affect the ability to parallelize the model. Therefore, model definition and PDES algorithm design are not independent processes. Simulation model definition and parallel algorithm design are very different activities. Therefore success in a large PDES study implies a need for a team combining individuals with “hard-core” simulation modeling knowledge as well as individuals with PDES algorithm knowledge. Such a team could determine if an efficiency problem should be solved by model redefinition, by changing the PDES algorithm, or both. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Commentary—Will Parallel Simulation Research Survive?
Authors: Lin Yi-Bing 
Published: October 2008

In his feature article, Fujimoto pointed out that the success of parallel simulation depends not only on the speedup that can be achieved through parallel simulation but also on the effort required to develop the parallel code. The general simulation community will only recognize parallel simulation technology if several practical simulation applications are found such that the total cost of the code development and code execution for parallel simulation is much less than the cost of sequential simulation. The sequential execution times of most examples listed in Table II in the feature article were less than two hours. It is difficult to justify parallel simulation as the right approach to follow if one needs to spend one additional day (or more) to develop parallel code in order to reduce a two hour execution time to several minutes. Most parallel simulation research focuses on reducing execution time of parallel simulation. Fujimoto proposed several approaches to address the parallel code development issue. I will consider this issue in a different aspect as a supplement. In addition, I will discuss how to predict the performance of parallel simulation, an issue not explicitly discussed in the feature article. Another issue not addressed in the feature article is the distributed computing platform for parallel simulation. Many examples listed in Table II in the feature article were run on shared memory architectures, and none of the examples were run on a network of workstations, a widely used hardware platform which cannot be ignored by parallel simulation researchers. It is difficult to gain acceptable speedup for parallel simulation in a network of workstations due to long communication delays. One possible solution is to connect the workstations using a high speed network. Another solution is to carefully map the processes to the processors such that inter-processor communications are reduced. How to do the latter efficiently is still an open issue. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Rejoinder—Future Directions in Parallel Simulation Research
Authors: Fujimoto Richard M. 
Published: October 2008

The commentators provide many insightful and thought-provoking remarks regarding the parallel discrete event simulation (PDES) field, including important suggestions regarding future directions for PDES research. In the sections that follow, I will first discuss some general points raised by Reynolds regarding “alleviating performance concerns,” and then go on to discuss specific points regarding the approaches that were discussed in the feature article toward making parallel simulation technology more accessible to the simulation community. I will conclude with a few comments regarding additional “silver bullets” suggested by the commentators. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Parallel Asynchronous Hungarian Methods for the Assignment Problem
Authors: Bertsekas Dimitri P. , Castañon David A. 
Published: October 2008

In this paper, we discuss the parallel asynchronous implementation of the Hungarian method for solving the classical assignment problem. Multiple augmentations and price rises are simultaneously attempted starting from several unassigned sources and using possibly outdated price and assignment information. The results are then merged asynchronously subject to rather weak compatibility conditions. We show the validity of this algorithm and we demonstrate computationally that an asynchronous implementation is often faster than its synchronous counterpart. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Approximation Algorithms for Three-Machine Open Shop Scheduling
Authors: Chen Bo , Strusevich Vitaly A. 
Published: October 2008

This paper shows that a greedy algorithm for three machine open shop scheduling with the objective to minimize the makespan provides schedules with the worst-case performance ratio 5/3. A linear time heuristic is presented which improves the schedules and reduces the ratio to 3/2. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
State-of-the-Art Survey—The Traveling Salesman Problem: A Neural Network Perspective
Authors: Potvin Jean-Yves 
Published: October 2008

This paper surveys the “neurally” inspired problem-solving approaches to the traveling salesman problem, namely, the Hopfield-Tank network, the elastic net, and the self-organizing map. The latest achievements in the neural network domain are reported and numerical comparisons are provided with the classical solution approaches of operations research. An extensive bibliography with more than one hundred references is also included. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Mathematical Programming in Neural Networks
Authors: Mangasarian O. L. 
Published: October 2008

This paper highlights the role of mathematical programming, particularly linear programming, in training neural networks. A neural network description is given in terms of separating planes in the input space that suggests the use of linear programming for determining these planes. A more standard description in terms of a mean square error in the output space is also given, which leads to the use of unconstrained minimization techniques for training a neural network. The linear programming approach is demonstrated by a brief description of a system for breast cancer diagnosis that has been in use for the last four years at a major medical facility. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Learning Algorithms for Neural-Net Decision Support
Authors: Piramuthu Selwyn , Kuan Chung-Ming , Shaw Michael J. 
Published: October 2008

Artificial Neural Networks present a new paradigm for decision support that is adaptive and capable of integrating knowledge acquisition, problem solving, and learning. In this paper, we show that the performance of the classical back-propagation algorithm for training artificial neural networks can be improved by applying modified approaches which have better convergence properties, and are faster than the commonly used steepest gradient search method. Simulation results on test problems show that the proposed algorithms perform better than the steepest gradient search algorithm in terms of faster convergence with learning accuracy at least as good as in classical back propagation. Inductive learning algorithms (ID3 and NEWQ) and Probit are also used to compare the relative performances of connectionist, inductive learning and statistical procedures. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Feedforward Neural Nets as Models for Time Series Forecasting
Authors: Tang Zaiyong , Fishwick Paul A. 
Published: October 2008

We have studied neural networks as models for time series forecasting, and our research compares the Box-Jenkins method against the neural network method for long and short term memory series. Our work was inspired by previously published works that yielded inconsistent results about comparative performance. We have since experimented with 16 time series of differing complexity using neural networks. The performance of the neural networks is compared with that of the Box-Jenkins method. Our experiments indicate that for time series with long memory, both methods produced comparable results. However, for series with short memory, neural networks outperformed the Box-Jenkins model. Because neural networks can be easily built for multiple-step-ahead forecasting, they may present a better long term forecast model than the Box-Jenkins method. We discussed the representation ability, the model building process and the applicability of the neural net approach. Neural networks appear to provide a promising alternative for time series forecasting. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs
Authors: Fischetti Matteo , Toth Paolo 
Published: October 2008

An efficient algorithm for the solution of the Min-Sum Arborescence Problem with fixed root-vertex in complete digraphs is presented. The algorithm is based on the well-known Edmonds method. The new approach makes use of simple data structures leading to improvements affecting both computing times and memory requirements. Further improvements are obtained by using a new algorithm based on the solution of a sparse problem. The linear programming reduced costs associated with the arcs are also computed. A FORTRAN implementation is described; the corresponding code is available, on request, from the authors. Extensive computational results on both real-world and random instances are given, showing the effectiveness of the proposed algorithms. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Rejoinder—The Last Word on Interior Point Methods for Linear Programming—For Now
Authors: Lustig Irvin J. , Marsten Roy E. , Shanno David F. 
Published: October 2008

Rejoinder to commentaries to the author's feature article “Interior Point Methods for Linear Programming: Computational State of art.” INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.