Search for: All records

Water Distribution Networks are a particularly critical infrastructure for the high energy costs and frequent failures. Variable Speed Pumps have been introduced to improve the regulation of water pumps, a key for the overall infrastructure performance. This paper addresses the problem of analyzing the effect of the VSPs regulation on the pressure distribution of a WDN, which is highly correlated to leakages and energy costs. Due to the fact that water network behavior can only be simulated, we formulate the problem as a black box feasibility determination, which we solve with a novel stochastic partitioning algorithm, the Feasibility Set Approximation Probabilistic Branch and Bound, that extends the algorithm previously proposed by two of the authors. We use, as black box, EPANet, a widely adopted hydraulic simulator. The preliminary results, over theoretical functions as well as a water distribution network benchmark case, show the viability and advantages of the proposed approach. 

Optimizing the performance of complex systems modeled by stochastic computer simulations is a challenging task, partly because of the lack of structural properties (e.g., convexity). This challenge is magnified by the presence of random error whereby an adaptive algorithm searching for better designs can at times mistakenly accept an inferior design. In contrast to performing multiple simulations at a design point to estimate the performance of the design, we propose a framework for adaptive search algorithms that executes a single simulation for each design point encountered. Here the estimation errors are reduced by averaging the performances from previously evaluated designs drawn from a shrinking ball around the current design point. We show under mild regularity conditions for continuous design spaces that the accumulated errors, although dependent, form a martingale process, and hence, by the strong law of large numbers for martingales, the average errors converge to zero as the algorithm proceeds. This class of algorithms is shown to converge to a global optimum with probability one. By employing a shrinking ball approach with single observations, an adaptive search algorithm can simultaneously improve the estimates of performance while exploring new and potentially better design points. Numerical experiments offer empirical support for this paradigm of single observation simulation optimization. 

Simulated systems are often described with a variety of models of different complexity. Making use of these models, algorithms can use low complexity, “low-fidelity” models or meta-models to guide sampling for purposes of optimization, improving the probability of generating good solutions with a small number of observations. We propose an optimization algorithm that guides the search for solutions on a high-fidelity model through the approximation of a level set from a low-fidelity model. Using the Probabilistic Branch and Bound algorithm to approximate a level set for the low-fidelity model, we are able to efficiently locate solutions inside of a target quantile and therefore reduce the number of high-fidelity evaluations needed in searches. The paper provides an algorithm and analysis showing the increased probability of sampling high-quality solutions within a low-fidelity level set. We include numerical examples that demonstrate the effectiveness of the multi-fidelity level set approximation method to locate solutions. 

We focus on simulation optimization algorithms that are designed to accommodate noisy black-box functions on mixed integer/continuous domains. There are several approaches used to account for noise which include aggregating multiple function replications from sample points and a newer method of aggregating single replications within a “shrinking ball.” We examine a range of algorithms, including, simulated annealing, interacting particle, covariance-matrix adaption evolutionary strategy, and particle swarm optimization to compare the effectiveness in generating optimal solutions using averaged function replications versus a shrinking ball approximation. We explore problems in mixed integer/continuous domains. Six test functions are examined with 10 and 20 dimensions, with integer restrictions enforced on 0%, 50%, and 100% of the dimensions, and with noise ranging from 10% to 20% of function output. This study demonstrates the relative effectiveness of using the shrinking ball approach, demonstrating that its use typically enhances solver performance for the tested optimization methods. 

Simulation models commonly describe complex systems with no closed-form analytical representation. This paper proposes an algorithm for functions on continuous domains that fits into the nested partition framework and uses quantile estimation to rank regions and identify the most promising region. Additionally, we apply the optimal computational budget allocation (OCBA) method for allocating sample points using the normality property of quantile estimators. We prove that, for functions satisfying the Lipschitz condition, the algorithm converges in probability to a region that contains the true global optimum. The paper concludes with some numerical results.