bluuebunny/crossref_metadata_2025 huggingface dataset:
Solid-state Photopolymerization of Diacetylene-containing Carboxylates with Naphthylmethylammonium as the Countercation in a Two-dimensional Array
Authors: Matsumoto Akikazu , Matsumoto Akinori , Kunisue Takafumi , Tanaka Akira , Tohnai Norimitsu , Sada Kazuki , Miyata Mikiji
Published: December 2003

Naphthylmethylammonium salts of a series of diacetylene-containing carboxylic acids with various sizes of alkyl chains were photopolymerized in the crystalline state. X-ray crystal structure analyses confirmed lamellar structures characterized with the two-dimensional hydrogen networks formed between carboxylate anion and countercation layers in the crystals. The absorption properties of the resulting polymers depended on the length of alkyl substituents.
Internet-Type Queues with Power-Tailed Interarrival Times and Computational Methods for Their Analysis
Authors: Harris Carl M. , Brill Percy H. , Fischer Martin J.
Published: December 2003

Internet traffic flows have often been characterized as having power-tailed (long-tailed, fat-tailed, heavy-tailed) packet interarrival times or service requirements. In this work, we focus on the development of complete and computationally efficient steady-state solutions of queues with power-tailed interarrival times when the service times are assumed exponential. The classical method for obtaining the steady-state probabilities and delay-time distributions for the G/M/1 (G/M/c) queue requires solving a root-finding problem involving the Laplace-Stieltjes transform of the interarrival-time distribution function. Then the exponential service assumption is combined with the derived geometric arrival-point probabilities to get both the limiting general-time state and delay distributions. However, in situations where there is a power tail, the interarrival transform is typically quite complicated and never analytically tractable. In addition, it is possible that there is only a degenerate steady-state system-size probability distribution. Thus, an alternative approach to obtaining a steady-state solution is typically needed when power-tailed interarrivals are present. We exploit the exponentiality of the steady-state delay distributions for the G/M/1 and G/M/c queues, using level-crossings and a transform approximation method, to develop an alternative root-finding problem when there are power-tailed interarrival times. Extensive computational results are given.
Enhanced Model Representations for an Intra-Ring Synchronous Optical Network Design Problem Allowing Demand Splitting
Authors: Sherali Hanif D. , Smith J. Cole , Lee Youngho
Published: December 2003

In this paper, we consider a network design problem arising in the context of deploying synchronous optical networks (SONET) using a unidirectional path switched ring architecture, a standard of transmission using optical fiber technology. Given several rings of this type, the problem is to find an assignment of nodes to possibly multiple rings, and to determine what portion of demand traffic between node pairs spanned by each ring should be allocated to that ring. The constraints require that the demand traffic between each node pair should be satisfiable given the ring capacities, and that no more than a specified maximum number of nodes should be assigned to each ring. The objective function is to minimize the total number of node-to-ring assignments, and hence, the capital investment in add-drop multiplexer equipments. We formulate the problem as a mixed-integer programming model, and propose several alternative modeling techniques designed to improve the mathematical representation of this problem. We then develop various classes of valid inequalities for the problem along with suitable separation procedures for tightening the representation of the model, and accordingly, prescribe an algorithmic approach that coordinates tailored routines with a commercial solver (CPLEX). We also propose a heuristic procedure which enhances the solvability of the problem and provides bounds within 5–13% of the optimal solution. Promising computational results are presented that exhibit the viability of the overall approach and that lend insights into various modeling and algorithmic constructs.
General Open and Closed Queueing Networks with Blocking: A Unified Framework for Approximation
Authors: Vroblefski Mark , Ramesh R. , Zionts Stanley
Published: December 2003

In this paper, we develop a unified framework for approximating open and closed queueing networks under any general blocking protocol by extending and generalizing the approximation algorithm for open tandem queues under minimal blocking presented in Di Mascolo et al. (1996). The proposed framework is based on decomposition. We develop decomposition structures and analysis algorithms for any general blocking system using the framework. The proposed algorithms have been extensively tested using simulations as a benchmarking device. The results show that the proposed framework yields robust, reliable, and accurate estimates of system characteristics, such as throughput and Work-In-Process inventory in a wide range of system configurations. The computational load is minimal. The unified framework presents a highly useful set of tools of analysis for queueing-system designers to use in evaluating the performance under numerous design alternatives. Directions for future research are presented, with a focus on critical application areas such as packet-switching-network design and cellular manufacturing.
Approximation of Point Sets by 1-Corner Polygonal Chains
Authors: Díaz-Báñez José-Miguel , Gómez Francisco , Hurtado Ferran
Published: December 2003

