Fast computation of bounds for two-terminal network reliability

In this paper, an algorithm for the fast computation of network reliability bounds is proposed. The evaluation of the network reliability is an intractable problem for very large networks, and hence approximate solutions based on reliability bounds have assumed importance. The proposed bounds computation algorithm is based on an efficient BDD representation of the reliability graph model and a novel search technique to find important minpaths/mincuts to quickly reduce the gap between the reliability upper and lower bounds. Furthermore, our algorithm allows the control of the gap between the two bounds by controlling the overall execution time. Therefore, a trade-off between prediction accuracy and computational resources can be easily made in our approach. The numerical results are presented for large real example reliability graphs to show the efficacy of our approach.     

THE DESIGN AND ANALYSIS OF ALGORITHM OF MINIMUM COST SPANNING TREE

ＴＨＥＤＥＳＩＧＮＡＮＤＡＮＡＬＹＳＩＳＯＦＡＬＧＯＲＩＴＨＭＯＦＭＩＮＩＭＵＭＣＯＳＴＳＰＡＮＮＩＮＧＴＲＥＥ￥（徐绪松，刘大成，吴丽华）ＸｕＸｕｓｏｎｇ；ＬｉｕＤａｃｈｅｎｇ；ＷｕＬｉｈｕａ（ＳｃｈｏｏｌｏｆＭａｎａｇｅｍｅｎｔ，ＷｕｈａｎＵｎｉ...     

Multistate components assignment problem with optimal network reliability subject to assignment budget

The typical assignment problem for finding the optimal assignment of a set of components to a set of locations in a system has been widely studied in practical applications. However, this problem mainly focuses on maximizing the total profit or minimizing the total cost without considering component’s failure. In practice, each component should be multistate due to failure, partially failure, or maintenance. That is, each component has several capacities with a probability distribution and may fail. When a set of multistate components is assigned to a system, the system can be treated as a stochastic-flow network. The network reliability is the probability that d units of homogenous commodity can be transmitted through the network successfully. The multistate components assignment problem to maximize the network reliability is never discussed. Therefore, this paper focuses on solving this problem under an assignment budget constraint, in which each component has an assignment cost. The network reliability under a components assignment can be evaluated in terms of minimal paths and state-space decomposition. Subsequently an optimization method based on genetic algorithm is proposed. The experimental results show that the proposed algorithm can be executed in a reasonable time.     

Computation of spectral sets for uncertain linear fractional-order systems

The present paper proposes an algorithm to compute the spectral set of a family of fractional-order pseudo-polynomials. The algorithm makes use of interval constraint propagation technique to find out all the structural roots of the given uncertain fractional-order systems in the given search domain. It is first shown that the problem of finding the spectral set can be formulated as an interval constraint satisfaction problem and then solved using branch and prune algorithm. The algorithm guarantees that all the points of the spectral set are computed to prescribed accuracy. The proposed algorithm is demonstrated on a plant with nonlinear parametric dependencies and also on a practical application of a gas turbine plant.     

A neural network approach to efficient valuation of large portfolios of variable annuities

Managing and hedging the risks associated with Variable Annuity (VA) products require intraday valuation of key risk metrics for these products. The complex structure of VA products and computational complexity of their accurate evaluation have compelled insurance companies to adopt Monte Carlo (MC) simulations to value their large portfolios of VA products. Because the MC simulations are computationally demanding, especially for intraday valuations, insurance companies need more efficient valuation techniques. Recently, a framework based on traditional spatial interpolation techniques has been proposed that can significantly decrease the computational complexity of MC simulation (Gan and Lin, 2015). However, traditional interpolation techniques require the definition of a distance function that can significantly impact their accuracy. Moreover, none of the traditional spatial interpolation techniques provide all of the key properties of accuracy, efficiency, and granularity (Hejazi et al., 2015). In this paper, we present a neural network approach for the spatial interpolation framework that affords an efficient way to find an effective distance function. The proposed approach is accurate, efficient, and provides an accurate granular view of the input portfolio. Our numerical experiments illustrate the superiority of the performance of the proposed neural network approach compared to the traditional spatial interpolation schemes.     

Methods for optimizing gas transmission networks

