Deterministic network interdiction optimization via an evolutionary approach

This paper introduces an evolutionary optimization approach that can be readily applied to solve deterministic network interdiction problems. The network interdiction problem solved considers the minimization of the maximum flow that can be transmitted between a source node and a sink node for a fixed network design when there is a limited amount of resources available to interdict network links. Furthermore, the model assumes that the nominal capacity of each network link and the cost associated with their interdiction can change from link to link. For this problem, the solution approach developed is based on three steps that use: (1) Monte Carlo simulation, to generate potential network interdiction strategies, (2) Ford-Fulkerson algorithm for maximum s-t flow, to analyze strategies’ maximum source-sink flow and, (3) an evolutionary optimization technique to define, in probabilistic terms, how likely a link is to appear in the final interdiction strategy. Examples for different sizes of networks and network behavior are used throughout the paper to illustrate the approach. In terms of computational effort, the results illustrate that solutions are obtained from a significantly restricted solution search space. Finally, the authors discuss the need for a reliability perspective to network interdiction, so that solutions developed address more realistic scenarios of such problem.     

All-terminal network reliability optimization via probabilistic solution discovery

This paper presents a new algorithm that can be readily applied to solve the all-terminal network reliability allocation problems. The optimization problem solved considers the minimization of the network design cost subject to a known constraint on all-terminal reliability by assuming that the network contains a known number of functionally equivalent components (with different performance specifications) that can be used to provide redundancy. The algorithm is based on two major steps that use a probabilistic solution discovery approach and Monte Carlo simulation to generate the quasi-optimal network designs. Examples for different sizes of all-terminal networks are used throughout the paper to illustrate the approach. The results obtained for the larger networks with unknown optima show that the quality of the solutions generated by the proposed algorithm is significantly higher with respect to other approaches and that these solutions are obtained from restricted solution search space. Although developed for all-terminal reliability optimization, the algorithm can be easily applied in other resource-constrained allocation problems.     

Algorithms for discrete and continuous multicommodity flow network interdiction problems

We consider a network interdiction problem on a multicommodity flow network, in which an attacker disables a set of network arcs in order to minimize the maximum profit that can be obtained from shipping commodities across the network. The attacker is assumed to have some budget for destroying (or “interdicting”) arcs, and each arc is associated with a positive interdiction expense. In this paper, we examine problems in which interdiction must be discrete (i.e., each arc must either be left alone or completely destroyed), and in which interdiction can be continuous (the capacities of arcs may be partially reduced). For the discrete problem, we describe a linearized model for optimizing network interdiction that is similar to previous studies in the field, and compare it to a penalty model that does not require linearization constraints. For the continuous case, we prescribe an optimal partitioning algorithm along with a heuristic procedure for estimating the optimal objective function value. We demonstrate on a set of randomly generated test data that our penalty model for the discrete interdiction problem significantly reduces computational time when compared to that consumed by the linearization model.     

Harmony search optimization algorithm for a novel transportation problem in a consolidation network

This article presents a new harmony search optimization algorithm to solve a novel integer programming model developed for a consolidation network. In this network, a set of vehicles is used to transport goods from suppliers to their corresponding customers via two transportation systems: direct shipment and milk run logistics. The objective of this problem is to minimize the total shipping cost in the network, so it tries to reduce the number of required vehicles using an efficient vehicle routing strategy in the solution approach. Solving several numerical examples confirms that the proposed solution approach based on the harmony search algorithm performs much better than CPLEX in reducing both the shipping cost in the network and computational time requirement, especially for realistic size problem instances.     

Assessing the effectiveness of k-shortest path sets in problems of network interdiction

This paper focuses on the network interdiction problem and integration of a solution methodology based on k-shortest path sets. We design and conduct an experiment using the road network of Northridge, California to assess performance of the k-shortest path approach under varying assumptions which include homogeneous and heterogeneous arc metrics, the use or non-use of pseudo nodes and alternate origin-destination scenarios. We compare the obtained solutions from the k-shortest path set approach to optimal solutions obtained by implementing Benders Decomposition and observe the differences in computation time and the objective gap for all cases of the experimental design. We also introduce a similarity measure based on spatial analysis techniques to compare coverage as a secondary measure of performance. The observed findings support the use of a k-shortest path set approach in situations where computation time prohibits the need to derive an optimal solution. Additionally, we show that the k-shortest path set approach performs better on heterogeneous networks and that only a small number need be used for k to achieve strong interdiction solutions.     

