A new approach to solving stochastic programming problems with recourse

A new numerical approach to the solution of two-stage stochastic linear programming problems is described and evaluated. The approach avoids the solution of the first-stage problem and uses the underlying deterministic problem to generate a sequence of values of the first-stage variables which lead to successive improvements of the objective function towards the optimal policy. The model is evaluated using an example in which randomness is described by two correlated factors. The dynamics of these factors are described by stochastic processes simulated using lattice techniques. In this way, discrete distributions of the random parameters are assembled. The solutions obtained with the new iterative procedure are compared with solutions obtained with a deterministic equivalent linear programming problem. It is concluded that they are almost identical. However, the computational effort required for the new approach is negligible compared with that needed for the deterministic equivalent problem.     

Topology optimization of buildings subjected to stochastic wind loads

Traditionally, the main structural system of tall buildings is designed iteratively to resist extreme wind loads, which provides safe, but typically suboptimal building systems. Topology optimization provides a general approach to obtain optimal material layout to carry the required load within specified design constraints. The wind loading on a structure is typically modeled as an equivalent static load or as a spatio-temporal stochastic field. While a few models for stochastic wind excitation are available, these approaches are focused on obtaining samples for time history analyses. In this study the stochastic wind excitation is modeled as a filtered vector white noise; the state space representation of the filter is obtained by solving a regularized optimization problem from known stationary wind power spectral densities. An augmented state space representation is formed by combining the equation of motion for the structure with the excitation filter. The stationary covariances of the structural responses of interest are then obtained by solving the associated Lyapunov equation. Dynamic condensation of the equations of motion is employed to increase the efficiency of the proposed approach. Objective functions for the optimization scheme are defined in terms of the stationary covariance of the response; various objectives are considered corresponding to typical design considerations. An equivalent smooth formulation is employed to solve the non-smooth min–max problem. A gradient-based method is used to update the design variables, while the sensitivities are computed from the solution of an adjoint Lyapunov equation. The proposed topology optimization scheme is illustrated for a tall building subjected to along-wind and across-wind loads. The results presented herein demonstrate the efficacy of the proposed approach for efficient topology optimization of buildings subjected to stochastic wind excitation.     

Optimum design of stochastically excited non‐linear dynamic systems without geometric constraints

This paper presents an efficient procedure for min–max dynamic response optimization of stochastically excited non‐linear systems with multiple time‐delayed inputs. This procedure employs a stochastic linearization technique to overcome system non‐linearity and an auto‐covariance analysis technique to represent the original stochastic mechanical model in a suitable form for optimization. Special attention is given to the sensitivity analysis, due to the complex nature of the problem. Therefore, exact expressions are obtained in a simple form for the evaluation of the required gradients, which greatly improve the stability and efficiency of the optimization algorithm. The numerical results and performance are presented by means of solving two min–max dynamic response optimization problems. Copyright © 2002 John Wiley & Sons, Ltd.     

Stochastic optimization using a sparse grid collocation scheme

In computational sciences, optimization problems are frequently encountered in solving inverse problems for computing system parameters based on data measurements at specific sensor locations, or to perform design of system parameters. This task becomes increasingly complicated in the presence of uncertainties in boundary conditions or material properties. The task of computing the optimal probability density function (PDF) of parameters based on measurements of physical fields of interest in the form of a PDF, is posed as a stochastic optimization problem. This stochastic optimization problem is solved by dividing it into two problems—an auxiliary optimization problem to construct stochastic space representations from the PDF of measurement data, and a stochastic optimization problem to compute the PDF of problem parameters. The auxiliary optimization problem is solved using a downhill simplex method, whilst a gradient based approach is employed for solving the stochastic optimization problem. The gradients required for stochastic optimization are defined, using appropriate stochastic sensitivity problems. A computationally efficient sparse grid collocation scheme is utilized to compute the solution of these stochastic sensitivity problems. The implementation discussed, requires minimum intrusion into existing deterministic solvers, and it is thus applicable to a variety of problems. Numerical examples involving stochastic inverse heat conduction problems, contamination source identification problems and large deformation robust design problems are discussed.     

Stochastic inverse heat conduction using a spectral approach

