Scenario decomposition algorithms for stochastic programs compute bounds by dualizing all nonanticipativity constraints and solving individual scenario problems independently. We develop an approach that improves on these bounds by reinforcing a carefully chosen subset of nonanticipativity constraints, effectively placing scenarios into groups. Specifically, we formulate an optimization problem for grouping scenarios that aims to improve the bound by optimizing a proxy metric based on information obtained from evaluating a subset of candidate feasible solutions. We show that the proposed grouping problem is NP-hard in general, identify a polynomially solvable case, and present two formulations for solving the problem: a matching formulation for a special case and a mixed-integer programming formulation for the general case. We use the proposed grouping scheme as a preprocessing step for a particular scenario decomposition algorithm and demonstrate its effectiveness in solving standard test instances of two-stage 0–1 stochastic programs. Using this approach, we are able to prove optimality for all previously unsolved instances of a standard test set. Additionally, we implement this scheme as a preprocessing step for PySP, a publicly available and widely used implementation of progressive hedging, and compare this grouping approach with standard grouping approaches on large-scale stochastic unit commitment instances. Finally, the idea is extended to propose a finitely convergent algorithm for two-stage stochastic programs with a finite feasible region.

We present our study of solving large unit commitment problems in the California ISO planning model. The model calculates hourly day-ahead unit commitments, and all instances need to be solved close to optimality within an hour. It takes CPLEX, the current state-of-the-art solver, up to 5 and 10 hours to solve the deterministic instances and the 5-scenario stochastic instances, respectively. The 20-scenario instances are practically unsolvable as no feasible solutions are found after 24 hours.We consider improving solution times through distributed-memory parallelization. Prior techniques such as distributed branch- and-bound perform poorly for our problems. We propose coordinated concurrent search to solve the deterministic instances on a cluster. For stochastic instances, we propose parallelization strategy that combines scenario-based decomposition and asynchronous solves guided by intermediate results from progressive hedging. Our decomposition creates linear sub problems instead of quadratic ones that are oftentimes intractable. On a cluster of 16 IBM Power7 machines, our parallel implementation achieves on average 12.7 and 22 times speedup for the deterministic instances and the 5-scenario stochastic instances, respectively. All problems are solved within an hour to near optimality including the previously unsolvable 20-scenario stochastic instances.

This paper proposes a general framework for generating cache-oblivious layouts for binary search trees. A cache-oblivious layout attempts to minimize cache misses on any hierarchical memory, independent of the number of memory levels and attributes at each level such as cache size, line size, and replacement policy. Recursively partitioning a tree into contiguous subtrees and prescribing an ordering amongst the subtrees, Hierarchical Layouts generalize many commonly used layouts for trees such as in-order, pre-order and breadth-first. They also generalize the various flavors of the van Emde Boas layout, which have previously been used as cache-oblivious layouts. Hierarchical Layouts thus unify previous attempts at deriving layouts for search trees. The paper then derives a new locality measure (the Weighted Edge Product) that mimics the probability of cache misses at multiple levels, and shows that layouts that reduce this measure perform better. We analyze the various degrees of freedom in the construction of Hierarchical Layouts, and investigate the relative effect of each of these decisions in the construction of cache-oblivious layouts. Optimizing the Weighted Edge Product for complete binary search trees, we introduce the MINWEP layout, and show that it outperforms previously used cache-oblivious layouts by almost 20%.

We consider single processor preemptive scheduling with job-dependent setup times. In this model, a job-dependent setup time is incurred when a job is started for the first time, and each time it is restarted after preemption. This model is a common generalization of preemptive scheduling, and actually of non-preemptive scheduling as well. The objective is to minimize the sum of any general non-negative, non-decreasing cost functions of the completion times of the jobs -- this generalizes objectives of minimizing weighted flow time, flow-time squared, tardiness or the number of tardy jobs among many others. Our main result is a randomized polynomial time O(1)-speed O(1)-approximation algorithm for this problem. Without speedup, no polynomial time finite multiplicative approximation is possible unless P=NP. We extend the approach of Bansal et al. (FOCS 2007) of rounding a linear programming relaxation which accounts for costs incurred due to the non-preemptive nature of the schedule. A key new idea used in the rounding is that a point in the intersection polytope of two matroids can be decomposed as a convex combination of incidence vectors of sets that are independent in both matroids. In fact, we use this for the intersection of a partition matroid and a laminar matroid, in which case the decomposition can be found efficiently using network flows. Our approach gives a randomized polynomial time offline O(1)-speed O(1)-approximation algorithm for the broadcast scheduling problem with general cost functions as well.

Virtualized cloud systems are prone to performance anomalies due to various reasons such as resource contentions, software bugs, and hardware failures. In this paper, we present a novel Predictive Performance Anomaly Prevention (PREPARE) system that provides automatic performance anomaly prevention for virtualized cloud computing infrastructures. PREPARE integrates online anomaly prediction, learning-based cause inference, and predictive prevention actuation to minimize the performance anomaly penalty without human intervention. We have implemented PREPARE on top of the Xen platform and tested it on the NCSU's Virtual Computing Lab using a commercial data stream processing system (IBM System S) and an online auction benchmark (RUBiS). The experimental results show that PREPARE can effectively prevent performance anomalies while imposing low overhead to the cloud infrastructure.