Exact topology discovery algorithm for the capacity and delay constrained loop network

We have developed an exact model and algorithm for the delay-constrained minimum cost loop problem (DC-MCLP) of finding broadcast loops from a source node. While the traditional minimum cost loop problem (MCLP) deals with only the traffic capacity constraint served by a port of source node, the DC-MCLP deals with the mean network delay and traffic capacity constraints simultaneously. The DC-MCLP consists of finding a set of minimum cost loops to link end-user nodes to a source node satisfying the traffic requirements at end-nodes and the required mean delay of the network. In the DC-MCLP, the objective function is to minimise the total link cost. We have formulated the DC-MCLP and proposed an exact algorithm for its solution. The proposed algorithm is composed of two phases: in the first phase, it generates feasible paths to satisfy the traffic capacity constraint; in the second phase it finds the exact loop topology through matching and allocating optimal link capacity to satisfy the mean delay constraint. In addition, we have derived several properties including the memory and time complexity of the proposed algorithm. Performance evaluation shows that the proposed algorithm has good efficiency for networks with less than thirty nodes and light traffic. Our proposed algorithm can be applied to find the broadcast loops for real-time multimedia traffic     

一种结合网络编码的路径代价衡量方法

针对无线路由协议中的路径代价衡量问题,结合网络编码改善无线节点信息互换的思想,提出了一种结合网络编码的路径代价衡量方法--RMNC,其核心思想是利用流量参数反映信息流的网络编码"搭乘"程度和逐节点计算路径的代价.通过将传输流流量参数和路径中节点左右链路信息流流量参数进行运算,获得路径上的各个节点的传输代价;网络中某一条路径的代价等于组成这条路径的节点传输代价之和,通过比较不同路径的逐节点计算代价值,获得最短路径.分析和模拟测试结果表明,RMNC可以有效地获得结合网络编码的最短路径,达到提高传输性能的目的.尽管传输延时有所增加,但可以接受,方法可行.     

Exact algorithm for delay-constrained capacitated minimum spanning tree network

The delay-constrained capacitated minimum spanning tree (DC-CMST) problem of finding several broadcast trees from a source node is discussed. While the traditional CMST problem deals with only the traffic capacity constraint served by a port of the source node, and delay-constrained minimum spanning tree (DCMST) considers only the maximum end-end delay constraint, the DC-CMST problem deals with both the mean network delay and traffic capacity constraints. The DC-CMST problem consists of finding a set of minimum cost spanning trees to link end-nodes to a source node satisfying the traffic requirements at end-nodes and the required mean delay of the network. In the DC-CMST problem, the objective function is to minimise the total link cost. A dynamic programming-based three-phase algorithm that solves the DC-CMST problem is proposed. In the first phase, the algorithm generates feasible solutions to satisfy the traffic capacity constraint. It finds the CMSTs in the second phase, and allocates the optimal link capacities to satisfy the mean delay constraint in the third phase. Performance evaluation shows that the proposed algorithm has good efficiency for any network with less than 30 nodes and light traffic. The proposed algorithm can be applied to any network regardless of its configuration, and used for the topological design of local networks and for efficient routing algorithms capable of constructing least cost broadcast trees.     

Cutset enumeration of network systems with link and node failures

Network reliability analysis has received considerable attention and is thus widely studied to predict and prevent any network failure. However, most of such works presume perfectly reliable nodes. Although a few studies have considered both link and node failures, none of these methods has utilized the minimal paths or cuts, which are considered as fundamental approaches in the network reliability evaluation. An efficient method for deducing the minimal cutsets of a system subject to both link and node failures from the minimal cutsets of the system, which assumes perfect node reliability, is presented. The proposed method does not require re-enumeration of minimal cutsets for the additional consideration of the node failures. For a simple extension of such a method, the proposed approach can be embedded in any exact or approximate algorithm to account for link failures as well as node failures. As a result, the application of this method would be more realistic and valuable in practice for the reliability evaluation of networks with unreliable nodes.     

A TWO-PHASE NETWORK DESIGN HEURISTIC FOR MINIMUM COST WATER DISTRIBUTION SYSTEMS UNDER A RELIABILITY CONSTRAINT