In this paper we consider some problems that belong to the interplay between the field of Facility Location and the area of Computational Geometry. Specifically, given a set S of points in the plane, we discuss several variations of the problem of finding monotone 1-corner polygonal chains that minimize the maximum vertical distance to S.
Multiple-Machine Lower Bounds for Shop-Scheduling Problems
Authors: Sourd Francis , Nuijten Wim
Published: December 2003

In order to compute lower bounds for shop scheduling problems, a lot of attention has been paid to adjustment techniques based on one-machine relaxations. We present such a new technique but, following the observation that machines are connected to each other through precedence constraints, we also study techniques that are based on the combination of precedence constraints and disjunctive constraints between operations that are processed on different machines. A computational study of the effectiveness of these new techniques is performed on job-shop and flow-shop instances.
Cascade Graphs: Design, Analysis and Algorithms for Relational Joins
Authors: Gopal Ram D. , Ramesh R. , Zionts Stanley
Published: December 2003

The focus of this work is on join optimization in relational database systems. The importance of join optimization is critically underscored by the high cost of relational joins and their frequent needs in traditional as well as emerging database applications. We demonstrate that the sequence in which the pages of the relations are accessed to process a join is a critical determinant of the join execution cost and an optimization of this sequence can lead to a significant improvement in performance over the traditional approaches. We initially develop three network structures to represent a join on two relations: page connectivity graph, cascade and block tree cascade. A page connectivity graph is a bipartite representation of the set of connected pages in the two relations according to the join predicate. To reveal the structural properties of the join, the nodes of the bipartite graph are ordered into a set of levels, and the resulting isomorphic structure is termed a cascade. From the cascade, a tree structure termed a block tree cascade is derived by selectively grouping nodes at each level of the cascade into blocks. We formulate the join as a tree traversal process, and accordingly develop efficient tree traversal algorithms. We develop a compact data structure to store the resulting access path, and provide a comprehensive analysis of the algorithms with detailed assessments of their performance. The performance evaluation demonstrates that the proposed approach can result in significant cost savings over the current join processing methods, for low to modest values of the join selectivity factor.
A Flexible Java Representation for Uncertainty in Online Operations-Research Models
Authors: Shapiro Joel A. , Powell Warren B. , Bernstein David
Published: December 2003

Online OR models have been the subject of increased attention in recent years with the rapid expansion of the Internet. Although much has been written about the implementation, as well as the formal analysis of online models, little has been said about how to handle uncertainty in an online setting. In particular, the dynamic nature of uncertainty that is so characteristic of online models, where estimates and distributions evolve in parallel with the state of the model, has been largely ignored. In this paper, we present a new representation for uncertainty in online models. This representation is object-oriented and, as such, provides several important software-engineering advantages over traditional representations for uncertainty. Moreover, by using the event listener paradigm it provides an explicit mechanism for handling dynamic uncertainty in an elegant and extensible manner. A series of computational experiments demonstrates that there is no significant overhead to our representation when compared to traditional representations on a realistic application and, in some cases, our representation can be noticeably faster.
Linear Time Dynamic-Programming Algorithms for New Classes of Restricted TSPs: A Computational Study
Authors: Balas Egon , Simonetti Neil
Published: December 2003

Consider the following restricted (symmetric or asymmetric) traveling-salesman problem (TSP): given an initial ordering of the n cities and an integer k > 0, find a minimum-cost feasible tour, where a feasible tour is one in which city i precedes city j whenever j ≥ i + k in the initial ordering. Balas (1996) has proposed a dynamic-programming algorithm that solves this problem in time linear in n, though exponential in k. Some important real-world problems are amenable to this model or some of its close relatives.

The algorithm of Balas (1996) constructs a layered network with a layer of nodes for each position in the tour, such that source-sink paths in this network are in one-to-one correspondence with tours that satisfy the postulated precedence constraints. In this paper we discuss an implementation of the dynamic-programming algorithm for the general case when the integer k is replaced with city-specific integers k(j), j = 1, . . ., n.

We discuss applications to, and computational experience with, TSPs with time windows, a model frequently used in vehicle routing as well as in scheduling with setup, release and delivery times. We also introduce a new model, the TSP with target times, applicable to Just-in-Time scheduling problems. Finally for TSPs that have no precedence restrictions, we use the algorithm as a heuristic that finds in linear time a local optimum over an exponential-size neighborhood. For this case, we implement an iterated version of our procedure, based on contracting some arcs of the tour produced by a first application of the algorithm, then reapplying the algorithm to the shrunken graph with the same k.
The Bounded Cycle-Cover Problem
Authors: Hochbaum Dorit S. , Olinick Eli V.
Published: December 2003

