Finding maximum subgraphs with relatively large vertex connectivity

We consider a clique relaxation model based on the concept of relative vertex connectivity. It extends the classical definition of a k-vertex-connected subgraph by requiring that the minimum number of vertices whose removal results in a disconnected (or a trivial) graph is proportional to the size of this subgraph, rather than fixed at k. Consequently, we further generalize the proposed approach to require vertex-connectivity of a subgraph to be some function f of its size. We discuss connections of the proposed models with other clique relaxation ideas from the literature and demonstrate that our generalized framework, referred to as f-vertex-connectivity, encompasses other known vertex-connectivity-based models, such as s-bundle and k-block. We study related computational complexity issues and show that finding maximum subgraphs with relatively large vertex connectivity is NP-hard. An interesting special case that extends the R-robust 2-club model recently introduced in the literature, is also considered. In terms of solution techniques, we first develop general linear mixed integer programming (MIP) formulations. Then we describe an effective exact algorithm that iteratively solves a series of simpler MIPs, along with some enhancements, in order to obtain an optimal solution for the original problem. Finally, we perform computational experiments on several classes of random and real-life networks to demonstrate performance of the developed solution approaches and illustrate some properties of the proposed clique relaxation models.     

On the solution‐space geometry of random constraint satisfaction problems

For various random constraint satisfaction problems there is a significant gap between the largest constraint density for which solutions exist and the largest density for which any polynomial time algorithm is known to find solutions. Examples of this phenomenon include random k‐SAT, random graph coloring, and a number of other random constraint satisfaction problems. To understand this gap, we study the structure of the solution space of random k‐SAT (i.e., the set of all satisfying assignments viewed as a subgraph of the Hamming cube). We prove that for densities well below the satisfiability threshold, the solution space decomposes into an exponential number of connected components and give quantitative bounds for the diameter, volume, and number.© 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 251–268, 2011     

Spatial and time decomposition algorithms for dynamic nonlinear network optimization using duality

The structural and computational aspects of two decomposition algorithms suitable for dynamic optimization of nonlinear interconnected networks are examined. Both methods arise from a decomposition based on Lagrangian duality theory of the addressed dynamic optimization problem, which is the minimization of energy costs over a given time period, subject to the requirement that the network equations and inequality restrictions are satisfied. The first algorithm uses a spatial decomposition of the state space into subgroups of state variables associated with particular network zones. This leads to a number of lower-dimensional optimization problems which can be solved individually at one level and coordinated at a higher level to account for interactions between these zones. The second algorithm uses time decomposition to solve a sequence of static optimization problems, one for each time increment into which the interval is subdivided, which are then coordinated to take account of dynamic interaction between the time increments. Computational results from an actual network in the United Kingdom are presented for both methods.     

A least squares identification algorithm for a state space model with multi-state delays

A parameter estimator is presented for a state space model with time delay based on the given input–output data. The basic idea is to expand the state equations and to eliminate some state variables, and to substitute the state equation into the output equation to obtain the identification model which contains the information vector and parameter vector. A least squares algorithm is developed to estimate the system parameter vectors. Finally, an illustrative example is provided to verify the effectiveness of the proposed algorithm.     

Delay-dependent robust exponential state estimation of Markovian jumping fuzzy Hopfield neural networks with mixed random time-varying delays

This paper investigates delay-dependent robust exponential state estimation of Markovian jumping fuzzy neural networks with mixed random time-varying delay. In this paper, the Takagi–Sugeno (T–S) fuzzy model representation is extended to the robust exponential state estimation of Markovian jumping Hopfield neural networks with mixed random time-varying delays. Moreover probabilistic delay satisfies a certain probability-distribution. By introducing a stochastic variable with a Bernoulli distribution, the neural networks with random time delays is transformed into one with deterministic delays and stochastic parameters. The main purpose is to estimate the neuron states, through available output measurements such that for all admissible time delays, the dynamics of the estimation error is globally exponentially stable in the mean square. Based on the Lyapunov–Krasovskii functional and stochastic analysis approach, several delay-dependent robust state estimators for such T–S fuzzy Markovian jumping Hopfield neural networks can be achieved by solving a linear matrix inequality (LMI), which can be easily facilitated by using some standard numerical packages. The unknown gain matrix is determined by solving a delay-dependent LMI. Finally some numerical examples are provided to demonstrate the effectiveness of the proposed method.     

