bluuebunny/crossref_metadata_2025 huggingface dataset:
Linear Discriminant Functions Determined by Genetic Search
Authors: Koehler Gary J.
Published: October 2008

This paper studies a genetic algorithm that determines linear discriminant functions. The objective is to minimize the number of misclassifications and then to minimize the number of used attributes. The algorithm produces results that are significantly better than Fisher's method for minimizing the probability of misclassification but not significantly different than those that exactly minimize the number of misclassifications. The algorithm has the added benefit that the solutions obtained are more parsimonious than these exact algorithms since two objectives could be considered simultaneously. In our empirical studies, the algorithm routinely found the optimal solution while taking significantly less time than exact algorithms which must both find and prove optimality.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Preprocessing in Stochastic Programming: The Case of Linear Programs
Authors: Wallace Stein W. , Wets Roger J-B.
Published: October 2008

The purpose of this paper is to investigate different preprocessing procedures for stochastic linear programs. The procedures are meant to be of use mostly for the modeler, but there are important computational implications as well. We discuss how to check if the problem under investigation is overspecified, i.e have options (columns) that can never be in an optimal solution, if the problem is tight or loose in terms of feasibility, and we demonstrate how to achieve relatively complete recourse in a number of cases. Computational results are detailed.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
The Vehicle Routing Problem with Time Windows: Minimizing Route Duration
Authors: Savelsbergh Martin W. P.
Published: October 2008

We investigate the implementation of edge-exchange improvement methods for the vehicle routing problem with time windows with minimization of route duration as the objective. The presence of time windows as well as the chosen objective cause verification of the feasibility and profitability of a single edge-exchange to require an amount of computing time that is linear in the number of vertices. We show how this effort can, on the average, be reduced to a constant.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
The Ca/M/s/m Retrial Queue: A Computational Approach
Authors: Yang Tao , Posner Morton J. M. , Templeton James G. C.
Published: October 2008

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

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
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.
Parallel Taboo Search Techniques for the Job Shop Scheduling Problem
Authors: Taillard Éric D.
Published: October 2008

We apply the global optimization technique called taboo search to the job shop scheduling problem and show that our method is typically more efficient than the shifting bottleneck procedure, and also more efficient than a recently proposed simulated annealing implementation. We also identify a type of problem for which taboo search provides an optimal solution in a polynomial mean time in practice, while an implementation of the shifting bottleneck procedure seems to take an exponential amount of computation time. Included are computational results that establish new best solutions for a number of benchmark problems from the literature. Finally, we give a fast parallel algorithm that provides good solutions to very large problems in a very short computation time.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Fast Clustering Algorithms
Authors: Dorndorf Ulrich , Pesch Erwin
Published: October 2008

This paper considers the problem of partitioning the vertices of a weighted complete graph into cliques of unbounded size and number, such that the sum of the edge weights of all cliques is maximized. The problem is known as the clique-partitioning problem and arises as a clustering problem in qualitative data analysis. A simple greedy algorithm is extended to an ejection chain heuristic leading to optimal solutions in all practical test problems known from literature. The heuristic is used to compute an initial lower bound as well as to guide branching in a branch and bound algorithm which is superior to present exact methods. Empirical data for all three algorithms are reported.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Double-Layered Learning Approach to Acquiring Rules for Classification: Integrating Genetic Algorithms with Similarity-Based Learning
Authors: Sikora Riyaz , Shaw Michael
Published: October 2008

In this paper, we describe a machine learning technique based on a double-layered architecture and Genetic Algorithms (GAs), which can be used to learn decision rules for financial classification. Once the rules have been acquired, they can be stored in an expert system for future application. Genetic algorithms represent a class of learning algorithms modeled on the biological evolution process. Equipped with unique search behavior and solution-seeking properties, they provide an interesting technique for such classification tasks as bankruptcy prediction and credit analysis. However, some modifications to the basic genetic algorithms are necessary in order to make the method suitable for solving these classification problems. One of the objectives of this paper is to develop a representation scheme for the concepts to be learned that can be incorporated in a genetic algorithm. More importantly, we expand on the concept of the genetic algorithm and develop a learning method called the Double-layered Learning System (DLS) that integrates the genetic algorithm with a similarity-based learning technique called the Probabilistic Learning System (PLS1).