An adjoint‐based functional optimization technique in conjunction with the spectral stochastic finite element method is proposed for the solution of an inverse heat conduction problem in the presence of uncertainties in material data, process conditions and measurement noise. The ill‐posed stochastic inverse problem is restated as a conditionally well‐posed L₂ optimization problem. The gradient of the objective function is obtained in a distributional sense by defining an appropriate stochastic adjoint field. The L₂ optimization problem is solved using a conjugate‐gradient approach. Accuracy and effectiveness of the proposed approach is appraised with the solution of several stochastic inverse heat conduction problems. Copyright © 2004 John Wiley & Sons, Ltd.     

Global and Local Optimization Algorithms for Optimal Signal Set Design

The problem of choosing an optimal signal set for non-Gaussian detection was reduced to a smooth inequality constrained mini-max nonlinear programming problem by Gockenbach and Kearsley. Here we consider the application of several optimization algorithms, both global and local, to this problem. The most promising results are obtained when special-purpose sequential quadratic programming (SQP) algorithms are embedded into stochastic global algorithms.     

Simulation response optimization via an alternating variable methodsimulation response optimization

Simulation response optimization has wide applications for management of systems that are so complicated that the performance can only be evaluated by using simulation. This paper modifies the Hooke-Jeeves alternating variable method used in deterministic optimization to suit the stochastic environment in simulation response optimization. The basic idea underlying the proposed method is to conduct several different replications at each trial point to obtain a reliable estimate of the theoretical response. To avoid misjudging the real difference between two points due to the stochastic nature, a t-test instead of a simple comparison of the mean responses is performed. Empirical results from a stochastic Watson function with nine variables, a queueing problem with two variables, and an inventory problem with two variables indicate that the alternating variable method modified in this paper is superior to the Nelder-Mead simplex method, two stochastic approximation methods, and Fu and Healy's hybrid method. It is also robust with respect to the parameter for deciding the number of replications conducted at each trial point.     

Tradeoff analysis of non-linear dynamical systems under stochastic excitation

An efficient methodology to carry out multi-objective optimization of non-linear structural systems under stochastic excitation is presented. Specifically, an efficient determination of particular Pareto or non-inferior solutions is implemented. Pareto solutions are obtained by compromise programming which is based on the minimization of the distance between the point that contains the individual optima of each of the objective functions and the Pareto set. The response of the structural system is characterized in terms of the first two statistical moments of the response process, i.e. the mean and variance. An efficient sensitivity analysis of non-inferior solutions with respect to the design variables becomes possible with the proposed formulation. Such information is used for decision making and tradeoff analysis. The compromise programming problem is solved by an efficient procedure that combines a local statistical linearization approach, modal analysis, global approximation concepts, and a sequential optimization scheme. Numerical results show that the total number of stochastic analyses required during the multi-objective optimization process is in general very small. Hence, different compromise solutions including the design that best represents the outcome that the designer considers potentially satisfactory are obtained in an efficient manner. In this way, the analyst can conduct a decision-making analysis through an efficient interactive procedure.     

Structural optimization of non-linear systems under stochastic excitation

This work concentrates on the structural optimization of a class of non-linear systems with deterministic structural parameters subject to stochastic excitation. The optimization problem is formulated as the minimization of an objective function subject to constraints on the response level. The stochastic response is characterized by its first two statistical moments, which are computed by a statistical equivalent linearization technique. The implicit structural optimization problem is replaced by a sequence of explicit sub-optimization problems. The sub-problems are constructed by using a conservative first-order approximation of the objective and constraint functions. The applicability of the proposed design process is demonstrated in three numerical examples where the methodology is applied to systems with nonlinearity of hardening and hysteretic type. The effects of the nonlinearity on the general performance of the final designs are discussed. At the same time, some engineering implications of the results obtained in this work are addressed.     

Capacitated disassembly scheduling with random demand

This paper considers disassembly scheduling, which is the problem of determining the quantity and timing of the end-of-use/life products to be disassembled while satisfying the demand for their parts obtained from disassembling the products over a planning horizon. This paper focuses on the problem with stochastic demand of parts/modules, capacity restrictions on disassembly resources, and multiple product types with a two-level product structure. The two-level product structure implies that an end-of-use/life product is hierarchically decomposed into two levels where the first level corresponds to the parts/modules and the second level corresponds to the product. We formulate the problem as a stochastic inventory model and to solve the problem we propose a Lagrangian heuristic algorithm as well as an optimisation algorithm for the sub-problems obtained from Lagrangian decomposition. The test results on randomly generated problems show that the Lagrangian heuristic algorithm demonstrates good performance in terms of solution quality and time.     

Particle-swarm harmony search for water network design

