bluuebunny/crossref_metadata_2025_split huggingface dataset:
Parallel Taboo Search Techniques for the Job Shop Scheduling Problem
Authors: Taillard Éric D. 
Published: October 2008

We apply the global optimization technique called taboo search to the job shop scheduling problem and show that our method is typically more efficient than the shifting bottleneck procedure, and also more efficient than a recently proposed simulated annealing implementation. We also identify a type of problem for which taboo search provides an optimal solution in a polynomial mean time in practice, while an implementation of the shifting bottleneck procedure seems to take an exponential amount of computation time. Included are computational results that establish new best solutions for a number of benchmark problems from the literature. Finally, we give a fast parallel algorithm that provides good solutions to very large problems in a very short computation time. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Fast Clustering Algorithms
Authors: Dorndorf Ulrich , Pesch Erwin 
Published: October 2008

This paper considers the problem of partitioning the vertices of a weighted complete graph into cliques of unbounded size and number, such that the sum of the edge weights of all cliques is maximized. The problem is known as the clique-partitioning problem and arises as a clustering problem in qualitative data analysis. A simple greedy algorithm is extended to an ejection chain heuristic leading to optimal solutions in all practical test problems known from literature. The heuristic is used to compute an initial lower bound as well as to guide branching in a branch and bound algorithm which is superior to present exact methods. Empirical data for all three algorithms are reported. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Double-Layered Learning Approach to Acquiring Rules for Classification: Integrating Genetic Algorithms with Similarity-Based Learning
Authors: Sikora Riyaz , Shaw Michael 
Published: October 2008

In this paper, we describe a machine learning technique based on a double-layered architecture and Genetic Algorithms (GAs), which can be used to learn decision rules for financial classification. Once the rules have been acquired, they can be stored in an expert system for future application. Genetic algorithms represent a class of learning algorithms modeled on the biological evolution process. Equipped with unique search behavior and solution-seeking properties, they provide an interesting technique for such classification tasks as bankruptcy prediction and credit analysis. However, some modifications to the basic genetic algorithms are necessary in order to make the method suitable for solving these classification problems. One of the objectives of this paper is to develop a representation scheme for the concepts to be learned that can be incorporated in a genetic algorithm. More importantly, we expand on the concept of the genetic algorithm and develop a learning method called the Double-layered Learning System (DLS) that integrates the genetic algorithm with a similarity-based learning technique called the Probabilistic Learning System (PLS1). By combining a learning paradigm that searches through the “hypothesis space” (GA) with a paradigm that searches through the “instance space” (PLS1), DLS permits synergistic improvement of the learning performance. We demonstrate the feasibility of such a hybrid approach computationally by presenting the design, implementation, and performance evaluation of DLS. DLS proves to be an effective improvement over both GA and PLS1. The efficacy of the results points towards the importance of such hybrid approaches in providing more robust machine learning methods. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Feature Article—Visualization and Optimization
Authors: Jones Christopher V. 
Published: October 2008

Research in optimization has developed faster and faster algorithms that have analyzed very complicated problems, thereby saving billions of dollars. Solving problems using optimization techniques involves more than just developing clever algorithms, however. Building, debugging, validating, and understanding models, algorithms, data, and solutions require appropriate representations of the models, the algorithms, the data, and the solutions. This paper explores current practice and ongoing research in different representations or visualizations useful for representing optimization models, understanding optimization algorithms, validating and exploring optimal solutions, and summarizing the results. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Commentary—The Promise of OR is Helping to Solve Problems
Authors: Greenberg Harvey J. , Murphy Frederic H. 
Published: October 2008

When you were learning optimization, how many times did you draw pictures to help you understand what was happening? When you now obtain results from an optimization model, how many times do you draw sketches and form mental pictures of what the solution means? When the solution does not look right, how often do you use this process of visualization to help you debug the model or this instance of it? INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Commentary—Designing Tools for Visualization and Optimization
Authors: Keiper Jerry , Wickham-Jones Tom 
Published: October 2008

