A new importance sampling Monte Carlo method for a flow network reliability problem

The exact evaluation of the probability that the maximum st‐flow is greater than or equal to a fixed demand in a stochastic flow network is an NP‐hard problem. This limitation leads one to consider Monte Carlo alternatives. In this paper, we propose a new importance sampling Monte Carlo method. It is based on a recursive use of the state space decomposition methodology of Doulliez and Jamoulle during the simulation process. We show theoretically that the resulting estimator belongs to the variance‐reduction family and we give an upper bound on its variance. As shown by experimental tests, the new sampling principle offers, in many cases, substantial speedups with respect to a previous importance sampling based on the same decomposition procedure and its best performances are obtained when highly reliable networks are analyzed. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 204–228, 2002; DOI 10.1002/nav.10004     

Using stochastic programming to solve an outpatient appointment scheduling problem with random service and arrival times

We study a stochastic outpatient appointment scheduling problem (SOASP) in which we need to design a schedule and an adaptive rescheduling (i.e., resequencing or declining) policy for a set of patients. Each patient has a known type and associated probability distributions of random service duration and random arrival time. Finding a provably optimal solution to this problem requires solving a multistage stochastic mixed‐integer program (MSMIP) with a schedule optimization problem solved at each stage, determining the optimal rescheduling policy over the various random service durations and arrival times. In recognition that this MSMIP is intractable, we first consider a two‐stage model (TSM) that relaxes the nonanticipativity constraints of MSMIP and so yields a lower bound. Second, we derive a set of valid inequalities to strengthen and improve the solvability of the TSM formulation. Third, we obtain an upper bound for the MSMIP by solving the TSM under the feasible (and easily implementable) appointment order (AO) policy, which requires that patients are served in the order of their scheduled appointments, independent of their actual arrival times. Fourth, we propose a Monte Carlo approach to evaluate the relative gap between the MSMIP upper and lower bounds. Finally, in a series of numerical experiments, we show that these two bounds are very close in a wide range of SOASP instances, demonstrating the near‐optimality of the AO policy. We also identify parameter settings that result in a large gap in between these two bounds. Accordingly, we propose an alternative policy based on neighbor‐swapping. We demonstrate that this alternative policy leads to a much tighter upper bound and significantly shrinks the gap.     

A branch‐and‐price approach for the stochastic generalized assignment problem

In this article, we address a stochastic generalized assignment machine scheduling problem in which the processing times of jobs are assumed to be random variables. We develop a branch‐and‐price (B&P) approach for solving this problem wherein the pricing problem is separable with respect to each machine, and has the structure of a multidimensional knapsack problem. In addition, we explore two other extensions of this method—one that utilizes a dual‐stabilization technique and another that incorporates an advanced‐start procedure to obtain an initial feasible solution. We compare the performance of these methods with that of the branch‐and‐cut (B&C) method within CPLEX. Our results show that all B&P‐based approaches perform better than the B&C method, with the best performance obtained for the B&P procedure that includes both the extensions aforementioned. We also utilize a Monte Carlo method within the B&P scheme, which affords the use of a small subset of scenarios at a time to estimate the “true” optimal objective function value. Our experimental investigation reveals that this approach readily yields solutions lying within 5% of optimality, while providing more than a 10‐fold savings in CPU times in comparison with the best of the other proposed B&P procedures. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 131–143, 2014     

加权随机模拟的时变可靠性分析方法

针对结构时变可靠性的随机模拟分析方法计算代价大的问题,在极值方法的基础上提出基于加权随机模拟的时变可靠性分析策略。时变可靠性分析需要计算在不同时间处的失效概率,通常需要进行多次可靠性分析,计算代价巨大。所提方法通过对常规静态可靠性的随机模拟方法进行改进拓展,运用加权策略分别发展了加权蒙特卡洛法和加权重要抽样法,使之能够高效分析计算时变可靠性问题。所提方法仅需一次常规可靠性分析模拟,即可得到时变失效概率函数估计。采用管状悬臂梁和十杆桁架两个算例进行验证。结果表明,基于加权思想的分析方法在能确保精确度的前提下能够大幅度减小计算量,提高计算效率。     

