Application of the cross-entropy method to clustering and vector quantization

We apply the cross-entropy (CE) method to problems in clustering and vector quantization. The CE algorithm for clustering involves the following iterative steps: (a) generate random clusters according to a specified parametric probability distribution, (b) update the parameters of this distribution according to the Kullback–Leibler cross-entropy. Through various numerical experiments, we demonstrate the high accuracy of the CE algorithm and show that it can generate near-optimal clusters for fairly large data sets. We compare the CE method with well-known clustering and vector quantization methods such as K-means, fuzzy K-means and linear vector quantization, and apply each method to benchmark and image analysis data.     

A projection method forl p norm location-allocation problems

We present a solution method for location-allocation problems involving thel _p norm, where 1 <p < . The method relaxes the {0, 1} constraints on the allocations, and solves for both the locations and allocations simultaneously. Necessary and sufficient conditions for local minima of the relaxed problem are stated and used to develop an iterative algorithm. This algorithm finds a stationary point on a series of subspaces defined by the current set of activities. The descent direction is a projection onto the current subspace of a direction incorporating second-order information for the locations, and first-order information for the allocations. Under mild conditions, the algorithm finds local minima with {0, 1} allocations and exhibits quadratic convergence. An implementation that exploits the special structure of these problems to dramatically reduce the computational cost of the required numerical linear algebra is described. Numerical results for thirty-six test problems are included.This research was supported in part by Natural Sciences and Engineering Research Council (NSERC) of Canada grants A-5671 and A-8639, and by the Advanced Research Projects Agency of the Department of Defense and was monitored by the Air Force Office of Scientific Research under Contract No F49620-91-C-0079. The United States Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation hereon.Corresponding author.     

The advantage of small machines in a stochastic fluid production process

We consider a stochastic fluid production model, where m machines which are subject to breakdown and repair, produce a fluid at ratep > 0 per machine if it is working. This fluid is fed into an infinite buffer with stochastic output rate. Under the assumption that the machine processes are independent and identically distributed, we prove that the buffer content at timet is less or equal in the increasing convex ordering to the buffer content at time t of a model withm m machines and production ratep =m/m p. This formulation includes a conjecture posed by Mitra [6]. More-over, it is shown how to extend this result to Brownian flow systems, systems obtained by diffusion approximation and simple stochastic flow networks like tandem buffer and assembly systems.     

A fluid model with upward jumps at the boundary

We consider a single buffer fluid system in which the instantaneous rate of change of the fluid is determined by the current state of a background stochastic process called “environment”. When the fluid level hits zero, it instantaneously jumps to a predetermined positive level q. At the jump epoch the environment state can undergo an instantaneous transition. Between two consecutive jumps of the fluid level the environment process behaves like a continuous time Markov chain (CTMC) with finite state space. We develop methods to compute the limiting distribution of the bivariate process (buffer level, environment state). We also study a special case where the environment state does not change when the fluid level jumps. In this case we present a stochastic decomposition property which says that in steady state the buffer content is the sum of two independent random variables: one is uniform over [0,q], and the other is the steady-state buffer content in a standard fluid model without jumps.      

Managing capacity flexibility in make-to-order production environments

This paper addresses the problem of managing flexible production capacity in a make-to-order (MTO) manufacturing environment. We present a multi-period capacity management model where we distinguish between process flexibility (the ability to produce multiple products on multiple production lines) and operational flexibility (the ability to dynamically change capacity allocations among different product families over time). For operational flexibility, we consider two polices: a fixed allocation policy where the capacity allocations are fixed throughout the planning horizon and a dynamic allocation policy where the capacity allocations change from period to period. The former approach is modeled as a single-stage stochastic program and solved using a cutting-plane method. The latter approach is modeled as a multi-stage stochastic program and a sampling-based decomposition method is presented to identify a feasible policy and assess the quality of that policy. A computational experiment quantifies the benefits of operational flexibility and demonstrates that it is most beneficial when the demand and capacity are well-balanced and the demand variability is high. Additionally, our results reveal that myopic operating policies may lead a firm to adopt more process flexibility and form denser flexibility configuration chains. That is, process flexibility may be over-valued in the literature since it is assumed that a firm will operate optimally after the process flexibility decision. We also show that the value of process flexibility increases with the number of periods in the planning horizon if an optimal operating policy is employed. This result is reversed if a myopic allocation policy is adopted instead.     