What does the future hold for the visualization aspects of optimization? Christopher Jones's article reviews current work and makes predictions for the future. At Wolfram Research both of us have been engaged on the Mathematica® project[6] for most of its life. Through our work, we have gained much experience and insight into the development of integrated mathematical software. Many of the lessons that we have learned can be directly applied to the applications Jones foresees. In his article, Jones reviews some of the ways in which visualization is crucial to operations research (OR). The simplest of these involves the effective presentation of OR results while, for more complex uses, visualization is a key element of the solution process itself. A more specialized use involves the role of visualization in developing new OR algorithms. As visualization techniques are developed and become more widespread on existing computer systems, the use of visualization in OR will become more widely used and more sophisticated. For these ideas to reach their full potential, new tools and new techniques must be developed and embodied in actual applications. One important way this happens is through the efforts of the commercial software world. In recent years, there has been an active area of enterprise leading to the rise of whole new classes of mathematical software products. Typical applications cover the areas of statistics, graphics, and computer algebra as well as general mathematics. As an aside, it is interesting to speculate on the relationship between work in academic research institutions and the creation of these products. Because Wolfram Research is one of the key players in this field, it is interesting to consider the points that Jones makes and to compare them with our own experience. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Experimental Evaluation of a Procedure for Estimating Nonhomogeneous Poisson Processes Having Cyclic Behavior
Authors: Johnson Mary A. , Lee Sanghoon , Wilson James R. 
Published: October 2008

This paper summarizes an experimental evaluation of a procedure for estimating a nonhomogeneous Poisson process having an exponential rate function, where the exponent may include both polynomial and trigonometric components. Maximum likelihood estimates of the unknown continuous parameters of the rate function are obtained numerically, and the degree of the polynomial rate component is determined by a likelihood ratio test. Our evaluation is limited to the case of a known frequency. To examine the small- and large-sample behavior of the estimation procedure for many types of time-dependent arrival processes encountered in previous work, we performed 100 independent replications of twelve selected Poisson processes over two observation intervals. On each replication of each case, we applied the fitting procedure to estimate the parameters of the target process; and we computed the corresponding estimates of the rate and mean-value functions over the observation interval. Evaluation of the fitting procedure was based on plotted tolerance bands for the rate and mean-value functions together with summary statistics for the maximum and average absolute estimation errors in these functions over the observation interval. The experimental results provide substantial evidence of the procedure's numerical stability and practical usefulness. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A GRASP for the Vehicle Routing Problem with Time Windows
Authors: Kontoravdis George , Bard Jonathan F. 
Published: October 2008

This paper addresses the problem of finding the minimum number of vehicles required to visit a set of nodes subject to time window constraints. A secondary objective is to minimize the total distance traveled. Each node requires a predetermined amount of service in the form of pickups and deliveries. The fleet is homogeneous and is located at a common depot. Vehicle capacity is finite and split service is not permitted. A greedy randomized adaptive search procedure (GRASP) is used to obtain feasible solutions. Results are reported for standard 100 node data sets as well as for a number of real-world problems with up to 417 customers. The findings indicate that, in general, the proposed procedure outperforms current techniques and requires only a small fraction of the time taken by exact methods. To gauge the quality of the solutions, three different lower bounding heuristics were developed. The first considers the “bin packing” aspect of the problem with regard to vehicle capacity; the second is based on the maximum clique associated with the customers' incompatibility graph; the third independently exploits the time window constraints. Using these heuristics, it is empirically demonstrated that the optimum is found in almost all cases involving balanced service and tight capacity constraints and a significant proportion of the remainder. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Comparisons Between Aggregation/Disaggregation and a Direct Algorithm for Computing the Stationary Probabilities of a Markov Chain
Authors: Heyman Daniel P. , Goldsmith Meredith J. 
Published: October 2008

Aggregation/disaggregation is an iterative scheme that leads to an algorithm for computing the steady-state distribution of a finite Markov chain. The idea is to partition the states into aggregates, estimate the probability that the Markov chain is in a particular aggregate, and then estimate the conditional probability of being in each state of an aggregate given that the Markov chain is in some state in that aggregate. Previous computational performance studies of this algorithm concentrated on applying it to chains that were nearly decomposable. We focus on chains that are not nearly decomposable. We compare this iterative algorithm to a direct method that is a variant of Gaussian elimination. We use a variety of test problems that range in size from 500 to 5,000 states, and which include unstructured and banded matrices. We conclude that, for this array of problems, the direct method requires less computation. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Preprocessing in Stochastic Programming: The Case of Capacitated Networks
Authors: Wallace Stein W. , Wets Roger J-B 
Published: October 2008