基于蒙特卡洛和multi-Agents的舰艇编队维修保障能力优化求解

针对舰艇编队的维修保障能力评估,采用蒙特卡洛方法和智能计算技术进行了建模,并在分布交互仿真环境下进行了求解.通过将舰艇编队维修系统按维修单位的功能划分成多个子系统,每个子系统抽象为能进行局部优化的Agent,实现了基于Agent的建模.在此基础上,重点讨论了基于HLA的仿真环境,通过应用RTI的服务确保了求解过程的时空一致性.仿真试验结果表明:通过采用蒙特卡洛方法、智能技术及分布交互仿真技术相结合的方法,能有效地对舰艇编队的维修保障能力进行评估.     

Statistical decision analysis of stochastic linear programming problems

This paper presents a statistical decision analysis of a one-stage linear programming problem with deterministic constraints and stochastic criterion function. Procedures for obtaining numerical results are given which are applicable to any problem having this general form. We begin by stating the statistical decision problems to be considered, and then discuss the expected value of perfect information and the expected value of sample information. In obtaining these quantities, use is made of the distribution of the optimal value of the linear programming problem with stochastic criterion function, and so we discuss Monte Carlo and numerical integration procedures for estimating the mean of this distribution. The case in which the random criterion vector has a multivariate Normal distribution is discussed separately, and more detailed methods are offered. We discuss dual problems, including some relationships of this work with other work in probabilistic linear programming. An example is given in Appendix A showing application of the methods to a sample problem. In Appendix B we consider the accuracy of a procedure for approximating the expected value of information.     

Strategic capacity decision‐making in a stochastic manufacturing environment using real‐time approximate dynamic programming

In this study, we illustrate a real‐time approximate dynamic programming (RTADP) method for solving multistage capacity decision problems in a stochastic manufacturing environment, by using an exemplary three‐stage manufacturing system with recycle. The system is a moderate size queuing network, which experiences stochastic variations in demand and product yield. The dynamic capacity decision problem is formulated as a Markov decision process (MDP). The proposed RTADP method starts with a set of heuristics and learns a superior quality solution by interacting with the stochastic system via simulation. The curse‐of‐dimensionality associated with DP methods is alleviated by the adoption of several notions including “evolving set of relevant states,” for which the value function table is built and updated, “adaptive action set” for keeping track of attractive action candidates, and “nonparametric k nearest neighbor averager” for value function approximation. The performance of the learned solution is evaluated against (1) an “ideal” solution derived using a mixed integer programming (MIP) formulation, which assumes full knowledge of future realized values of the stochastic variables (2) a myopic heuristic solution, and (3) a sample path based rolling horizon MIP solution. The policy learned through the RTADP method turned out to be superior to polices of 2 and 3. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 2010     

Multiple-attribute decision making with partial information: The expected-value criterion

We consider the multiple-attribute decision problem with finite action set and additive utility function. We suppose that the decision maker cannot specify nonnegative weights for the various attributes which would resolve the problem, but that he/she supplies ordinal information about these weights which can be translated into a set of linear constraints restricting their values. A bounded polytope W of feasible weight vectors is thus determined. Supposing that each element of W has the same chance of being the “appropriate one,” we compute the expected utility value of each action. The computation method uses a combination of numerical integration and Monte Carlo simulation and is equivalent to finding the center of mass of the bounded polytope W . Comparisons are made with another criterion already presented, the comparative hyper-volume criterion, and two small examples are presented.     

非线性随机动态响应的高效模拟方法

提出了一种分析多自由度非线性系统在随机激励下响应的高效模拟方法。该方法以蒙特卡罗方法为基础,针对动态问题,建立了有效的重要性判别准则,采用俄罗斯轮盘赌与分裂方法来处理响应样本,增加了样本在低失效概率区域出现的几率,提高了模拟效率。通过两个算例表明,该方法操作简单,可以大大地减少计算量,能够适用于实际的工程问题。     