We describe two methods for the optimization of gas transmission networks. The first method reduces the number of variables in the optimization problem by eliminating the pipe-flow variables. The second method solves an optimization problem with the full set of variables to achieve better behaviour. These two methods are compared by a series of tests based on the British Gas NTS (National Transmission System). The results of these tests are reported. By formulating the network problem as an optimization problem we have been able to replace heuristics by well proven methods. The reliability of the algorithm using the reduced set of unknowns varied depending on the size of problem and the type of objective function being minimized. The algorithm using the full set of unknowns had no such difficulties, even though it needs to be used with some care. The algorithm is robust in the sense that when the objective function has the necessary continuities, there is a feasible point and the penalty terms ensure positive curvature, then a solution is found reliably. The algorithm based on the reduced set of unknowns is considerably faster than that using the full set, when it succeeds. The factor between the times taken ranges from 1.2 to 5 (average 3) for the smallest network. For the second case comparison is harder since the reduced set algorithm was given a head start in five cases. For the other five the factor is between 2.3 and 8.3. For the largest problem there is just one case in which the comparison is on equal terms, and here the factor is 18. It is clear that the reliability of the full set algorithm is bought at a considerable cost which rises as the problem gets bigger. The main conclusion is that the Sequential Augmented Lagrange Method yields a reliable algorithm for minimizing objective functions of practical interest based on gas networks such as the British Gas National Transmission System. It is not satisfactory to carry over to the case with machines techniques like those of the nodal and loop methods which work well on networks with no machines.     

Practical sequential bounds for approximating two-terminal reliability

With increasing emphases on better and more reliable services, network systems have incorporated reliability analysis as an integral part in their planning, design and operation. This article first presents a simple exact decomposition algorithm for computing the NP-hard two-terminal reliability, which measures the probability of successful communication from specified source node to sink node in the network. Then a practical bounding algorithm, which is indispensable for large networks, is presented by modifying the exact algorithm for obtaining sequential lower and upper bounds on two-terminal reliability. Based on randomly generated large networks, computational experiments are conducted to compare the proposed algorithm to the well-known and widely used edge-packing approximation model and to explore the performance of the proposed bounding algorithm. Computational results reveal that the proposed bounding algorithm is superior to the edge-packing model, and the trade-off of accuracy for execution time ensures that an exact difference between upper and lower bounds on two-terminal reliability can be obtained within an acceptable time.     

An analytical methodology for assessment of smart monitoring impact on future electric power distribution system reliability

Smart grid is referred to a modernized power grid which can mitigate fault detection and allow self‐healing of the system without the intervention of operators. This article proposes an innovative analytical formulation using Markov method to evaluate electric power distribution system reliability in smart grids, which incorporates the impact of smart monitoring on the overall system reliability. An accurate reliability model of the main network components and the communication infrastructure have been also considered in the methodology. The proposed approach was applied to a well‐known test bed (Roy Billinton Test System) and various reliability case studies with monitoring provision and monitoring deficiency are analyzed. This article involves the developing possibilities of communication technologies and next‐generation control systems of the entire smart network based on the real‐time monitoring and modern control system to achieve a reliable, economical, safe, and high efficiency of electricity. The implementations indicate that using an appropriate set of the smart grid monitoring devices for power system components can virtually influence all the reliability indices although the amount of improvement varies between techniques. The proposed approach determined that smart monitoring for which components of the electric power distribution systems are tailored and deduce to major economical benefits. The described approach also reveals which reliability indices drastically influenced using monitoring. © 2014 Wiley Periodicals, Inc. Complexity 21: 99–113, 2015     

A cross entropy based algorithm for reliability problems

The Cross Entropy method has recently been applied to combinatorial optimization problems with promising results. This paper proposes a Cross Entropy based algorithm for reliability optimization of complex systems, where one wants to maximize the reliability of a system through optimal allocation of redundant components while respecting a set of budget constraints. We illustrate the effectiveness of the proposed algorithm on two classes of problems, software system reliability optimization and complex network reliability optimization, by testing it on instances from the literature as well as on randomly generated large scale instances. Furthermore, we show how a Cross Entropy-based algorithm can be fine-tuned by using a training scheme based upon the Response Surface Methodology. Computational results show the effectiveness as well as the robustness of the algorithm on different classes of problems.     

On the computation of all supported efficient solutions in multi-objective integer network flow problems