We consider the bounded cycle-cover problem, which is to find a minimum cost cycle cover of a two-connected graph such that no cycle in the cover contains more than a prescribed numbered of edges. This problem arises in the design of fiber-optic telecommunications networks that employ multiple self-healing rings to provide routing for communication traffic, even in the event of a fiber cut or other type of link failure. We present this problem, along with several related problems, and develop heuristic algorithms that find near optimal solutions for the bounded cycle-cover problem based on solution techniques for these related problems. Empirical results of these algorithms, applied to randomly generated problem instances, are presented and discussed.
Properties of Batched Quadratic-Form Variance Parameter Estimators for Simulations
Authors: Alexopoulos Christos , Goldsman David , Tokol Gamze
Published: December 2003

We examine the practice of batching of certain quadratic-form estimators for the variance parameter of a stochastic process. The class of batched quadratic-form estimators includes, among others, the standardized time series (STS) weighted area and weighted Cramér-von Mises estimators. We give results on the expected value and variance of such estimators as the batch size and/or the number of batches increase. In particular, we show that the above STS estimators are consistent for the variance parameter in terms of mean squared error. An analytical example involving a first-order autoregressive process illustrates our findings.
Representations of the all_different Predicate of Constraint Satisfaction in Integer Programming
Authors: Williams H.P. , Yan Hong
Published: December 2003

The use of predicates to state constraints in Constraint Satisfaction is explained. If, as an alternative, the traditional approach of Integer Programming (IP) is used, it is desirable to model these constraints so as to give as tight a linear programming relaxation as possible. One of the most commonly used predicates is the “all_different” predicate. Different applications of this are described together with different IP formulations. The facet defining constraints for the convex hull are then described and proved to be facet defining.
Modeling and Analysis of Discrete-Time Multiserver Queues with Batch Arrivals: GIX/Geom/m
Authors: Chaudhry M. L. , Gupta U. C. , Goswami V.
Published: December 2003

Multiserver queues are often encountered in telecommunication systems and have special importance in the design of ATM networks. This paper analyzes a discrete-time multiserver queueing system with batch arrivals in which the interbatch and service times are, respectively, arbitrarily and geometrically distributed. Using supplementary-variable and embedded-Markov-chain techniques, the queue is analyzed only for the early arrival system. Since the late arrival system can be discussed similarly, it is not considered here. In addition to developing relations among state probabilities at prearrival, arbitrary, and outside observer's observation epochs, the numerical evaluation of state probabilities is also discussed. It is also shown that, in the limiting case, the relations developed here tend to continuous-time counterparts. Further, the waiting-time distribution of a random customer of a batch is obtained. Finally, in some cases simulation experiments have been performed to validate our results.
The Path Restoration Version of the Spare Capacity Allocation Problem with Modularity Restrictions: Models, Algorithms, and an Empirical Analysis
Authors: Kennington Jeffery L. , Lewis Mark W.
Published: December 2003

This investigation presents a strategy to construct a compact mathematical model of the path-restoration version of the spare capacity allocation problem. The strategy uses a node-arc formulation and combines constraints whenever multiple working paths affected by an edge failure have identical origins or destinations. Another unique feature of this model is the inclusion of modularity restrictions corresponding to the discrete capacities of the equipment used in telecommunication networks.

The new model can be solved using a classical branch-and-bound algorithm with a linear-programming relaxation. A preprocessing module is developed, which generates a set of cuts that strengthens this linear programming relaxation. The overhead associated with the cuts is offset by the improved bounds produced. A new branch-and-bound algorithm is developed that exploits the modularity restrictions. In an extensive empirical analysis, a software implementation of this algorithm was found to be substantially faster than CPLEX 6.5.3. For a test suite of 50 problems, each having 50 nodes and 200 demands from a uniform distribution with a small variance, our new software obtained solutions guaranteed to be within 4% of optimality in five minutes of CPU time on a DEC AlphaStation.
Fast Heuristics for the Maximum Feasible Subsystem Problem
Authors: Chinneck John W.
Published: December 2003

Given an infeasible set of linear constraints, finding the maximum cardinality feasible subsystem is known as the maximum feasible subsystem problem. This problem is known to be NP-hard, but has many practical applications. This paper presents improved heuristics for solving the maximum feasible subsystem problem that are significantly faster than the original, but still highly accurate.
Algorithms for Hybrid MILP/CP Models for a Class of Optimization Problems
Authors: Jain Vipul , Grossmann Ignacio E.
Published: December 2003

The goal of this paper is to develop models and methods that use complementary strengths of Mixed Integer Linear Programming (MILP) and Constraint Programming (CP) techniques to solve problems that are otherwise intractable if solved using either of the two methods. The class of problems considered in this paper have the characteristic that only a subset of the binary variables have non-zero objective function coefficients if modeled as an MILP. This class of problems is formulated as a hybrid MILP/CP model that involves some of the MILP constraints, a reduced set of the CP constraints, and equivalence relations between the MILP and the CP variables. An MILP/CP based decomposition method and an LP/CP-based branch-and-bound algorithm are proposed to solve these hybrid models. Both these algorithms rely on the same relaxed MILP and feasibility CP problems. An application example is considered in which the least-cost schedule has to be derived for processing a set of orders with release and due dates using a set of dissimilar parallel machines. It is shown that this problem can be modeled as an MILP, a CP, a combined MILP-CP OPL model (Van Hentenryck 1999), and a hybrid MILP/CP model. The computational performance of these models for several sets shows that the hybrid MILP/CP model can achieve two to three orders of magnitude reduction in CPU time.
Convergence Properties of the Batch Means Method for Simulation Output Analysis
Authors: Steiger Natalie M. , Wilson James R.
Published: December 2003