We investigate different preprocessing procedures for stochastic linear programs whose recourse stage involves directed capacitated networks. The procedures are aimed to help the modeling process, but there are important computational implications as well. We discuss how to check if the problem is tight or loose in terms of feasibility, and we demonstrate how to achieve relatively complete recourse. As a result of our developments, we obtain a computationally feasible way of finding all relevant inequalities required by the Gale and Hoffman theorem on feasibility in networks. Computational results are detailed. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Spectral Analysis of Basic TES Processes
Authors: Jagerman David L. , Melamed Benjamin 
Published: October 2008

This paper studies the spectral properties of a class of stochastic sequences generated by basic TES (Transform-Expand-Sample) methods, as well as transformed TES sequences. A TES sequence is obtained as a marginally uniform process from an autoregressive scheme with modulo-1 reduction, followed by additional transformations. We derive formulas for the spectral density function and the spectral distribution function which are suitable for efficient numerical computation. A set of examples is calculated and exhibited for TES processes with uniform and exponential marginals. The results contribute to the understanding of TES sequences as models of autocorrelated sequences, particularly in a Monte Carlo simulation context. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Expressing Special Structures in an Algebraic Modeling Language for Mathematical Programming
Authors: Fourer Robert , Gay David M. 
Published: October 2008

A knowledge of the presence of certain special structures can be advantageous in both the formulation and solution of linear programming problems. Thus it is desirable that linear programming software offer the option of specifying such structures explicitly. As a step in this direction, we describe extensions to an algebraic modeling language that encompass piecewise-linear, network and related structures. Our emphasis is on the modeling considerations that motivate these extensions, and on the design issues that arise in integrating these extensions with the general-purpose features of the language. We observe that our extensions sometimes make models faster to translate as well as to solve, and that they permit a “column-wise” formulation of the constraints as an alternative to the “row-wise” formulation most often associated with algebraic languages. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Optimal Scheduling of Tasks on Identical Parallel Processors
Authors: Dell’Amico Mauro , Martello Silvano 
Published: October 2008

We consider the classical problem of scheduling n tasks with given processing time on m identical parallel processors so as to minimize the maximum completion time of a task. We introduce lower bounds, approximation algorithms and a branch-and-bound procedure for the exact solution of the problem. Extensive computational results show that, in many cases, large-size instances of the problem can be solved exactly. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
On the Asymptotic Optimality of Multiprocessor Scheduling Heuristics for the Makespan Minimization Problem
Authors: Han Sunan , Hong Dawei , Leung Joseph Y.-T. 
Published: October 2008

The asymptotic performance of heuristic algorithms for the multiprocessor scheduling problem is considered. Let rLS denote the ratio of the makespan of any list schedule to the optimal makespan. Let m denote the number of processors and n the number of jobs. We show that the mean and variance of rLS have upper bounds which approach 1 and 0, respectively, at a rate of O(m log n/n), under the assumption that job processing times are independent, identically distributed according to any distribution F over (0, ∞) with ∫(0,∞) eαtdF(t) < ∞ for some α > 0. If the processing times are distributed over (0, 1], a slightly faster convergence rate of O(m/n) is obtained. Furthermore, we show that almost surely, rLS approaches 1 at a rate faster than O(m/n1−β) for any 0 < β < 1. Similar results are also obtained for the Multifit algorithm due to Coffman, Garey and Johnson. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Analyzing the Pooling Problem
Authors: Greenberg Harvey J. 
Published: October 2008

