bluuebunny/crossref_metadata_2025 huggingface dataset:
Tabu Search Applied to the Quadratic Assignment Problem
Authors: Skorin-Kapov Jadranka
Published: October 2008

This paper describes an adaptation of Tabu Search, a recent technique to overcome local optimality, to the Quadratic Assignment Problem (QAP). Computational experiments with different parameter values and different strategies have been performed for some QAPs from the literature and some randomly generated QAPs of dimensions varying between 42 and 90. The method is implemented in a flexible form which allows the user to interact and change the parameters (tabu list size, the iteration limit, a search diversification parameter and the number of new starting solutions) during the run. The results suggest that good tabu list sizes increase with dimension of the problem. The algorithm appears to be a very efficient method for QAPs: for the standard problems tested, the best known solutions were obtained using less CPU time than previously reported in the literature. For Steinberg's problem (n = 36) with rectangular distances, a better solution than previously known in the literature was obtained. In addition, in comparison with simulated annealing, tabu search appears to be superior with respect to the solution quality.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Book Review
Authors: Jones Richard H.
Published: October 2008

Review of: Newton, J. H. (1988) TIMESLAB: A Time Series Analysis Laboratory, Wadsworth & Brooks/Cole, Pacific Grove, California. Reviewed by: Richard H. Jones.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Computational Testing: Why, How and How Much
Authors: Greenberg Harvey J.
Published: October 2008

This considers the issues associated with performing and reporting computational testing in the context of original research in operations research, particularly in its interface with computer science. The scope includes non-numerical computations, such as fundamental algorithms and information structures in new modeling languages, and many criteria besides speed of computation, like robustness and depth. Beginning with a foundation of why we perform computational testing, some principles are described that draw heavily from the works of others. Then, methods of how to perform computational testing are suggested, ranging from quantitative statistical techniques to qualitative factor analysis. Finally, the issue of how much computational testing is appropriate is considered in the context of guidelines for referees and editors who deal with such issues.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
The Influence of Computer Language on Computational Comparisons: An Example from Network Optimization
Authors: Lustig Irvin J.
Published: October 2008

C and Fortran implementations of the network simplex method are compared in a study to determine the effect of computer language on computational comparisons. For an algorithm that uses pointers in data structures, the capability of C to represent pointers as true memory addresses provides a faster implementation of that algorithm. The C implementation can be from 1.2 to 3.0 times faster than the Fortran implementation depending upon the computer used for the experiments and the particular problem solved. Hence, greater care must be taken when choosing a programming language for the implementation of a specific algorithm.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Optimal Preemptive Scheduling of Two Unrelated Processors
Authors: Gonzalez Teofilo , Lawler Eugene L. , Sahni Sartaj
Published: October 2008

The problem of constructing makespan-optimal preemptive schedules for n independent jobs on m unrelated parallel processors is discussed. For the case of two processors, we present a linear time algorithm to construct optimal schedules. The schedules generated by our algorithm have at most two preemptions.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Editor's Introduction
Authors: Greenberg Harvey J.
Published: October 2008

Brief overview of papers published in the issue.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Minimizing Total Tardiness on a Single Machine with Precedence Constraints
Authors: Leung Joseph Y.-T. , Young Gilbert H.
Published: October 2008

The problem of minimizing the total tardiness for a set of unit-processing-time jobs on a single machine is considered. J. K. Lenstra and A. H. G. Rinnooy Kan have shown that the problem is NP-hard if the jobs have arbitrary precedence constraints. They asked whether the problem remains NP-hard for tree-structured precedence constraints. In this paper we show that the problem is NP-hard even for a set of chains. Our result gives a sharp boundary for the complexity of this problem, since there is a simple, polynomial-time algorithm for a set of independent jobs.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Neural Networks for Selective Vehicle Routing Heuristics
Authors: Nygard Kendall E. , Juell Paul , Kadaba Nagesh
Published: October 2008