By combining a learning paradigm that searches through the “hypothesis space” (GA) with a paradigm that searches through the “instance space” (PLS1), DLS permits synergistic improvement of the learning performance. We demonstrate the feasibility of such a hybrid approach computationally by presenting the design, implementation, and performance evaluation of DLS. DLS proves to be an effective improvement over both GA and PLS1. The efficacy of the results points towards the importance of such hybrid approaches in providing more robust machine learning methods.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Feature Article—Visualization and Optimization
Authors: Jones Christopher V.
Published: October 2008

Research in optimization has developed faster and faster algorithms that have analyzed very complicated problems, thereby saving billions of dollars. Solving problems using optimization techniques involves more than just developing clever algorithms, however. Building, debugging, validating, and understanding models, algorithms, data, and solutions require appropriate representations of the models, the algorithms, the data, and the solutions. This paper explores current practice and ongoing research in different representations or visualizations useful for representing optimization models, understanding optimization algorithms, validating and exploring optimal solutions, and summarizing the results.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Commentary—The Promise of OR is Helping to Solve Problems
Authors: Greenberg Harvey J. , Murphy Frederic H.
Published: October 2008

When you were learning optimization, how many times did you draw pictures to help you understand what was happening? When you now obtain results from an optimization model, how many times do you draw sketches and form mental pictures of what the solution means? When the solution does not look right, how often do you use this process of visualization to help you debug the model or this instance of it?

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Commentary—Designing Tools for Visualization and Optimization
Authors: Keiper Jerry , Wickham-Jones Tom
Published: October 2008

What does the future hold for the visualization aspects of optimization? Christopher Jones's article reviews current work and makes predictions for the future. At Wolfram Research both of us have been engaged on the Mathematica® project[6] for most of its life. Through our work, we have gained much experience and insight into the development of integrated mathematical software. Many of the lessons that we have learned can be directly applied to the applications Jones foresees.

In his article, Jones reviews some of the ways in which visualization is crucial to operations research (OR). The simplest of these involves the effective presentation of OR results while, for more complex uses, visualization is a key element of the solution process itself. A more specialized use involves the role of visualization in developing new OR algorithms. As visualization techniques are developed and become more widespread on existing computer systems, the use of visualization in OR will become more widely used and more sophisticated.

For these ideas to reach their full potential, new tools and new techniques must be developed and embodied in actual applications. One important way this happens is through the efforts of the commercial software world. In recent years, there has been an active area of enterprise leading to the rise of whole new classes of mathematical software products. Typical applications cover the areas of statistics, graphics, and computer algebra as well as general mathematics. As an aside, it is interesting to speculate on the relationship between work in academic research institutions and the creation of these products. Because Wolfram Research is one of the key players in this field, it is interesting to consider the points that Jones makes and to compare them with our own experience.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Experimental Evaluation of a Procedure for Estimating Nonhomogeneous Poisson Processes Having Cyclic Behavior
Authors: Johnson Mary A. , Lee Sanghoon , Wilson James R.
Published: October 2008

This paper summarizes an experimental evaluation of a procedure for estimating a nonhomogeneous Poisson process having an exponential rate function, where the exponent may include both polynomial and trigonometric components. Maximum likelihood estimates of the unknown continuous parameters of the rate function are obtained numerically, and the degree of the polynomial rate component is determined by a likelihood ratio test. Our evaluation is limited to the case of a known frequency. To examine the small- and large-sample behavior of the estimation procedure for many types of time-dependent arrival processes encountered in previous work, we performed 100 independent replications of twelve selected Poisson processes over two observation intervals. On each replication of each case, we applied the fitting procedure to estimate the parameters of the target process; and we computed the corresponding estimates of the rate and mean-value functions over the observation interval. Evaluation of the fitting procedure was based on plotted tolerance bands for the rate and mean-value functions together with summary statistics for the maximum and average absolute estimation errors in these functions over the observation interval. The experimental results provide substantial evidence of the procedure's numerical stability and practical usefulness.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A GRASP for the Vehicle Routing Problem with Time Windows
Authors: Kontoravdis George , Bard Jonathan F.
Published: October 2008

