bluuebunny/crossref_metadata_2025 huggingface dataset:
Feature Selection via Mathematical Programming
Authors: Bradley P. S. , Mangasarian O. L. , Street W. N.
Published: October 2008

The problem of discriminating between two finite point sets in n-dimensional feature space by a separating plane that utilizes as few of the features as possible is formulated as a mathematical program with a parametric objective function and linear constraints. The step function that appears in the objective function can be approximated by a sigmoid or by a concave exponential on the nonnegative real line, or it can be treated exactly by considering the equivalent linear program with equilibrium constraints. Computational tests of these three approaches on publicly available real-world databases have been carried out and compared with an adaptation of the optimal brain damage method for reducing neural network complexity. One feature selection algorithm via concave minimization reduced cross-validation error on a cancer prognosis database by 35.4% while reducing problem features from 32 to 4.
Operator-Splitting Methods for Monotone Affine Variational Inequalities, with a Parallel Application to Optimal Control
Authors: Eckstein Jonathan , Ferris Michael C.
Published: October 2008

This article applies splitting techniques developed for set-valued maximal monotone operators to monotone affine variational inequalities, including, as a special case, the classical linear complementarity problem. We give a unified presentation of several splitting algorithms for monotone operators, and then apply these results to obtain two classes of algorithms for affine variational inequalities. The second class resembles classical matrix splitting, but has a novel “under-relaxation” step, and converges under more general conditions. In particular, the convergence proofs do not require the affine operator to be symmetric. We specialize our matrix-splitting-like method to discrete-time optimal control problems formulated as extended linear-quadratic programs in the manner advocated by Rockafellar and Wets. The result is a highly parallel algorithm, which we implement and test on the Connection Machine CM-5 computer family.
Integer Linear Programming and Constraint Programming Approaches to a Template Design Problem
Authors: Proll Les , Smith Barbara
Published: October 2008

We describe a design problem arising in the color printing industry and discuss a number of integer linear programming and constraint programming approaches to its solution. Despite the apparent simplicity of the problem it presents a challenge for both approaches. We present results for three typical cases and show that the constraint programming approach provides better results, although in some cases after considerable handcrafting. We also show that the results obtained by constraint programming can be improved by a simple goal programming model.
Branch and Infer: A Unifying Framework for Integer and Finite Domain Constraint Programming
Authors: Bockmayr Alexander , Kasper Thomas
Published: October 2008

We introduce branch and infer, a unifying framework for integer linear programming and finite domain constraint programming. We use this framework to compare the two approaches with respect to their modeling and solving capabilities, to introduce symbolic constraint abstractions into integer programming, and to discuss possible combinations of the two approaches.
Local Search Heuristics for the Single Machine Total Weighted Tardiness Scheduling Problem
Authors: Crauwels H. A. J. , Potts C. N. , Van Wassenhove L. N.
Published: October 2008

This paper presents several local search heuristics for the problem of scheduling a single machine to minimize total weighted tardiness. We introduce a new binary encoding scheme to represent solutions, together with a heuristic to decode the binary representations into actual sequences. This binary encoding scheme is compared to the usual “natural” permutation representation for descent, simulated annealing, threshold accepting, tabu search and genetic algorithms on a large set of test problems. Computational results indicate that all of the heuristics which employ our binary encoding are very robust in that they consistently produce good quality solutions, especially when multistart implementations are used instead of a single long run. The binary encoding is also used in a new genetic algorithm which performs very well and requires comparatively little computation time. A comparison of neighborhood search methods which use the permutation and binary representations shows that the permutation-based methods have a higher likelihood of generating an optimal solution, but are less robust in that some poor solutions are obtained. Of the neighborhood search methods, tabu search clearly dominates the others. Multistart descent performs remarkably well relative to simulated annealing and threshold accepting.
Partitioning the Attribute Set for a Probabilistic Reasoning System
Authors: Sarkar Sumit , Ghosh Deb
Published: October 2008

