bluuebunny/crossref_metadata_2025 huggingface dataset:
Primary and Secondary Route Selection in Backbone Computer Networks
Authors: Pirkul Hasan , Narasimhan Sridhar
Published: October 2008

This paper addresses the problem of selecting primary and secondary routes for every pair of communicating nodes in a backbone computer network. A primary route and a secondary route constitute a route pair. The secondary route is node-disjoint (and hence also link-disjoint) from the primary route. A mathematical programming model is developed whose objective is to select routes to minimize the mean delay faced by messages. The model captures situations where a single link or node failure would divert traffic to the appropriate secondary routes. A solution procedure based on a relaxation of the problem is presented. Computational results indicate the effectiveness of the solution procedure.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Tabu Search for General Zero-One Integer Programs Using the Pivot and Complement Heuristic
Authors: Aboudi Ronny , Jörnsten Kurt
Published: October 2008

Tabu search techniques have been applied to a wide class of optimization problems. Tabu search is a meta procedure that requires a subroutine to find local optima. In most examples of tabu search the subroutine used is problem specific. However, in order to apply tabu search successfully to general 0-1 integer programs, the subroutine must be general. The pivot and complement heuristic is a procedure that frequently finds feasible solutions for general 0-1 integer programs. In this paper we implement several elements of strategies proposed by tabu search method that result in general heuristics for 0-1 integer programs that could be included in an integer programming code. These heuristics employ the ZOOM/XMP implementation of the pivot and complement heuristic as a subroutine. Computational results indicate that these heuristics provide good bounds for many problems.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Numerical Factorization Methods for Interior Point Algorithms
Authors: Jung Ho-Won , Marsten Roy E. , Saltzman Matthew J.
Published: October 2008

Interior point algorithms for linear programming achieve significant reductions in computer time over earlier methods for many large linear programming problems (LPs) and solve problems larger than previously possible. The most computationally intensive step in each iteration of any interior point algorithm is the numerical factorization of a sparse, symmetric, positive definite matrix. In large or relatively dense problems, 80–90% or more of computational time is spent in this step. This study describes our implementations of two algorithms for performing this factorization, the column Cholesky and the multifrontal methods, based on graph theory applied to sparse symmetric matrices. We use advanced techniques such as loop unrolling and equivalent sparse matrix reordering to improve the performance of the factorization step. Our studies are incorporated into an implementation of the primal-dual barrier algorithm. Computational experiments on relatively large LPs on a DEC station 3100 demonstrate that the primal-dual barrier algorithm using our advanced column Cholesky outperforms by 20–60% the same algorithm using a straightforward column Cholesky. Also, our multifrontal method using the loop unrolling technique in a partial inner product routine shows a 10–50% speedup compared with no loop unrolling. The two methods exhibit comparable overall performance.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
The Reactive Tabu Search
Authors: Battiti Roberto , Tecchiolli Giampietro
Published: October 2008

We propose an algorithm for combinatorial optimization where an explicit check for the repetition of configurations is added to the basic scheme of Tabu search. In our Tabu scheme the appropriate size of the list is learned in an automated way by reacting to the occurrence of cycles. In addition, if the search appears to be repeating an excessive number of solutions excessively often, then the search is diversified by making a number of random moves proportional to a moving average of the cycle length. The reactive scheme is compared to a “strict” Tabu scheme that forbids the repetition of configurations and to schemes with a fixed or randomly varying list size. From the implementation point of view we show that the Hashing or Digital Tree techniques can be used in order to search for repetitions in a time that is approximately constant. We present the results obtained for a series of computational tests on a benchmark function, on the 0-1 Knapsack Problem, and on the Quadratic Assignment Problem.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Genetic Algorithms and Random Keys for Sequencing and Optimization
Authors: Bean James C.
Published: October 2008

In this paper we present a general genetic algorithm to address a wide variety of sequencing and optimization problems including multiple machine scheduling, resource allocation, and the quadratic assignment problem. When addressing such problems, genetic algorithms typically have difficulty maintaining feasibility from parent to offspring. This is overcome with a robust representation technique called random keys. Computational results are shown for multiple machine scheduling, resource allocation, and quadratic assignment problems.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
On Exploiting Original Problem Data in the Inverse Representation of Linear Programming Bases
Authors: Gondzio Jacek
Published: October 2008

