Speeding up COMPASS for high-dimensional discrete optimization via simulation

The convergent optimization via most promising area stochastic search (COMPASS) algorithm is a locally convergent random search algorithm for solving discrete optimization via simulation problems. COMPASS has drawn a significant amount of attention since its introduction. While the asymptotic convergence of COMPASS does not depend on the problem dimension, the finite-time performance of the algorithm often deteriorates as the dimension increases. In this paper, we investigate the reasons for this deterioration and propose a simple change to the solution-sampling scheme that significantly speeds up COMPASS for high-dimensional problems without affecting its convergence guarantee.     

Optimization via simulation: A review

We review techniques for optimizing stochastic discrete-event systems via simulation. We discuss both the discrete parameter case and the continuous parameter case, but concentrate on the latter which has dominated most of the recent research in the area. For the discrete parameter case, we focus on the techniques for optimization from a finite set: multiple-comparison procedures and ranking-and-selection procedures. For the continuous parameter case, we focus on gradient-based methods, including perturbation analysis, the likelihood ratio method, and frequency domain experimentation. For illustrative purposes, we compare and contrast the implementation of the techniques for some simple discrete-event systems such as the (s, S) inventory system and theGI/G/1 queue. Finally, we speculate on future directions for the field, particularly in the context of the rapid advances being made in parallel computing.     

Integrated distribution and loading planning via a compact metaheuristic algorithm

The present article examines a vehicle routing problem integrated with two-dimensional loading constraints, called 2L-CVRP. The problem is aimed at generating the optimal route set for satisfying customer demand. In addition, feasible loading arrangements have to be determined for the transported products. To solve 2L-CVRP, we propose a metaheuristic solution approach. The basic advantage of our approach lies at its compact structure, as in total, only two parameters affect the algorithmic performance. To optimize the routing aspects, we propose a local-search method equipped with an effective diversification component based on the regional aspiration criteria. The problem’s loading requirements are tackled by employing a two-dimensional packing heuristic which repetitively attempts to develop feasible loading patterns. These attempts are effectively coordinated via an innovative, simple-structured memory mechanism. The overall solution framework makes use of several memory components for drastically reducing the computational effort required. The performance of our metaheuristic development has been successfully evaluated on benchmark instances considering two distinct versions of the loading constraints. More specifically, the algorithm managed to improve or match the majority of best known solution scores for both problem versions.     

基于分支定界算法的物流配送网络优化研究

为进一步提高物流配送网络的运行效率,以配送总里程最短为目标,建立了单配送中心的配送优化模型,提出了一种基于分枝定界法的混合求解策略。该策略能有效地避免智能启发式算法的不稳定性和传统优化算法的指数爆炸问题,对现代配送网络的建设具有一定的理论和实践意义。     

Large scale petroleum reservoir simulation and parallel preconditioning algorithms research

Solving large scale linear systems efficiently plays an important role in a petroleum reservoir simulator, and the key part is how to choose an effective parallel preconditioner. Properly choosing a good preconditioner has been beyond the pure algebraic field. An integrated preconditioner should include such components as physical background, characteristics of PDE mathematical model, nonlinear solving method, linear     

基于粒子群优化算法的库存不确定性分析

库存不确定性问题是供应链不确定性研究的重点之一.利用粒子群优化算法快速搜寻最优解的优点对库存不确定性问题进行仿真分析,得出了库存不确定性环境下的最优解,这说明了粒子群优化算法能够辅助供应链管理者在不确定性环境下对供应链进行优化设计和决策分析.     

A simulation tool for voltage control studies in power systems

An electrical power system is a large scale system composed of complicated and sophisticated combination of multiple electronic and electromechanical components. In general, these components are nonlinear. Power system is also characterized by a wide range of normal operating conditions which continuously vary. To help the designer study the voltage control problems in power systems, a simulation tool is presented in this paper. It is based on decomposition of the overall system simulation task into three subtasks so as to attain both computational efficiency and flexibility. The use of the proposed simulation tool in a voltage control problem is also presented.     

