Evaluating Parallel Simulated Evolution Strategies for VLSI Cell Placement

Simulated Evolution (SimE) is an evolutionary metaheuristic that has produced results comparable to well established stochastic heuristics such as SA, TS and GA, with shorter runtimes. However, for optimization problems with a very large set of elements, such as in VLSI cell placement and routing, runtimes can still be very large and parallelization is an attractive option for reducing runtimes. Compared to other metaheuristics, parallelization of SimE has not been extensively explored. This paper presents a comprehensive set of parallelization approaches for SimE when applied to multiobjective VLSI cell placement problem. Each of these approaches are evaluated with respect to SimE characteristics and the constraints imposed by the problem instance. Conclusions drawn can be extended to parallelization of SimE when applied to other optimization problems.      

Decision support system for mass dispensing of medications for infectious disease outbreaks and bioterrorist attacks

A simulation and decision support system, RealOpt^©, for planning large-scale emergency dispensing clinics to respond to biological threats and infectious disease outbreaks is described. The system allows public health administrators to investigate clinic design and staffing scenarios quickly. RealOpt^© incorporates efficient optimization technology seamlessly interfaced with a simulation module. The system's correctness and computational advantage are validated via comparisons against simulation runs of the same model developed on a commercial system. Simulation studies to explore facility layout and staffing scenarios for smallpox vaccination and for an actual anthrax-treatment dispensing exercise and post event analysis are presented. The system produces results consistent with the model built on the commercial system, but requires only a fraction of the computational time. Each smallpox scenario runs within 1 CPU minute on RealOpt^©, versus run times of over 5–10 h on the commercial system. The system's fast computational time enables its use in large-scale studies, in particular an anthrax response planning exercise involving a county with 864,000 households. The computational effort required for this exercise was roughly 30 min for all scenarios considered, demonstrating that RealOpt^© offers a very promising avenue for pursuing a comprehensive investigation involving a more diverse set of scenarios, and justifying work towards development of a robust system that can be widely deployed for use by state, local, and tribal health practitioners. Using our staff allocation and assignments for the Anthrax field exercise, DeKalb county achieved the highest throughput among all counties that simultaneously conducted the same scale of Anthrax exercise at various locations, with labor usage at or below the other counties. Indeed, DeKalb exceeded the targeted number of households, and it processed 50% more individuals compared to the second place county. None of the other counties achieved the targeted number of households. The external evaluators commented that DeKalb produced the most efficient floor plan (with no path crossing), the most cost-effective dispensing (lowest labor/throughput value), and the smoothest operations (shortest average wait time, average queue length, equalized utilization rate). The study proves that even without historical data, using our system one can plan ahead and be able to wisely estimate the required labor resources. The exercise also revealed many areas that need attention during the operations planning and design of dispensing centers. The type of disaster being confronted (e.g., biological attack, infectious disease outbreak, or a natural disaster) also dictates different design considerations with respect to the dispensing clinic, facility locations, dispensing and backup strategies, and level of security protection. Depending on the situation, backup plans will be different, and the level of security and military personnel, as well as the number of healthcare workers required, will vary. In summary, the study shows that a real-time decision support system is viable through careful design of a stand-alone simulator coupled with powerful tailor-designed optimization solvers. The flexibility of performing empirical tests quickly means the system is amenable for use in training and preparation, and for strategic planning before and during an emergency situation. The system facilitates analysis of “what-if'' scenarios, and serves as an invaluable tool for operational planning and dynamic on-the-fly reconfigurations of large-scale emergency dispensing clinics. It also allows for “virtual field exercises” to be performed on the decision support system, offering insight into operations flow and bottlenecks when mass dispensing is required for a region with a large population. The system, designed in modular form with a flexible implementation, enables future expansion and modification regarding emergency center design with respect to treatment for different biological threats or disease outbreaks. Working with emergency response departments, further fine-tuning and development of the system will be made to address different biological attacks and infectious disease outbreaks, and to ensure its practicality and usability.     

物理实验教学新模式的探索与实践

提出了一种新的物理实验教学模式，论述了建立实验教学模式所遵循的基本原则和基本做法，简要介绍实施新的教学模式所取得的教学成果。     