This paper presents a new algorithm for identifying all supported non-dominated vectors (or outcomes) in the objective space, as well as the corresponding efficient solutions in the decision space, for multi-objective integer network flow problems. Identifying the set of supported non-dominated vectors is of the utmost importance for obtaining a first approximation of the whole set of non-dominated vectors. This approximation is crucial, for example, in two-phase methods that first compute the supported non-dominated vectors and then the unsupported non-dominated ones. Our approach is based on a negative-cycle algorithm used in single objective minimum cost flow problems, applied to a sequence of parametric problems. The proposed approach uses the connectedness property of the set of supported non-dominated vectors/efficient solutions to find all integer solutions in maximal non-dominated/efficient facets.     

考虑应急设施中断风险与防御的可靠性选址模型研究

为提高应急设施运行的可靠性和抵御中断风险的能力, 研究中断情境下的应急设施选址-分配决策问题。扩展传统无容量限制的固定费用选址模型, 从抵御设施中断的视角和提高服务质量的视角建立选址布局网络的双目标优化模型, 以应急设施的建立成本和抵御设施中断的加固成本最小为目标, 以最大化覆盖服务质量水平为目标, 在加固预算有限及最大最小容量限制约束下, 构建中断情境下应急设施的可靠性选址决策优化模型。针对所构建模型的特性利用非支配排序多目标遗传算法(NSGA-Ⅱ)求解该模型, 得到多目标的Pareto前沿解集。以不同的算例分析和验证模型和算法的可行性。在获得Pareto前沿的同时对不同中断概率进行灵敏度分析, 给出Pareto最优解集的分布及应急设施选址布局网络的拓扑结构。     

Isodistant points in competitive network facility location

An isodistant point is any point on a network which is located at a predetermined distance from some node. For some competitive facility location problems on a network, it is verified that optimal (or near-optimal) locations are found in the set of nodes and isodistant points (or points in the vicinity of isodistant points). While the nodes are known, the isodistant points have to be determined for each problem. Surprisingly, no algorithm has been proposed to generate the isodistant points on a network. In this paper, we present a variety of such problems and propose an algorithm to find all isodistant points for given threshold distances associated with the nodes. The number of isodistant points is upper bounded by nm, where n and m are the number of nodes and the number of edges, respectively. Computational experiments are presented which show that isodistant points can be generated in short run time and the number of such points is much smaller than nm. Thus, for networks of moderate size, it is possible to find optimal (or near-optimal) solutions through the Integer Linear Programming formulations corresponding to the discrete version of such problems, in which a finite set of points are taken as location candidates.     

An estimation of distribution algorithm for nurse scheduling

Schedules can be built in a similar way to a human scheduler by using a set of rules that involve domain knowledge. This paper presents an Estimation of Distribution Algorithm (EDA) for the nurse scheduling problem, which involves choosing a suitable scheduling rule from a set for the assignment of each nurse. Unlike previous work that used Genetic Algorithms (GAs) to implement implicit learning, the learning in the proposed algorithm is explicit, i.e. we identify and mix building blocks directly. The EDA is applied to implement such explicit learning by building a Bayesian network of the joint distribution of solutions. The conditional probability of each variable in the network is computed according to an initial set of promising solutions. Subsequently, each new instance for each variable is generated by using the corresponding conditional probabilities, until all variables have been generated, i.e. in our case, a new rule string has been obtained. Another set of rule strings will be generated in this way, some of which will replace previous strings based on fitness selection. If stopping conditions are not met, the conditional probabilities for all nodes in the Bayesian network are updated again using the current set of promising rule strings. Computational results from 52 real data instances demonstrate the success of this approach. It is also suggested that the learning mechanism in the proposed approach might be suitable for other scheduling problems.     

考虑传输容量的通信网端到端可靠性指标算法

归一化传输容量加权通信网端到端可靠性指标,非常适合评价现代高速宽带通信网络.然而计算全过程易于在计算机上编程实现的算法尚未见到.研究出一整套可靠性指标的计算方法.由于,从路由计算、不交化网络状态集及其对应容量的求取,到最后获得可靠性指标结果等各个环节,均实现了代数化或逻辑代数化运算,因此,整套算法易于编写计算机程序.详细介绍了算法各环节的计算规则与步骤,并对正确性与合理性进行了论证.通过举例详细说明算法的计算过程,并检验算法的正确性.     

基于改进PSO-BP神经网络的贮存可靠性预测