We examine key convergence properties of the steady-state simulation analysis method of nonoverlapping batch means (NOBM) when it is applied to a stationary, phi-mixing process. For an increasing batch size and a fixed batch count, we show that the standardized vector of batch means converges in distribution to a vector of independent standard normal variates—a well-known result underlying the NOBM method for which there appears to be no direct, readily accessible justification. To characterize the asymptotic behavior of the classical NOBM confidence interval for the mean response, we formulate certain moment conditions on the components (numerator and denominator) of the associated Student's t-ratio that are necessary to ensure the validity of the confidence interval. For six selected stochastic systems, we summarize an extensive numerical analysis of the convergence to steady-state limits of these moment conditions; and for two systems we present a simulation-based analysis exemplifying the corresponding convergence in distribution of the components of the NOBM t-ratio. These results suggest that in many simulation output processes, approximate joint normality of the batch means is achieved at a substantially smaller batch size than is required to achieve approximate independence; and an improved batch means method should exploit this property whenever possible.
The Semismooth Algorithm for Large Scale Complementarity Problems
Authors: Munson Todd S. , Facchinei Francisco , Ferris Michael C. , Fischer Andreas , Kanzow Christian
Published: December 2003

Complementarity solvers are continually being challenged by modelers demanding improved reliability and scalability. Building upon a strong theoretical background, the semismooth algorithm has the potential to meet both of these requirements. We discuss relevant theory associated with the algorithm and then describe a sophisticated implementation in detail. Particular emphasis is given to the use of preconditioned iterative methods to solve the (nonsymmetric) systems of linear equations generated at each iteration and robust methods for dealing with singularity. Results on the MCPLIB test suite indicate that the code is reliable and efficient and scales well to very large problems.
Initialization for NORTA: Generation of Random Vectors with Specified Marginals and Correlations
Authors: Chen Huifen
Published: December 2003

We propose a specific method for generating n-dimensional random vectors with given marginal distributions and correlation matrix. The method uses the NORTA (NORmal To Anything) approach, which generates a standard normal random vector and then transforms it into a random vector with specified marginal distributions. During initialization, n(n-1)/2 nonlinear equations need to be solved to ensure that the generated random vector has the specified correlation structure. To solve these equations, we apply retrospective approximation, a generic stochastic root-finding algorithm, with slight changes. Internal control variates are used to estimate function values. Empirical comparisons show that the control-variate variance-reduction technique improves the algorithm's convergence speed as well as its robustness. Simulation results for a variety of marginal distributions and correlation matrices are also presented.
A Dynamic Programming Based Pruning Method for Decision Trees
Authors: Li Xiao-Bai , Sweigart James , Teng James , Donohue Joan , Thombs Lori
Published: December 2003

This paper concerns a decision-tree pruning method, a key issue in the development of decision trees. We propose a new method that applies the classical optimization technique, dynamic programming, to a decision-tree pruning procedure. We show that the proposed method generates a sequence of pruned trees that are optimal with respect to tree size. The dynamic-programming-based pruning (DPP) algorithm is then compared with cost-complexity pruning (CCP) in an experimental study. The results of our study indicate that DPP performs better than CCP in terms of classification accuracy.
Phantom Harmonic Gradient Estimators for Nonpreemptive Priority Queueing Systems
Authors: Vázquez-Abad Felisa J. , Jacobson Sheldon H.
Published: December 2003

This paper presents a new gradient estimator for the steady-state expected sojourn (system) time in a nonpreemptive priority queueing system. The estimator uses the concept of a phantom system, together with the basic ideas in harmonic gradient estimation, to develop a single simulation run estimator, termed the phantom harmonic gradient (PHG) estimator. The estimator is shown to be strongly consistent and strongly consistent in the average sense as the sample size grows. An upper bound for the variance of the PHG estimator is presented. This bound is used to show that under mild conditions, the variance of the PHG estimator tends to zero as both the number of phantom systems and the sample size approach infinity. A variance-reduction technique that simultaneously uses both common and antithetic random numbers is presented. Computational results on several nonpreemptive queueing systems illustrate the effectiveness of the method and show that common and antithetic random numbers can be used simultaneously to reduce the variance of the phantom harmonic gradient estimator.
Ranking and Selection for Steady-State Simulation: Procedures and Perspectives
Authors: Goldsman David , Kim Seong-Hee , Marshall William S. , Nelson Barry L.
Published: December 2003