The ability of a computerized system to model the reasoning process of humans has become an important area of research. This research considers a probabilistic reasoning system for applications that require decision making under uncertain conditions. The reasoning system captures the uncertainty associated with different feasible outcomes, and based on historical data, provides users with a measure of this uncertainty. To make accurate predictions, the scheme requires that predictive variables that are not conditionally independent of each other given the outcome be grouped into compound attributes for the purpose of estimating probabilities. These compound attributes partition the entire set of predictive attributes into disjoint sets. An important design issue, then, is that the appropriate partitioning scheme be obtained before the reasoning scheme is used in practice. We formulate the problem of finding the optimal partitioning scheme, and present five different (although related) heuristic techniques to induce partitions from historical cases. Using simulated data, all five techniques are shown to capture accurately underlying dependencies across attributes when a reasonable amount of historical data is available for analysis. In situations where few historical cases are available, the induced structures are less accurate. In such situations, the performance of induced structures for making probability predictions is nevertheless found to be as good as that when using the true structure. Finally, we test for external validity by applying the techniques on a real-world dataset on credit applications for a bank. We show, using this dataset, that (i) the classificatory performance of the reasoning system using structures generated by the heuristic techniques is as good as the performance of the widely used decision tree induction algorithm C4.5, and (ii) the induced structures are able to provide reliable probability estimates for making decisions in environments with asymmetric misclassification costs.
An Efficient Algorithm for Solving an Air Traffic Management Model of the National Airspace System
Authors: Boyd E. Andrew , Burlingame Rusty , Lindsay Kenneth
Published: October 2008

Growth in traffic and changes in traffic patterns have caused an increase in the congestion and delay in the National Airspace System. Air traffic delay is very costly to the airlines, and minimizing this delay has been a subject of research for over a decade. A large integer programming model developed at the MITRE Corporation for minimizing air traffic delay is presented. Solving problem instances arising from this model involves the use of preprocessing, constraint strengthening, and a carefully designed computer implementation. Results are presented, demonstrating that the model can be solved to provable optimality in real time for problem instances involving over 1 million binary variables.
Distribution Estimation Using Laplace Transforms
Authors: Harris Carl M. , Marchal William G.
Published: October 2008

We propose two related methods for deriving probability distribution estimates using approximate rational Laplace transform representations. Whatever method is used, the result is a Coxian estimate for an arbitrary distribution form or plain sample data, with the algebra of the Coxian often simplifying to a generalized hyperexponential or phase-type. The transform (or, alternatively, the moment-generating function) is used to facilitate the computations and leads to an attractive algorithm. For method one, the first 2N − 1 derivatives of the transform are matched with those of an approximate rational function; for the second method, a like number of values of the transform are matched with those of the approximation. The numerical process in both cases begins with an empirical Laplace transform or truncation of the actual transform, and then requires only the solution of a relatively small system of linear equations, followed by root finding for a low-degree polynomial. Besides the computationally attractive features of the overall procedure, it addresses the question of the number of terms, or the order, involved in a generalized hyperexponential, phase-type, or Coxian distribution, a problem not adequately treated by existing methods. Coxian distributions are commonly used in the modeling of single-stage and network queueing problems, inventory theory, and reliability analyses. They are particularly handy in the development of large-scale model approximations.
Neural Networks for Combinatorial Optimization: A Review of More Than a Decade of Research
Authors: Smith Kate A.
Published: October 2008

It has been over a decade since neural networks were first applied to solve combinatorial optimization problems. During this period, enthusiasm has been erratic as new approaches are developed and (sometimes years later) their limitations are realized. This article briefly summarizes the work that has been done and presents the current standing of neural networks for combinatorial optimization by considering each of the major classes of combinatorial optimization problems. Areas which have not yet been studied are identified for future research.
Information Theory and the Finite-Time Behavior of the Simulated Annealing Algorithm: Experimental Results
Authors: Fleischer Mark , Jacobson Sheldon H.
Published: October 2008

This article presents an empirical approach that demonstrates a theoretical connection between (information theoretic) entropy measures and the finite-time performance of the simulated annealing algorithm. The methodology developed leads to several computational approaches for creating problem instances useful in testing and demonstrating the entropy/performance connection: use of generic configuration spaces, polynomial transformations between NP-hard problems, and modification of penalty parameters. In particular, the computational results show that higher entropy measures are associated with superior finite-time performance of the simulated annealing algorithm.
GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization
Authors: Laguna Manuel , Marti Rafael
Published: October 2008

In this article, we develop a greedy randomized adaptive search procedure (GRASP) for the problem of minimizing straight line crossings in a 2-layer graph. The procedure is fast and is particularly appealing when dealing with low-density graphs. When a modest increase in computational time is allowed, the procedure may be coupled with a path relinking strategy to search for improved outcomes. Although the principles of path relinking have appeared in the tabu search literature, this search strategy has not been fully implemented and tested. We perform extensive computational experiments with more than 3,000 graph instances to first study the effect of changes in critical search parameters and then to compare the efficiency of alternative solution procedures. Our results indicate that graph density is a major influential factor on the performance of a solution procedure.
Solving Parallel Machine Scheduling Problems by Column Generation
Authors: Chen Zhi-Long , Powell Warren B.
Published: October 2008