Portfolio optimization under D.C. transaction costs and minimal transaction unit constraints

This paper addresses itself to a portfolio optimization problem under nonconvex transaction costs and minimal transaction unit constraints. Associated with portfolio construction is a fee for purchasing assets. Unit transaction fee is larger when the amount of transaction is smaller. Hence the transaction cost is usually a concave function up to certain point. When the amount of transaction increases, the unit price of assets increases due to illiquidity/market impact effects. Hence the transaction cost becomes convex beyond certain bound. Therefore, the net expected return becomes a general d.c. function (difference of two convex functions). We will propose a branch-and-bound algorithm for the resulting d.c. maximization problem subject to a constraint on the level of risk measured in terms of the absolute deviation of the rate of return of a portfolio. Also, we will show that the minimal transaction unit constraints can be incorporated without excessively increasing the amount of computation.     

Solving Large Quadratic Assignment Problems in Parallel

Quadratic Assignment problems are in practice among the mostdifficult to solve in the class of NP-complete problems. Theonly successful approach hitherto has been Branch-and-Bound-basedalgorithms, but such algorithms are crucially dependent on good boundfunctions to limit the size of the space searched. Much work hasbeen done to identify such functions for the QAP, but with limitedsuccess.Parallel processing has also been used in order to increase the sizeof problems solvable to optimality. The systems used have, however, oftenbeen systems with relatively few, but very powerful vector processors, andhave hence not been ideally suited for computations essentially involving non-vectorizable computations on integers.In this paper we investigate the combination of one of the best bound functions for a Branch-and-Bound algorithm (the Gilmore-Lawler bound) and various testing, variable binding and recalculation of bounds between branchings when used in aparallel Branch-and-Bound algorithm. The algorithm has been implemented on a 16-processor MEIKO Computing Surface with Intel i860processors. Computational results from the solution of a number of large QAPs, including the classical Nugent 20 are reported.     

木耳高产栽培配方的数学模型及优化研究

崔文善，闫培生，张金政．木耳高产栽培配方的数学模型及优化研究．数理统计与管理，１９９７，１６（４），８～１１．本文采用回归正交设计方法，研究了泡桐木屑栽培木耳的配方组合与产量之间关系，并建立了数学模型。结果表明，以泡桐木屑为主料，各组分的适宜用量，以及它们之间合理组合，可显著提高木耳产量，降低生产成本，并具有较好的稳定性；其配方的优化方案为：泡桐木屑７７．６～８０．２％，麦夫１２．５～１４．８％，石灰２．４～２．７％，ＭｇＳＯ４１．３％，ＫＨ２ＰＯ４２．６％，糖１．０％。     

Zero duality gap for a class of nonconvex optimization problems

By an equivalent transformation using thepth power of the objective function and the constraint, a saddle point can be generated for a general class of nonconvex optimization problems. Zero duality gap is thus guaranteed when the primal-dual method is applied to the constructed equivalent form.The author very much appreciates the comments from Prof. Douglas J. White.     

Scenario optimization

Uncertainty in the parameters of a mathematical program may present a modeller with considerable difficulties. Most approaches in the stochastic programming literature place an apparent heavy data and computational burden on the user and as such are often intractable. Moreover, the models themselves are difficult to understand. This probably explains why one seldom sees a fundamentally stochastic model being solved using stochastic programming techniques. Instead, it is common practice to solve a deterministic model with different assumed scenarios for the random coefficients. In this paper we present a simple approach to solving a stochastic model, based on a particular method for combining such scenario solutions into a single, feasible policy. The approach is computationally simple and easy to understand. Because of its generality, it can handle multiple competing objectives, complex stochastic constraints and may be applied in contexts other than optimization. To illustrate our model, we consider two distinct, important applications: the optimal management of a hydro-thermal generating system and an application taken from portfolio optimization.     

Worst-case distribution analysis of stochastic programs

We show that for even quasi-concave objective functions the worst-case distribution, with respect to a family of unimodal distributions, of a stochastic programming problem is a uniform distribution. This extends the so-called ``Uniformity Principle' of Barmish and Lagoa (1997) where the objective function is the indicator function of a convex symmetric set.