bluuebunny/crossref_metadata_2025 huggingface dataset:
The Distribution Problem with Carrier Service: A Dual Based Penalty Approach
Authors: Diaby Moustapha , Ramesh R.
Published: October 2008

The distribution problem with carrier service is an important optimization problem that often arises in vehicle routing. The problem arises in the distribution of commodities from a central facility to a set of geographically distributed locations. Each location has a certain demand, the distribution vehicle has a load capacity, and the entire operation should be completed within a certain time. An outside carrier is available for direct service of locations from the central facility. The problem is to determine a feasible tour for the company vehicle and the locations to be served by the outside carrier such that the total cost of the operations is minimized. We model this problem and develop a solution technique using valid inequalities. A key feature of the solution approach is that it can easily be extended to solve similar problems with any type and number of side constraints as encountered in the current model. The algorithm has been extensively tested and computational results for problems having up to 200 locations are presented. The results show that the proposed approach is efficient and viable for solving problems of medium to large size. We also present a real-world application, and show how the model is implemented within the framework of an order scheduling and vehicle routing system. We present performance results with real-world data and demonstrate the operational efficiency achieved by using the proposed approach.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Hulls and Efficient Sets for the Rectilinear Norm
Authors: Chhajed Dilip , Chandru Vijay
Published: October 2008

Given a set of points on the plane, we study the structure of their rectilinear hull. We also consider the multiple objective decision of identifying a facility location that minimizes the rectilinear distance to each of these points. We show specific correspondences between the efficient (non-dominated) solutions to the location problem and the rectilinear hulls of point sets in the plane.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Disjoint Paths in the Plane
Authors: Liebling Th. M. , Margot F. , Müller D. , Prodon A. , Stauffer L.
Published: October 2008

Given n pairs of points in the Euclidean plane, we address the problem of finding paths of minimum length linking the pairs that can be made disjoint by infinitesimal deformations. We present and compare several fast heuristics and their implementation.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Stability of p-Persistent CSMA/CD
Authors: Park June S. , Bartoszyński Robert , Rosenkrantz Walter A.
Published: October 2008

A semi-Markovian model is developed for slotted p-persistent CSMA/CD with a finite population of buffered users. A subsequence of the queuing process at embedded Markov epochs is characterized as a multidimensional, nonnegative random walk which is spatially homogeneous and uniformly downward bounded. Sufficient conditions for ergodicity, recurrence and transience of the queuing process are obtained using multidimensional Lyapunov functions, and also by a supermartingale method of independent interest. For the CSMA/CD system with symmetric users, the stability conditions are evaluated in parameters based on an exact joint probability generating function of the random drift. Important properties of the queuing behavior and stability conditions are uncovered through a numerical analysis. In passing, we remark on queuing properties and stability conditions of slotted ALOHA for comparison with the CSMA/CD.

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 Constraint and Mixed-Integer Programming Solvers for Batch Sequencing with Sequence-Dependent Setups
Authors: Jordan Carsten , Drexl Andreas
Published: October 2008

A batch sequencing model with sequence-dependent setup-times and -costs is used to compare modeling and solving with two different general solvers. “Conceptual models” are implemented and solved using the constraint programming language CHARME. The mixed-integer-programming (MIP) formulation of the same problem is solved with OSL, a state-of-the-art MIP solver. We compare modeling in both solvers and the performance of the constraint versus the mixed-integer programming solver.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Introduction to the Cluster on Knowledge and Data Management
Authors: Basu Amit
Published: October 2008

The design and analysis of efficient database management systems (DBMSs) and knowledge based systems (KBSs) is an important research area where operations research (OR) methods such as mathematical programming, stochastic modeling, and simulation have a significant role to play. To appreciate this, consider that although relational database technology is about 25 years old, it is only in the last 5 to 10 years that large organizations have started adopting relational DBMSs for critical applications, primarily because of concerns about the efficiency of relational systems. Mathematical programming models that address the significant costs of data processing, and permit OR-based performance analysis of DBMSs, are essential for making the technology more acceptable and reliable. Similarly, relatively few organizations today use KBSs for domains where the knowledge bases are large, or where response time is critical. As with DBMSs, the primary constraint is efficiency and reliability. OR methods for optimization can be used to improve the performance of these systems, and OR methods for performance analysis can help answer critical questions about their efficiency and reliability. The articles in this cluster present interesting examples of the use of OR in data and knowledge management. The articles address issues ranging from established ones such as distributed database design, query optimization, and rule processing to emerging areas such as main memory databases.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Stochastic Model for Performance Evaluation of Main Memory Resident Database Systems
Authors: Goes Paulo B.
Published: October 2008