考虑油膜动态过程的海上溢油应急物资调度优化

针对溢油应急响应中海上油膜所具有的动态特性,综合考虑需求点的时变物资需求、运输网络的不确定性以及物资调度决策与外部决策环境之间的相互作用关系之后,构建了效率目标与成本目标相结合的多目标海上溢油应急物资调度优化模型。根据模型的特点,提出了一种基于鲸鱼算法的求解方法。该算法利用非线性收敛因子克服了算法后期易陷入局部最优的不足,同时还引入小生境共享机制以确保解的多样性。最后,通过仿真案例对模型与算法的有效性与可行性进行了验证。结果表明,该方法可以为决策者提供高质量的决策支持。     

Reliability analysis of non‐repairable systems modeled by dynamic fault trees with priority AND gates

Many real‐life systems are typically involved in sequence‐dependent failure behaviors. Such systems can be modeled by dynamic fault trees (DFTs) with priority AND gates, in which the occurrence of the top events depends on not only combinations of basic events but also their failure sequences. To the author's knowledge, the existing methods for reliability assessment of DFTs with priority AND gates are mainly Markov‐state‐space‐based, inclusion–exclusion‐based, Monte Carlo simulation‐based, or sequential binary decision diagram‐based approaches. Unfortunately, all these methods have their shortcomings. They either suffer the problem of state space explosion or are restricted to exponential components time‐to‐failure distributions or need a long computation time to obtain a solution with a high accuracy. In this article, a novel method based on dynamic binary decision tree (DBDT) is first proposed. To build the DBDT model of a given DFT, we present an adapted format of the traditional Shannon's decomposition theorem. Considering that the chosen variable index has a great effect on the final scale of disjoint calculable cut sequences generated from a built DBDT, which to some extent determines the computational efficiency of the proposed method, some heuristic branching rules are presented. To validate our proposed method, a case study is analyzed. The results indicate that the proposed method is reasonable and efficient. Copyright © 2015 John Wiley & Sons, Ltd.     

Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach

This paper addresses the problem of virtual circuit switching in bounded degree expander graphs. We study the static and dynamic versions of this problem. Our solutions are based on the rapidly mixing properties of random walks on expander graphs. In the static version of the problem an algorithm is required to route a path between each of K pairs of vertices so that no edge is used by more than g paths. A natural approach to this problem is through a multicommodity flow reduction. However, we show that the random walk approach leads to significantly stronger‐results than those recently obtained by Leighton and Rao [Proc. of 9th International Parallel Processing Symposium, 1995] using the multicommodity flow setup. In the dynamic version of the problem connection requests are continuously injected into the network. Once a connection is established it utilizes a path (a virtual circuit) for a certain time until the communication terminates and the path is deleted. Again each edge in the network should not be used by more than g paths at once. The dynamic version is a better model for the practical use of communication networks. Our random walk approach gives a simple and fully distributed solution for this problem. We show that if the injection to the network and the duration of connection are both controlled by Poisson processes then our algorithm achieves a steady state utilization of the network which is similar to the utilization achieved in the static case situation. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 87–109, 1999     

面向不确定需求租户集的云服务智能匹配模型

为了解决云计算环境下由海量租户集和资源集间的不确定性因素引起的高质量云服务获取困难的问题,提出了一种描述动态异构租户集不确定性需求的方法.在此基础上,构建属性权重完全未知情况下的云服务智能匹配模型,排除了租户提交权值造成的偏差.神经网络以属性区间计算的相离度作为输入,服务满意度为输出来动态模拟租户集的不确定需求,运用萤火虫算法求解模型获取最优服务组合.最后,实例验证了神经网络的可靠性以及算法的有效性.实验结果表明,模型能有效获取高质量的云服务组合,优于传统的匹配方法.     

On the maximum small-world subgraph problem