Optimal power control in a wireless network using a model with stochastic link coefficients

This paper addresses optimal power allocation in a wireless communication network under uncertainty. The paper introduces a framework for optimal transmit power allocation in a wireless network where both the useful and interference coefficients are random. The new approach to power control is based on a stochastic programming formulation with probabilistic SIR constraints. This allows to state the power allocation problem as a convex optimization problem assuming normally or log‐normally distributed communication link coefficients. Numerical examples illustrate the performance of the optimal stochastic power allocation. A distributed algorithm for the decentralized solution of the stochastic power allocation problem is discussed. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Route optimization for multiple searchers

We consider a discrete time‐and‐space route‐optimization problem across a finite time horizon in which multiple searchers seek to detect one or more probabilistically moving targets. This article formulates a novel convex mixed‐integer nonlinear program for this problem that generalizes earlier models to situations with multiple targets, searcher deconfliction, and target‐ and location‐dependent search effectiveness. We present two solution approaches, one based on the cutting‐plane method and the other on linearization. These approaches result in the first practical exact algorithms for solving this important problem, which arises broadly in military, rescue, law enforcement, and border patrol operations. The cutting‐plane approach solves many realistically sized problem instances in a few minutes, while existing branch‐and‐bound algorithms fail. A specialized cut improves solution time by 50[percnt] in difficult problem instances. The approach based on linearization, which is applicable in important special cases, may further reduce solution time with one or two orders of magnitude. The solution time for the cutting‐plane approach tends to remain constant as the number of searchers grows. In part, then, we overcome the difficulty that earlier solution methods have with many searchers. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

一种用于 C~3I 系统的异类传感器数据融合算法

在文献〔８〕和〔９〕基础上研究了在不等样本情况下的异类传感器——雷达与ＥＳＭ——的航迹相关问题。首先,基于模糊综合函数找出两个最可能的雷达与ＥＳＭ航迹相关对,然后,利用统计理论并采用多门限决策方法进行雷达与ＥＳＭ航迹相关判决。仿真结果表明,与文献〔８〕的方法相比,在雷达航迹比较多的情况下,本文所提出的在不等样本情况下的雷达与ＥＳＭ相关算法具有与其很相近的性能,但计算量明显减少;而与文献〔９〕的方法相比,这里采用多门限决策方法又可同时减小两类错误概率。     

导弹突防后弹道机动调整策略强化学习

针对弹道导弹中段突防后飞行弹道与标准弹道产生较大偏离的弹道机动调整问题,建立了机动调整时机策略最优化模型。设计了机动调整逆序Q学习算法,采用Tile coding逼近器编码状态特征空间,并对其进行线性逼近。构建了Q学习算法与蒙特卡罗方法相结合的逆序更新策略机制,以对导弹机动调整最优时机进行训练。仿真测试分析结果表明,在给定场景参数下,通过10 000代强化学习算法训练得到的策略能够可靠地使用最少机动次数控制导弹突防后飞行弹道的调整决策,验证了方法的有效性。     

基于Monte Carlo法的地空导弹火力分配优化问题研究

在确定地空导弹对目标的可射击系数、火力重叠修正系数和转火矛盾修正系数的基础上,结合Monte Carlo法的基本原理,介绍了解决地空导弹火力分配优化问题的一般步骤。运用计算机模拟技术,通过算例,证明了该方法的可行性,为有效解决地空导弹火力分配优化问题提供了一种较为科学的方法。     

Adaptive importance sampling for extreme quantile estimation with stochastic black box computer models

Quantile is an important quantity in reliability analysis, as it is related to the resistance level for defining failure events. This study develops a computationally efficient sampling method for estimating extreme quantiles using stochastic black box computer models. Importance sampling has been widely employed as a powerful variance reduction technique to reduce estimation uncertainty and improve computational efficiency in many reliability studies. However, when applied to quantile estimation, importance sampling faces challenges, because a good choice of the importance sampling density relies on information about the unknown quantile. We propose an adaptive method that refines the importance sampling density parameter toward the unknown target quantile value along the iterations. The proposed adaptive scheme allows us to use the simulation outcomes obtained in previous iterations for steering the simulation process to focus on important input areas. We prove some convergence properties of the proposed method and show that our approach can achieve variance reduction over crude Monte Carlo sampling. We demonstrate its estimation efficiency through numerical examples and wind turbine case study.     