With the rapid evolution in the computer industry where memory chips of increasing capacity are introduced every year at lower costs coupled with the increasing demand for massive on-line databases, a great deal of research has been done in the area of main memory resident databases. The use of these systems can achieve significant performance improvements in environments with very high volume of transactions by eliminating the need for most I/O functions while performing basic database operations. A primary concern in such systems is how to develop efficient recovery mechanisms to cope with system failures that can erase the contents of the main memory. This paper presents a stochastic model to evaluate the performance of the database system in terms of normal operation, checkpointing and recovery from system failures. Through a multi-variate model important transform results of effective residence times in each of the database states are derived, which allows the computation of first moments of interest, ergodic state probabilities, including the system availability, and reward measures. The model developed in the paper is significantly more general than previous stochastic models for traditional databases thus capturing the special features of recovery of main memory systems. The applicability of the model is supported and verified through numerical experiments.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Relationship Between CNF and DNF Systems Derivable from Examples
Authors: Triantaphyllou Evangelos , Soyster Allen L.
Published: October 2008

In learning from examples, the main goal is to use a collection of positive examples and a collection of negative examples to derive a Boolean expression which satisfies the requirements imposed by the examples. In order to represent such a Boolean expression, the conjunctive normal form (CNF) and the disjunctive normal form (DNF) have been proposed. This paper makes two contributions. First it shows how to use any DNF algorithm to derive a CNF formula (or vice-versa). Furthermore, it demonstrates how to make efficient use of DNF algorithms which cannot handle a large number of positive (or negative) examples by using them as negative (or positive) examples and deriving CNF (or vice-versa). Therefore, the findings of this paper can be used to solve efficiently large scale learning problems. Two learning algorithms are used to illustrate the above issues.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Graph Theory-Based Approach for Partitioning Knowledge Bases
Authors: Srikanth Rajan
Published: October 2008

The growing interest in using structured methodologies for design and development is a clear signal of the maturation of knowledge-based systems technology. The objective of this paper is to explore “modularization”—one of the cardinal principles of good design—as it applies to knowledge-based systems. Drawing upon the fact that graphs have routinely been used to pictorially depict different approaches to knowledge representation, this paper argues that the problem of modularizing a knowledge base corresponds to one of decomposing its equivalent graph with nodes depicting objects/frames/rules, and edges depicting relationships between them. The problem of finding cohesive, minimally coupled decompositions of this graph is made particularly interesting because it is not meaningful to assign cardinal weights to the labelled edges (or relationships) for minimum cost partitioning, and difficult to assess the similarity of different nodes (or objects/frames/rules) for purposes of clustering. A lexicographic ordering of edge types can however be, and often is specified, as are structural properties for each of the subgraphs. The paper proposes a formulation of the decomposition problem as one of partitioning the graph of a knowledge base using a “pseudo-cost” construct that ensures internal structural properties of subgraphs while operationalizing lexicographic priority in the placement of partition boundaries. It also demonstrates how a heuristic algorithm for partitioning knowledge bases can be developed by using this construct and appropriately adapting any of the procedures currently available for minimum cost graph partitioning.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Staged Primal-Dual Algorithm for Perfect b-Matching with Edge Capacities
Authors: Miller Donald L. , Pekny Joseph F.
Published: October 2008

We describe an algorithm for finding a minimum cost perfect b-matching in a weighted undirected graph G=(V,E), with arbitrary edge capacities. The algorithm is based on a staged approach that sequentially applies increasingly more expensive steps until a solution is found. The most significant step involves a primal-dual tree growth procedure that selectively activates and deactivates facet inducing blossom constraints. The algorithm progressively eliminates half-integral values from the primal solution without creating any new fractional values. We introduce the concept of frozen supervertices to address previously unknown complications that arise due to the presence of non-unit capacity edges. We discuss the relationship of the algorithm to previously published cutting plane methods. The algorithm is guaranteed to terminate in O(|V|2|E|) steps, although computational results suggest that much less effort is typically required. Computational results show the algorithm to be effective on problems derived from TSPLIB ranging in size from 532 to 3795 vertices for various b values.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Parallel Algorithms for Stochastic Dynamic Programming with Continuous State and Control Variables
Authors: Eschenbach Elizabeth A. , Shoemaker Christine A. , Caffey Hugh M.
Published: October 2008