We consider a class of problems of scheduling n jobs on m identical, uniform, or unrelated parallel machines with an objective of minimizing an additive criterion. We propose a decomposition approach for solving these problems exactly. The decomposition approach first formulates these problems as an integer program, and then reformulates the integer program, using Dantzig-Wolfe decomposition, as a set partitioning problem. Based on this set partitioning formulation, branch-and-bound exact solution algorithms can be designed for these problems. In such a branch-and-bound tree, each node is the linear relaxation problem of a set partitioning problem. This linear relaxation problem is solved by a column generation approach where each column represents a schedule on one machine and is generated by solving a single machine subproblem. Branching is conducted on variables in the original integer programming formulation instead of variables in the set partitioning formulation such that single machine subproblems are more tractable. We apply this decomposition approach to two particular problems: the total weighted completion time problem and the weighted number of tardy jobs problem. The computational results indicate that the decomposition approach is promising and capable of solving large problems.
On Exploiting Problem Structure in a Basis Identification Procedure for Linear Programming
Authors: Andersen Erling D.
Published: October 2008

During the last decade, interior-point methods have become an efficient alternative to the simplex algorithm for solution of large-scale linear programming (LP) problems. However, in many practical applications of LP, interior-point methods have the drawback that they do not generate an optimal basic and nonbasic partition of the variables. This partition is required in the traditional sensitivity analysis and is highly useful when a sequence of related LP problems are solved. Therefore, in this article we discuss how an optimal basic solution can be generated from the interior-point solution. The emphasis of the article is on how problem structure can be exploited to reduce the computational cost associated with the basis identification. Computational results are presented that indicate that it is highly advantageous to exploit problem structure.
Exact Solution of the Quadratic Knapsack Problem
Authors: Caprara Alberto , Pisinger David , Toth Paolo
Published: October 2008

The Quadratic Knapsack Problem (QKP) calls for maximizing a quadratic objective function subject to a knapsack constraint, where all coefficients are assumed to be nonnegative and all variables are binary. The problem has applications in location and hydrology, and generalizes the problem of checking whether a graph contains a clique of a given size. We propose an exact branch-and-bound algorithm for QKP, where upper bounds are computed by considering a Lagrangian relaxation that is solvable through a number of (continuous) knapsack problems. Suboptimal Lagrangian multipliers are derived by using subgradient optimization and provide a convenient reformulation of the problem. We also discuss the relationship between our relaxation and other relaxations presented in the literature. Heuristics, reductions, and branching schemes are finally described. In particular, the processing of each node of the branching tree is quite fast: We do not update the Lagrangian multipliers, and use suitable data structures to compute an upper bound in linear expected time in the number of variables. We report exact solution of instances with up to 400 binary variables, i.e., significantly larger than those solvable by the previous approaches. The key point of this improvement is that the upper bounds we obtain are typically within 1% of the optimum, but can still be derived effectively. We also show that our algorithm is capable of solving reasonable-size Max Clique instances from the literature.
An Efficient Decomposition Algorithm to Optimize Spare Capacity in a Telecommunications Network
Authors: Kennington Jeffery L. , Whitler Jason E.
Published: October 2008

This article presents a new model for the spare capacity allocation problem in a self-healing, mesh SONET telecommunications network. This model is known as the spare capacity network flow model and has not, it is believed, previously appeared in the literature. The spare capacity network flow model uses a node-arc formulation while others have used an arc-path approach. The node-arc formulation is much more compact, and its special structure can be exploited in devising solution techniques. An original algorithm, inspired by Benders' decomposition procedure and called the network cut algorithm, is developed to solve the spare capacity network flow model. Application of decomposition principles results in an algorithm that iterates between a pure integer master problem and a set of minimum cost network flow subproblems. The algorithm incorporates a branch-and-bound procedure to solve the master problem, and a pure network dual simplex optimizer to solve the subproblems. The network cut algorithm is much more efficient than directly solving either the continuous relaxation or the mixed integer version of the spare capacity network flow model.
A Computational Study of Search Strategies for Mixed Integer Programming
Authors: Linderoth J. T. , Savelsbergh M. W. P.
Published: October 2008