In the vehicle routing problem (VRP), there is a collection of stops with known demands for service, and a fleet of vehicles with known capacities available to serve the stops. The problem is to assign the stops to vehicles, and specify routing sequences for each vehicle so that total distance is minimized. Many heuristic algorithms for the VRP have been developed over the last 25 years. Given a particular vehicle routing problem instance, we address here the issue of selecting which heuristic algorithm to apply to the problem. A modular system of neural networks is the knowledge base that is used to make the selection. Three types of multiple-layer neural networks are involved, and all are trained with the back-propagation learning paradigm. After training, the neural network system was applied to a collection of new problems not used in training. The system was very successful in identifying the optimal algorithm to apply to the new problems. We conclude that neural networks have considerable promise for use in vehicle routing model management systems.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Generating Markov-Chain Transitions Quickly: II
Authors: Fox Bennett L. , Young Andrew R.
Published: October 2008

A predecessor to this paper gives a way to generate transitions in continuous-time Markov chains. It is fast when a “similarity” condition holds. Exploiting a balanced binary search tree, we reduce the computational complexity of that method.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Pattern Classification Using Linear Programming
Authors: Roy Asim , Mukhopadhyay Somnath
Published: October 2008

The paper presents a new method for pattern classification that uses linear programming formulations. The method can generate neural network type networks to take advantage of parallel computation in the classification phase. Application of the technique to a wide variety of problems, including speech and image recognition, is being explored.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Book Reviews
Authors: Greenberg Harvey J. , Chinneck John W. , Karam Gerald M.
Published: October 2008

Review of: Bertsekas, D. P., and Tsitsiklis (1989) Parallel and Distributed Computation: Numerical Methods, Prentice-Hall, Englewood Cliffs, NJ. Reviewed by: Harvey J. Greenberg.

Review of: Van Hentenryck, Pascal (1989) Constraint Satisfaction in Logic Programming, MIT Press, Cambridge, MA. Reviewed by: John W. Chinneck and Gerald M. Karam.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
An Introduction to Graph-Based Modeling Systems, Part II: Graph-Grammars and the Implementation
Authors: Jones Christopher V.
Published: October 2008

Attributed graphs are a widely used paradigm for representing management science models. In Part I of the study, we presented an overview of the concept of a Graph-Based Modeling System (GBMS), which supports the construction of a variety of models as long as the models can be expressed as attributed graphs. The key concept underlying the research is graph-grammars, a formal technique to specify how to build graphs with desired properties. Graph-grammars, as shown in Part I, among other capabilities, facilitate the creation of direct manipulation, computer graphics interfaces for graph-based models. A brief overview of a prototype implementation to do so, Networks, was also provided. In this concluding part, the implementation and the core technology underlying the research—graph-grammars—will be presented in detail.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Computational Comparison of Two Algorithms for the Euclidean Single Facility Location Problem
Authors: Ben Rosen J. , Xue Guo-Liang
Published: October 2008

The best known first order and second order methods for the Euclidean single facility location problem are Weiszfeld's algorithm and Newton's algorithm, respectively. With only a linear rate of convergence, Weiszfeld's algorithm is a simple closed form iteration formula. With a quadratic rate of convergence, Newton's algorithm is more complicated and requires a line search at each iteration. In this paper, computational comparisons were made between these two algorithms. Both sequential and parallel versions of each algorithm were compared. These results show that the second order method is more efficient for low dimensional problems while the first order method is more efficient for high dimensional problems. A parallel version of each algorithm was implemented on a NCUBE hypercube with 64 processors and tested on randomly generated problems with space dimension from 2 to 9, and the number of existing facilities from 1000 to 9000. A speedup of as high as 58 was achieved with 64 processors.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Comparison of Two Simulated Annealing Algorithms Applied to the Directed Steiner Problem on Networks
Authors: Osborne Lawrence J. , Gillett Billy E.
Published: October 2008

The well-known Steiner problem on networks is an NP-complete problem for which there are many deterministic algorithms and heuristics. In this paper a new approach to the directed version of this problem is made by applying the ideas of statistical mechanics through the use of the method of simulated annealing. Two different types of cooling algorithms are tailored to the Directed Steiner Problem. Computations are done on a test bed of 480 random graphs in order to study the performance of these algorithms. In addition to the quality of the final answers, the study looks at the distribution of first occurrences during the execution of the cooling schedules of answers that are within 3% of the optimum. The study suggests that these near-optimal answers appear according to an approximately exponential distribution and that they can be obtained in polynomial time. Experiments also indicate that for random graphs annealing usually gives near-optimal answers in less time than does branch and bound.

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 the Cancellation Sequence Method of Tabu Search
Authors: Dammeyer Frank , Forst Peter , Voss Stefan
Published: October 2008