This paper addresses the problem of finding the minimum number of vehicles required to visit a set of nodes subject to time window constraints. A secondary objective is to minimize the total distance traveled. Each node requires a predetermined amount of service in the form of pickups and deliveries. The fleet is homogeneous and is located at a common depot. Vehicle capacity is finite and split service is not permitted. A greedy randomized adaptive search procedure (GRASP) is used to obtain feasible solutions. Results are reported for standard 100 node data sets as well as for a number of real-world problems with up to 417 customers. The findings indicate that, in general, the proposed procedure outperforms current techniques and requires only a small fraction of the time taken by exact methods. To gauge the quality of the solutions, three different lower bounding heuristics were developed. The first considers the “bin packing” aspect of the problem with regard to vehicle capacity; the second is based on the maximum clique associated with the customers' incompatibility graph; the third independently exploits the time window constraints. Using these heuristics, it is empirically demonstrated that the optimum is found in almost all cases involving balanced service and tight capacity constraints and a significant proportion of the remainder.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Comparisons Between Aggregation/Disaggregation and a Direct Algorithm for Computing the Stationary Probabilities of a Markov Chain
Authors: Heyman Daniel P. , Goldsmith Meredith J.
Published: October 2008

Aggregation/disaggregation is an iterative scheme that leads to an algorithm for computing the steady-state distribution of a finite Markov chain. The idea is to partition the states into aggregates, estimate the probability that the Markov chain is in a particular aggregate, and then estimate the conditional probability of being in each state of an aggregate given that the Markov chain is in some state in that aggregate. Previous computational performance studies of this algorithm concentrated on applying it to chains that were nearly decomposable. We focus on chains that are not nearly decomposable. We compare this iterative algorithm to a direct method that is a variant of Gaussian elimination. We use a variety of test problems that range in size from 500 to 5,000 states, and which include unstructured and banded matrices. We conclude that, for this array of problems, the direct method requires less computation.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Preprocessing in Stochastic Programming: The Case of Capacitated Networks
Authors: Wallace Stein W. , Wets Roger J-B
Published: October 2008

We investigate different preprocessing procedures for stochastic linear programs whose recourse stage involves directed capacitated networks. The procedures are aimed to help the modeling process, but there are important computational implications as well. We discuss how to check if the problem is tight or loose in terms of feasibility, and we demonstrate how to achieve relatively complete recourse. As a result of our developments, we obtain a computationally feasible way of finding all relevant inequalities required by the Gale and Hoffman theorem on feasibility in networks. Computational results are detailed.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Spectral Analysis of Basic TES Processes
Authors: Jagerman David L. , Melamed Benjamin
Published: October 2008

This paper studies the spectral properties of a class of stochastic sequences generated by basic TES (Transform-Expand-Sample) methods, as well as transformed TES sequences. A TES sequence is obtained as a marginally uniform process from an autoregressive scheme with modulo-1 reduction, followed by additional transformations. We derive formulas for the spectral density function and the spectral distribution function which are suitable for efficient numerical computation. A set of examples is calculated and exhibited for TES processes with uniform and exponential marginals. The results contribute to the understanding of TES sequences as models of autocorrelated sequences, particularly in a Monte Carlo simulation context.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Expressing Special Structures in an Algebraic Modeling Language for Mathematical Programming
Authors: Fourer Robert , Gay David M.
Published: October 2008

A knowledge of the presence of certain special structures can be advantageous in both the formulation and solution of linear programming problems. Thus it is desirable that linear programming software offer the option of specifying such structures explicitly. As a step in this direction, we describe extensions to an algebraic modeling language that encompass piecewise-linear, network and related structures. Our emphasis is on the modeling considerations that motivate these extensions, and on the design issues that arise in integrating these extensions with the general-purpose features of the language. We observe that our extensions sometimes make models faster to translate as well as to solve, and that they permit a “column-wise” formulation of the constraints as an alternative to the “row-wise” formulation most often associated with algebraic languages.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Optimal Scheduling of Tasks on Identical Parallel Processors
Authors: Dell’Amico Mauro , Martello Silvano
Published: October 2008