The branch-and-bound procedure for solving mixed integer programming (MIP) problems using linear programming relaxations has been used with great success for decades. Over the years, a variety of researchers have studied ways of making the basic algorithm more effective. Breakthroughs in the fields of computer hardware, computer software, and mathematics have led to increasing success at solving larger and larger MIP instances. The goal of this article is to survey many of the results regarding branch-and-bound search strategies and evaluate them again in light of the other advances that have taken place over the years. In addition, novel search strategies are presented and shown to often perform better than those currently used in practice.
An Approximation Scheme for Minimizing Agreeably Weighted Variance on a Single Machine
Authors: Woeginger Gerhard J.
Published: October 2008

We consider the problem of minimizing the weighted variance of job completion times on a single machine with job-dependent, agreeable weights. In 1995, Cai derived a fully polynomial time approximation scheme for the special case where the weights of the jobs are polynomially bounded in the number n of jobs. In this article, we completely settle the approximability status of this scheduling problem. We construct a fully polynomial time approximation scheme for the general case, without putting any restrictions on the weights of the jobs.
Mathematical Programming for Data Mining: Formulations and Challenges
Authors: Bradley P. S. , Fayyad Usama M. , Mangasarian O. L.
Published: October 2008

This article is intended to serve as an overview of a rapidly emerging research and applications area. In addition to providing a general overview, motivating the importance of data mining problems within the area of knowledge discovery in databases, our aim is to list some of the pressing research challenges, and outline opportunities for contributions by the optimization research communities. Towards these goals, we include formulations of the basic categories of data mining methods as optimization problems. We also provide examples of successful mathematical programming approaches to some data mining problems.
Data Mining by Decomposition: Adaptive Search for Hypothesis Generation
Authors: Bhargava Hemant K.
Published: October 2008

Data mining methods search large databases for interesting patterns that may lead to useful decisions in organizations. When the database is defined over scores of attributes, the complexity of the search increases due to the combinatorial explosion at the attribute-space level, because billions of attribute subsets are candidates for forming interesting patterns in the database. A useful way to address this complexity is to partition the search problem and apply separate, but intertwined, algorithms for attribute search and pattern search. A genetic algorithm is applied on the attribute search problem to identify subsets that lead to more interesting patterns. This method is applied on a real world database arising from the investigations into the “Persian Gulf Illness.” Computational experiments resulted in significant success compared to random or manual attribute selection.
Direct Marketing Performance Modeling Using Genetic Algorithms
Authors: Bhattacharyya Siddhartha
Published: October 2008

Data analysts in direct marketing seek models to identify the most promising individuals to mail to and thus maximize returns from solicitations. A variety of criterion can be used to assess model performance, including response to or revenue generated from earlier solicitations. Given budgetary limitations, typically a fraction of the total customer database is selected for mailing. This depth-of-file that is to be mailed to provides potentially useful information that should be considered in model determination. This article presents a genetic algorithm-based approach for obtaining models in explicit consideration of this mailing depth. Issues related to overfitting, common in application of machine learning techniques, are examined, and experiments are based on a real-life data set.
Feature Selection for Financial Credit-Risk Evaluation Decisions
Authors: Piramuthu Selwyn
Published: October 2008

Credit-risk evaluation decisions are important for the financial institutions involved due to the high level of risk associated with wrong decisions. Various machine learning methods have been shown to perform reasonably well for this complex and unstructured problem. However, selecting a “good” set of features to be used in any learning system is a hard problem. We survey recent developments in feature selection and propose a new methodology based on the “Blurring” measure. The proposed feature selection method (FSB) is used to preprocess input data for induced decision trees. Three financial credit-risk evaluation data sets are used to illustrate the performance of the proposed method. In addition to FSB, results from randomly selected features, features selected using the Patrick-Fisher probabilistic distance measure, as well as no feature selection are provided for comparison purposes. Given the characteristics of the financial credit-risk evaluation domain, any improvement in classification performance is deemed beneficial. Preliminary results indicate that for comparable tree size, classification performance of FSB on classifying heretofore unseen examples is good compared to the other three methods evaluated in this study.
A Study of Composite or Hybrid Classifiers for Knowledge Discovery
Authors: Kumar Akhil , Olmeda Ignacio
Published: October 2008