A clique (or a complete subgraph) is a popular model for an “ideal” cluster in a network. However, in many practical applications this notion turns out to be overly restrictive as it requires the existence of all pairwise links within the cluster. Thus, the researchers and practitioners often rely on various clique relaxation ideas for more flexible models of highly connected clusters. In this paper, we propose a new clique relaxation model referred to as a small-world subgraph, which represents a network cluster with “small-world” properties: low average distance and high clustering coefficient. In particular, we demonstrate that the proposed small-world subgraph model has better “cohesiveness” characteristics than other existing clique relaxation models in some worst-case scenarios. The main focus of the paper is on the problem of finding a small-world subgraph of maximum cardinality in a given graph. We describe a mixed integer programming (MIP) formulation of the problem along with several algorithmic enhancements. For solving large-scale instances of the problem we propose a greedy-type heuristic referred to as the iterative depth-first search (IDF) algorithm. Furthermore, we show that the small-world subgraphs identified by the IDF algorithm have an additional property that may be attractive from the practical perspective, namely, 2-connectivity. Finally, we perform extensive computational experiments on real-world and randomly generated networks to demonstrate the performance of the developed computational approaches that also reveal interesting insights about the proposed clique relaxation model.     

A novel hybrid decomposition-ensemble model based on VMD and HGWO for container throughput forecasting

This paper built a hybrid decomposition-ensemble model named VMD-ARIMA-HGWO-SVR for the purpose of improving the stability and accuracy of container throughput prediction. The latest variational mode decomposition (VMD) algorithm is employed to decompose the original series into several modes (components), then ARIMA models are built to forecast the low-frequency components, and the high-frequency components are predicted by SVR models which are optimized with a recently proposed swarm intelligence algorithm called hybridizing grey wolf optimization (HGWO), following this, the prediction results of all modes are ensembled as the final forecasting result. The error analysis and model comparison results show that the VMD is more effective than other decomposition methods such as CEEMD and WD, moreover, adopting ARIMA models for prediction of low-frequency components can yield better results than predicting all components by SVR models. Based on the results of empirical study, the proposed model has good prediction performance on container throughput data, which can be used in practical work to provide reference for the operation and management of ports to improve the overall efficiency and reduce the operation costs.     

Book review

The concept of antagonistic games for classical discrete control problems is applied and new classes of zero-sum dynamic games on networks are formulated and studied. Polynomial-time algorithms for solving max–min paths problem on networks are proposed and their applications (which might occur within certain financial applications) for solving max–min control problems and determining optimal strategies in zero-sum cyclic games are described. In addition max–min control problems with infinite time horizons which lead to cyclic games are studied and polynomial-time algorithm for solving zero value cyclic games is proposed.     

Multivariate sensitivity analysis for dynamic models with both random and random process inputs

Dynamic models with both random and random process inputs are frequently used in engineering. However, sensitivity analysis (SA) for such models is still a challenging problem. This paper, therefore, proposes a new multivariate SA technique to aid the safety design of these models. The new method can decompose the SA of dynamic models into a series of SA of their principle components based on singular value decomposition, which will make the SA of dynamic models much more efficient. It is shown that the effect of both random and random process inputs on the uncertainty of dynamic output can be measured from their effects on both the distributions and directions of the principle components, based on which the individual sensitivities are defined. The generalized sensitivities are then proposed to synthesize the information that is spread between the principal components to assess the influence of each input on the entire uncertainty of dynamic output. The properties of the new sensitivities are derived and an efficient estimation algorithm is proposed based on unscented transformation. Numerical results are discussed with application to a hydrokinetic turbine blade model, where the new method is compared with the existing variance-based method.     

Noncompliant oligopolistic firms and marketable pollution permits: Statics and dynamics