We compare two partitioning methods for solving a multi-dimensional optimal control problem in parallel using continuous state, continuous control, stochastic dynamic programming (SCP). The algorithm uses tensor products to interpolate the multi-dimensional, continuous variable state space. Unlike previous parallel SDP applications, an iterative optimization routine is used to find the optimal continuous control for each node point in the state space. This routine causes load balance and dependence problems not encountered in previous parallel SDP applications. Even with these additional computational complexities, superb efficiencies are achieved on a shared memory MIMD architecture. The two methods of solution differ in the following way: Method 1 uses the outer state loop index to send subsets of the state space (called parcels) to each concurrent process. The number of parcels sent as parallel tasks is the number of discretizations of one of the state variables. Method 2 allows the user to determine the number of parcels to be sent as parallel tasks. Method 2 splits the state space into a greater number of parcels, so that the processors are more likely to finish at the same time at a synchronization barrier. Computational results indicate that Method 2 has better load balance, with efficiencies up to 93.5%.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Tabu Thresholding: Improved Search by Nonmonotonic Trajectories
Authors: Glover Fred
Published: October 2008

There is an appeal to methods like simulated annealing and threshold acceptance that operate by imposing a monotonically declining ceiling on objective function levels or degrees of disimprovement (treated probabilistically or deterministically). An alternative framework, embodied in tabu search, instead advocates a nonmonotonic form of control, keyed not only to the objective function but to other elements such as values of variables, direction of search, and levels of feasibility and infeasibility. This creates a more flexible search behavior and joins naturally with the use of memory-based strategies that are the hallmark of tabu search approaches. Embodied particularly in the strategic oscillation component of tabu search, this nonmonotonic control has been shown in a variety of studies to yield outcomes superior to those of simulated annealing and threshold acceptance. The question arises whether such an approach offers a sufficiently rich source of search trajectories to be relied upon as a primary guidance mechanism, with greatly reduced reliance on forms of memory customarily used in tabu search. To provide an easily implemented method of this type we propose a tabu thresholding approach, which joins prescriptions of strategic oscillation with a candidate list procedure derived from network optimization studies. The candidate list and tabu search philosophies are mutually reinforcing, and the computational advantages contributed by these elements, documented by studies cited in this paper, motivate a closer look at combining them. The result yields a method with a significant potential for variation and an ability to take advantage of special structure.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Problem and Heuristic Space Search Strategies for Job Shop Scheduling
Authors: Storer Robert H. , Wu S. David , Vaccari Renzo
Published: October 2008

In a recent paper we discussed “problem” and “heuristic” spaces which serve as a basis for local search in job shop scheduling problems. By encoding schedules as heuristic, problem pairs (H,P) search spaces can be defined by perturbing problem data and/or heuristic parameters. In this paper we attempt to determined, through computational testing, how these spaces can be successfully searched. Well known local search strategies are applied in problem and heuristic space and compared to Shifting Bottleneck heuristics, and to probabilistic dispatching methods. An interesting result is the good performance of genetic algorithms in problem space.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Study of the Augmented System and Column-Splitting Approaches for Solving Two-Stage Stochastic Linear Programs by Interior-Point Methods
Authors: Czyzyk Joseph , Fourer Robert , Mehrotra Sanjay
Published: October 2008

Linear programs that arise in two-stage stochastic programming offer a particularly difficult test of the robustness of interior-point methods. These LPs are typically very large, yet incorporate “dense columns”—corresponding to the first-stage variables—that rule out the standard approach of solving the so-called normal equations. We compare two alternative approaches by running tests on six groups of stochastic linear programs that have been used in previous studies. We find that the augmented system approach consistently requires an amount of work that is very nearly linear in the number of scenarios, whereas the column-splitting approach requires a less predictable amount of work that grows worse than quadratically in some cases. We conclude by explaining how the differences between the two approaches can be viewed as a consequence of the way in which myopic elimination strategies deal with the block-structured matrices involved. Our analysis also leads to a useful comparison of the augmented system approach with the Schur complement approach considered in other recent research.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Feature Article—Toward an Experimental Method for Algorithm Simulation
Authors: McGeoch Catherine C.
Published: October 2008

This feature article surveys issues arising in the design, development, and execution of computational experiments to study algorithms. An algorithm is viewed here as an abstract model of an implemented program: experiments are performed to study the model, and new insights about the model can be applied to predict program performance. Issues related to choosing performance measures, planning experiments, developing software tools, running tests, and analyzing data are considered. Some hazards and difficulties of computational research that arise particularly in the context of algorithmic problems are also surveyed.
Rejoinder—Challenges in Algorithm Simulation
Authors: McGeoch Catherine C.
Published: October 2008

This is the rejoinder of the author to the commentaries and complements to her featured article “Toward an Experimental Method for Algorithm Simulation” in the same issue.
Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances
Authors: Williamson David P. , Goemans Michel X.
Published: October 2008