The optimal design of water distribution networks is a non-linear, multi-modal, and constrained problem classified as an NP-hard combinatorial problem. Because of the drawbacks of calculus-based algorithms, the problem has been tackled by assorted stochastic algorithms, such as the genetic algorithm, simulated annealing, tabu search, shuffled frog-leaping algorithm, ant colony optimization algorithm, harmony search, cross entropy, and scatter search. This study proposes a modified harmony search algorithm incorporating particle swarm concept. This algorithm was applied to the design of four bench-mark networks (two-loop, Hanoi, Balerma, and New York City networks), with good results.     

Manpower supply planning for aircraft line maintenance under stochastic incidents

We plan the manpower supply for aircraft line maintenance, taking into account two types of stochastic incidents: manpower demands for a flight and the number of aircraft needing to be serviced at one time. The problem is solved to find the shift and maintenance group combinations best suited for the given airline. The optimal aircraft maintenance certification for a crew is also analyzed to improve the entire manpower structure. In addition, the addition of temporary manpower required for actual daily operations is also considered as a part of understanding the total manpower utilized in actual operations. An integrated method including scenario generation and a stochastic model is developed to deal with the problem. Finally, we perform a case study based on operating data obtained from a major airline in Taiwan. The results and findings are compared with the airline’s current manpower plan in the discussion, and suggestions for improvement are made.     

Locating capacitated facilities to maximize captured demand

We consider the problem of locating a set of facilities on a network to maximize the expected number of captured demand when customer demands are stochastic and congestion exists at facilities. Customers travel to their closest facility to obtain service. If the facility is full (no more space in the waiting room), they attempt to obtain service from the next-closest facility not yet visited from its current position on the network. A customer is lost either when the closest facility is located too far away or all facilities have been visited. After formulating the model, we propose two heuristic procedures. We combine the heuristics with an iterative calibration scheme to estimate the expected demand rate faced by the facilities: this is required for evaluating objective function values. Extensive computational results are presented.     

A perturbation method for stochastic meshless analysis in elastostatics

A stochastic meshless method is presented for solving boundary‐value problems in linear elasticity that involves random material properties. The material property was modelled as a homogeneous random field. A meshless formulation was developed to predict stochastic structural response. Unlike the finite element method, the meshless method requires no structured mesh, since only a scattered set of nodal points is required in the domain of interest. There is no need for fixed connectivities between nodes. In conjunction with the meshless equations, classical perturbation expansions were derived to predict second‐moment characteristics of response. Numerical examples based on one‐ and two‐dimensional problems are presented to examine the accuracy and convergence of the stochastic meshless method. A good agreement is obtained between the results of the proposed method and Monte Carlo simulation. Since mesh generation of complex structures can be a far more time‐consuming and costly effort than the solution of a discrete set of equations, the meshless method provides an attractive alternative to finite element method for solving stochastic mechanics problems. Copyright © 2001 John Wiley & Sons, Ltd.     

A new bi-fidelity model reduction method for Bayesian inverse problems

This work presents a new bi-fidelity model reduction approach to the inverse problem under the framework of Bayesian inference. A low-rank approximation is introduced to the solution of the corresponding forward problem and admits a variable-separation form in terms of stochastic basis functions and physical basis functions. The calculation of stochastic basis functions is computationally predominant for the low-rank expression. To significantly improve the efficiency of constructing the low-rank approximation, we propose a bi-fidelity model reduction based on a novel variable-separation method, where a low-fidelity model is used to compute the stochastic basis functions and a high-fidelity model is used to compute the physical basis functions. The low-fidelity model has lower accuracy but efficient to evaluate compared with the high-fidelity model; it accelerates the derivative of recursive formulation for the stochastic basis functions. The high-fidelity model is computed in parallel for a few samples scattered in the stochastic space when we construct the high-fidelity physical basis functions. The required number of forward model simulations in constructing the basis functions is very limited. The bi-fidelity model can be constructed efficiently while retaining good accuracy simultaneously. In the proposed approach, both the stochastic basis functions and physical basis functions are calculated using the model information. This implies that a few basis functions may accurately represent the model solution in high-dimensional stochastic spaces. The bi-fidelity model reduction is applied to Bayesian inverse problems to accelerate posterior exploration. A few numerical examples in time-fractional derivative diffusion models are carried out to identify the smooth field and channel-structured field in porous media in the framework of Bayesian inverse problems.     