Optimal resource allocation and redistribution strategy in military conflicts with Lanchester square law attrition

We address the problem of optimal decision‐making in conflicts based on Lanchester square law attrition model where a defending force needs to be partitioned optimally, and allocated to two different attacking forces of differing strengths and capabilities. We consider a resource allocation scheme called the Time Zero Allocation with Redistribution (TZAR) strategy, where allocation is followed by redistribution of defending forces, on the occurrence of certain decisive events. Unlike previous work on Lanchester attrition model based tactical decision‐making, which propose time sequential tactics through an optimal control approach, the present article focuses on obtaining simpler resource allocation tactics based on a static optimization framework, and demonstrates that the results obtained are similar to those obtained by the more complex dynamic optimal control solution. Complete solution for this strategy is obtained for optimal partitioning of resources of the defending forces. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

基于Bayes小子样二项分布单元可靠性评定的仿真方法

对于小子样二项分布单元可靠度下限评定,经典方法有很大局限性,文中介绍了Bayes方法。并在其基础上提出基于Bayes方法的Monte Carlo仿真方法,示例证明,该方法有很好的应用前途。     

The dynamic and stochastic knapsack Problem with homogeneous‐sized items and postponement options

This article generalizes the dynamic and stochastic knapsack problem by allowing the decision‐maker to postpone the accept/reject decision for an item and maintain a queue of waiting items to be considered later. Postponed decisions are penalized with delay costs, while idle capacity incurs a holding cost. This generalization addresses applications where requests of scarce resources can be delayed, for example, dispatching in logistics and allocation of funding to investments. We model the problem as a Markov decision process and analyze it through dynamic programming. We show that the optimal policy with homogeneous‐sized items possesses a bithreshold structure, despite the high dimensionality of the decision space. Finally, the value (or price) of postponement is illustrated through numerical examples. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 267–292, 2015     

A selective newsvendor approach to order management

Consider a supplier offering a product to several potential demand sources, each with a unique revenue, size, and probability that it will materialize. Given a long procurement lead time, the supplier must choose the orders to pursue and the total quantity to procure prior to the selling season. We model this as a selective newsvendor problem of maximizing profits where the total (random) demand is given by the set of pursued orders. Given that the dimensionality of a mixed‐integer linear programming formulation of the problem increases exponentially with the number of potential orders, we develop both a tailored exact algorithm based on the L‐shaped method for two‐stage stochastic programming as well as a heuristic method. We also extend our solution approach to account for piecewise‐linear cost and revenue functions as well as a multiperiod setting. Extensive experimentation indicates that our exact approach rapidly finds optimal solutions with three times as many orders as a state‐of‐the‐art commercial solver. In addition, our heuristic approach provides average gaps of less than 1% for the largest problems that can be solved exactly. Observing that the gaps decrease as problem size grows, we expect the heuristic approach to work well for large problem instances. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2008     

Tests for homogeneity of distributions of component lifetimes from system lifetime data with known system signatures

In this article, we discuss the problem of testing the homogeneity of distributions of component lifetimes based on system lifetime data when the system signatures are known. Both parametric and nonparametric procedures are developed for this problem. For nonparametric testing, the Mann–Whitney‐type statistic is used, and its performance and limitations are discussed. Next, we assume the component lifetimes to follow exponential distributions and then develop different parametric tests. Exact and asymptotic methods are developed based on the method of moments estimators. A Monte Carlo simulation study is used to compare the performance of different parametric procedures with that of the nonparametric procedure. Based on the results of the simulation study, discussions and practical recommendations are made and finally some concluding remarks are provided. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 550–563, 2015