Mathematical programming formulations for approximate simulation of multistage production systems

Mathematical programming representation has been recently used to describe the behavior of discrete event systems as well as their formal properties. This new way of representing discrete event systems paves the way to the creation of simpler mathematical programming models that reduce the complexity of the system analysis. The paper proposes an approximate representation for a class of production systems characterized by several stages, limited buffer capacities and stochastic production times. The approximation exploits the concept of a time buffer, modeled as a constraint that put into a temporal relationship the completion times of two customers in a sample path. The main advantage of the proposed formulation is that it preserves its linearity even when used for optimization and, for such a reason, it can be adopted in simulation–optimization problems to reduce the initial solution space. The approximate formulation is applied to relevant problems such as buffer capacity allocation in manufacturing systems and control parameters setting in pull systems.     

Optimization and analysis aid via data-mining for simulated production systems

The optimization of a production system consists of determining a value for certain parameters which influence system performance. However, the majority of optimization methods deliver a solution without any form of explanation and this is no longer sufficient in a production context. Decision-makers would also like to have an analysis of their systems and especially of the high-performance behavior of those systems. In order to avoid the “black box” effect of many optimization methods, and to produce knowledge on system behavior (characterization of solutions that perform well, determination of critical parameters) and analyze efficient solutions, the author proposes a methodology which is based on the synergy between evolutionist optimization and an induction graph learning method. This approach is illustrated via the study of a simulated job-shop composed of five workstations, one entry station and one exit station; the numbers of machines at each station, the management method and the number of stock places in each station have to be optimized and analyzed.     

Augmented penalty functions for delayed control systems

A descent method is given for the numerical solution of delayed optimal control problems with fixed delays by first reducing them to nondelayed problems and then using the technique of augmented penalty functions. The system resulting from the reduction to a nondelayed problem is of higher order than the original system; however, the time is proportionally shorter, and the variational matrices are sparse.     

Integrating simulation modelling and GIS: spatial decision support systems for evacuation planning

A prototype spatial decision support system (SDSS) has been designed for contingency planning for emergency evacuations which combines simulation techniques with spatial data handling and display capabilities of a geographical information system (GIS). It links together the topographical support and analysis provided by the GIS–ARC/INFO, with a simulation model designed to simulate the dynamics of an evacuation process in detail. Our aim has been to design a SDSS so that it provides an interactive evacuation simulator with dynamic graphics that allows for experimentation with policies by providing rapid feedback from the simulation. The idea is that emergency planners will be able to use the SDSS to experiment with emergency evacuation plans in order to plan for different contingencies. This paper concentrates on the issues involved in designing an effective integration link interface between the GIS and the simulation model when building a SDSS of this type.     

Flexible composition and execution of large scale applications on distributed e-infrastructures

Computer simulation is finding a role in an increasing number of scientific disciplines, concomitant with the rise in available computing power. Marshalling this power facilitates new, more effective and different research than has been hitherto possible. Realizing this inevitably requires access to computational power beyond the desktop, making use of clusters, supercomputers, data repositories, networks and distributed aggregations of these resources. The use of diverse e-infrastructure brings with it the ability to perform distributed multiscale simulations. Accessing one such resource entails a number of usability and security problems; when multiple geographically distributed resources are involved, the difficulty is compounded. In this paper we present a solution, the Application Hosting Environment,³ which provides a Software as a Service layer on top of distributed e-infrastructure resources. We describe the performance and usability enhancements present in AHE version 3, and show how these have led to a high performance, easy to use gateway for computational scientists working in diverse application domains, from computational physics and chemistry, materials science to biology and biomedicine.     

Rapid and modular prototyping-based Petri nets and distributed simulation for manufacturing systems