A method for handling the inverse of linear programming bases is presented. The method extensively exploits the fact that the original problem data (i.e., the constraint matrix) must be stored anyway. It then builds the basis inverse representation of two matrices: an easily invertible submatrix of the constraint matrix (fundamental basis) and a Schur complement containing information on the difference between the fundamental and the current bases. Since the fundamental basis does not have to be stored, the memory space required by the method is limited to that for a small, dense Schur complement. Computational comparisons are made with advanced implementations of LU factorizations with Bartels-Golub updating. Tests performed on real-life linear programs from the Netlib collection indicate that the method may be used for solving large problems.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
CONOPT—A Large-Scale GRG Code
Authors: Drud Arne Stolbjerg
Published: October 2008

CONOPT is a generalized reduced-gradient (GRG) algorithm for solving large-scale nonlinear programs involving sparse nonlinear constraints. The paper will discuss strategic and tactical decisions in the development, upgrade, and maintenance of CONOPT over the last 8 years. A verbal and intuitive comparison of the GRG algorithm with the popular methods based on sequential linearized subproblems forms the basis for discussions of the implementation of critical components in a GRG code: basis factorizations, search directions, line-searches, and Newton iterations. The paper contains performance statistics for a range of models from different branches of engineering and economics of up to 4000 equations with comparative figures for MINOS version 5.3. Based on these statistics the paper concludes that GRG codes can be very competitive with other codes for large-scale nonlinear programming from both an efficiency and a reliability point of view. This is especially true for models with fairly nonlinear constraints, particularly when it is difficult to attain feasibility.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Commentary—Visualization and Optimization: The Future Lies Together
Authors: Bell Peter C.
Published: October 2008

Visualization and optimization are complementary approaches to problem solving, not rivals: a future involving closer integration promises to benefit both areas and to stimulate their development. Jones' important and extensive feature article highlights progress being made on many different dimensions from the perspective of the researcher and scholar. A recent paper by Greenberg[4] augments Jones' article. In order to provide a contrasting view with the objective of stimulating further debate and hopefully some new research, I will try to present the perspective of an important set of “customers” for optimization: senior decision makers who use optimization in solving important problems.

After presenting a view of problem solving using optimization, I will attempt to make the case that visualization is very important to the future of optimization, and that the emergence of visualization presents important opportunities for further developments within optimization.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Rejoinder—Anchoring and Cross-Fertilization
Authors: Jones Christopher V.
Published: October 2008

Rejoinder to commentaries to the author's feature article “Visualization and Optimization.”

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Consistency in Valuation-Based Systems
Authors: Shenoy Prakash P.
Published: October 2008

This paper has three main results. First, we present a new computational technique for checking for inconsistencies in valuation-based systems. This technique is different from the implicit enumeration method of Davis-Putnam and its variants. Our technique uses the divide-and-conquer method of dynamic programming. The computational complexity of this technique depends on the sizes of the valuations and on the graphical structure of the valuation-based system. Second, if a valuation-based system is consistent, we describe a method for generating a model for the system, i.e., an assignment of values for each variable that is consistent with each valuation in the system. Third, if a valuation-based system is inconsistent, we describe a method for isolating a minimal inconsistent set of valuations.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Newton Based Radius Reduction Algorithm for Nearest Point Problems in Pos Cones
Authors: Al-Sultan Khaled S.
Published: October 2008

We develop an interior point algorithm for finding the nearest point in Pos cones to a given point in Rn. The algorithm is based on constructing a sequence of spheres of reduced radii that intersect the cone until a sphere that just touches the cone is found in which case the problem is solved. Implementation of the algorithm and some preliminary computational experience are presented.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Numerical Method for Controlled Routing in Large Trunk Line Networks via Stochastic Control Theory
Authors: Kushner Harold J. , Yang Jichuan
Published: October 2008

The paper discusses a powerful approach to the routing problem in large networks of the trunk line type. The approximations are based on heavy traffic limit theorems. The sequence of suitably scaled available circuits converges to a reflected diffusion process as the network size grows, under reasonable conditions. This limit model contains the basic features of the original network, and provides a very useful basis for a good control strategy for the physical system. The optimal ergodic cost problem for a three (link) dimensional system is solved numerically via the Markov chain approximation method to get the optimal controls. These “three link” results can be approximated in such a way that they can be applied to a physical network of arbitrary size, using only “local” information. Indeed, the numerical approximations have the interpretation of a type of simplified or “aggregated” network, which allows the use of physical intuition in its application. The resulting polities are compared in simulations (on systems with hundreds of links) to other current approaches, and found to be quite competitive and have many advantages.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Perspectives on Simulation Research and Practice
Authors: Kelton W. David
Published: October 2008