This note deals with the Cancellation Sequence Method given in a recent paper on Tabu Search by F. Glover. Slight modifications and corrections are proposed and verified by the use of some examples.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Book Review
Authors: Lodwick Weldon A.
Published: October 2008

Review of: W.-Y. Ng (1989) Interactive Multi-Objective Programming as a Framework for Computer-Aided Control Systems Design, Lecture Notes in Information Science, Springer-Verlag, New York. Reviewed by: Weldon A. Lodwick.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
An Empirical Analysis of the Dense Assignment Problem: Sequential and Parallel Implementations
Authors: Kennington Jeffery L. , Wang Zhiming
Published: October 2008

The best algorithms for the dense assignment problem are acknowledged to be the auction algorithm and the shortest augmenting path algorithm. In this investigation we present an empirical analysis of two of the current best software implementations of these two methods on three different serial machines. These software implementations were developed by D. P. Bertsekas of the Massachusetts Institute of Technology and by R. Jonker and T. Volgenant of the University of Amsterdam. This report is an independent evaluation of the software implementation of these two algorithms. For the sample of problems examined and the sample of hardware used (IBM 3081D, Sequent Symmetry S81, and VAX 750), we found that the shortest augmenting path algorithm was the fastest. We also report our empirical results with a parallel version of the shortest augmenting path algorithm. On 1200×1200 dense assignment problems, speedups of approximately four were achieved using ten processors. Million arc problems were solved in less than twelve seconds on a Sequent Symmetry S81 with the parallel shortest augmenting path algorithm.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Nonstandard Genetic Algorithm for the Nonlinear Transportation Problem
Authors: Michalewicz Zbigniew , Vignaux George A. , Hobbs Matthew
Published: October 2008

We describe a nonstandard genetic algorithm approach to the nonlinear transportation problem. This extends our earlier research for the linear transportation problem. New “chromosome structures” and “genetic operators” are introduced to preserve feasibility. Results seem promising.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Rule-Based Generation of Model Structures in Multifaceted Modeling and System Design
Authors: Rozenblit Jerzy W. , Huang Yueh M.
Published: October 2008

A framework for aiding the construction of simulation models in system design problems is presented. The framework employs concepts of artificial intelligence and simulation modeling. A knowledge representation scheme called system entity structure expresses information about the structure of the system to be designed and its corresponding models. More specifically, the entity structure represents objects and their attributes, decompositions, and taxonomies. A knowledge base of production rules is defined for a given design domain and is incorporated in an expert system shell which recommends a feasible configuration of design objects from the system entity structure, based on specific design objectives, constraints, and requirements. This configuration is a basis for constructing a model of the system. The methodology for constructing the system entity structure and its corresponding rule base is presented. A case study based on a high level robot design problem is discussed to illustrate the conceptual framework.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
SQLMP: A Data Sublanguage for Representation and Formulation of Linear Mathematical Models
Authors: Choobineh Joobin
Published: October 2008

We show how algebraic linear optimization models can be mapped to the relational model of data. We then introduce SQLMP, a new language for model description and manipulation. SQLMP (SQL for Mathematical Programming) is the result of endowing the Structured Query Language (SQL) with additional constructs for the definition of the objective functions and the constraints of optimization models. Features of SQLMP enable 1) smooth integration of mathematical models with SQL-based databases, 2) model manipulation, and 3) attainment of a high degree of model independence. Formal syntax of the SQLMP is given.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
TSPLIB—A Traveling Salesman Problem Library
Authors: Reinelt Gerhard
Published: October 2008

This paper contains the description of a traveling salesman problem library (TSPLIB) which is meant to provide researchers with a broad set of test problems from various sources and with various properties. For every problem a short description is given along with known lower and upper bounds. Several references to computational tests on some of the problems are given.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Solving Piecewise-Linear Programs: Experiments with a Simplex Approach
Authors: Fourer Robert , Marsten Roy E.
Published: October 2008