There are several well-known techniques for knowledge discovery such as neural networks, discriminant analysis, etc. This article compares the forecasting accuracy of five models (two parametric and three nonparametric) and proposes composite (or hybrid) methods based on combining the individual methods. Basically, a composite classifier makes use of “trained” models whose “expertise” is combined to obtain an optimal classifier. All the methods are illustrated and evaluated using marketing data related to the problem of deciding whether a supermarket should carry a new product. All methods except one performed considerably better on predicting the reject decision accurately than the accept decision. However, when hybrid methods were devised and tested, the performance on “accept” decisions improved dramatically, while the overall performance was almost the same as before. Moreover, no pure method dominated any of the four hybrid methods. We also performed a cost analysis to show that, depending upon the ratio of the costs of Type 1 and Type 2 errors, the hybrid methods could outperform all the pure methods in terms of total profit for the supermarket.
Semantics-Based Transaction Processing for Real-Time Databases: The Case of Automated Stock Trading
Authors: Konana Prabhudev , Ram Sudha
Published: October 2008

In the future, automated stock trading (AST) databases will need to support execution of transactions with time constraints similar to that discussed in real-time databases. Transactions in AST databases repeat from a predictable set of transaction classes where the logical read-sets and write-sets of these classes can be established a priori. We propose a novel transaction management mechanism that exploits this a priori knowledge of data requirements to minimize wasted resources and transaction restarts inherent in existing real-time transaction processing mechanisms based on dynamic acquisition of resources. Preanalysis provides a mechanism to incorporate transaction semantics, identify potentially detrimental conflicts, and induce favorable serialization orders before transactions execute. By blocking potentially conflicting transactions, we incorporate an implicit overload management technique. Scheduling decisions can be made efficient to complement serialization orders, thus reducing unnecessary transaction restarts. Our protocol is evaluated using simulation and is shown to outperform existing real-time concurrency control mechanisms under various workload and resource parameters.
Matrix Sensitivity Analysis from an Interior Solution of a Linear Program
Authors: Greenberg Harvey J.
Published: October 2008

This article considers the effect of changing matrix coefficients in a linear program after we have obtained an interior solution. Changes are restricted to where there remains an optimal solution to the perturbed problem (called “admissible”). Mills' minimax theorem provides one approach and has been used for similar sensitivity analysis from a basic optimum. Here we consider the effect on the optimal partition and how the analysis results relate to the classical approach that uses a basic solution.
A Fuzzy Hopfield-Tank Traveling Salesman Problem Model
Authors: Wolfe William J.
Published: October 2008

This article describes a Hopfield-Tank model of the Euclidean traveling salesman problem (using Aiyer's subspace approach) that incorporates a “fuzzy” interpretation of the rows of the activation array. This fuzzy approach is used to explain the network's behavior. The fuzzy interpretation consists of computing the center of mass of the positive activations in each row. This produces real numbers along the time line, one for each city, and defines a tour in a natural way (referred to as a “fuzzy tour”). A fuzzy tour is computed at each iteration, and examination of such tours exposes fine features of the network dynamics. For example, these tours demonstrate that the network goes through (at least) three phases: “centroid,” “monotonic,” and “nearest-city.” The centroid (initial) phase of the network produces an approximation to the centroid tour (i.e., the tour that orders the cities by central angle with respect to the centroid of the cities). The second phase produces an approximation to the monotonic tour (i.e., the tour that orders the cities by their projection onto the principal axis of the cities). The third phase produces an approximation to a nearest-city tour, that is, a tour whose length is between the tour lengths of the nearest-city-best (best starting city) and nearest-city-worst (worst starting city). Simulations are presented for up to 125 uniformly randomly generated cities.
Optimal Integer Solutions to Industrial Cutting Stock Problems
Authors: Degraeve Zeger , Schrage Linus
Published: October 2008

The “textbook” treatment of the cutting stock problem, using a method termed column generation, solves the problem as if one is allowed to use fractional amounts of patterns. In practice, one can typically run only an integer quantity of a pattern. Dyckhoff was the first to propose an integer linear programming formulation for the problem of getting a guaranteed global optimum to cutting stock problems under the integrality requirement. We describe and test an extension of a method proposed by Degraeve for embedding a column generation procedure within branch and bound. We show that our algorithm is quite general. It can easily cope with various combinations of real world complications, such as 1) upper bounds on the amount by which the demand may be oversatisfied, 2) a limit on maximum waste allowed in each pattern, and 3) a limit on the maximum number of knives in the cutting patterns. We validate our approach using both industrial data sets from the paper industry and generated data sets. The performance of the algorithm is compared with Dyckhoff's formulation.
Handling Sensor Data in Rapidly Changing Environments to Support Soft Real-Time Requirements
Authors: Datta Anindya , Viguier Igor R.
Published: October 2008