Competitive Parallel Disk Prefetching and Buffer Management

We provide a competitive analysis framework for online prefetching and buffer management algorithms in parallel I/O systems, using a read-once model of block references. This has widespread applicability to key I/O-bound applications such as external merging and concurrent playback of multiple video streams. Two realistic lookahead models, global lookahead and local lookahead, are defined. Algorithms NOM and GREED, based on these two forms of lookahead are analyzed for shared buffer and distributed buffer configurations, both of which occur frequently in existing systems. An important aspect of our work is that we show how to implement both of the models of lookahead in practice using the simple techniques of forecasting and flushing.Given a D-disk parallel I/O system and a globally shared I/O buffer that can hold up to M disk blocks, we derive a lower bound of on the competitive ratio of any deterministic online prefetching algorithm with O(M) lookahead. NOM is shown to match the lower bound using global M-block lookahead. In contrast, using only local lookahead results in an Ω(D) competitive ratio. When the buffer is distributed into D portions of M/D blocks each, the algorithm GREED based on local lookahead is shown to be optimal, and NOM is within a constant factor of optimal. Thus we provide a theoretical basis for the intuition that global lookahead is more valuable for prefetching in the case of a shared buffer configuration, whereas it is enough to provide local lookahead in the case of a distributed configuration. Finally, we analyze the performance of these algorithms for reference strings generated by a uniformly-random stochastic process and we show that they achieve the minimal expected number of I/Os. These results also give bounds on the worst-case expected performance of algorithms which employ randomization in the data layout.     

Simulation optimization of buffer allocations in production lines with unreliable machines

We use a recent simulationbased optimization method, sample path optimization, to find optimal buffer allocations in tandem production lines where machines are subject to random breakdowns and repairs, and the product is fluidtype. We explore some of the functional properties of throughput of such systems and exploit these properties to prove the almost sure convergence of our optimization technique, under a regularity condition on the steady state. Utilizing a generalized semiMarkov process (GSMP) representation of the system, we derive recursive expressions to compute onesided directional derivatives of throughput, from a single simulation run. Finally, we give computational results for lines with up to 50 machines. We also compare results for smaller lines with the results from a more conventional method, stochastic approximation, whenever applicable. In these numerical studies, our method performed quite well on problems that are considered difficult by current computational standards.     

On the Mean Production-rate Analysis of a Two-stage Production System with End Buffer and Random Demand

This paper deals with the transient fluctuations of the mean production rate of a two-stage production system subject to interstage and end inspections and end buffer. The interstage and end inspections are instantaneous, and the end buffer is with finite capacity of size N. A stochastic model is developed to describe the system, and analytical expressions to evaluate the mean production rate (MPR) of machine j (=I, II) in [0, t] with arbitrary distributions of processing times at the stages of production and exponential supply and demand pattern have been obtained by using the state-space method and the regeneration-point technique. A particular case is investigated, and numerical results are presented.     

The Gibbs Cloner for Combinatorial Optimization, Counting and Sampling

We present a randomized algorithm, called the cloning algorithm, for approximating the solutions of quite general NP-hard combinatorial optimization problems, counting, rare-event estimation and uniform sampling on complex regions. Similar to the algorithms of Diaconis–Holmes–Ross and Botev–Kroese the cloning algorithm is based on the MCMC (Gibbs) sampler equipped with an importance sampling pdf and, as usual for randomized algorithms, it uses a sequential sampling plan to decompose a “difficult” problem into a sequence of “easy” ones. The cloning algorithm combines the best features of the Diaconis–Holmes–Ross and the Botev–Kroese. In addition to some other enhancements, it has a special mechanism, called the “cloning” device, which makes the cloning algorithm, also called the Gibbs cloner fast and accurate. We believe that it is the fastest and the most accurate randomized algorithm for counting known so far. In addition it is well suited for solving problems associated with the Boltzmann distribution, like estimating the partition functions in an Ising model. We also present a combined version of the cloning and cross-entropy (CE) algorithms. We prove the polynomial complexity of a particular version of the Gibbs cloner for counting. We finally present efficient numerical results with the Gibbs cloner and the combined version, while solving quite general integer and combinatorial optimization problems as well as counting ones, like SAT.     

Buffer allocation for a class of nonlinear stochastic knapsack problems

