"Many everday tasks in operations research involve solving complicated optimization problems. The travelling salesman problem (TSP), the quadratic assignment problem (QAP) and the max-cut problem are a representative sample of combinatorial optimization problems (COP) where the problem being studied is completely known and static. In contrast, the buffer allocation problem (BAP) is a noisy estimation problem where the objective function needs to be estimated since it is unknown. Discrete event simulation is one method for estimating an unknown objective function.
"The purpose of this tutorial is to show that the CE method provides a simple, efficient and general method for solving such problems. Moreover, we wish to show that the CE method is also valuable for rare event simulation, where very small probabilities need to be accurately estimated - for example in reliability analysis, or performance analysis of telecommunication systems. This tutorial is intended for a broad audience of operations research specialists, computer scientists, mathematicians, statistiticans and engineers. Our aim is to explain the foundations of the CE method and consider various applications.
"The CE method was motivated by an adaptive algorithm for estimating probabilities of rare events in complex stochastic networks (Rubinstein, 1997), which involves variance minimization. It was soon realized (Rubinstein 1999, 2001) that a simple cross-entropy modification of Rubinstein 1997 could b used not only for estimating probabilities of rare events but for solving difficult COPs as well. This is done by translating the "deterministic" optimization problem into a related "stochastic" optimization problem and then using rare event simulation techniques similar to Rubenstein 1997. Several recent applications demonstrate the power of the CE method (Rubinstein 1999) as a generic and practical tool for solving NP-hard problems.
"The CE method involves an iterative procedure where each iteration can be broken down into two phases:
"1. Generate a random data sample (trajectories, vectors, etc) according to a specified mechanism
"2. Update the parameters of the random mechanism based on the data to produce a 'better' sample in the next iteration.
"The significance of the CE method is that it defines a precise mathematical framework for deriving fast, and in some sense 'optimal' updating/learning rules, based on advanced simulation theory. Other well-known randomized methods for combinatorial optimization problems are simulated annealing (Aarts and Korst, 1989), tabu search (Glover and Laguna 1993), and genetic algorithms (Goldberg 1989). Recent related work on randomized combinatorial optimization includes the nested partitioning method (Shi and Olafsson 2000), and the ant colony optimization meta-heuristic (Colorni et al 1996; Dorigo, Di Caro and Gambardella 1999; Gutjahr 2000).
"Many COPS can be formulate as optimization problems concerning a weighted graph. As mentioned before, in CE a deterministic optimization problem is translated into an associated stochastic optimization problem. Depending on the particular problem, we introduce randomness in either (a) the nodes or (b) the edges of the graph. We speak of stochastic node networks (SNN) in the former case and stochastic edge networks (SEN) in the latter. Examples of SNN problems are the maximal cut (max-cut) problem, the buffer-allocation problem and clustering problems. Examples of SEN problems are the travelling salesman problem, the quadratic assignment problem, the clique problem, and optimal policy search in Markovian decision problems (MDPs).
"It should be emphasized that the CE method may be successfully applied to both deterministic and stochastic COPs. In the latter the objective function itself is random or needs to be estimated via simulation. Stochastic COPs typically occur in stochastic schedulgin, flow control and routing of data networks and in various simulation-based optimization problems (Rubinstein and Melamed, 1998), such as the optimal buffer allocation problem (Alon et al 2005)
"Estimation of the probability of rare events is essential for guaranteeing adequate performance of engineering systems. For example, consider a telecommunications system that accepts calls from many customers. Under normal operating conditions each client may be rejected with a very small probability.