We report tests of CPLP, a piecewise-linear simplex implementation based on the XMP subroutine library. Using test problems of various shapes and origins, we judge CPLP against a comparable linear bounded-variable simplex code that is applied to equivalent linear programs. Our evidence indicates that CPLP is typically 2 to 3 times faster in solving the test problems that are most significantly piecewise-linear; previously predicted advantages of the piecewise-linear simplex approach are observed to occur, though with different combinations of advantages being relevant in different cases. The savings achieved by CPLP appear likely to extend, moreover, to the costs involved in formulating, generating and analyzing piecewise-linear programs.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Solving Large Sparse Nonlinear Programs Using GRG
Authors: Smith Stuart , Lasdon Leon
Published: October 2008

We describe a feasibility-retaining GRG algorithm for large sparse nonlinear programs of general form. Its FORTRAN implementation, LSGRG, is enhanced by heuristics which aid in basis selection, combatting degeneracy, dynamic tolerance adjustment, and predicting Newton failures. Key roles are also played by efficient procedures for basis inversion and by both pure and limited memory BFGS methods for computing the search direction. The design goal for LSGRG is maximum reliability with at least acceptable speed. Extensive computational tests on both FORTRAN and GAMS models indicate that LSGRG is promising in this regard. Comparisons are presented with GRG2, a sparsity oriented SQP code, and MINOS, indicating that LSGRG is a useful complement to MINOS in a multi-solver NLP environment.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Exploiting Special Structure in Primal Dual Interior Point Methods
Authors: Hurd James K. , Murphy Frederic H.
Published: October 2008

This paper examines special sparsity structures in linear programs that can accelerate calculations in the primal dual method. Our results extend previous research by quantifying more precisely conditions for retaining sparsity during iterations. Special structures that meet these conditions include simple upper bounds, variable upper bounds, and chained upper bounds. We describe an implementation and illustrate the benefits for the uncapacitated facility location problem.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Scheduling Checks and Saves
Authors: Boguslavsky Leonid B. , Coffman Edward G. , Gilbert Edgar N. , Kreinin Alexander Y.
Published: October 2008

A job is to be run on a machine subject to random failures. Failures are not self-evident. They must be detected by explicit tests, or checks. Checks detect failures to avoid wasting time working with a defective machine. After each successful check one has the option of saving the work just completed. Then, when failures occur, only the work done since the last save must be repeated. Effective use of checks and saves requires a compromise, since these procedures are themselves time-consuming. Scheduling saves alone, when failures are evident as soon as they occur, is often called checkpointing. The novelty of the model studied here stems from not assuming that failures are self-evident. This compounds the usual checkpointing problem by requiring schedules of failure checks as well as saves. This paper gives schedules of checks and saves that minimize the expected total time required to complete a given job. The most general failure mechanism considered is a renewal process. The Poisson process receives special emphasis, as it leads to the simplest results.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Book Review
Authors: Vohra Rakesh V.
Published: October 2008

Review of F.S. Hillier and G.J. Lieberman (1990) Introduction to Mathematical Programming, 5th Edition, and Introduction to Stochastic Models in Operations Research, 5th Edition, McGraw-Hill Publishing Company, Hightstown, NJ. Reviewed by Rakesh V. Vohra, Faculty of Management Sciences, Ohio State University, Columbus, Ohio 43210, USA.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Preprocessing Nonlinear Functional Constraints with Applications to the Pooling Problem
Authors: Lodwick Weldon A.
Published: October 2008

Methods to uncover redundancies, infeasibilities and bound structures on variables for nonlinear constraint sets are developed. It is these methods that comprise the preprocessing that is derived here. Bilinear constraint sets ate used to illustrate the methods. Thus, special emphasis is given to bilinearities and a nonlinear programming model in which bilinearities arise naturally, a generic petroleum refinery model and its associated pooling problem. The usefulness of the approaches developed herein include their applications to preoptimization/postoptimization analyses of nonlinear programming problems and the generation of starting values for nonlinear programming optimizers. Numerical examples are given that use existing optimization packages in conjunction with a computer-aided analysis system, and point to the practical implementability of the methods derived.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Generalized Networks: Parallel Algorithms and an Empirical Analysis
Authors: Clark Robert H. , Kennington Jeffery L. , Meyer Robert R. , Ramamurti Muthukrishnan
Published: October 2008