This paper presents a two-phase design and optimization procedure for constructing a pipe network water distribution system having a built-in degree of reliability. The first phase is comprised of an algorithm called TREESEARCH which iteratively constructs a tree pipe network. Starting with a shortest-path based tree, the procedure employs a linear programming subproblem to systematically modify this tree by adding and deleting one link at a time, with the aim of reducing the cost of the network while satisfying the flow continuity, energy balance, and pressure head requirement constraints. The second phase of the algorithm, called REDUNDANCY, is concerned with the issue of reliability. In this phase, the tree network constructed by the algorithm TREESEARCH is augmented through the addition of links so that there are at least two arc-disjoint paths from each source node to every demand node it serves. This augmentation is performed through the use of a set covering problem which recommends the links to be added, and a Hardy-Cross solver for redesigning the perturbed network to ensure feasibility, while attempting to minimize the overall design cost. The two phases are coordinated by applying algorithm REDUNDANCY to several candidate solutions presented by TREESEARCH. Two example problems from the literature, one involving a single source and the other a multiple source network, are solved using the proposed procedure. The solutions obtained have a smaller cost than those previously obtained by other researchers.     

Element substitution algorithm for general two-terminal network reliability analyses

The computation of the reliability of two-terminal networks is a classical reliability problem. For these types of problems, one is interested, from a general perspective, in obtaining the probability that two specific nodes can communicate. This paper presents a holistic algorithm for the analysis of general networks that follow a two-terminal rationale. The algorithm is based on a set replacement approach and an element inheritance strategy that effectively obtains the minimal cut sets associated with a given network. The vast majority of methods available for obtaining two-terminal reliability are generally based on assumptions about the performance of the network. Some methods assume network components can be in one of two states: (i) either completely failed; or (ii) perfectly functioning, others usually assume that nodes are perfectly reliable and thus, these methods have to be complemented or transformed to account for node failure, and the remaining methods assume minimal cut sets can be readily computed in order to analyze more complex network and component behavior. The algorithm presented in this paper significantly differs from previous approaches available in the literature in the sense that it is based on a predecessor matrix and an element substitution technique that allows for the exact computation of minimal cut sets and the immediate inclusion of node failure without any changes to the pseudo-code. Several case networks are used to validate and illustrate the algorithms.     

A probabilistic computational framework for bridge network optimal maintenance scheduling

This paper presents a probabilistic computational framework for the Pareto optimization of the preventive maintenance applications to bridges of a highway transportation network. The bridge characteristics are represented by their uncertain reliability index profiles. The in/out of service states of the bridges are simulated taking into account their correlation structure. Multi-objective Genetic Algorithms have been chosen as numerical tool for the solution of the optimization problem. The design variables of the optimization are the preventive maintenance schedules of all the bridges of the network. The two conflicting objectives are the minimization of the total present maintenance cost and the maximization of the network performance indicator. The final result is the Pareto front of optimal solutions among which the managers should chose, depending on engineering and economical factors. A numerical example illustrates the application of the proposed approach.     

Artificial Intelligence Based Reliable Load Balancing Framework in Software-Defined Networks

Software-defined networking (SDN) plays a critical role in transforming networking from traditional to intelligent networking. The increasing demand for services from cloud users has increased the load on the network. An efficient system must handle various loads and increasing needs representing the relationships and dependence of businesses on automated measurement systems and guarantee the quality of service (QoS). The multiple paths from source to destination give a scope to select an optimal path by maintaining an equilibrium of load using some best algorithms. Moreover, the requests need to be transferred to reliable network elements. To address SDN’s current and future challenges, there is a need to know how artificial intelligence (AI) optimization techniques can efficiently balance the load. This study aims to explore two artificial intelligence optimization techniques, namely Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO), used for load balancing in SDN. Further, we identified that a modification to the existing optimization technique could improve the performance by using a reliable link and node to form the path to reach the target node and improve load balancing. Finally, we propose a conceptual framework for SDN futurology by evaluating node and link reliability, which can balance the load efficiently and improve QoS in SDN.     

Soft computing approach for reliability optimization: State-of-the-art survey