Databases have been mandated as the chosen platform to develop automated control systems for environments where the state of the system changes rapidly and actions need to be taken with timing constraints, for example, stock trading, air traffic control, network management, and process control to name a few. Input data in such systems come from sensors distributed throughout the physical environment being monitored. As the system state changes rapidly, the sensors report information fast and with high volumes. Control decisions in such systems are highly dependent on the accuracy and timeliness of such recorded sensor-reported data. In this paper we suggest ways to algorithmically maintain the accuracy and timeliness of sensor data by enforcing two properties termed recency and temporal consistency. Simultaneously, our algorithms also attempt to satisfy quality of service requirements on response times of queries submitted in such systems. The performance of these algorithms is validated through an extensive simulation.
Editor's Introduction
Authors: Greenberg Harvey J.
Published: October 2008

Dedication to deceased distinguished leaders in the field: Darwin D. Klingman and William Orchard-Hays. Brief overview of papers published in the issue.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Identifying Minimally Infeasible Subsystems of Inequalities
Authors: Gleeson John , Ryan Jennifer
Published: October 2008

Given an infeasible system of linear inequalities, we show that the problem of identifying all minimally infeasible subsystems can be reduced to the problem of finding all vertices of a related polyhedron. This results in a shorter enumeration than that performed by previous method to solve this problem.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
On Valuation and Optimization Problems in Fuzzy Graphs: A General Approach and Some Particular Cases
Authors: Delgado Miguel , Verdegay Jose L. , Vila Maria-Amparo
Published: October 2008

This deals with the problem of valuation and optimization in fuzzy graphs in a general manner. Valuations are defined as functions depending on membership levels. A general solution procedure is developed for optimization problems on the basis of α-cut representation. Finally, this procedure is applied to a classical problem: to find the minimal path in a fuzzy graph.

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

Attributed graphs are a widely used paradigm for representing management science models. Examples include vehicle routing, production planning, simulation and decision trees. With the proliferation of computer graphics, direct manipulation interfaces have been created for many of these models. Although such systems can facilitate modeling and analysis, they generally prove quite expensive to develop. Since all of these models can be represented using an attributed graph, one can exploit that commonality to develop tools and techniques to facilitate developing computer graphics interfaces for such models. This paper discusses the concept of such a graph-based modeling system (GBMS) and a prototype implementation (Networks) that facilitates the creation of computer graphics interfaces for models that can be represented as attributed graphs. This study is divided into two parts; part I presents an overall introduction to the concepts; part II will discuss these concepts in detail.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Using Simulated Annealing to Solve Controlled Rounding Problems
Authors: Kelly James , Golden Bruce , Assad Arjang
Published: October 2008

Controlled rounding is a procedure whereby tabular data gathered from respondents is perturbed in such a way as to preserve the anonymity of the respondents while maintaining the integrity of the data. This paper describes an algorithm for solving three-dimensional controlled rounding problems which is based on simulated annealing, linear programming, and binary search procedures. Numerical results obtained from processing 32,500 randomly generated tables and 292 real-life tables have demonstrated that this algorithm can efficiently find controlled roundings, provided they exist. The algorithm is significantly faster than any previously known solution procedure for this class of problems.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Backbone Network Design Tools with Economic Tradeoffs
Authors: Gavish Bezalel , Altinkemer Kemal
Published: October 2008

This paper studies the problem of assigning capacities to the links in a backbone network and determining the primary routes used by messages for each origin-destination communicating pair in the network. The topology of the backbone network is assumed to be known and the end to end traffic requirements are given. The problem is to find the least cost design where the system costs are composed of connection costs which depend on link capacities and queueing costs which are incurred by users due to the limited capacities of links. The goal is to determine the routing and link capacities simultaneously. The problem is formulated and lower bounds are obtained by Lagrangean relaxation embedded in a subgradient optimization procedure. Cut constraints which are redundant in the original formulation are introduced, they improve the lower bounds. A heuristic method based on the Lagrangean solution is described. Extensive computational results are reported.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Path Planning in 0/1/∞ Weighted Regions with Applications
Authors: Gewali Laxmi P. , Meng Alex C. , Mitchell Joseph S. B. , Ntafos Simeon
Published: October 2008