In this paper, we examine a class of nonlinear, stochastic knapsack problems which occur in manufacturing, facility or other network design applications.Series, merge-and-split topologies of series-parallelM/M/1/K andM/M/C/K queueing networks with an overall buffer constraint bound are examined. Bounds on the objective function are proposed and a sensitivity analysis is utilized to quantify the effects of buffer variations on network performance measures.     

Estimation of an optimal solution of a LP problem with unknown objective function

We consider a linear programming problem with unknown objective function. Random observations related to the unknown objective function are sequentially available. We define a stochastic algorithm, based on the simplex method, that estimates an optimal solution of the linear programming problem. It is shown that this algorithm converges with probability one to the set of optimal solutions and that its failure probability is of order inversely proportional to the sample size. We also introduce stopping criteria for the algorithm. The asymptotic normality of some suitably defined residuals is also analyzed. The proposed estimation algorithm is motivated by the stochastic approximation algorithms but it introduces a generalization of these techniques when the linear programming problem has several optimal solutions. The proposed algorithm is also close to the stochastic quasi-gradient procedures, though their usual assumptions are weakened.Mathematics Subject Classification (2000): 90C05, 62L20, 90C15Acknowledgments. I would like to thank two unknown referees for their fruitful suggestions that have helped to improve the paper.     

A probabilistic interpretation and stochastic particle approximations of the 3-dimensional Navier-Stokes equations

We develop a probabilistic interpretation of local mild solutions of the three dimensional Navier-Stokes equation in the L^p spaces, when the initial vorticity field is integrable. This is done by associating a generalized nonlinear diffusion of the McKean-Vlasov type with the solution of the corresponding vortex equation. We then construct trajectorial (chaotic) stochastic particle approximations of this nonlinear process. These results provide the first complete proof of convergence of a stochastic vortex method for the Navier-Stokes equation in three dimensions, and rectify the algorithm conjectured by Esposito and Pulvirenti in 1989. Our techniques rely on a fine regularity study of the vortex equation in the supercritical L^p spaces, and on an extension of the classic McKean-Vlasov model, which incorporates the derivative of the stochastic flow of the nonlinear process to explain the vortex stretching phenomenon proper to dimension three. Supported by Fondecyt Project 1040689 and Nucleus Millennium Information and Randomness ICM P01-005.     

Optimal buffer size for a stochastic processing network in heavy traffic

We consider a one-dimensional stochastic control problem that arises from queueing network applications. The state process corresponding to the queue-length process is given by a stochastic differential equation which reflects at the origin. The controller can choose the drift coefficient which represents the service rate and the buffer size b>0. When the queue length reaches b, the new customers are rejected and this incurs a penalty. There are three types of costs involved: A “control cost” related to the dynamically controlled service rate, a “congestion cost” which depends on the queue length and a “rejection penalty” for the rejection of the customers. We consider the problem of minimizing long-term average cost, which is also known as the ergodic cost criterion. We obtain an optimal drift rate (i.e. an optimal service rate) as well as the optimal buffer size b ^*>0. When the buffer size b>0 is fixed and where there is no congestion cost, this problem is similar to the work in Ata, Harrison and Shepp (Ann. Appl. Probab. 15, 1145–1160, 2005). Our method is quite different from that of (Ata, Harrison and Shepp (Ann. Appl. Probab. 15, 1145–1160, 2005)). To obtain a solution to the corresponding Hamilton–Jacobi–Bellman (HJB) equation, we analyze a family of ordinary differential equations. We make use of some specific characteristics of this family of solutions to obtain the optimal buffer size b ^*>0. A.P. Weerasinghe’s research supported by US Army Research Office grant W911NF0510032.     

Scenario tree reduction for multistage stochastic programs

A framework for the reduction of scenario trees as inputs of (linear) multistage stochastic programs is provided such that optimal values and approximate solution sets remain close to each other. The argument is based on upper bounds of the L _r -distance and the filtration distance, and on quantitative stability results for multistage stochastic programs. The important difference from scenario reduction in two-stage models consists in incorporating the filtration distance. An algorithm is presented for selecting and removing nodes of a scenario tree such that a prescribed error tolerance is met. Some numerical experience is reported.     

Model-Based Search for Combinatorial Optimization: A Critical Survey