The objective of this research was to develop and empirically test new simplex-based parallel algorithms for the generalized network optimization problem. One of these algorithms is essentially a “data parallel” method in which each processor executes identical code on a portion of the data. (However, since the data sets are not necessarily disjoint, “locks” are used to ensure exclusive access.) A second algorithm exhibits “control parallelism,” using different processors to simultaneously execute the different subtasks of the simplex method. “Locks” are not needed in this second approach, but, instead, at the beginning of each pivot, an “audit” of the proposed entering arc is performed in order to ensure correctness of the method. These parallel algorithms were implemented on the Sequent Symmetry multiprocessor, empirically tested on a variety of problems produced by two random problem generators, and compared with two leading state-of-the-art serial codes. Good speedups were obtained relative to the serial codes, and the relative performance of the two parallel methods was found to be dependent on connectedness properties of the optimal solutions of the test problems. The largest test problem, a generalized transportation problem having 30,000 nodes and 1.2 million arcs was optimized in approximately 11 minutes by our parallel code, displaying a speedup of 13 on 15 processors.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
An Optimal Algorithm for the Orienteering Tour Problem
Authors: Ramesh R. , Yoon Yong-Seok , Karwan Mark H.
Published: October 2008

Orienteering is a sport in which a competitor selects a path from a start to a destination, visiting control points along the path. Each control point has an associated score, and the travel between control points involves a certain cost. The problem is to select a set of control points to visit, so that the total score is maximized subject to a budget constraint on total cost. Several versions of this problem exist. In the version considered in this research, the start and the destination are the same, and the problem is to construct a subtour of the set of control points. The orienteering problem is a variant of the traveling salesman problem, and arises in vehicle routing and production scheduling situations. This problem has been shown to be NP-hard in the literature. We develop an optimal algorithm to solve this problem, using Lagrangean relaxation within a branch-and-bound framework. The Lagrangean relaxation is solved by a degree-constrained spanning tree procedure. Characteristics of the Lagrangean relaxation are studied, and several implementation features to improve the performance of the algorithm are presented. Detailed computational results for problems having up to 150 control points are presented. The results show that the proposed approach is viable for solving problems of medium to large size.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Massively Parallel Algorithms for Singly Constrained Convex Programs
Authors: Nielsen Soren S. , Zenios Stavros A.
Published: October 2008

We develop four iterative algorithms for the solution of separable, convex nonlinear optimization problems with a single linear constraint and bounded variables. The design of the algorithms makes them suitable for implementation on massively parallel computers of the SIMD (i.e., Single Instruction, Multiple Data) class. The algorithms are specialized for the solution of network problems whereby the linear constraint reflects conservation of flow. Details of implementations on a Connection Machine CM-2 are reported. The numerical results indicate that all algorithms are very effective, and can solve very large problems. Three of the algorithms are also very efficient when implemented on the massively parallel system. Interestingly, the most effective algorithm (in number of steps required to solve the test problems) is the least efficient (in solution time) when implemented in parallel.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Jackknifing under a Budget Constraint
Authors: Glynn Peter W. , Heidelberger Philip
Published: October 2008

In this paper, we consider the problem of estimating a parameter α that can be expressed as a nonlinear function of sample means. We develop a jackknife estimator for α that is appropriate to computational settings in which the total computer budget to be used is constrained. Despite the fact that the jackknifed observations are not i.i.d., we are able to show that our jackknife estimator reduces bias without increasing asymptotic variance. This makes the estimator particularly suitable for small sample applications. Because a special case of this estimator problem is that of estimating a ratio of two means, the results in this paper are partinent to regenerative steady-state simulations.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Guest Editors' Introduction
Authors: Mitchell Joseph S. B. , Lenstra Jan Karel
Published: October 2008

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Dynamic Three-Dimensional Linear Programming
Authors: Eppstein David
Published: October 2008

We perform linear programming optimizations on the intersection of k polyhedra in R3, represented by their outer recursive decompositions, in expected time O(k log k log n + √k log k log3 n). We use this result to derive efficient algorithms for dynamic linear programming problems in which constraints are inserted and deleted, and queries must optimize specified objective functions. As an application, we describe an improved solution to the planar 2-center problem.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Matching Points into Pairwise-Disjoint Noise Regions: Combinatorial Bounds and Algorithms
Authors: Arkin Esther M. , Kedem Klara , Mitchell Joseph S. B. , Sprinzak Josef , Werman Michael
Published: October 2008