We present and evaluate three ranking-and-selection procedures for use in steady-state simulation experiments when the goal is to find which among a finite number of alternative systems has the largest or smallest long-run average performance. All three procedures extend existing methods for independent and identically normally distributed observations to general stationary output processes, and all procedures are sequential. We also provide our thoughts about the evaluation of simulation design and analysis procedures, and illustrate these concepts in our evaluation of the new procedures.
A MINSAT Approach for Learning in Logic Domains
Authors: Felici Giovanni , Truemper Klaus
Published: December 2003

This paper describes a method for learning logic relationships that correctly classify a given data set. The method derives from given logic data certain minimum cost satisfiability problems, solves these problems, and deduces from the solutions the desired logic relationships. Uses of the method include data mining, learning logic in expert systems, and identification of critical characteristics for recognition systems. Computational tests have proved that the method is fast and effective.
Combining Column Generation and Lagrangean Relaxation to Solve a Single-Machine Common Due Date Problem
Authors: van den Akker Marjan , Hoogeveen Han , van de Velde Steef
Published: December 2003

Column generation has proved to be an effective technique for solving the linear programming relaxation ofhuge set covering or set partitioning problems, and column generation approaches have led to state-of-the-art so-called branch-and-price algorithms for various archetypical combinatorial optimization problems. We use a combination of column generation and Lagrangean relaxation to tackle a single-machine common due date problem, where Lagrangean relaxation is exploited for early termination of the column generation algorithm and for speeding up the pricing algorithm. We show that the Lagrangean lower bound dominates the lower bound that can be derived from the column generation algorithm when applied to the standard linear programming formulation, but we also show how the linear programming formulation can be adapted such that the corresponding lower bound is equal to the Lagrangean lower bound.

Our comprehensive computational study shows that the combined algorithm is by far superior to two existing purely column generation algorithms: it solves instances with up to 125 jobs to optimality, while a purely column generation algorithm can solve instances with up to only 60 jobs.
Minimax Models for Diverse Routing
Authors: Brumbaugh-Smith James P. , Shier Douglas R.
Published: December 2003

An important task in the management and administration of communication networks is constructing routes for messages to follow from source to destination. A common approach is to route along the shortest available path connecting the source to the destination, where link lengths can be defined in a variety of ways (e.g., time, cost, impact on average queueing delay, or capacity required). This paper presents a family of novel minimax models for determining a set of paths from the source to the destination that are reasonably short in length while also reasonably diverse (disjoint). The overall goal is to design a routing scheme that is both ef.cient and robust, resulting in greater network reliability. Several models are investigated and a column-generation approach is proposed for exact solution. Computational results show that this exact technique can be applied effectively to moderate sized networks. For even larger networks, heuristic methods are developed and tested.
MINLPLib—A Collection of Test Models for Mixed-Integer Nonlinear Programming
Authors: Bussieck Michael R. , Drud Arne Stolbjerg , Meeraus Alexander
Published: December 2003

The paper describes a new computerized collection of test models for mixed-integer nonlinear programming. Because there is no standard format for nonlinear models, the model collection is augmented with a translation server that can transform the models from their basic GAMS format into other formats, including AMPL, BARON, LGO, LINGO, and MINOPT. The translation server can also be used to transform industrial models that contain confidential information. Such transformations allow many of these models to be distributed to the research community as highly relevant algorithmic test models.
A Genetic Algorithm-Based Approach for Building Accurate Decision Trees
Authors: Fu Zhiwei , Golden Bruce L. , Lele Shreevardhan , Raghavan S. , Wasil Edward A.
Published: December 2003

In dealing with a very large data set, it might be impractical to construct a decision tree using all of the points. Even when it is possible, this might not be the best way to utilize the data. As an alternative, subsets of the original data set can be extracted, a tree can be constructed on each subset, and then parts of individual trees can be combined in a smart way to produce an improved final set of feasible trees or a final tree. In this paper, we take trees generated by a commercial decision tree package, namely, C4.5, and allow them to crossover and mutate (using a genetic algorithm) for a number of generations in order to yield trees of better quality. We conduct a computational study of our approach using a real-life marketing data set. In this study, we divide the data set into training, scoring, and test sets, and find that our approach produces uniformly high-quality decision trees. In addition, we investigate the impact of scaling and demonstrate that our approach can be used effectively on very large data sets.
Chained Lin-Kernighan for Large Traveling Salesman Problems
Authors: Applegate David , Cook William , Rohe André
Published: December 2003