This paper discusses recent developments in simulation research, current directions, as well as how research interacts with practice and software development. Among the methodological research areas considered are modeling techniques, generation of random numbers and processes, and statistical design and analysis. Projections for future research are made, and ways in which practice can both benefit from research as well as help guide it are discussed.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Structured Expert System for Model Management in Inventory Control
Authors: Ghiaseddin Nasir , Matta Khalil , Sinha Diptendu
Published: October 2008

The focus of this paper is on the expert system design for inventory control model management. The model selection procedure uses the knowledge of inventory theory as well as user-specific heuristics and approximation rules. The models available in the model base are represented in a model selection tree using information currently present in the inventory control literature. We explore the use of a structured design methodology through incorporating knowledge modules (i.e., sub-expert system) at the nodes of the model selection tree. The knowledge base is also modularized into selection, application, and solution knowledge bases in addition to a database, each with its unique and independent set of rules and/or storage requirements. This structured design reduces the knowledge representation complexity, facilitates the search process and allows for the use of backtracking procedures to select approximate models for the problem. Implementation of the system using the expert system shell GURU is discussed and sample consultation is provided in the appendix.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Computational Study of Satisfiability Algorithms for Propositional Logic
Authors: Harche F. , Hooker J. N. , Thompson G. L.
Published: October 2008

We implement several recent algorithms for the satisfiabiiity problem in propositional logic and test them on a wide variety of benchmark problems. We focus on algorithms based on some kind of tree search, including three versions of the classical Davis-Putnam-Loveland method, the method of Jeroslow and Wang, the Horn Relaxation method of Gallo and Urbani, the branch and cut method of Hooker and Fedjki, and the column subtraction method of Harche and Thompson. We design experiments so as to identify the important factors that influence the performance of tree search algorithms. We find that the choice of which variable to branch on is a key factor. Methods based on weak relaxations (e.g., Horn relaxation) are best for easy problems, and the column subtraction method is clearly the most robust, as it was the only algorithm to solve the hardest problems. if Davis-Putnam-Loveland is properly implemented, it and the remaining methods generally excel on problems that are neither too easy nor too hard.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
An EP Algorithm for Computing a Minimum Weight Perfect Matching for a Set of Points on the Plane
Authors: Osiakwan Constantine K. N. , Akl Selim G.
Published: October 2008

Given a graph induced by an even number of points on the plane, the minimum weight matching problem calls for finding a pairing of all the points such that the sum of the distances between the paired points is the smallest possible. In this paper, we propose a parallel algorithm for this problem. The algorithm is designed for the EREW PRAM model of parallel computation with p processors. For points on the Euclidean and manhattan planes, the algorithm executes in O((n2.5log4n)/p) time, where p ≤ n0.5. The algorithm provides an optimal speedup with respect to the fastest existing sequential algorithm.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Preprocessing and Probing Techniques for Mixed Integer Programming Problems
Authors: Savelsbergh M. W. P.
Published: October 2008

In the first part of the paper, we present a framework for describing basic techniques to improve the representation of a mixed integer programming problem. We elaborate on identification of infeasibility and redundancy, improvement of bounds and coefficients, and fixing of binary variables. In the second part of the paper, we discuss recent extensions to these basic techniques and elaborate on the investigation and possible uses of logical consequences.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Matching Based Exact Algorithm for Capacitated Vehicle Routing Problems
Authors: Miller Donald L.
Published: October 2008

A branch and bound algorithm for capacitated vehicle routing is described. Lower bounds are derived by relaxing the subtour elimination and vehicle capacity constraints to yield a perfect b-matching problem. Bounds are strengthened by using Lagrange multipliers to enforce subtour elimination and capacity constraints. Computational results are reported for problems taken from the literature for sizes up to 61 vertices. With the exception of the 48 vertex instance (att48.vrp), the algorithm solves all problems in TSPLIB having 51 or fewer vertices.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Numerical Inversion of Laplace Transforms of Probability Distributions
Authors: Abate Joseph , Whitt Ward
Published: October 2008