贮存可靠性是军事储备质量监测的重要环节,科学准确地预测贮存可靠度是现代化军事评估的必然要求。针对历史贮存数据,建立可靠度与年限的贮存可靠性预测模型,采用进化策略改进粒子群算法(PSO)优化BP神经网络进行贮存可靠性预测。通过数据扩充提高样本质量和数量,应用改进后的PSO算法优化BP神经网络的初始权值和阈值,提高网络的泛化能力。PSO算法较好的全局搜索能力与BP网络很强的局部搜索能力相结合,能够避免早熟现象,提高算法的收敛速度及预测精度。实验结果表明,改进的PSO-BP网络模型比PSO-BP和BP神经网络获得更好的预测性能。     

Mathematical modelling for optimized control of Moscow's sewer network

An algorithm for the optimized control of a branching urban head-and-gravity sewer network is proposed. The control consists in redistribution of the sewage flows between the network structural components. The algorithm is based on a mathematical model and presupposes the use of a computer. The mathematical model consists of a set of algebraic equations with the structure transporting capacities captured as constraints. The mathematical task of control is stated and solved as an optimization problem. The objective function is the minimization of total electric energy consumption over all the network pumping stations. The assumptions substantiated by practice would reduce the problem to the known problem of linear programming. The discharge through each pumping station of the considered subnetwork of Moscow's sewer network was computed using a mathematical model and was compared to the value observed under the same actual conditions. From this comparison, it was concluded that the proposed algorithm was more successful in controlling the network than was the traditional operation. The correction of the working conditions of some pumping stations of the Moscow sewer subnetwork in accordance with the precalculated time schedule, has allowed a significant decrease in the electric energy consumption for conveyance of the sewage through the network.     

单调线性互补问题的最小原则(Ⅰ)

本文的主要结果可概括为以下两部分：１．在文［１］基础上给出单调线性互补问题（ＭＬＣＰ）最小原则的形式和提出在有限步内可求出ＭＬＣＰ解集的两种方法；２．导出仅用ＭＬＣＰ的一个解的梯度和约束集即可刻划ＭＬＣＰ解集的充要条件．     

Artificial neural network based inverse reliability analysis

An inverse reliability analysis is the problem to find design parameters corresponding to specified reliability levels expressed by reliability index or by theoretical failure probability. Design parameters can be deterministic or they can be associated to random variables described by statistical moments. The aim is to solve generally not only the single design parameter case but also the multiple parameter problems with given multiple reliability constraints. A new general approach of inverse reliability analysis is proposed. The inverse analysis is based on the coupling of a stochastic simulation of Monte Carlo type and an artificial neural network. A novelty of the approach is the utilization of the efficient small-sample simulation method Latin Hypercube Sampling used for the stochastic preparation of the training set. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Dynamic programming algorithms for the bi-objective integer knapsack problem

This paper presents two new dynamic programming (DP) algorithms to find the exact Pareto frontier for the bi-objective integer knapsack problem. First, a property of the traditional DP algorithm for the multi-objective integer knapsack problem is identified. The first algorithm is developed by directly using the property. The second algorithm is a hybrid DP approach using the concept of the bound sets. The property is used in conjunction with the bound sets. Next, the numerical experiments showed that a promising partial solution can be sometimes discarded if the solutions of the linear relaxation for the subproblem associated with the partial solution are directly used to estimate an upper bound set. It means that the upper bound set is underestimated. Then, an extended upper bound set is proposed on the basis of the set of linear relaxation solutions. The efficiency of the hybrid algorithm is improved by tightening the proposed upper bound set. The numerical results obtained from different types of bi-objective instances show the effectiveness of the proposed approach.     

Solving multi-objective multicast routing problems by evolutionary multi-objective simulated annealing algorithms with variable neighbourhoods

This paper presents the investigation of an evolutionary multi-objective simulated annealing (EMOSA) algorithm with variable neighbourhoods to solve the multi-objective multicast routing problems in telecommunications. The hybrid algorithm aims to carry out a more flexible and adaptive exploration in the complex search space by using features of the variable neighbourhood search to find more non-dominated solutions in the Pareto front. Different neighbourhood strictures have been designed with regard to the set of objectives, aiming to drive the search towards optimising all objectives simultaneously. A large number of simulations have been carried out on benchmark instances and random networks with real world features including cost, delay and link utilisations. Experimental results demonstrate that the proposed EMOSA algorithm with variable neighbourhoods is able to find high-quality non-dominated solutions for the problems tested. In particular, the neighbourhood structures that are specifically designed for each objective significantly improved the performance of the proposed algorithm compared with variants of the algorithm with a single neighbourhood.