The pooling problem is a non-convex mathematical program that arises in blending materials to produce products, such as the blending of crude or refined petroleum. Each material has a set of attributes with associated qualities, such as percentage sulfur and octane rating. Pool qualities are determined by a flow-weighted average of the source qualities, and product qualities are similarly defined by a flow-weighted average of pool qualities. Product qualities are constrained to lie in specified ranges. The pooling problem is to minimize the total cost of flows, subject to flow and quality constraints. Present solution methods are based on sequential linear programming, and sensitivity analysis relies upon Lagrange multipliers. These methods are not exact and can lead to erroneous conclusions. A new method is presented that is based upon computational geometry, which provides exact answers to questions of sensitivity analysis and infeasibility diagnosis. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Single Machine Scheduling to Minimize Total Weighted Late Work
Authors: Hariri A. M. A. , Potts C. N. , Van Wassenhove L. N. 
Published: October 2008

In the problem of scheduling a single machine to minimize total weighted late work, there are n jobs to be processed for which each has an integer processing time, a weight and a due date. The objective is to minimize the total weighted late work, where the late work for a job is the amount of processing of this job which is performed after its due date. An O(n log n) algorithm is derived for the preemptive total weighted late work problem. For non-preemptive scheduling, efficient algorithms are derived for the special cases in which all processing times are equal and in which all due dates are equal. A pseudopolynomial algorithm is presented for the general non-preemptive total weighted late work problem. Also, a branch and bound algorithm in which lower bounds are obtained using the dynamic programming state-space relaxation method is proposed for this general problem. Computational results with the branch and bound algorithm for problems with up to 700 jobs are given. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Primal-Dual and Primal Interior Point Algorithms for General Nonlinear Programs
Authors: Lasdon Leon S. , Plummer John , Yu Gang 
Published: October 2008

An interior point algorithm for general nonlinear programs is presented. Inequality constraints are converted to equalities with slack variables. All bounds are handled with a barrier term in the objective. The Kuhn-Tucker system of the resulting equality constrained barrier problem is solved directly by Newton's Method. Primal-Dual, Primal, and Primal-Dual with trust region variants are developed and evaluated. An implementation which utilizes the true Lagrangian Hessian and exploits Jacobian and Hessian sparsity is described. Computational results are presented and discussed. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Load Balancing in Hypercube Solution of Stochastic Optimization Problems
Authors: Berland Nils Jacob 
Published: October 2008

In some stochastic optimization problems the error bounds computed for the expected optimum can be decreased through recursive divide-and-conquer methods based on partitioning the support of the random variables. Each generated partition from the divide-and-conquer process can be treated independently. This class of problems is therefore easy to parallelize, and we describe two parallel implementations of this divide-and-conquer algorithm applied to PERT. Our results indicate that parallel processing and divide-and-conquer are indeed feasible and efficient for problems of this type. The tests were done on an Intel iPSC/2 multicomputer with 16 nodes. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Parallel Search Algorithms for Discrete Optimization Problems
Authors: Grama Ananth , Kumar Vipin 
Published: October 2008

Discrete optimization problems (DOPs) arise in various applications such as planning, scheduling, computer aided design, robotics, game playing and constraint directed reasoning. Often, a DOP is formulated in terms of finding a (minimum cost) solution path in a graph from an initial node to a goal node and solved by graph/tree search methods. Availability of parallel computers has created substantial interest in exploring parallel formulations of these graph and tree search methods. This article provides a survey of various parallel search algorithms such as Backtracking, IDA*, A*, Branch-and-Bound techniques and Dynamic Programming. It addresses issues related to load balancing, communication costs, scalability and the phenomenon of speedup anomalies in parallel search. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Data-Parallel Implementations of Dense Simplex Methods on the Connection Machine CM-2
Authors: Eckstein Jonathan , Boduroğlu İ. İlkay , Polymenakos Lazaros C. , Goldfarb Donald 
Published: October 2008

We describe three data-parallel implementations of the simplex method for dense linear programming problems. The first implementation uses a full tableau and the most-negative reduced cost pivot rule, the second uses a tableau and the steepest-edge pivot rule, and the third is a revised method with explicit inverse. All are implemented on a Connection Machine CM-2 massively parallel computer system, using a variant of Fortran 90. Using special data structures called stripe arrays, we produce efficient implementations. We compare the implementations to one another and to MINOS 5.4 on a Sun workstation. Test problems are from NETLIB, supplemented by a few additional, genuinely dense models from real applications. An appendix also gives recent results on the Connection Machine CM-5. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.