In this paper we introduce model-based search as a unifying framework accommodating some recently proposed metaheuristics for combinatorial optimization such as ant colony optimization, stochastic gradient ascent, cross-entropy and estimation of distribution methods. We discuss similarities as well as distinctive features of each method and we propose some extensions.     

Using linear programming to analyze and optimize stochastic flow lines

This paper presents a linear programming approach to analyze and optimize flow lines with limited buffer capacities and stochastic processing times. The basic idea is to solve a huge but simple linear program that models an entire simulation run of a multi-stage production process in discrete time, to determine a production rate estimate. As our methodology is purely numerical, it offers the full modeling flexibility of stochastic simulation with respect to the probability distribution of processing times. However, unlike discrete-event simulation models, it also offers the optimization power of linear programming and hence allows us to solve buffer allocation problems. We show under which conditions our method works well by comparing its results to exact values for two-machine models and approximate simulation results for longer lines.     

On the Convergence of the Cross-Entropy Method

The cross-entropy method is a relatively new method for combinatorial optimization. The idea of this method came from the simulation field and then was successfully applied to different combinatorial optimization problems. The method consists of an iterative stochastic procedure that makes use of the importance sampling technique. In this paper we prove the asymptotical convergence of some modifications of the cross-entropy method.     

Asymptotically optimal importance sampling for Jackson networks with a tree topology

This note describes an importance sampling (IS) algorithm to estimate buffer overflows of stable Jackson networks with a tree topology. Three new measures of service capacity and traffic in Jackson networks are introduced and the algorithm is defined in their terms. These measures are effective service rate, effective utilization and effective service-to-arrival ratio of a node. They depend on the nonempty/empty states of the queues of the network. For a node with a nonempty queue, the effective service rate equals the node’s nominal service rate. For a node i with an empty queue, it is either a weighted sum of the effective service rates of the nodes receiving traffic directly from node i, or the nominal service rate, whichever smaller. The effective utilization is the ratio of arrival rate to the effective service rate and the effective service-to-arrival ratio is its reciprocal. The rare overflow event of interest is the following: given that initially the network is empty, the system experiences a buffer overflow before returning to the empty state. Two types of buffer structures are considered: (1) a single system-wide buffer shared by all nodes, and (2) each node has its own fixed size buffer. The constructed IS algorithm is asymptotically optimal, i.e., the variance of the associated estimator decays exponentially in the buffer size at the maximum possible rate. This is proved using methods from (Dupuis et al. in Ann. Appl. Probab. 17(4):1306–1346, 2007), which are based on a limit Hamilton–Jacobi–Bellman equation and its boundary conditions and their smooth subsolutions. Numerical examples involving networks with as many as eight nodes are provided.     

Nonlinear Prices in Nonconvex Economies with Classical Pareto and Strong Pareto Optimal Allocations

The paper is devoted to applications of modern tools of variational analysis to equilibrium models of welfare economics involving generally nonconvex economies with infinite-dimensional commodity spaces. The main results relate to the so-called generalized/extended second welfare theorem ensuring an equilibrium price support at Pareto optimal allocations. Based on advanced tools of variational analysis and generalized differentiation, we establish refined results of this type with the novel usage of nonlinear prices at the three types to optimal allocations: weak Pareto, Pareto, and strong Pareto. We pay a special attention to strong Pareto optimal allocations in economies with ordering commodity spaces showing that enhanced results for them do not require, in contrast to the classical types of weak Pareto and Pareto optimality, any net demand qualification conditions. Mathematics Subject Classifications (2000): 91B50, 49J52 Dedicated to the memory of Yuri Abramovich     

An SQP algorithm for extended linear-quadratic problems in stochastic programming

Extended Linear-Quadratic Programming (ELQP) problems were introduced by Rockafellar and Wets for various models in stochastic programming and multistage optimization. Several numerical methods with linear convergence rates have been developed for solving fully quadratic ELQP problems, where the primal and dual coefficient matrices are positive definite. We present a two-stage sequential quadratic programming (SQP) method for solving ELQP problems arising in stochastic programming. The first stage algorithm realizes global convergence and the second stage algorithm realizes superlinear local convergence under a condition calledB-regularity.B-regularity is milder than the fully quadratic condition; the primal coefficient matrix need not be positive definite. Numerical tests are given to demonstrate the efficiency of the algorithm. Solution properties of the ELQP problem underB-regularity are also discussed.Supported by the Australian Research Council.