A vehicle routing problem with time windows and stochastic demands

Abstract

This study presents an approach for considering a vehicle routing problem where customers’ pickup demands are uncertain and require serving within some settled time windows. Customers’ demands are assumed to follow given discrete probability distributions. This study proposes a nonlinear stochastic integer program with recourse to formulate the vehicle routing problem with stochastic demands and time windows (VRPTW‐SD, for short). The objective of the VRPTW‐SD is to minimize the total cost of the first‐stage solution and expected recourse cost of the second‐stage solution. The total cost of the first‐stage problem includes the total travel cost for all links and the total waiting cost at all nodes. When a vehicle capacity is attained or exceeded, recourse actions are needed and recourse costs incurred in order to finish the planned route schedules. Two categories of schedule failure are introduced in this work; the recourse costs derive from the variations in travel time travel time, waiting time, and penalties of late arrival for time windows. In addition, an optimization algorithm is developed for solving the VRPTW‐SD, according to the framework of the L‐shaped method. Numerical results are given to demonstrate its validity.     

Waveform estimation with jitter noise using stochastic up and downmethod

Jitter noise exists, especially, when sampling high-frequency waveforms. This paper aims to address this problem through a stochastic method. By studying the stochastic up and down method in detail, we propose a “ratio indicator”, which can supplement the basic stochastic up and down method. Simulation results show that the proposed method gives good estimates with known error bounds     

Optimization of aluminium sheet hot stamping process using a multi-objective stochastic approach

This article aims to investigate the means to obtain optimal hot stamping process parameters and the influence of the stochastic variability of these parameters on forming quality. A multi-objective stochastic approach, integrating response surface methodology (RSM), multi-objective genetic algorithm optimization non-dominated sorting genetic algorithm II (NSGA-II) and the Monte Carlo simulation (MCS) method is proposed in this article to achieve this goal. RSM was used to establish the relationship between the process parameters and forming quality indices. NSGA-II was utilized to obtain a Pareto frontier, which consists of a series of optimal process parameters. The MCS method was employed to study and reduce the influence of a stochastic property of these process parameters on forming quality. The results confirmed the efficiency of the proposed multi-objective stochastic approach during optimization of the hot stamping process. Robust optimal process parameters guaranteeing good forming quality were also obtained using this approach.     

A robust dual algorithm for topology design of structures in discrete variables

Dual optimization algorithms for the topology optimization of continuum structures in discrete variables are gaining popularity in recent times since, in topology design problems, the number of constraints is small in comparison to the number of design variables. Good topologies can be obtained for the minimum compliance design problem when the perimeter constraint is imposed in addition to the volume constraint. However, when the perimeter constraint is relaxed, the dual algorithm tends to give bad results, even with the use of higher‐order finite element models as we demonstrate in this work. Since, a priori, one does not know what a good value of the perimeter to be specified is, it is essential to have an algorithm which generates good topologies even in the absence of the perimeter constraint. We show how the dual algorithm can be made more robust so that it yields good designs consistently in the absence of the perimeter constraint. In particular, we show that the problem of checkerboarding which is frequently observed with the use of lower‐order finite elements is eliminated. Copyright © 2001 John Wiley & Sons, Ltd.     

Post optimization for accurate and efficient reliability‐based design optimization using second‐order reliability method based on importance sampling and its stochastic sensitivity analysis

In this study, a post optimization technique for a correction of inaccurate optimum obtained using first‐order reliability method (FORM) is proposed for accurate reliability‐based design optimization (RBDO). In the proposed method, RBDO using FORM is first performed, and then the proposed second‐order reliability method (SORM) is performed at the optimum obtained using FORM for more accurate reliability assessment and its sensitivity analysis. In the proposed SORM, the Hessian of a performance function is approximated by reusing derivatives information accumulated during previous RBDO iterations using FORM, indicating that additional functional evaluations are not required in the proposed SORM. The proposed SORM calculates a probability of failure and its first‐order and second‐order stochastic sensitivity by applying the importance sampling to a complete second‐order Taylor series of the performance function. The proposed post optimization constructs a second‐order Taylor expansion of the probability of failure using results of the proposed SORM. Because the constructed Taylor expansion is based on the reliability method more accurate than FORM, the corrected optimum using this Taylor expansion can satisfy the target reliability more accurately. In this way, the proposed method simultaneously achieves both efficiency of FORM and accuracy of SORM. Copyright © 2015 John Wiley & Sons, Ltd.