In the broadest sense, reliability is a measure of performance of systems. As systems have grown more complex, the consequences of their unreliable behavior have become severe in terms of cost, effort, lives, etc., and the interest in assessing system reliability and the need for improving the reliability of products and systems have become very important. Most solution methods for reliability optimization assume that systems have redundancy components in series and/or parallel systems and alternative designs are available. Reliability optimization problems concentrate on optimal allocation of redundancy components and optimal selection of alternative designs to meet system requirement. In the past two decades, numerous reliability optimization techniques have been proposed. Generally, these techniques can be classified as linear programming, dynamic programming, integer programming, geometric programming, heuristic method, Lagrangean multiplier method and so on. A Genetic Algorithm (GA), as a soft computing approach, is a powerful tool for solving various reliability optimization problems. In this paper, we briefly survey GA-based approach for various reliability optimization problems, such as reliability optimization of redundant system, reliability optimization with alternative design, reliability optimization with time-dependent reliability, reliability optimization with interval coefficients, bicriteria reliability optimization, and reliability optimization with fuzzy goals. We also introduce the hybrid approaches for combining GA with fuzzy logic, neural network and other conventional search techniques. Finally, we have some experiments with an example of various reliability optimization problems using hybrid GA approach.     

Port-of-entry safety via the reliability optimization of container inspection strategy through an evolutionary approach

Up to now, of all the containers received in USA ports, roughly between 2% and 5% are scrutinized to determine if they could cause some type of danger or contain suspicious goods. Recently, concerns have been raised regarding the type of attack that could happen via container cargo leading to devastating economic, psychological and sociological effects. Overall, this paper is concerned with developing an inspection strategy that minimizes the total cost of inspection while maintaining a user-specified detection rate for “suspicious” containers. In this respect, a general model for describing an inspection strategy is proposed. The strategy is regarded as an (n+1)-echelon decision tree where at each of these echelons, a decision has to be taken, regarding which sensor to be used, if at all. Second, based on the general decision-tree model, this paper presents a minimum cost container inspection strategy that conforms to a pre-specified user detection rate under the assumption that different sensors with different reliability and cost characteristics can be used. To generate an optimal inspection strategy, an evolutionary optimization approach known as probabilistic solution discovery algorithm has been used.     

Reliability of a computer network in case capacity weight varying with arcs, nodes and types of commodity

The computer network can be modeled as a capacitated-flow network. This paper concentrates on a two-commodity capacitated-flow network with three characters: (1) nodes as well as arcs have multiple possible capacities and may fail, (2) each component (arc/node) has both capacity and cost attributes; and (3) the capacity weight varies with arcs, nodes and types of commodity (or named file). We study the possibility that a given quantity of two types of files can be transmitted through this network simultaneously under the budget constraint. Such a possibility is named the system reliability which is a performance index to measure the quality level of supply demand systems such as computer, telecommunication, electric-power transmission and transportation systems. The approach of minimal paths is applied to describe the relationship among flow assignments and capacity vectors. A simple algorithm in terms of minimal paths is proposed to evaluate the system reliability.     

Multi-haul quasi network flow model for vertical alignment optimization

The vertical alignment optimization problem for road design aims to generate a vertical alignment of a new road with a minimum cost, while satisfying safety and design constraints. A new model called multi-haul quasi network flow (MH-QNF) for vertical alignment optimization is presented with the goal of improving the accuracy and reliability of previous mixed integer linear programming models. The performance of the new model is compared with two state-of-the-art models in the field: the complete transportation graph (CTG) and the quasi network flow (QNF) models. The numerical results show that, within a 1% relative error, the proposed model is robust and solves more than 93% of test problems compared to 82% for the CTG and none for the QNF. Moreover, the MH-QNF model solves the problems approximately eight times faster than the CTG model.     

Maximal network reliability for a stochastic power transmission network

Many studies regarded a power transmission network as a binary-state network and constructed it with several arcs and vertices to evaluate network reliability. In practice, the power transmission network should be stochastic because each arc (transmission line) combined with several physical lines is multistate. Network reliability is the probability that the network can transmit d units of electric power from a power plant (source) to a high voltage substation at a specific area (sink). This study focuses on searching for the optimal transmission line assignment to the power transmission network such that network reliability is maximized. A genetic algorithm based method integrating the minimal paths and the Recursive Sum of Disjoint Products is developed to solve this assignment problem. A real power transmission network is adopted to demonstrate the computational efficiency of the proposed method while comparing with the random solution generation approach.