We consider several cases of the point matching problem in which we are to find a transformation of a set of n points such that each transformed point lies in one of n given pairwise-disjoint “noise regions.” We prove upper and lower bounds on the number of possible matches, under a variety of types of transformations (rotations, translations, similarity) and noise regions (circles, squares, polygons). We also give efficient algorithms for computing the set of all possible matches, along with a corresponding transformation that realizes each match.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Fast Algorithms for Geometric Traveling Salesman Problems
Authors: Bentley Jon Jouis
Published: October 2008

This paper describes efficient algorithms for computing approximate traveling salesman tours in multidimensional point sets. We describe implementations of a dozen starting heuristics (including Nearest Neighbor and Farthest Insertion) and three local optimizations (including 2-Opt and 3-Opt). Experiments indicate that most of the algorithms run in O(N log N) time on uniform data sets, and many run almost as fast on very nonuniform data. The program that implements the algorithms is able to solve uniform planar million-city traveling salesman problems to within a few percent of optimal in several midicomputer CPU hours. The algorithms and program apply to many distance metrics and dimensions.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
The Voronoi Partition of a Network and Its Implications in Location Theory
Authors: Hakimi S. Louis , Labbé Martine Labbé , Schmeichel Edward
Published: October 2008

Given a network N(V, E) and a set of points Xp = {x1, …, xp} on N, we first present an algorithm for computing the Voronoi partition of N(V, E) into territories T(x1), …, T(xp). After describing two ways to measure the “size” of a territory, we introduce and discuss the more challenging problem of selecting Xp so that the maximum size among the resulting territories is as small as possible. For one especially natural way to measure the size of a territory, we show that this latter problem is NP-complete when p is part of the input, but that the problem can be solved in polynomial time for any fixed p.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
On the Optimal Bisection of a Polygon
Authors: Koutsoupias Elias , Papadimitriou Christos H. , Sideri Martha
Published: October 2008

We show that bisecting a polygon into two equal (possibly disconnected) parts with the smallest possible total perimeter is NP-complete, and it is in fact NP-hard to approximate within any ratio. In contrast, we give a dynamic programming algorithm which finds a subdivision into two parts with total perimeter at most that of the optimum bisection, such that the two parts have areas within ε of each other; the time is polynomial in the number of sides of the polygon, and 1/ε. When the polygon is convex, or if the parts are required to be connected, then the exact problem can be solved in quadratic time.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Dimensional Analysis in Mathematical Modeling Systems: A Simple Numerical Method
Authors: Bhargava Hemant K.
Published: October 2008

This paper develops a numerical method for dimensional analysis, which has previously been treated as a problem requiring symbolic mathematics techniques. The numerical method obeys the laws of dimensional arithmetic. This is achieved by specifying an encoding of units of measurement as prime numbers, and manipulating the resulting expressions numerically. The unique factorization theorem is applied to show that this method makes trivial the problems of dimensional simplification and verification of dimensional equivalency, which are central issues in dimensional arithmetic. The solution has applications in mathematical modeling systems, chiefly in the model validation and model solution phases. The paper also describes a first-order logic language, Ldim, which can be used in such systems to represent and manipulate dimensional information.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Measuring Congestion for Dynamic Task Allocation in Distributed Simulation
Authors: Shanker Murali S. , Kelton W. David , Padman Rema
Published: October 2008

An important factor affecting the performance of distributed simulations running on parallel-processing computers is the allocation of logical processes to the available physical processors. An inefficient allocation can result in excessive communication times and unfavorable load conditions. This leads to long run times, possibly giving performance worse than that with a uniprocessor sequential event-list implementation. But the efficiency of any allocation strategy is dependent on the metric, or measure, it uses to characterize the load in the distributed system. This paper presents a simple and intuitive way of measuring and reallocating the load when the objective is to minimize simulation run time. The metric, based on estimating measures of message utilization at each processor, has been used in an adaptive scheme for load allocation, and experiments on an iPSC/2 Hypercube indicate that it successfully characterizes the load for purposes of reducing simulation run time.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Selecting Parameters of Phase Distributions: Combining Nonlinear Programming, Heuristics, and Erlang Distributions
Authors: Johnson Mary A.
Published: October 2008