We present a simple algorithm for numerically inverting Laplace transforms. The algorithm is designed especially for probability cumulative distribution functions, but it applies to other functions as well. Since it does not seem possible to provide effective methods with simple general error bounds, we simultaneously use two different methods to confirm the accuracy. Both methods are variants of the Fourier-series method. The first, building on Dubner and Abate (Dubner, H., J. Abate. 1968. Numerical inversion of Laplace transforms by relating them to the finite Fourier cosine transform. JACM 15 115–123.) and Simon, Stroot, and Weiss (Simon, R. M., M. T. Stroot, G. H. Weiss. 1972. Numerical inversion of Laplace transforms with application to percentage labeled experiments. Comput. Biomed. Res. 6 596–607.), uses the Bromwich integral, the Poisson summation formula and Euler summation; the second, building on Jagerman (Jagerman, D. L. 1978. An inversion technique for the Laplace transform with applications. Bell System Tech. J. 57 669–710 and Jagerman, D. L. 1982. An inversion technique for the Laplace transform. Bell System Tech. J. 61 1995–2002.), uses the Post-Widder formula, the Poisson summation formula, and the Stehfest (Stehfest, H. 1970. Algorithm 368. Numerical inversion of Laplace transforms. Comm. ACM 13 479–490 (erratum: 13 624).) enhancement. The resulting program is short and the computational experience is encouraging.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Efficient Computation of Probabilities of Events Described by Order Statistics and Applications to Queue Inference
Authors: Jones Lee K. , Larson Richard C.
Published: October 2008

This paper derives recursive algorithms for efficiently computing event probabilities related to order statistics and applies the results in a queue inferencing setting. Consider a set of N i.i.d. random variables in [0, 1]. When the experimental values of the random variables are arranged in ascending order from smallest to largest, one has the order statistics of the set of random variables. Both a forward and a backward recursive O(N3) algorithm are developed for computing the probability that the order statistics vector lies in a given N-rectangle. The new algorithms have applicability in inferring the statistical behavior of Poisson arrival queues, given only the start and stop times of service of all N customers served in a period of continuous congestion. The queue inference results extend the theory of the “Queue Inference Engine” (QIE), originally developed by Larson in 1990 (Larson, R. C. 1990. The queue inference engine: Deducing queue statistics from transactional data. Management Sci. 36(5) 586–601, and 1991. The queue inference engine: Addendum. Management Sci. 37(6) 1062.). The methodology is extended to a third O(N3) algorithm, employing both forward and backward recursion, that computes the conditional average probability (averaged over all N customers in a congestion period) that the in-queue wait is less than t minutes, given the departure time data and assuming first come, first served service. To our knowledge, this result is the first O(N3) exact algorithm for computing points on the in-queue waiting time distribution function, conditioned on the start and stop time data. The paper concludes with an extension to the computation of certain correlations of in-queue waiting times. Illustrative computational results are included throughout.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Revised Stochastic Complementation Algorithm for Nearly Completely Decomposable Markov Chains
Authors: Mattingly R. Bruce
Published: October 2008

This paper presents a new algorithm which uses stochastic complementation to compute the stationary distribution vector of a nearly completely decomposable (NCD) Markov chain. NCD problems are ill-conditioned, and many methods suffer from loss of accuracy. A formal error analysis and test results from a series of NCD problems are presented which show that the new algorithm computes accurate solutions to this type of problem. Operation counts and timings from experiments are presented which highlight the efficiency of the new algorithm.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Bounds and Approximations for Overheads in the Time to Join Parallel Forks
Authors: Downey Peter J.
Published: October 2008

This paper studies the effects of overheads in massively parallel processing. The execution times for tasks on individual processors are modeled as independent and identically but arbitrarily distributed random variables. The time to execute a process fork is assumed to be distributed exponentially. The main result bounds (in expectation) the overhead time in forking a large number of tasks across n machines and then waiting for the join event. The model used is appropriate for massive parallelism (when n is large): in fact, the bound serves as a heavy traffic limit approached as n→ ∞ and for task times that are large in comparison to the time to execute a fork. In this model, the expected total time to reach the final join consists of a forking overhead that grows linearly with the number of processors n, a time for parallel execution of tasks that decreases in n, and finally a synchronization delay that is a concave sublinear function of ρ = EX/EA, which is the ratio of expected task time to the expected time needed to fork a new process. This overhead function is typically no worse than o(ρ). An interesting aspect of the analysis is that the original problem reduces to a previously studied problem in queueing theory: estimating total end-to-end delay in an infinite-server resequencing system. The new results thus provide new bounds and heavy-traffic approximations (in distribution and in expectation) for the theory of M/GI/∞ resequencing queues.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Matching Identification Problem: A Knowledge Acquisition Approach
Authors: Mehrez Abraham , Steinberg Geoffrey
Published: October 2008