We describe the challenges of characterizing, constructing and managing the usage profiles of System S applications. A running System S application is a directed graph with software processing elements(PEs) as vertices and data streams as edges connecting the PEs. The resource usage of each PE is a critical input to the runtime scheduler for proper resource allocation. We represent the resource usage of PEs in terms of resource functions (RFs) that are used by the System S scheduler, with one RF per resource per PE. The first challenge is that it is difficult to build good RFs that can accurately predict the resource usage of a PE because the PEs perform arbitrary computations. A second set of challenges arises in managing the RFs and performance data so that we can apply them for PEs that are re-run or reused by the same or different applications or users. We report our experience in overcoming these challenges. Specifically, we present an empirical characterization of PE RFs from several real streaming applications running in a System S testbed. This indicates that our simple models of resource usage that build on the data-flow nature of the underlying application can be effective, even for complex PEs. To illustrate our methodology, we evaluate and analyze the performance of these applications as a function of the quality of our resource profile models. The system automatically learns the models from the raw metrics data collected from running PEs. We describe our approach to managing the metrics and RF models, which allows us to construct generalizable RFs and eliminates the learning time for new PEs by intelligently storing and reusing the metrics data.

We introduce a graph clustering problem motivated by a stream processing application. Input to our problem is an undirected graph with vertex and edge weights. A cluster is a subset of the vertices. The {\em size} of a cluster is defined as the total vertex weight in the subset plus the total edge weight at the boundary of the cluster. The bounded size graph clustering problem ($\GC$) is to partition the vertices into clusters of size at most a given budget and minimize the total edge-weight across the clusters. In the {\em multiway cut} version of the problem, we are also given a subset of vertices called {\em terminals}. No cluster is allowed to contain more than one terminal. Our problem differs from most of the previously studied clustering problems in that the number of clusters is not specified. We first show that the feasibility version of the multiway cut $\GC$ problem, i.e., determining if there exists a clustering with bounded-size clusters satisfying the multiway cut constraint, can be solved in polynomial time. Our algorithm is based on the min-cut subroutine and an uncrossing argument. This result is in contrast with the NP-hardness of the min-max multiway cut problem, considered by Svitkina and Tardos (2004), in which the number of clusters must equal the number of terminals. Our results for the feasibility version also generalize to any symmetric submodular function. We next show that the optimization version of $\GC$ is NP-hard by showing an approximation-preserving reduction from the $\frac 13$-balanced cut problem. Our main result is an $O(\log^2 n)$-approximation to the optimization version of the multiway cut $\GC$ problem violating the budget by an $O(\log n)$ factor, where $n$ denotes the number of vertices. Our algorithm is based on a set-cover-like greedy approach which iteratively computes bounded-size clusters to maximize the number of new vertices covered.

Protection of one's intellectual property is a topic with important technological and legal facets. The significance of this issue is amplified nowadays due to the ease of data dissemination through the internet. Here, we provide technological mechanisms for establishing the ownership of a dataset consisting of multiple objects. The objects that we consider in this work are shapes (i.e., two dimensional contours), which abound in disciplines such as medicine, biology, anthropology and natural sciences. The protection of the dataset is achieved through means of embedding of an imperceptible ownership 'seal', that imparts only minute visual distortions. This seal needs to be embedded in the proper data space so that its removal or destruction is particularly difficult. Our technique is robust to many common transformations, such as data rotation, translation, scaling, noise addition and resampling. In addition to that, the proposed scheme also guarantees that important distances between the dataset shapes/objects are not distorted. We achieve this by preserving the geodesic distances between the dataset objects. Geodesic distances capture a significant part of the dataset structure, and their usefulness is recognized in many machine learning, visualization and clustering algorithms. Therefore, if a practitioner uses the protected dataset as input to a variety of mining, machine learning, or database operations, the output will be the same as on the original dataset. We illustrate and validate the applicability of our methods on image shapes extracted from anthropological and natural science data.

This work presents a technique of convincingly claiming ownership rights over a trajectory dataset. The presented methodology distorts imperceptibly a collection of sequences, effectively embedding a secret key, while retaining as well as possible the neighborhood of each object, which is vital for operations such as similarity search, classification or clustering.

In computing centers, power-aware operating systems ensure that processor temperatures do not exceed a threshold by utilizing system-throttling. In this technique, the system load (or alternatively, the clock speed) is scaled when the temperature hits this threshold. At other times, the system operates at maximum load. In this paper, we show that such simple system-throttling rules are in fact the best one can achieve under certain assumptions. We show that maintaining a constant operating speed (and thus temperature) always does more work than operating in alternating periods of cooling and heating. As a result, for certain settings and for a reasonable temperature model, we prove that system-throttling is the most effective temperature-aware scheduling. Naturally, these assumptions do not always hold; we also discuss the scenario when some of our assumptions are relaxed, and argue why one needs more complex scheduling algorithms in this case.

We approach the problem of discovering interesting orders in data. In many applications, it is more important to find interesting partial orders since there is often no clear ordering between certain sets of elements. Furthermore, a partial order is more robust against partially erroneous data. We present the notion of fundamental partial orders (FPO), and argue that any partial order that satisfies this property is an interesting partial order. To mine such partial orders, we present a two-stage methodology that first finds an interesting total order, and then discovers a partial order satisfying FPO using this total order. To illustrate, we focus on {0,1} data. This is an important problem with many applications, e.g., in paleontology, where we chronologically order fossil sites by minimizing Lazarus counts. We present the experimental results of our method on paleontological data, and show that it outperforms existing approaches. The techniques developed here are general and can be abstracted for mining partial orders in any setting.

Abstract A network is said to be survivable if it has sufficient capacity for rerouting all of its flow under the failure of any one of its edges. Here, we present a polyhedral approach for designing survivable networks. We describe a mixed‐integer programming model, in which sufficient slack is explicitly introduced on the directed cycles of the network while flow routing decisions are made. In case of a failure, flow is rerouted along the slacks reserved on directed cycles. We give strong valid inequalities that use the survivability requirements. We present a computational study with a column‐and‐cut generation algorithm for designing capacitated survivable networks. © 2004 Wiley Periodicals, Inc.