Because of their denseness and tractability, phase (PH) distributions are widely used in probabilistic modeling. However, full exploitation of the favorable properties of PH distributions requires the ability to specify PH-distribution parameters to obtain adequate distribution approximations. We combine nonlinear-programming techniques and heuristics to select mixtures of Erlang distributions (a subset of the PH family) to approximate non-PH distributions. Heuristics are used to select the number of Erlang distributions mixed and the order of each mixed Erlang distribution, both of which have an important effect on the range of distribution properties that can be attained. Heuristics are also used for assigning initial values and bounds to the mixing probabilities and the means of the mixed Erlang distributions. Then nonlinear-programming methods are used to determine final values of these continuous parameters. Using a variety of criteria, we show that good fits can often be obtained with a moderate amount of computation and user interaction.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
The Alternating Step Method for Monotropic Programming on the Connection Machine CM-2
Authors: Eckstein Jonathan
Published: October 2008

The alternating step method is a massively parallel alternating direction method for monotropic programming, that is, convex programming with a separable objective function and linear constraints. This paper specializes the alternating step method to generalized network problems with positive semi-definite quadratic arc costs, and describes its implementation on a massively parallel computer, the Connection Machine CM-2. Extensive computational tests reveal that while the method is disappointingly slow for most problems with purely linear cost functions, it is competitive with dual relaxation methods on many problems having positive definite objectives. Furthermore, the algorithm continues to perform well even if a minority of arcs are given purely linear costs.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
ALPO: Another Linear Program Optimizer
Authors: Vanderbei Robert J.
Published: October 2008

This paper describes an implementation of the one-phase primal-dual path-following algorithm for solving linear programming problems. The design is intended to be simple, portable and robust. These design goals are achieved without sacrificing state-of-the-art performance. We give a rather complete description of the algorithm and the implementation. Computational results obtained for the NETLIB suite of problems run on a Silicon Graphics workstation are also presented.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Shortening Future-Event Lists
Authors: Fox Bennett L.
Published: October 2008

For discrete-event simulations with many exponential variates but not necessarily continuous-time Markov chains, we shorten the future-event list. No matter how many underlying exponential variates are present in principle, at any time, at most one exponential variate is on the future-event list. We point out how to find quickly the corresponding event so that overall computational complexity of the work to generate transitions is reduced.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Production Scheduling System
Authors: Nussbaum Miguel , Parra Eduardo A.
Published: October 2008

A knowledge-based scheduling system is described for a real case study. The problem is solved for a plant with multipurpose machines and job-shop batch characteristics. Given the available machines, the list of production orders, the products' due-dates and process description for each product, the system sequences machines for all required products, using an heuristic approach based on the information of the status of the plant and the characteristics of the orders. This work describes in detail several concepts defined in this project. A qualitative analysis of the advantages and disadvantages of these ideas is given, and empirical results are exhibited using real data from the plant.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Separable Quadratic Programming via a Primal-Dual Interior Point Method and its Use in a Sequential Procedure
Authors: Carpenter Tamra J. , Lustig Irvin J. , Mulvey John M. , Shanno David F.
Published: October 2008

This paper extends a primal-dual interior point procedure for linear programs to the case of convex separable quadratic objectives. Included are efficient procedures for: attaining primal and dual feasibility, variable upper bounding, and free variables. A sequential procedure that invokes the quadratic solver is proposed and implemented for solving linearly constrained convex separable nonlinear programs. Computational results are provided for several large test cases from stochastic programming. The proposed methods compare favorably with MINOS, especially for the larger examples. The nonlinear programs range in size up to 8,700 constraints and 22,000 variables.

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—Constrained Nonlinear 0–1 Programming
Authors: Hansen Pierre , Jaumard Brigitte , Mathon Vincent
Published: October 2008

We consider nonlinear programs in 0–1 variables with nonlinear constraints and survey the main approaches to their solution: (i) linearization; (ii) algebraic methods; (iii) enumerative methods and (iv) cutting-plane methods. We also present an extensive computational comparison of algorithms of all four categories. Enumerative methods appear to be the most promising.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Feature Article—Parallel Discrete Event Simulation: Will the Field Survive?
Authors: Fujimoto Richard M.
Published: October 2008

