bluuebunny/crossref_metadata_2025_split huggingface dataset:
Tabu Search—Part I
Authors: Glover Fred 
Published: October 2008

This paper presents the fundamental principles underlying tabu search as a strategy for combinatorial optimization problems. Tabu search has achieved impressive practical successes in applications ranging from scheduling and computer channel balancing to cluster analysis and space planning, and more recently has demonstrated its value in treating classical problems such as the traveling salesman and graph coloring problems. Nevertheless, the approach is still in its infancy, and a good deal remains to be discovered about its most effective forms of implementation and about the range of problems for which it is best suited. This paper undertakes to present the major ideas and findings to date, and to indicate challenges for future research. Part I of this study indicates the basic principles, ranging from the short-term memory process at the core of the search to the intermediate and long term memory processes for intensifying and diversifying the search. Included are illustrative data structures for implementing the tabu conditions (and associated aspiration criteria) that underlie these processes. Part I concludes with a discussion of probabilistic tabu search and a summary of computational experience for a variety of applications. Part II of this study (to appear in a subsequent issue) examines more advanced considerations, applying the basic ideas to special settings and outlining a dynamic move structure to insure finiteness. Part II also describes tabu search methods for solving mixed integer programming problems and gives a brief summary of additional practical experience, including the use of tabu search to guide other types of processes, such as those of neural networks. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Neural Network-Based Optimization Algorithm for the Static Weapon-Target Assignment Problem
Authors: Wacholder Eitan 
Published: October 2008

A neural network-based algorithm was developed for the static weapon-target assignment problem in ballistic missile defense. An optimal assignment policy is one which allocates targets to weapon platforms such that the total expected leakage value of targets surviving the defense is minimized. This involves the minimization of a nonlinear objective function subject to inequality constraints specifying the maximum number of interceptors available to each platform and the maximum number of interceptors allowed to be fired at each target as imposed by the battle management/command control and communications system. The algorithm consists of solving a system of ordinary differential equations whose trajectories are the assignment variables of the problem. Simulations of the algorithm on PC and VAX computers were carried out using a simple numerical scheme. In all the battle instances tested, the algorithm has proven to be stable and to converge to solutions very close to global optima. The time to achieve convergence was consistently less than the time constant of the network's processing elements (neurons). This suggests that fast solutions can be realized if the algorithm is implemented in hardware circuits. Three series of battle scenarios are analyzed and discussed in detail. The main advantage of this algorithm is that it can be adapted to either a special-purpose hardware circuit or a general-purpose concurrent machine to yield fast and accurate solutions to difficult decision problems. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Anomalous Acceleration in Parallel Multiple-Cost-Row Linear Programming
Authors: Phillips Andrew T. , Ben Rosen J 
Published: October 2008

Earlier parallel computational results on constrained global optimization problems have shown that speedups greater than the number of processors can occur in practice. To show how this is possible, a relatively simple example of a multiple-cost-row linear program is presented in which the parallel algorithm gives a speedup, over its sequential version, greater than the number of processors. In addition, it is shown that for a particular problem instance (taken from another special class of multiple-cost-row linear programming problems), the average parallel speedup, taken over all orderings of the cost rows, can also be greater than the number of processors. 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 Uncapacitated Networks
Authors: Wallace Stein W. , Wets Roger J-B 
Published: October 2008

Preprocessing can speed up the solution procedures for two-stage stochastic programming. We consider the case when the second-stage problem is a pure, uncapacitated network. We describe a number of procedures to reduce the size of the recourse problem. We describe a procedure for generating efficiently the (induced) feasibility cuts, and show that further reductions are possible if more information about the node-types is taken into account. We also investigate network collapsing techniques that would simplify the work required to find both optimality cuts and feasibility cuts, if we had not yet reduced the problem to one with relatively complete recourse. Computational results confirm that substantial savings are possible. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Implementation of a Dual Affine Interior Point Algorithm for Linear Programming
Authors: Marsten Roy E. , Saltzman Matthew J. , Shanno David F. , Pierce George S. , Ballintijn J. F. 
Published: October 2008

The dual affine interior point method is extended to handle variables with simple upper bounds as well as free variables. During execution, variables which appear to be going to zero are fixed at zero, and rows with slack variables bounded away from zero are removed. A variant of the big-M artificial variable method to attain feasibility is derived. The simplex method is used to recover an optimal basis upon completion of the algorithm, and the effects of scaling are discussed. Computational experience on a variety of problems is presented. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
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.
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.