We consider a 2-approximation algorithm for Euclidean minimum-cost perfect matching instances proposed by the authors in a previous paper. We present computational results for both random and real-world instances having between 1,000 and 131,072 vertices. The results indicate that our algorithm generates a matching within 2% of optimal in most cases. In over 1,400 experiments, the algorithm was never more than 4% from optimal. For the purposes of the study, we give a new implementation of the algorithm that uses linear space instead of quadratic space, and appears to run faster in practice.
An Improved Algorithm for the Constrained Bottleneck Spanning Tree Problem
Authors: Punnen Abraham P. , Nair K. P. K.
Published: October 2008

We propose an algorithm to solve the bottleneck spanning tree problem with an additional linear constraint. Our algorithm has an improved worst case performance over the best known algorithm for this problem. In a graph with n nodes and m edges such that m ≥ O(n log n log log*n), where log* n is the iterative logarithm of n, our algorithm runs in O(m) time and hence is the best possible in that case. For a large class of graphs, the proposed algorithm has almost the same complexity as that of computing just one minimum spanning tree.
A Comparison of Alternative Approaches for Numerical Solutions of GI/PH/1 Queues
Authors: Kao Edward P. C.
Published: October 2008

This paper compares alternative approaches for computing the R matrix of Neuts in numerical solutions of queues of GI/PH/1 type. We consider the relative merits of using two algorithms proposed recently by Latouche, the state reduction procedure proposed in this journal by Kao, and an approach based on the work of Sengupta using the notion of matrix exponential. There are three areas of interest: efficiency, memory accesses, and accuracy. In the empirical investigation, we use a subset of PH/PH/1 problems studied by Ramaswami and Latouche and a set of problems having non-phase-type interarrival times. At the expense of incurring varying degrees of loss of accuracy, the two algorithms proposed by Latouche and the method based on the work of Sengupta call for a lesser amount of computation than that of Kao's. When compared with the three alternatives, this study shows empirically that the R matrices obtained by state reduction—even when the approach is extended to Markov chains with denumerable state spaces—are closer to their respective true but unknown values.
Application of an Annealed Neural Network to a Timetabling Problem
Authors: Mausser Helmut E. , Magazine Michael J. , Moore John B.
Published: October 2008

In this paper, we use an annealed neural network to solve a timetabling problem with contiguity and availability constraints. A novel feature of the problem is that it may not be possible to satisfy the complete set of scheduling requirements, forcing the network to exhibit selection capability. We formulate the problem in a manner consistent with neural computation, describe our implementation of the annealed neural network, and report computational results for a series of randomly-generated problems. Solution quality varies depending on the size and difficulty of the problem, as well as on the values of the penalty parameters used to weight the various constraints.
Some Experimental and Theoretical Results on Test Case Generators for the Maximum Clique Problem
Authors: Sanchis Laura A. , Jagota Arun
Published: October 2008

We describe and analyze test case generators for the maximum clique problem (or equivalently for the maximum independent set or vertex cover problems). The generators produce graphs with specified number of vertices and edges, and known maximum clique size. The experimental hardness of the test cases is evaluated in relation to several heuristics for the maximum clique problem, based on neural networks, and derived from the work of A. Jagota. Our results show that the hardness of the graphs produced by this method depends in a crucial way on the construction parameters; for a given edge density, challenging graphs can only be constructed using this method for a certain range of maximum clique values; the location of this range depends on the expected maximum clique size for random graphs of that density; the size of the range depends on the density of the graph. We also show that one of the algorithms, based on reinforcement learning techniques, has more success than the others at solving the test cases produced by the generators. In addition, NP-completeness reductions are presented showing that (in spite of what might be suggested by the results just mentioned) the maximum clique problem remains NP-hard even if the domain is restricted to graphs having a constant edge density and a constant ratio of the maximum clique size to the number of vertices, for almost all valid combinations of such values. Moreover, the set of all graphs produced by the generators, and having a constant ratio and edge density, is also NP-hard for almost all valid parameter combinations.
The Multi-Tier Tree Problem
Authors: Mirchandani Prakash
Published: October 2008