We consider the terrain navigation problem in a two-dimensional polygonal subdivision with three types of regions: obstacles, “free” regions (in which one can travel at no cost), and regions in which cost is proportional to distance traveled. We present an algorithm whose running time is O(E + nlog n), where n is the number of vertices representing the subdivision, and E is bounded above by the size of the visibility graph induced by the set of obstacles and free regions, which is no worse than quadratic (O(n2)). In addition, we present algorithms to solve a variety of important generalizations and applications: (1) an O(n2) algorithm for constructing a critical graph of size O(n2) (which can be searched in time O(n2log n) for shortest paths) for the case in which linear features (roads) are added, thereby allowing arbitrary weights on the edges of the subdivision; (2) similar time bounds for the case in which the linear features include a possible “cost of crossing”; (3) an O(n2W) algorithm for finding lexicographically shortest paths in weighted regions (with W different weights); (4) an O(k2n2) algorithm for planning least-risk paths in a simple polygon that contains k line-of-sight threats (this becomes O(k4n4) in polygons with holes); and (5) an O(k2n3) algorithm for finding least-risk watchman routes in simple rectilinear polygons (a watchman route is such that each point in the polygon is visible from at least one point along the route).

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Computing Sparse LU Factorizations for Large-Scale Linear Programming Bases
Authors: Suhl Uwe H. , Suhl Leena M.
Published: October 2008

This paper discusses the computation of LU factorizations for large sparse matrices with emphasis on large-scale linear programming bases. We present new implementation techniques which reduce the computation times significantly. Numerical experiments with large-scale real life test problems were conducted. The software is compared with the basis factorization of MPSX/370, IBM's commercial LP system.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Discrete Event Simulation Model Decomposition by Principal Components Analysis
Authors: Bauer Kenneth W. , Kochar Bipin , Talavage Joseph J.
Published: October 2008

A solution is offered to the simulation model decomposition problem. Discrete-event simulation models as described by condition specifications (CS) are cast as cluster interaction graphs (CIGs). These CIGs are analyzed using rotated principal component solutions. The loading patterns of these solutions provide a suggested decomposition. The method is demonstrated on a small CS of a harbor simulation model, as well as a larger CS of a flexible manufacturing system (FMS) simulation.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
On Finding Primal- and Dual-Optimal Bases
Authors: Megiddo Nimrod
Published: October 2008

We show that if there exists a strongly polynomial time algorithm that finds a basis which is optimal for both the primal and the dual problems, given an optimal solution for one of the problems, then there exists a strongly polynomial algorithm for the general linear programming problem. On the other hand, we give a strongly polynomial time algorithm that finds such a basis, given any pair of optimal solutions (not necessarily basic) for the primal and the dual problems. Such an algorithm is needed when one is using an interior point method and is interested in finding a basis which is both primal- and dual-optimal.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Unique Names Violations, a Problem for Model Integration or You Say Tomato, I Say Tomahto
Authors: Bhargava Hemant K. , Kimbrough Steven O. , Krishnan Ramayya
Published: October 2008

The tomato-tomahto problem (known as the synonymy problem in the database literature) arises in the context of model management when different names are used in different models for what should be identical variables, and these different models are to be integrated or combined into a larger model. When this problem occurs, it is said that the unique names assumption has been violated. We propose a method by which violations of the unique names assumption can be automatically detected. The method relies on declaring four kinds of information and modeling variables: dimensional information, laws relating dimensional expressions, information (called the quiddity) about the intended interpretation of the variables, and laws relating quiddity expressions. We present and discuss the method and the principles and theory behind it, and we describe our (prototype) implementation of the method, as an additional function of an existing model management system.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Locating Minimal Infeasible Constraint Sets in Linear Programs
Authors: Chinneck John W. , Dravnieks Erik W.
Published: October 2008

With ongoing advances in hardware and software, the bottleneck in linear programming is no longer a model solution, it is the correct formulation of large models in the first place. During initial formulation (or modification), a very large model may prove infeasible, but it is often difficult to determine how to correct it. We present a formulation aid which analyzes infeasible LPs and identifies minimal sets of inconsistent constraints from among the perhaps very large set of constraints defining the problem. This information helps to focus the search for a diagnosis of the problem, speeding the repair of the model. We present a series of filtering routines and a final integrated algorithm which guarantees the identification of at least one minimal set of inconsistent constraints. This guarantee is a significant advantage over previous methods. The algorithms are simple, relatively efficient, and easily incorporated into standard LP solvers. Preliminary computational results are reported.

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