This paper presents an approach to simulate and implement by stepwise refinement the whole manufacturing system (MS) by means of distributed simulation. This approach is based on the use of different classes of Petri nets to model different levels of a manufacturing system. Furthermore these classes may match the abstraction levels of a high-level Petri net used to model the MS. Each level can be simulated on a processor or a cluster of processors which can communicate between themselves using a network. The main contribution is to give the opportunity to combine simulation, performance evaluation and emulation. The emulation means that a part of the system can be run in real time while the other part is simulated. Moreover based on the abstraction levels of high-level Petri nets, subsystems can be integrated step-by-step from the design stage to the implementation one, allowing inter-changeability between simulated components and real-time physical systems. This approach is achieved by defining a simulation engine which involves a local simulator, an emulator and an interface to the physical process. Criteria are defined to use an emulator or a local control software for a physical process as a logical process for the conservative distributed simulation.     

Statistical learning control of uncertain systems: theory and algorithms

It has recently become clear that many control problems are too difficult to admit analytic solutions. New results have also emerged to show that the computational complexity of some “solved” control problems is prohibitive. Many of these control problems can be reduced to decidability problems or to optimization questions. Even though such questions may be too difficult to answer analytically, or may not be answered exactly given a reasonable amount of computational resources, researchers have shown that we can “approximately” answer these questions “most of the time”, and have “high confidence” in the correctness of the answers.     

Financial planning for the preventive maintenance of power distribution systems via fuzzy AHP

One of the most important objectives of electricity distribution companies is to improve the reliability of the distribution networks. To this end, the electricity distribution companies try to optimally use the existing financial resources in the planning of preventive maintenance (PM) programs to reduce the imposed costs on the system due to the failure of network components and to improve the network reliability. In fuzzy analytical hierarchical process (fuzzy AHP) method, the degree of network reliability and the effectiveness of PM budget in the improvement of network reliability are selected as decision criteria in the budget allocation procedure. The areas served by the power distribution network are prioritized relative to each other and are assigned weights based on these priorities. The PM budget is determined based on the obtained weights. The medium voltage distribution network of seven areas in the city of Tehran have been selected for the implementation of the proposed method and the analysis of the obtained results. © 2014 Wiley Periodicals, Inc. Complexity 21: 36–46, 2016     

A framework for the probabilistic analysis of hierarchical planning systems

As we have argued in previous papers, multi-level decision problems can often be modeled as multi-stage stochastic programs, and hierarchical planning systems designed for their solution, when viewed as stochastic programming heuristics, can be subjected to analytical performance evaluation. The present paper gives a general formulation of such stochastic programs and provides a framework for the design and analysis of heuristics for their solution. The various ways to measure the performance of such heuristics are reviewed, and some relations between these measures are derived. Our concepts are illustrated on a simple two-level planning problem of a general nature and on a more complicated two-level scheduling problem.     

Optimization of control setting and size of shunt capacitors on distribution feeders

Loads on electric utility systems have two components: active power (measured in kilowatts) and reactive power (measured in kilovars). Active power has to be generated at the power plant, whereas reactive power can be provided by either power plants or capacitors. It is a well-known fact that shunt power capacitors are the most economical source to meet the reactive power requirements of inductive loads and transmission lines operating at a lagging power factor.This paper describes new contributions to the problem of optimization of size and control setting of shunt capacitors on distribution feeders, so that the losses along the feeder are minimized. The variation of the KVAR of the load on the feeder with the distance from the substation is assumed to be linear. The parameters of this function are estimated from the available KVAR loading on the feeder first by using least-square techniques and then by using least-absolute-value parameter estimation techniques. The results obtained are compared with that obtained if the current profile is assumed to be uniformly distributed on the feeder. Our results show that the optimum size of the capacitor bank as well as its optimum location depend on the parameters of the model used for the load. Also, our results show a large saving in the size of the capacitor banks used with a considerable per-unit-loss reduction along the feeder.This work was supported by the National Science and Engineering Research Council of Canada, Grant No. A4146. The first author acknowledges the help received from Engineer Samy Soliman for reviewing all the mathematical expressions in this paper.