Despite over a decade and a half of research and several successes, technologies to use parallel computers to speed up the execution of discrete event simulation programs have not had a significant impact in the general simulation community. Unless new inroads are made in reducing the effort and expertise required to develop efficient parallel simulation models, the field will continue to have limited application, and will remain a specialized technique used by only a handful of researchers. The future success, or failure, of the parallel discrete event simulation field hinges on the extent to which this problem can be addressed. Moreover, failure to meet this challenge will ultimately limit the effectiveness of discrete event simulation, in general, as a tool for analyzing and understanding large-scale systems. Basic underlying principles and techniques that are used in parallel discrete event simulation are briefly reviewed. Taking a retrospective look at the field, several successes and failures in utilizing this technology are discussed. It is noted that past research has not paid adequate attention to the problem of developing simulation models for efficient parallel execution, highlighting the need for future research to pay more attention to this problem. A variety of approaches to make parallel discrete event simulation an effective tool are discussed.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Feature Article—Interior Point Methods for Linear Programming: Computational State of the Art
Authors: Lustig Irvin J. , Marsten Roy E. , Shanno David F.
Published: October 2008

A survey of the significant developments in the field of interior point methods for linear programming is presented, beginning with Karmarkar's projective algorithm and concentrating on the many variants that can be derived from logarithmic barrier methods. Full implementation details of the primal-dual predictor-corrector code OB1 are given, including preprocessing, matrix orderings, and matrix factorization techniques. A computational comparison of OB1 with a state-of-the-art simplex code using eight large models is given. In addition, computational results are presented where OB1 is used to solve two very large models that have never been solved by any simplex code

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Commentary—Theory and Practice for Interior-Point Methods
Authors: Todd Michael J.
Published: October 2008

The last decade has been a fascinating time for researchers interested in linear programming and its extensions. It opened with Narendra Karmarkar's theoretical paper on the computational complexity of linear programming problems and his claims that his method solved problems 50 times faster than the simplex method. After 10 years of development in both interior-point and simplex methods, we are now at a point at which both approaches can handle problems that seemed intractable before, but where interior-point methods seem to be superior to simplex algorithms for many very large-scale sparse linear programming problems. Lustig, Marsten, and Shanno (LMS) provide an excellent overview of these advances, particularly with respect to their computational significance. Of course, they have been major contributors to the development of interior-point algorithms as well as of sophisticated implementations with their OB1 code. Their experience leads to many interesting insights and also raises some questions: why does the primal-dual method allow such long steps (99.95% of the way to the whereas primal or dual affine-scaling methods seem limited to, say, 95%)? Do the primal and dual “help each other?” And why does the primal-dual affine-scaling algorithm perform poorly, while even tiny centering components render it highly efficient?

In these remarks I want to try to indicate the interplay between theory and computational practice, highlight theoretical developments with (potentially) important consequences and point out some major remaining tasks.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Commentary—Interior-Point Methods: Algorithms and Formulations
Authors: Vanderbei Robert J.
Published: October 2008

The paper by Lustig, Marsten, and Shanno (LMS) gives an excellent presentation of the current state of the art for interior-point methods (as represented by their OB1 code) as it compares to the current state of the art for the simplex method (represented by OSL). The paper is well organized and thoughtful. The results of their experiments clearly indicate that for large problems interior-point methods offer a serious alternative to the simplex method. In these comments, we will try to clarify the relation among some of the algorithms discussed in LMS.

In addition, we will compare the implementation strategy described in LMS, which is based on solving the so-called normal equations, to an alternative implementation strategy based on solving the so-called reduced Karush-Kuhn-Tucker (KKT) system. We will show that for many problems the two approaches yield virtually identical results but, for certain classes of challenging problems, the reduced KKT approach yields a much more efficient code. Also, we will argue that the reduced KKT system approach is more easily extended to quadratic and convex optimization problems.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Complexity of Hierarchical Trees in Evidence Theory
Authors: Dugat Vincent , Sandri Sandra
Published: October 2008

In this article we propose a structure called hierarchical tree to reduce the complexity of the Dempster's rule of combination in evidence theory. Our algorithm is bounded by O(22n−2) in the worst case versus O(22n) for the brute-force algorithm. We can hope for a better average complexity. Furthermore, we propose algorithms based on hierarchical trees to reduce the complexity of the computation of Bel, Pl and Q functions.

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