This paper is concerned with an identification problem of a set of K out of N numbers. Two parties are involved in the identification process, the inquirer and the respondent. The set to be identified is referred to as the chosen subset and it is known only to the respondent. The identification process involves the inquirer who wishes to identify the chosen subset by asking a series of questions. At each question the inquirer selects a subset of K elements out of N, the inquired subset, and receives from the respondent partial information about the number of elements which belongs to both the inquired subset and the chosen subset. The questions continue until the chosen subset is identified. A possible application of the problem is related to learning games. Two types of algorithms, which are independent of each other and aimed at identifying the chosen subset, are presented in this paper. Type I algorithms (uncertainty reduction) select only subsets that have not yet been rejected as being the chosen subset. A linear integer programming model is employed to identify the set of subsets that have not yet been rejected—the uncertainty set. For Type I algorithms two different decision rules are considered to select a subset. Each decision rule selects the elements of the next inquired subset by employing a different probabilistic argument: 1) randomly select the next subset from among the subsets not yet ruled out, or 2) select as the next subset the one whose elements occur most frequently among the subsets not yet ruled out. Type II algorithms (static and dynamic processing) select a subset according to a different principle which allows the inquirer to select a subset that may not belong to the uncertainty set. This is accomplished by marginally interchanging the elements of any two successive subsets. Analytical solutions are provided for algorithms of Type II. Furthermore, a comparison between the two types of algorithms under different measures of performance, such as the expected number of questions (subsets) required to identify the chosen subset, is conducted through a simulation analysis.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Incorporating the Majority Consensus Concurrency Control Mechanism into the Database Allocation Problem
Authors: Ram Sudha , Narasimhan Sridhar
Published: October 2008

The problem of database allocation incorporating a specific concurrency control mechanism and queuing delays is addressed in this paper. A mathematical model is presented to aid designers in the development of distributed database systems. The model takes into account the pattern of usage of the databases, communication costs in the network, costs for maintaining consistency among the various copies of a database, and storage costs. A solution procedure based on the principle of Lagrangian relaxation is proposed to solve the model. Some analysis of the model is reported along with several useful observations.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Access Path Optimization in Relational Joins
Authors: Gopal Ram D. , Ramesh R. , Zionts Stanley
Published: October 2008

The objective of access path optimization in relational joins is to minimize the number of pages accessed in performing a join, since the cost of data retrieval from disk accounts for most of the join processing costs. We develop an efficient approach to access path optimization by modeling an access path as a tree traversal process. Two join algorithms are developed using this model. The access path is stored as a compact index relation, which requires absolutely minimal storage. The join is easily materialized by reading the index relation sequentially, and performing the operations coded in its tuples in their serial order. The proposed approach is shown to result in globally minimal page accesses in certain classes of joins. Using a detailed probabilistic analysis and computational study, the proposed approach is shown to be much superior to the state-of-the-art join optimization methods for a general class of joins.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Interval Graph Problems on Reconfigurable Meshes
Authors: Olariu S. , Schwing J. L. , Zhang J.
Published: October 2008

A graph G is an interval graph if there is a one-one correspondence between its vertices and a family I of intervals, such that two vertices in G are adjacent if and only if their corresponding intervals overlap. In this context, the family I of intervals is referred to as an interval model of G. Recently, a powerful architecture called the reconfigurable mesh has been proposed: in essence, a reconfigurable mesh consists of a mesh-connected architecture augmented by a dynamically reconfigurable bus system. In this paper, we exploit the reconfigurable mesh architecture for the purpose of obtaining constant-time algorithms for a number of computational problems on interval graphs. These problems include finding a maximum size independent set, a minimum clique cover, a minimum size dominating set, a shortest path between any two vertices in G, the diameter and the center of G, as well as Breadth-First Search and Depth-First Search trees for G. Specifically, with an n-vertex interval graph specified by its interval model as input, all our algorithms run in constant time on a reconfigurable mesh of size n × n.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Performance Issues for the Iterative Solution of Markov Decision Processes on Parallel Computers
Authors: Archibald T. W. , McKinnon K. I. M. , Thomas L. C.
Published: October 2008