This paper studies the multi-tier tree (MTT) problem, a generalization of the Steiner-tree problem, in which we are given a graph with its nodes partitioned into several tiers (grades), and grade dependent edge-costs. The MTT problem seeks the cost minimizing choice of grades for the edges such that every pair of nodes, say at tiers t′ and t″ ≥ t′, is connected by a path containing grade-t′ or better (grade) edges. The MTT problem arises in the telecommunication setting (where we must choose between competing communication technologies) end in the transportation setting (where the cost incurred determines the type of access provided between two points). In this paper, we develop two solution approaches for the problem. We first develop a recursive heuristic for the MTT problem, and obtain data-independent bounds for MTT problems with 3-tiers. For one case, the bound on the performance ratio of the recursive heuristic is 1.52241. Next, we develop a dual-based solution procedure for this problem, and conduct an extensive computational study to test the efficacy of the procedure. Our study, with problems having up to 2000 nodes, 6000 edges end 5 tiers (with up to 60,000 integer and 24 million continuous variables), shows that the method is quite effective in generating solutions within 6% of optimality in a reasonable amount of time.
Multicommodity Flows in Ring Networks
Authors: Vachani Rita , Shulman Alexander , Kubat Peter , Ward Julie
Published: October 2008

In this paper, we consider the problem of multicommodity flows in a ring network. Using necessary and sufficient conditions to ensure feasible linear and integral flows in the network, and the special structure of the ring topology, we construct efficient algorithms to route all the demands.
Capacitated Network Design—Polyhedral Structure and Computation
Authors: Bienstock Daniel , Günlük Oktay
Published: October 2008

We study a capacity expansion problem that arises in telecommunication network design. Given a capacitated network and a traffic demand matrix, the objective is to add capacity to the edges, in multiples of various modularities, and route traffic, so that the overall cost is minimized. We study the polyhedral structure of a mixed-integer formulation of the problem and develop a cutting-plane algorithm using facet defining inequalities. The algorithm produces an extended formulation providing both a vary good lower bound and a starting point for branch and bound. The overall algorithm appears effective when applied to problem instances using real-life data.
Use of Representative Operation Counts in Computational Testing of Algorithms
Authors: Ahuja Ravindra K. , Orlin James B.
Published: October 2008

In the mathematical programming literature, researchers have conducted a large number of computational studies to assess the empirical behavior of various algorithms and have utilized CPU time as the primary measure of performance. CPU time has the following drawbacks as a measure of an algorithm's performance: it is implementation dependent, hard to replicate, and limited in the insight it provides into an algorithm's behavior. In this paper, we illustrate the notion of representative operation counts that can complement the conventional CPU time analysis and can help us (i) to identity the asymptotic bottleneck operations in an algorithm, (ii) to estimate an algorithm's running time for different problem sizes, and (iii) to obtain a fairer comparison of several algorithms. These concepts are easily incorporated into empirical studies and often yield valuable insights into an algorithm's behavior.
Bottleneck Steiner Subnetwork Problems with k-Connectivity Constraints
Authors: Averbakh Igor , Berman Oded
Published: October 2008

The objective is to connect a given set of terminal nodes of a network by a subnetwork of maximum bottleneck capacity. The bottleneck capacity of a subnetwork is the minimum of the capacities of its edges. For the problem with the additional requirement that the connecting subnetwork must be k-edge-connected or k-node-connected, k = 2,3, algorithms with complexities O(m + n log n) are given, where m and n are the numbers of edges and nodes of the network respectively. For the problem where the connecting subnetwork is required to be k-edge-connected or k-node-connected, k ≥ 4, the complexities of the proposed algorithms are O(m + fk(n) · log n) and O(m + gk(n) · log n) respectively, where fk(m)(gk(m)) is the complexity of finding nontrivial k-edge-connected components (k-node-connected components) of a network. The results of the paper improve known complexities for k ≥ 2 in the case of k-edge-connectivity requirement and for k ≥ 3 in the case of k-node-connectivity requirement.
An O(n log n) Algorithm for the Two-Machine Flow Shop Problem with Controllable Machine Speeds
Authors: van Hoesel C. P. M. , Wagelmans A. P. M. , van Vliet M.
Published: October 2008

In this paper we consider the two-machine flow shop problem with varying machine speeds. We present an algorithm which determines the optimal permutations for all machine speeds in O(n log n) time, where n is the number of jobs. To achieve this bound on the running time, the algorithm employs an elementary dominance relation.
A Branch-and-Bound Algorithm for Single-Machine Earliness–Tardiness Scheduling with Idle Time
Authors: Hoogeveen J. A. , van de Velde S. L.
Published: October 2008