We discuss several issues that arise in the implementation of Martin, Otto, and Felten's Chained Lin-Kernighan heuristic for large-scale traveling salesman problems. Computational results are presented for TSPLIB instances ranging in size from 11,849 cities up to 85,900 cities; for each of these instances, solutions within 1% of the optimal value can routinely be found in under one CPU minute on a 300 MHz Pentium II workstation, and solutions within 0.5% of optimal can routinely be found in under ten CPU minutes. We also demonstrate the scalability of the heuristic, presenting results for randomly generated Euclidean instances having up to 25,000,000 cities. For the largest of these random instances, a tour within 1% of an estimate of the optimal value was obtained in under one CPU day on a 64-bit IBM RS6000 workstation.
Efficient and Anonymous Web-Usage Mining for Web Personalization
Authors: Shahabi Cyrus , Banaei-Kashani Farnoush
Published: December 2003

The World Wide Web (WWW) is the largest distributed information space and has grown to encompass diverse information resources. Although the web is growing exponentially, the individual's capacity to read and digest content is essentially fixed. The full economic potential of the web will not be realized unless enabling technologies are provided to facilitate access to web resources. Currently web personalization is the most promising approach to remedy this problem, and web mining, particularly web-usage mining, is considered a crucial component of any efficacious web-personalization system. In this paper, we describe a complete framework for web-usage mining to satisfy the challenging requirements of web-personalization applications. For online and anonymous web personalization to be effective, web usage mining must be accomplished in real time as accurately as possible. On the other hand, web-usage mining should allow a compromise between scalability and accuracy to be applicable to real-life websites with numerous visitors. Within our web-usage-mining framework, we introduce a distributed user-tracking approach for accurate, scalable, and implicit collection of the usage data. We also propose a new model, the feature-matrices (FM) model, to discover and interpret users' access patterns. With FM, various spatial and temporal features of usage data can be captured with flexible precision so that we can trade off accuracy for scalability based on the specific application requirements. Moreover, tunable complexity of the FM model allows real-time and adaptive access pattern discovery from usage data. We define a novel similarity measure based on FM that is specifically designed for accurate classification of partial navigation patterns in real time. Our extensive experiments with both synthetic and real data verify correctness and efficacy of our web-usage-mining framework for anonymous and efficient web personalization.
On the Existence and Significance of Data Preprocessing Biases in Web-Usage Mining
Authors: Zheng Zhiqiang , Padmanabhan Balaji , Kimbrough Steven O.
Published: December 2003

The literature on web-usage mining is replete with data preprocessing techniques, which correspond to many closely related problem formulations. We survey data preprocessing techniques for session-level pattern discovery and compare three of these techniques in the context of understanding session-level purchase behavior on the web. Using real data collected from 20,000 users' browsing behavior over a period of six months, four different models (linear regressions, logistic regressions, neural networks, and classification trees) are built based on data preprocessed using three different techniques. The results demonstrate that the three approaches result in radically different conclusions and provide initial evidence that a data preprocessing bias exists, the effect of which can be significant.
A Framework for the Evaluation of Session Reconstruction Heuristics in Web-Usage Analysis
Authors: Spiliopoulou Myra , Mobasher Bamshad , Berendt Bettina , Nakagawa Miki
Published: December 2003

Web-usage mining has become the subject of intensive research, as its potential for personalized services, adaptive Web sites and customer profiling is recognized. However, the reliability of Web-usage mining results depends heavily on the proper preparation of the input datasets. In particular, errors in the reconstruction of sessions and incomplete tracing of users’ activities in a site can easily result in invalid patterns and wrong conclusions. In this study, we evaluate the performance of heuristics employed to reconstruct sessions from the server log data. Such heuristics are called to partition activities first by user and then by visit of the user in the site, where user identification mechanisms, such as cookies, may or may not be available. We propose a set of performance measures that are sensitive to two types of reconstruction errors and appropriate for different applications in knowledge discovery (KDD) applications.

We have tested our framework on the Web server data of a frame-based Web site. The first experiment concerned a specific KDD application and has shown the sensitivity of the heuristics to particularities of the site's structure and traffic. The second experiment is not bound to a specific application but rather compares the performance of the heuristics for different measures and thus for different application types. Our results show that there is no single best heuristic, but our measures help the analyst in the selection of the heuristic best suited for the application at hand.
Web Business Intelligence: Mining the Web for Actionable Knowledge
Authors: Srivastava Jaideep , Cooley Robert
Published: December 2003