This paper analyses the implementation of an iterative solution method for Markov decision processes on distributed memory multiple instruction multiple data (MIMD) parallel processors. To preserve the good convergence properties of this method a parallel algorithm must be synchronous and the aim of this paper is to understand the factors which influence the efficiency of synchronous parallel algorithms for iterative methods. Models are developed for processor communication time, processor calculation time and overall run time which are also appropriate for other iterative methods. Such iterative methods are used in many other problem areas, including dynamic programming and the solution of linear and differential equations. The timing models guide the development of a phased pipeline algorithm. For 60,000 state sparse Markov decision processes using 121 processors, this algorithm gives 60-fold speed-ups relative to the best sparse serial algorithm.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Commentary—Simulation of Algorithms for Performance Analysis
Authors: L'Ecuyer Pierre
Published: October 2008

This is a commentary and a complement to the McGeoch’s feature article. Certain topics of current interest related to modeling, statistical output analysis, efficiency improvement, and random number generation, for stochastic discrete-event simulation is presented.
Commentary—On Algorithm Analysis
Authors: Shier Douglas R.
Published: October 2008

This is a commentary to the McGeoch's feature article. The objective is to reinforce certain issues and to suggest conceptual framework for future exploration.
Isomorphic Routing on a Toroidal Mesh
Authors: Mao Weizhen , Nicol David M.
Published: October 2008

We study a routing problem that arises on SIMD parallel architectures whose communication network forms a toroidal mesh. We assume there exists a set of k message descriptors {(xi, yi) ∣ i = 1, 2, …, k}, where (xi, yi) indicates that the ith message's recipient is offset from its sender by xi hops in one mesh dimension, and yi hops in the other. Every processor has k messages to send, and all processors use the same set of message descriptors. The SIMD constraint implies that at any routing step, every processor is actively routing messages with the same descriptors as any other processor. We call this Isomorphic Routing. Our objective is to find the isomorphic routing schedule with the minimum makespan. We consider a number of variations on the problem, yielding complexity results from O(k) to NP-complete. Most of our results follow after we transform the problem into a scheduling problem, where it is related to other well-known scheduling problems.
Perturbation: An Efficient Technique for the Solution of Very Large Instances of the Euclidean TSP
Authors: Codenotti Bruno , Manzini Giovanni , Margara Luciano , Resta Giovanni
Published: October 2008

In this paper we introduce a technique for developing efficient iterated local search procedures and we apply it to solve very large instances of the Euclidean Traveling Salesman Problem (TSP). This technique, which we call perturbation, uses global information on TSP instances to speed-up the computation and to improve the quality of the tours found by heuristic methods. The main idea is to escape from local optima by introducing perturbations in the problem instance rather than in the solution. The performance of our algorithms has been tested and compared with known methods. To this end, we have executed a number of experiments both on available benchmarks, for which the optimal tour length is known, and on randomly generated instances, for which the comparison is done with the Held-Karp lower bound. The experimental results, performed on up to 100,000 cities, show that our algorithms outperform the known methods for iterating local search for very large instances.
A Fast Composite Heuristic for the Symmetric Traveling Salesman Problem
Authors: Renaud Jacques , Boctor Fayez F. , Laporte Gilbert
Published: October 2008

This article describes a new composite heuristic for the symmetric Traveling Salesman Problem. The heuristic consists of three phases: construction of an initial envelope, insertion of the remaining vertices, and improvement procedure. The heuristic is shown to perform very well both on randomly generated instances and on TSPLIB problems.
Stopping Criteria for Finite Length Genetic Algorithms
Authors: Aytug Haldun , Koehler Gary J.
Published: October 2008

Considerable empirical results have been reported on the computational performance of genetic algorithms but little has been studied on their convergence behavior or on stopping criteria. In this paper we derive bounds on the number of iterations required to achieve a level of confidence to guarantee that a genetic algorithm has seen all populations and, hence, an optimal solution.
A Branch and Cut Algorithm for a Steiner Tree-Star Problem
Authors: Lee Youngho , Chiu Steve Y. , Ryan Jennifer
Published: October 2008

This paper deals with a Steiner tree-star problem that is a special case of the degree constrained node-weighted Steiner tree problem. This problem arises in the context of designing telecommunications networks for digital data service, provided by regional telephone companies. In this paper, we develop an effective branch and cut procedure coupled with a suitable separation procedure that identifies violated facets for fractional solutions to the relaxed formulation. Computational results indicate that large problem instances with up to 200 nodes can be solved within acceptable time bounds.
Experience with a Cutting Plane Algorithm for the Capacitated Spanning Tree Problem
Authors: Hall Leslie
Published: October 2008