We address the NP-hard single-machine problem of scheduling n independent jobs so as to minimize the sum of α times total completion time and β times total earliness with β > α, which can be rewritten as an earliness–tardiness problem. Postponing jobs by leaving the machine idle may then be advantageous. The allowance of machine idle time between the execution of jobs singles out our problem from most concurrent research on problems with earliness penalties. Solving the problem to optimality poses a computational challenge, since the possibility of leaving the machine idle has a major effect on designing a branch-and-bound algorithm in general, and on computing lower bounds in particular. We present a branch-and-bound algorithm which is based upon many dominance rules and various lower bound approaches, including relaxation of the machine capacity, data manipulation, and Lagrangian relaxation. The algorithm is shown to solve small instances with up to 20 jobs.
On the Laguerre Method for Numerically Inverting Laplace Transforms
Authors: Abate Joseph , Choudhury Gagan L. , Whitt Ward
Published: October 2008

The Laguerre method for numerically inverting Laplace transforms is an old established method based on the 1935 Tricomi–Widder theorem, which shows (under suitable regularity conditions) that the desired function can be represented as a weighted sum of Laguerre functions, where the weights are coefficients of a generating function constructed from the Laplace transform using a bilinear transformation. We present a new variant of the Laguerre method based on: (i) using our previously developed variant of the Fourier-series method to calculate the coefficients of the Laguerre generating function, (ii) developing systematic methods for scaling, and (iii) using Wynn's ϵ-algorithm to accelerate convergence of the Laguerre series when the Laguerre coefficients do not converge to zero geometrically fast. These contributions significantly expand the class of transforms that can be effectively inverted by the Laguerre method. We provide insight into the slow convergence of the Laguerre coefficients as well as propose a remedy. Before acceleration, the rate of convergence can often be determined from the Laplace transform by applying Darboux's theorem. Even when the Laguerre coefficients converge to zero geometrically fast, it can be difficult to calculate the desired functions for large arguments because of roundoff errors. We solve this problem by calculating very small Laguerre coefficients with low relative error through appropriate scaling. We also develop another acceleration technique for the case in which the Laguerre coefficients converge to zero geometrically fast. We illustrate the effectiveness of our algorithm through numerical examples.
Scheduling Periodic Tasks
Authors: Korst Jan , Aarts Emile , Lenstra Jan Karel
Published: October 2008

We consider the problem of nonpreemptively scheduling periodic tasks on a minimum number of processors, assuming that the tasks have to be executed strictly periodically. We show that the problem is NP-complete in the strong sense, even in the case of a single processor, but that it is solvable in polynomial time if the periods and execution times are divisible. The latter condition generalizes the situation in which all periods and execution times are powers of 2. We also propose an approximation algorithm, which is based on successively assigning tasks to processors according to some priority rule.
Appreciation to Referees
Authors: Golden Bruce
Published: October 2008

On behalf of the Editorial Board, I would like to thank the following individuals who have acted as referees for papers considered for publication during 1996. —Bruce L. Golden, Editor
A Mathematical Programming Approach to Data Base Normalization
Authors: Bala Mohan , Martin Kipp
Published: October 2008

A critical step in the process of creating a relational data base is normalization, whereby a series of tables is created in order to avoid redundancy problems and insertion and deletion anomalies. Several important normalization decision problems are NP-Complete. In this paper we develop a unified approach to data base normalization using linear integer programming. These linear integer programming formulations result from structuring normalization problems as gainfree Leontief substitution flow problems on hypergraphs. We provide a sufficient condition based on the structural properties of the hypergraph which yields a strongly polynomial algorithm for testing whether or not a given decomposition is in third normal form. We also show that under these conditions the key of a relation is unique and a relation in third normal form is also in Boyce-Codd normal form. We also provide linear integer programming formulations for solving normalization decision problems when no special structure is present. We test these linear integer programming models for normalization against existing normalization algorithms and find the mathematical programming approach is several orders of magnitude faster. Our results suggest that the mathematical programming approach is practical for normalizing actual large scale data bases.
How Much Communication Does Parallel Branch and Bound Need?
Authors: Eckstein Jonathan
Published: October 2008

Consider the classical branch and bound algorithm for mixed integer programming (MIP). Parallel implementations of this method are known to be viable and reasonably scalable on systems with sophisticated, high-performance interprocessor communication capabilities. But how parallel can the algorithm be when communication is more rudimentary? This article attempts to address this question by comparing two different implementations of MIP branch and bound on CM-5 systems with between 4 and 64 processors, using a selection of MIPLIB test problems. The first code, CMMIP, exploits many of the advanced features of the CM-5 network, whereas the second, called LCMIP, has a minimal, relatively infrequent communication pattern. Generally speaking, the performance of the low-communication code is competitive for relatively difficult problems and/or small processor configurations, but it appears that advanced communications features are essential to extract the maximum degree of parallelism from a given problem instance.
A Branch-and-Bound Approach Using Polyhedral Results for a Clustering Problem
Authors: Palubeckis Gintaras
Published: October 2008