It is estimated that over seven billion static pages exist in the Web today, and backend databases can potentially produce at least three times as many dynamic pages. However, the best search engines index only approximately 20% of the static pages. So the real question is: While the Web is certainly the most amazing and comprehensive information source ever created, are you really getting all the information you need for your specific purpose? The answer to this question is mostly “yes” for the individual user, who uses the Web as an information source for casual purposes. However, for an individual who uses the Web as an essential and comprehensive source of information—for business or research—the answer is quite the opposite. Even a sophisticated Web user requires a significant amount of time and effort to find all of the information needed for a given task. In this paper the concept of Web Business Intelligence (WBI) is introduced, an emerging class of software that leverages the unprecedented content on the Web to extract actionable knowledge in an organizational setting. The contributions include an architecture for WBI, a survey of technologies relevant to the various components of the architecture, and illustration of the value of WBI by means of a detailed example from the e-finance domain. This article concludes with a discussion on the future of WBI.
Tour Merging via Branch-Decomposition
Authors: Cook William , Seymour Paul
Published: December 2003

Robertson and Seymour introduced branch-width as a new connectivity invariant of graphs in their proof of the Wagner conjecture. Decompositions based on this invariant provide a natural framework for implementing dynamic-programming algorithms to solve graph optimization problems. We describe a heuristic method for finding branch decompositions; the method is based on the eigenvector technique for finding graph separators. We use this as a tool to obtain high-quality tours for the traveling salesman problem by merging collections of tours produced by standard traveling salesman heuristics.
An Exact Approach to the Strip-Packing Problem
Authors: Martello Silvano , Monaci Michele , Vigo Daniele
Published: December 2003

We consider the problem of orthogonally packing a given set of rectangular items into a given strip, by minimizing the overall height of the packing. The problem is NP-hard in the strong sense, and finds several applications in cutting and packing. We propose a new relaxation that produces good lower bounds and gives information to obtain effective heuristic algorithms. These results are used in a branch-and-bound algorithm, which was able to solve test instances from the literature involving up to 200 items.
A New Genetic Algorithm for the Quadratic Assignment Problem
Authors: Drezner Zvi
Published: December 2003

In this paper we propose several variants of a new genetic algorithm for the solution of the quadratic assignment problem. We designed a special merging rule for creating an offspring that exploits the special structure of the problem. We also designed a new type of a tabu search, which we term a concentric tabu search. This tabu search is applied on the offspring before consideration for inclusion in the population. The algorithm provided excellent results for a set of 29 test problems having between 30 and 100 facilities.
The Granular Tabu Search and Its Application to the Vehicle-Routing Problem
Authors: Toth Paolo , Vigo Daniele
Published: January 2004

We describe a new variant, called granular tabu search, of the well-known tabu-search approach. The method uses an effective intensification/diversification tool that can be successfully applied to a wide class of graph-theoretic and combinatorial-optimization problems. Granular tabu search is based on the use of drastically restricted neighborhoods, not containing the moves that involve only elements that are not likely to belong to good feasible solutions. These restricted neighborhoods are called granular, and may be seen as an efficient implementation of candidate-list strategies proposed for tabu-search algorithms. Results of computational testing of the proposed approach on the well-known symmetric capacitated and distance-constrained vehicle-routing problem are discussed, showing that the approach is able to determine very good solutions within short computing times.
Symmetric and Asymmetric Parallelization of a Cost-Decomposition Algorithm for Multicommodity Flow Problems
Authors: Cappanera Paola , Frangioni Antonio
Published: January 2004

We study the coarse-grained parallelization of an efficient bundle-based cost-decomposition algorithm for the solution of multicommodity min-cost flow (MMCF) problems. We show that a code exploiting only the natural parallelism inherent in the cost-decomposition approach, i.e., solving the min-cost flow subproblems in parallel, obtains satisfactory efficiencies even with many processors on large, difficult MMCF problems with many commodities. This is exactly the class of instances where the decomposition approach attains its best results in sequential. The parallel code we developed is highly portable and flexible, and it can be used on different machines. We also show how to exploit a common characteristic of current supercomputer facilities, i.e., the side-to-side availability of massively parallel and vector supercomputers, to implement an asymmetric decomposition algorithm where each architecture is used for the tasks for which it is best suited.
Execution Conditions: A Formalization of Event Cancellation in Simulation Graphs
Authors: Ingalls Ricki G. , Morrice Douglas J. , Yücesan Enver , Whinston Andrew B.
Published: January 2004

Simulation graph models provide a powerful and general modeling framework for discrete-event simulation. Within this framework it has been shown that an eventcancellation construct is a modeling convenience rather than a necessary modeling tool. As a result, very little work on the formal development of simulation graph models directly considers an event-canceling construct. However, to the simulation practitioner, the modeling convenience and functionality provided by a canceling construct is important. This is clearly demonstrated by the presence of some sort of event-canceling construct in all the major simulation software packages. This paper extends the simulation graph modeling framework to include a general approach to handling event cancellation. The extension is provided in algorithmic form. We demonstrate how the algorithm can be implemented in event graphs (and the corresponding commercial software SIGMA) and in the commercial software SIMAN.
Matching Assets with Demand in Supply-Chain Management at IBM Microelectronics
Authors: Lyon Peter , Milne R. John , Orzell Robert , Rice Robert
Published: December 2003