A basic problem in telecommunications network design is that of designing a capacitated centralized processing network. Such a network has a central processor that must be linked via a tree topology to several remote terminals that have specified demands. Each subtree off of the root is constrained to have at most a fixed, limited demand, represented by the sum of the demands of the nodes of the subtree. Finding provably optimal solutions to this class of problems has been surprisingly difficult, particularly for certain types of instances and choices of parameters. This paper presents computational results for the problem, based on a cutting plane algorithm. We first focus on the unit-demand case, known as the capacitated spanning tree problem, for which we present computational experience on a range of instances with up to 200 nodes. We then consider the general-demand case and report on branch-and-cut as well as cutting plane computations on a range of instances, including some from the vehicle routing literature.
Selecting Ingot Sizes for Joint Production of Sheet Products
Authors: Balakrishnan Anantaram , Gopalakrishnan Srimathy
Published: October 2008

This paper addresses a tactical planning problem of selecting standard ingot sizes to facilitate joint processing of finished sheets in a make-to-order aluminum sheet manufacturing plant. The facility has traditionally dedicated one ingot to each item ordered but is now considering producing multiple items from each ingot to reduce excess metal and exploit economies of scale in processing costs. The effectiveness of this joint processing strategy depends on the available standard ingot sizes. We develop an integer programming model to decide ingot sizes, given the projected demand and technological/operational constraints on combining orders. The model selects a prespecified number of standard sizes and determines which combinations to use to satisfy the demand for all products. The objective is to minimize the total weight of excess metal. We describe a dual-ascent method to generate lower bounds for the problem and heuristic procedures to identify good solutions. Computational results for test problem instances based upon data from an aluminum sheet manufacturer confirm the effectiveness of the algorithm; on average, the gaps between the upper and lower bounds are about 4%. We also illustrate how the model can be used to perform sensitivity analyses.
Inventory Management in Catalog Sales Companies
Authors: Bitran Gabriel R. , Mondschein Susana V.
Published: October 2008

One of the main features of the catalog sales industry is the ability to influence demand through the mailing policies. This characteristic forces catalog managers to define coordinated strategies between mailing and inventory decisions. In this paper we study inventory policies for each item promoted in the catalog, taking into account the mailing policies. For this purpose, we analyze two different approaches: the global and hierarchical models. Both approaches consider the dynamic and stochastic nature of the problem. Special emphasis is given to the development of a feedback strategy between the tactical and operational levels, in the hierarchical approach, to avoid “infeasibilities” induced mainly by inventory imbalances. Given the complexity of the formulations, we develop heuristics based on the optimal solutions of particular problems. Preliminary computational results show that these heuristics have a satisfactory performance when compared with an upper bound derived for the problem. These results also show that the hierarchical approach has an excellent performance when one feedback from the operational to the tactical level is allowed. This interaction mimics what is usually observed in practice.
Methodology for Stochastic Graph Completion-Time Problems
Authors: Jayawardena T. , Yakowitz S.
Published: October 2008

Assume a completion time T0 and a graph having edges with randomly chosen weights are specified. Each time an edge is traversed, the weight is selected at random, according to a fixed probability law indexed by that edge. Successive observations are independent, and independent of realizations at other edges. We consider the stochastic shortest path and traveling salesman problems of finding paths which maximize the probability of completion by the specified time. The methodology combines techniques of machine learning with the “k-opt” heuristic. The algorithm is supported by convergence analysis, and is also shown in computational experiments to be successful for randomized versions of TSP problems already in the literature and having from 10 to 57 vertices. To our knowledge, this success is well beyond other computational stochastic traveling salesman studies reported elsewhere. A feature of the algorithm is that the distributions of the random edge weights need not be specified, and so the technique is suited to on-line operation.
A Column Generation Approach for Graph Coloring
Authors: Mehrotra Anuj , Trick Michael A.
Published: October 2008

We present a method for solving the independent set formulation of the graph coloring problem (where there is one variable for each independent set in the graph). We use a column generation method for implicit optimization of the linear program at each node of the branch-and-bound tree. This approach, while requiring the solution of a difficult subproblem as well as needing sophisticated branching rules, solves small to moderate size problems quickly. We have also implemented an exact graph coloring algorithm based on DSATUR for comparison. Implementation details and computational experience are presented.
An Improved Algorithm for Approximating the Performance of Stochastic Flow Networks
Authors: Jarvis James P. , Shier Douglas R.
Published: October 2008