This article describes a variation of the branch and bound method for solving a clustering problem stated as a partitioning problem on edge-weighted graphs. The key features of the approach are two. First, it employs the transformation of a subproblem according to some heuristic solution. For this, two clustering heuristics, constructive and iterative improvement, are adopted. Second, the lower bound computation is based on the use of the inequalities with zero right-hand side coefficient, each defining a facet of the polytope related to the transformed subproblem. A procedure is described for covering negative edges of the subproblem graph by cycles and paths inducing such inequalities. The objective function is modified each time by adding the left-hand side of the selected inequality to it. The lower bound is obtained by summing the weights of uncovered negative edges. The algorithm can be used for solving clustering problems in the area of qualitative data analysis. Computational results on both real and randomly generated clustering problems demonstrate the efficiency of the algorithm. in particular, all 10 real problems from the literature were solved in a total of less than 9 seconds on an IBM PC.
A New Knapsack Solution Approach by Integer Equivalent Aggregation and Consistency Determination
Authors: Babayev Djangir A. , Glover Fred , Ryan Jennifer
Published: October 2008

We present a new and highly efficient algorithm for the integer knapsack problem based on a special strategy for aggregating integer-valued equations. Employing a new theorem for creating a single equation with the same nonnegative integer solution set as a system of original equations, we transform the integer knapsack problem into an equivalent problem of determining the consistency of an aggregated equation for a parameterized right hand side. This last problem is solved by a newly developed algorithm with complexity O(min(n α1, n + α12)), where n is the number of variables and α1 is the smallest coefficient in the aggregated equation. Empirical outcomes show our procedure is significantly superior to advanced branch-and-bound methods (previously established to be the most efficient knapsack solution procedures), obtaining solutions several orders of magnitude faster for hard problems.
Computing Gradients in Large-Scale Optimization Using Automatic Differentiation
Authors: Bischof Christian H. , Bouaricha Ali , Khademi Peyvand M. , Moré Jorge J.
Published: October 2008

The accurate and efficient computation of gradients for partially separable functions is central to the solution of large-scale optimization problems, because these functions are ubiquitous in large-scale problems. We describe two approaches for computing gradients of partially separable functions via automatic differentiation. In our experiments we employ the ADIFOR (automatic differentiation of Fortran) tool and the SparsLinC (sparse linear combination) library. We use applications from the MINPACK-2 test problem collection to compare the numerical reliability and computational efficiency of these approaches with hand-coded derivatives and approximations based on differences of function values. Our conclusion is that automatic differentiation is the method of choice, providing code for the efficient computation of the gradient without the need for tedious hand-coding.
Commentary—When Genetic Algorithms Work Best
Authors: Kershenbaum Aaron
Published: October 2008

Colin Reeves' feature article provides an insightful survey of many of the applications of genetic algorithms (GAs) to the solution of current problems in operations research. In some cases, GAs were successful, and in others they were not. Reeves correctly does not offer GAs as a panacea, but instead offers considerable insight into when and why GAs work. The difference between a successful application of a GA and an unsuccessful one often lies in the encoding. Five properties of an ideal encoding are listed.
SALOME: A Bidirectional Branch-and-Bound Procedure for Assembly Line Balancing
Authors: Scholl Armin , Klein Robert
Published: October 2008

In this article, we report on new results for the well-known Simple Assembly Line Balancing Problem Type 1. For this NP-hard problem, a large number of exact and heuristic algorithms have been proposed in the last four decades. Recent research has led to efficient branch-and-bound procedures. Based on an analysis of their specific strengths, a new algorithm (Salome) is developed. Its main characteristic is a new branching strategy (local lower-bound method) and a bidirectional branching rule. Furthermore, new bounding and dominance rules are included. Computational experiments on the basis of former data sets, as well as a new, more challenging one, show that Salome outperforms the most effective existing procedures for solving this problem.
Scheduling Periodic Tasks with Slack
Authors: Korst Jan , Aarts Emile , Lenstra Jan Karel
Published: October 2008

We consider the problem of nonpreemptively scheduling periodic tasks on a minimum number of identical processors, assuming that some slack is allowed in the time between successive executions of a periodic task. We prove that the problem is NP-hard in the strong sense. Necessary and sufficient conditions are derived for scheduling two periodic tasks on a single processor, and for combining two periodic tasks into one larger task. Based on these results, we propose an approximation algorithm.
A Message from the President
Authors: Norden Peter V.
Published: October 2008