In this paper, we consider the modeling, analysis, and computation of solutions to both static and dynamic models of multiproduct, multipollutant noncompliant oligopolistic firms who engage in a market for pollution permits. In the case of the static model, we utilize variational inequality theory for the formulation of the governing equilibrium conditions as well as the qualitative analysis of the equilibrium pattern, including sensitivity analysis. We then propose a dynamic model, using the theory of projected dynamical systems, whose set of stationary points coincides with the set of solutions to the variational inequality problem. We propose an algorithm, which is a discretization in time of the dynamic adjustment process, and provide convergence results using the stability analysis results that are also provided herein. Finally, we apply the algorithm to several numerical examples to compute the profit-maximized quantities of the oligopolistic firms' products and the quantities of emissions, along with the equilibrium allocation of licenses and their prices, as well as the possible noncompliant overflows and underflows. This is the first time that these methodologies have been utilized in conjunction to study a problem drawn from environmental policy modeling and analysis.     

A semi-analytical direct optimal control solution for strongly excited and dissipative Hamiltonian systems

A semi-analytical direct optimal control solution for strongly excited and dissipative Hamiltonian systems is proposed based on the extended Hamiltonian principle, the Hamilton-Jacobi-Bellman (HJB) equation and its variational integral equation, and the finite time element approximation. The differential extended Hamiltonian equations for structural vibration systems are replaced by the variational integral equation, which can preserve intrinsic system structure. The optimal control law dependent on the value function is determined by the HJB equation so as to satisfy the overall optimality principle. The partial differential equation for the value function is converted into the integral equation with variational weighting. Then the successive solution of optimal control with system state is designed. The two variational integral equations are applied to sequential time elements and transformed into the algebraic equations by using the finite time element approximation. The direct optimal control on each time element is obtained respectively by solving the algebraic equations, which is unconstrained by the system state observed. The proposed control algorithm is applicable to linear and nonlinear systems with the quadratic performance index, and takes into account the effects of external excitations measured on control. Numerical examples are given to illustrate the optimal control effectiveness.     

Auxiliary model based least squares identification method for a state space model with a unit time-delay

This paper considers parameter estimation problems for state space systems with time-delay. By means of the property of the shift operator, the state space systems are transformed into the input–output representations and an auxiliary model identification method is presented to estimate the system parameters. Finally, an example is provided to test the effectiveness of the proposed algorithm.     

Coevolutionary-based Mechanisms for Network Anomaly Detection

The paper presents an approach based on the principles of immune systems applied to the anomaly detection problem. Flexibility and efficiency of the anomaly detection system are achieved by building a model of the network behavior based on the self–nonself space paradigm. Covering both self and nonself spaces by hyperrectangular structures is proposed. The structures corresponding to self-space are built using a training set from this space. The hyperrectangular detectors covering nonself space are created using a niching genetic algorithm. A coevolutionary algorithm is proposed to enhance this process. The results of experiments show a high quality of intrusion detection, which outperform the quality of the recently proposed approach based on a hypersphere representation of the self-space.      

Coupled torsion–bending dynamic analysis of gear-rotor-bearing system with eccentricity fluctuation

This study performs a coupled torsion–bending vibration responses of a gear-rotor-bearing system, which has taken time varying mesh stiffness, nonlinear bearing force and gear eccentricity into account. A 16 DOF nonlinear dynamic model of gear-rotor-rolling bearing transmission system with bending–torsion coupling is established to obtain the dynamic response to the changes of different parameters. Based on the Runge–Kutta numerical method, the dynamics of the system is investigated, which describes torsional and bending vibration properties of the system more comprehensively. The vibration responses of the gear-rotor-bearing system are discussed, and the effects of gear eccentricity and rotational speed on the system are investigated in detail. The results show that gear eccentricity and rotational speed have influences on the meshing state of gear teeth, the vibration amplitudes, the frequency multiplication and random frequency components. When the system is in a lower rotational speed, the eccentricity has greater effects on the vibration response. The proposed model and numerical results provide a useful source of reference for engineers in designing and vibration controlling such systems.     

Variance reduction for Markov chain processes using state space evaluation for control variates

We develop a method for reducing variance in Monte Carlo simulation of Markov chain processes based on extracting accurate control variates from state space evaluation functions. An example is given in the form of a simple combat model, where the net variance reduction (adjusted for additional calculation) is larger than a factor of 80. We also indicate how our algorithm may be applied to discrete event simulations and system dynamic models with discrete random events.