A problem encountered in the analysis of communication and other distribution systems is evaluating the performance of the system in meeting user demands with available resources. We consider the case in which user demands and available resources are only known stochastically and connecting links can operate at various levels. This situation can be modeled as a two-terminal stochastic network flow problem, in which each edge of the network assumes a finite number of values (corresponding to different capacity levels) with known probabilities. For each state of the network, we are interested in the maximum demand that can be met using the best allocation of resources. The approach used here to estimate the average unmet demand involves generating only “high leverage” states of the system—states having high probability and/or high values of unmet demand. A new algorithm is proposed for generating such states in monotone order, either by probability or by unmet demand. Bounds on the performance of the network are investigated.
An Implementation of LPFORM
Authors: Ma Pai-Chun , Murphy Frederic H. , Stohr Edward A.
Published: October 2008

This paper describes a Microsoft Windows-based system, LPFORM, that uses a graphical interface to assist a linear programming modeler in formulating and managing models. The system facilitates model building by providing multiple views of models during formulation and model interrogation, methods for model integration and a relational database for handling model data. The prototype demonstrates how such a system can enhance the work of model builders in a Windows environment.
Art Gallery Problems for Convex Nested Polygons
Authors: Bhadury J. , Chandru V. , Maheshwari A. , Chandrasekaran R.
Published: October 2008

In this article, we study a class of Art Gallery problems that are defined on a pair of convex nested polygons. Polynomial time algorithms are presented for all these problems, by reducing them to the Circle Covering problem, or by relating them to the Minimal Nested Polygon problem. Then it is shown that these problems can also be solved in polynomial time by formulating them as Integer Programs with the Circular Ones property. Finally the paper discusses how these algorithms can be efficiently implemented in parallel.
Bad Lattice Structures for Vectors of Nonsuccessive Values Produced by Some Linear Recurrences
Authors: L'Ecuyer Pierre
Published: October 2008

Usually, the t-dimensional spectral test for linear congruential generators examines the lattice structure of all the points formed by taking t successive values in the sequence. In this article, we consider the case where the t values taken are not successive, but separated by lags that are chosen a priori. For certain classes of linear congruential and multiple recursive generators, and for certain choices of the lags, we give lower bounds on the distance between hyperplanes. In some cases, those lower bounds are quite large, even in dimensions as small as t = 3. We give illustrations with specific classes of generators that have been proposed in the literature, and discuss the possible implications.
Toward a Taxonomy of Parallel Tabu Search Heuristics
Authors: Crainic Teodor Gabriel , Toulouse Michel , Gendreau Michel
Published: October 2008

In this paper we present a classification of parallel tabu search metaheuristics based, on the one hand, on the control and communication strategies used in the design of the parallel tabu search procedures, and on the other hand, on how the search space is partitioned. These criteria are then used to review the parallel tabu search implementations described in the literature. The taxonomy is further illustrated by the results of several parallelization implementations of a tabu search procedure for multicommodity location-allocation problems with balancing requirements.
Earliness-Tardiness Scheduling Around Almost Equal Due Dates
Authors: Hoogeveen J. A. , van de Velde S. L.
Published: October 2008

The just-in-time concept in manufacturing has aroused interest in machine scheduling problems with earliness-tardiness penalties. In particular, common due date problems, which are structurally less complicated than problems with general due dates, have emerged as an interesting and fruitful field of research. We prove that so-called almost common due date problems, in which the due date dj and processing time pj of each job Jj(j = 1, …, n) are such that dj ∈ [D, D + pj] for some constant D, are structurally less complicated also. Our main contribution is an O(n2) time dynamic programming algorithm for the almost common due date problem with large D. The dynamic programming algorithm is interesting in its own right, since the optimality principle behind it applies to other common due date and almost common due date problems as well.
OR/SM: A Prototype Integrated Modeling Environment Based on Structured Modeling
Authors: Wright Gordon P. , Dan Worobetz N. , Kang Myong , Mookerjee Radha V. , Chandrasekharan Radha
Published: October 2008

This article describes the design and implementation of (OR/SM), a computerized modeling environment based on Structured Modeling. The uniqueness of OR/SM is in the following: (1) the use of oracle Tools and Database as the delivery platform; (2) automatic and interactive links to sas, a powerful and widely used commercial statistical analysis software system and optimization solver; and (3) an interactive link to qs (Quantitative Systems)—a commercial software package for solving a wide range of operations management models. Some other key features are: (1) automatic generation of relational database tables for model data; (2) interactive checking of model syntax and semantics; and (3) automatic generation of several reference documents. Examples from blending, inventory control, and marketing mix management are used to illustrate the capabilities of OR/SM.