Editorial about the first issue of the new journal.
Management Communication Analysis
Authors: Bennett J. G.
Published: October 2008

Until recently, it has been assumed that within a corporation communications follow the lines drawn upon an organization chart. With this goes the belief that with clarity, a judicious balance of authority and cajolery, and the need to keep the organization going, the flow of messages will do what is required. Since failure of communication is, throughout the world, recognized as the principal cause of disputes and error of management, these assumptions must become suspect.

Communication analysis is more than a branch of management science; it is the basic instrument of the science as mathematics is the basic instrument of engineering. As mathematicians use instruments like computers to expedite their work, communications analysts use media; but, in neither case does the instrument do the creative work. In communication systems, the basic problems arise from human relationships, and for this reason it is a mistake to suppose that communication consists in the flow of orders and information and that the obstacles to communication are mainly economic and political. The real purpose of any communication is to evoke a positive response, whether in the form of overt action or a change of inner attitude. A message that has no effect upon either the behavior or the attitude of the recipient is not a communication.
“Dr. Mead, Could You Come Here a Minute?”
Authors: Kastens Merritt L.
Published: October 2008

An introductory editorial essay about various fundamental principles of management, developing new techniques, and making sure that the changes get accepted.
Council Happenings
Authors: Hess Sidney W.
Published: October 2008

This is the first of many columns your Secretary will write to advise you of activities of your Council. Minutes of our meetings are available from the executive office of Providence should you wish any further detail. We solicit your continual interest.
Note from Chairman of Student Chapters
Authors: Halbrecht Herbert Z.
Published: October 2008

We are anxious to organize Student Chapters of TIMS on every campus where we can attract enough students and faculty advisors to make such chapter activities viable, useful, and interesting. Possibly even joint chapters could be formed by two or three schools in the same area.

We are in the process of organizing panels of chief executives and senior operating officers of a number of the country's leading industrial, commercial, and financial corporations, nonprofit research firms, and major governmental agencies to lead seminars discussing how they actually use management sciences, what they really do, and what they foresee in terms of future functions as prospects for the students should they decide to enter industry.
Observations on Computer Simulation in the Civilian Concerns of Government
Authors: Tribus Myron
Published: October 2008

Simulation is a tool made practical by the capabilities of the modern highspeed computer, a tool which may be used by enlightened decision makers in the public and private sectors to gain insights into very complex situations. The advent of meaningful simulation models to help understand and contemplate large complex systems is relatively new.

At present there is no universal agreement on the meaning of the term. In my own view, simulation implies a concern with dynamics—that is, the use of any mathematical or physical model which may be moved through time.

Simulation may or may not involve the use of Monte Carlo techniques, but the prime thought here is that models are time dependent and may be used to study the effects of decisions made in one time period on behavior in subsequent time periods.
What is a Management Scientist?
Authors: Simon Leonard S.
Published: October 2008

Early in November, approximately 2,000 questionnaires were mailed to a randomly selected sample of the membership of The Institute of Management Sciences. The stated goal of the questionnaire was to accumulate data from which a discussion could commence about the definition of a management scientist.

Each of the questions was of an attitudinal nature and dealt with the individual's perception of himself and/or his professional colleagues who considered themselves management scientists. A copy of the questionnaire is provided in Exhibit I. The statements focused on three areas, namely the person's viewpoints on the training necessary to be a management scientist, the job characteristics of a management scientist, and the contribution of the management scientist to his organization. There were several statements related to each area, but these were randomized in actual presentation of the questionnaire.
Information Systems in Management Science—Human Relations and Information Systems
Authors: Stern Harry
Published: October 2008

Because I believe that the installation of a new computer program or new systems is not a meaningful event unless it causes a change, I was excited by an outline titled “Change Agent Skills” that appeared in the Reading Book for Laboratories in Human Relations Training, circulated by the NTL Institute for Applied Behavioral Science (which is associated with the National Education Association). The outline was one of the papers originally prepared for theory sessions at the Institute's laboratories.
Management Science Roundup
Authors: Bucatinsky Julio
Published: October 2008

—“Quantitative Techniques in Accounting”;

—“Corporate Planning”;

—“Simulation Applications”;

—“More on Simulation”;

—“Model of a Profit Sharing Plan”;

—“Management Science in Banking”;

—“Marketing and Financial Planning”;

—“To Learn How Higher Education Ticks”;

—“1970 Management Systems Conference”;

—“Seen Elsewhere: (1) Modeling of Distant Futures, (2) Algorithms, (3) Approximation by Linear Programming, and (4) Decision Theory Analysis”;

—“Bulletin Board”.