We consider the classical problem of scheduling n tasks with given processing time on m identical parallel processors so as to minimize the maximum completion time of a task. We introduce lower bounds, approximation algorithms and a branch-and-bound procedure for the exact solution of the problem. Extensive computational results show that, in many cases, large-size instances of the problem can be solved exactly.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
On the Asymptotic Optimality of Multiprocessor Scheduling Heuristics for the Makespan Minimization Problem
Authors: Han Sunan , Hong Dawei , Leung Joseph Y.-T.
Published: October 2008

The asymptotic performance of heuristic algorithms for the multiprocessor scheduling problem is considered. Let rLS denote the ratio of the makespan of any list schedule to the optimal makespan. Let m denote the number of processors and n the number of jobs. We show that the mean and variance of rLS have upper bounds which approach 1 and 0, respectively, at a rate of O(m log n/n), under the assumption that job processing times are independent, identically distributed according to any distribution F over (0, ∞) with ∫(0,∞) eαtdF(t) < ∞ for some α > 0. If the processing times are distributed over (0, 1], a slightly faster convergence rate of O(m/n) is obtained. Furthermore, we show that almost surely, rLS approaches 1 at a rate faster than O(m/n1−β) for any 0 < β < 1. Similar results are also obtained for the Multifit algorithm due to Coffman, Garey and Johnson.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Analyzing the Pooling Problem
Authors: Greenberg Harvey J.
Published: October 2008

The pooling problem is a non-convex mathematical program that arises in blending materials to produce products, such as the blending of crude or refined petroleum. Each material has a set of attributes with associated qualities, such as percentage sulfur and octane rating. Pool qualities are determined by a flow-weighted average of the source qualities, and product qualities are similarly defined by a flow-weighted average of pool qualities. Product qualities are constrained to lie in specified ranges. The pooling problem is to minimize the total cost of flows, subject to flow and quality constraints. Present solution methods are based on sequential linear programming, and sensitivity analysis relies upon Lagrange multipliers. These methods are not exact and can lead to erroneous conclusions. A new method is presented that is based upon computational geometry, which provides exact answers to questions of sensitivity analysis and infeasibility diagnosis.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Single Machine Scheduling to Minimize Total Weighted Late Work
Authors: Hariri A. M. A. , Potts C. N. , Van Wassenhove L. N.
Published: October 2008

In the problem of scheduling a single machine to minimize total weighted late work, there are n jobs to be processed for which each has an integer processing time, a weight and a due date. The objective is to minimize the total weighted late work, where the late work for a job is the amount of processing of this job which is performed after its due date. An O(n log n) algorithm is derived for the preemptive total weighted late work problem. For non-preemptive scheduling, efficient algorithms are derived for the special cases in which all processing times are equal and in which all due dates are equal. A pseudopolynomial algorithm is presented for the general non-preemptive total weighted late work problem. Also, a branch and bound algorithm in which lower bounds are obtained using the dynamic programming state-space relaxation method is proposed for this general problem. Computational results with the branch and bound algorithm for problems with up to 700 jobs are given.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Primal-Dual and Primal Interior Point Algorithms for General Nonlinear Programs
Authors: Lasdon Leon S. , Plummer John , Yu Gang
Published: October 2008

An interior point algorithm for general nonlinear programs is presented. Inequality constraints are converted to equalities with slack variables. All bounds are handled with a barrier term in the objective. The Kuhn-Tucker system of the resulting equality constrained barrier problem is solved directly by Newton's Method. Primal-Dual, Primal, and Primal-Dual with trust region variants are developed and evaluated. An implementation which utilizes the true Lagrangian Hessian and exploits Jacobian and Hessian sparsity is described. Computational results are presented and discussed.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Load Balancing in Hypercube Solution of Stochastic Optimization Problems
Authors: Berland Nils Jacob
Published: October 2008

In some stochastic optimization problems the error bounds computed for the expected optimum can be decreased through recursive divide-and-conquer methods based on partitioning the support of the random variables. Each generated partition from the divide-and-conquer process can be treated independently. This class of problems is therefore easy to parallelize, and we describe two parallel implementations of this divide-and-conquer algorithm applied to PERT. Our results indicate that parallel processing and divide-and-conquer are indeed feasible and efficient for problems of this type. The tests were done on an Intel iPSC/2 multicomputer with 16 nodes.

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