In the early 1990s, the IBM Corporation decided that its microelectronics division should expand from producing parts exclusively for other IBM locations to producing a range of products for diverse customers. To overhaul its supply-chain-management applications to handle the new business, it developed intelligent models to match assets with demand to determine which demands it could meet when and to provide manufacturing guidelines. In 1994, the PROFIT team began applying OR techniques to build these tools, interweaving linear programming with a traditional material resource planning algorithm and a heuristic matching process based on clues established in the explosion algorithm. The team has deployed three core applications: a weekly division run that determines customer commitments and manufacturing requirements, daily manufacturing runs that identify the best use of manufacturing resources to meet division requirements, and a division available-to-promise application that facilitates fast response to customers placing orders (not described). This work has improved manufacturing utilization and customer-order response time.
Optimized Crew Scheduling at Air New Zealand
Authors: Butchers E. Rod , Day Paul R. , Goldie Andrew P. , Miller Stephen , Meyer Jeff A. , Ryan David M. , Scott Amanda C. , Wallace Chris A.
Published: December 2003

The aircrew-scheduling problem consists of two important subproblems: the tours-of-duty planning problem to generate minimum-cost tours of duty (sequences of duty periods and rest periods) to cover all scheduled flights, and the rostering problem to assign tours of duty to individual crew members. Between 1986 and 1999, Air New Zealand staff and consultants in collaboration with the University of Auckland have developed eight application-specific optimization-based computer systems to solve all aspects of the tours-of-duty planning and rostering processes for Air New Zealand's national and international operations. These systems have saved NZ$15,655,000 per year while providing crew rosters that better respect crew members' preferences.
Enhancements to the FAA Ground-Delay Program Under Collaborative Decision Making
Authors: Chang Kan , Howard Ken , Oiesen Rick , Shisler Lara , Tanino Midori , Wambsganss Michael C.
Published: December 2003

When airport arrival capacity is reduced, it may not meet the demand placed by arriving aircraft. In these cases, the FAA enacts a ground-delay program (GDP) to delay flights before they depart from their origin airports, keeping traffic at an acceptable level for the affected arrival airport. However, air-traffic managers sometimes lacked current data and a common situational awareness when running a GDP. Working with the FAA and the airline community, Metron, Inc. and Volpe National Transportation Systems Center improved the process by using real-time data exchange between all users, new algorithms to assign flight-arrival slots, and new software at FAA facilities and airlines. This paper reflects the views and opinions of the authors and does not necessarily reflect that of the FAA.
Rightsizing and Management of Prototype Vehicle Testing at Ford Motor Company
Authors: Chelst Kenneth , Sidelko John , Przebienda Alex , Lockledge Jeffrey , Mihailidis Dimitrios
Published: December 2003

The prototype vehicles that Ford Motor Company uses to verify new designs are a major annual investment. A team of engineering managers studying for master's degrees in a Wayne State University program taught at Ford adapted a classroom set-covering example to begin development of the prototype optimization model (POM). Ford uses the POM and its related expert systems to budget, plan, and manage prototype test fleets and to maintain testing integrity, reducing annual prototype costs by more than $250 million. POM's first use on the European Transit vehicle reduced costs by an estimated $12 million. The model dramatically shortened the planning process, established global procedures, and created a common structure for dialogue between budgeting and engineering.
Decision Support with Web-Enabled Software
Authors: Cohen Marc-David , Kelly Charles B. , Medaglia Andrés L.
Published: December 2003

SAS develops software for building Web-based applications for data management, statistical analysis, forecasting, data mining, and operations research. Our customers have used these tools to build several kinds of Web-based decision-support applications. A Web-based optimization framework is used to solve a large-scale production-and-distribution problem at United Sugars Corporation, to solve an inventory replenishment problem at Cameron and Barkley, and to find optimal portfolios of suppliers using Dun and Bradstreet data. Applications implemented at Dow Corning and the Aeronautics Division of Lockheed Martin make statistical-process-control and project-management data available via the Web. We conclude with a discussion of Web mining and some of its challenges.
Prospects for Operations Research in the E-Business Era
Authors: Geoffrion Arthur M. , Krishnan Ramayya
Published: December 2003

The digital economy is creating abundant opportunities for operations research (OR) applications. Several factions of the profession are beginning to respond aggressively, leading to notable successes in such areas as financial services, electronic markets, network infrastructure, packaged OR-software tools, supply-chain management, and travel-related services. Because OR is well matched to the needs of the digital economy in certain ways and because certain enabling conditions are coming to pass, prospects are good for OR to team with related analytic technologies and join information technology as a vital engine of further development for the digital economy. OR professionals should prepare for a future in which most businesses will be e-businesses.