Review of: D. E. Goldberg, 1989. Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading, MA. Reviewed by: Jennifer Ryan.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Optimal Partial-Match Hashing Design
Authors: Jagannathan Raj
Published: October 2008

This paper suggests a method for determining an optimal hashing design for answering a partial-match query. Solution methods are suggested for the knapsack-type model, derived under the assumption that the attributes in a query are specified independently. It is further shown that the same nonlinear knapsack-type model holds even when the independence assumption is relaxed.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
A Pruning Procedure for Exact Graph Coloring
Authors: Sager Thomas J. , Lin Shi-Jen
Published: October 2008

The graph coloring problem can be stated: “Given an undirected graph, using a minimal number of colors, assign each vertex a color so that if two vertices are connected by an edge then they are not assigned the same color.” Graph coloring can be used to solve scheduling problems with constraints of the form: events e and e' cannot be scheduled together. Graph coloring is an NP-hard problem. Generally, large problems are solved heuristically, although some of the better heuristic algorithms use an exact graph coloring algorithm to finish coloring a graph after first reducing it heuristically to manageable size. Exact graph coloring is important both in its own right and as a component of heuristic coloring. We present an improved exact graph coloring algorithm which runs, in the mean, over 20% faster than the DSATUR algorithm on some classes of random graphs. The improvement over DSATUR stems from the ability to prune the search tree by detecting, in certain instances, the existence of a complete subgraph of cardinality equal to the number of colors used in the best coloring found so far.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Approaches to Diagnosing Infeasible Linear Programs
Authors: Greenberg Harvey J. , Murphy Frederic H.
Published: October 2008

This paper addresses the problem of diagnosing an infeasible linear program. In practice, there are several approaches one may take, most generally using the Phase I dual variables as an initial guide. Other approaches, however, have emerged to complement the traditional ones. These and new approaches are presented here with the aim of building a toolkit for automatic reasoning when an LP expert is not available.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Bounding Synchronization Overhead for Parallel Iteration
Authors: Downey Peter J.
Published: October 2008

Suppose m stochastically identical iterative processes are run in parallel. Each iteration of the process runs for a random time X, distributed identically and independently for each iteration. At the end of each iteration, each process checks a shared variable to see whether some global event has occurred; if it has, the process terminates and instantly joins a rendezvous with the other processes that have detected the event. The synchronization overhead is the time R(m)(t) needed to complete the rendezvous, measured from the time t of occurrence of the event (t is assumed to be independent of the m processes). It is not true (for general X) that ER(m)(t)≤EX, because t will more probably occur during a long iteration than a short one, and because R(m)(t) is an extreme value of a sample of size m. In renewal theory the random variable R(1)(t) is called the excess at t, and R(m)(t) will be the extreme of m i.i.d. excesses. While exact expressions for ER(m)(t) are impossible to obtain in practice, we give useful upper bounds. The bounds get tighter depending on information known about the underlying distribution of X. Results include: (1) a general bound valid for any X having finite third moment, (2) a better bound valid if X is dominated by an exponential in stochastic variability ordering, (3) an even better bound if X has bounded mean residual life, and (4) a bound valid when X has decreasing failure rate. The results are applied to searching a table in parallel and to on-line makespan scheduling.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
TES: A Class of Methods for Generating Autocorrelated Uniform Variates
Authors: Melamed Benjamin
Published: October 2008

This paper introduces a class of methods called TES (Transform-Expand-Sample) for generating autocorrelated variates with uniform marginals and Markovian structure. TES methods are readily implemented on a computer and have generation complexity comparable to that of the i.i.d. uniform sequence which they transform to an autocorrelated uniform sequence. For any prescribed correlation coefficient ρ, there is a TES method generating a uniform sequence with the 1-lag autocorrelation ρ, and the resultant autocorrelation is monotonic quadratic in two structural TES parameters. A simulation study reveals that TES methods give rise to autocorrelation functions with monotone decreasing as well as oscillating magnitude, bounded by monotone envelopes. The structural parameters were found to control the “amplitude” and “frequency” of the resultant autocorrelation function. A third parameter can be used to transform a TES sequence into more continuous-looking versions and to control the skewness of sample path cycles.

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