运用网络分析工具解决局域网广播风暴问题

为了解决网络广播风暴引起机房主机访问网站速度慢的问题,使用科来网络分析系统对网络流量、协议、数据包等进行分析,并结合ARP欺骗、ARP扫描、蠕虫、网络路由环路和物理环路的不同表征,逐一排查ARP病毒、蠕虫、网络路由环路三个可能导致广播风暴的原因,最终定位广播风暴是由网络物理环路和交换机配置错误所导致。通过修改交换机配置和网络拓扑的方式避免网络广播风暴,使机房主机访问网站速度恢复正常。     

图的赋权路径矩阵与所有点对最短路径问题

给出了二维元素矩阵的概念,对于赋权图对应的赋权矩阵,定义了二维元素初始赋权路径矩阵和二维元素一般赋权路径矩阵,在通常赋权矩阵“乘法”运算基础上定义了路径“乘法”运算,从而得到了二维元素一般赋权路径矩阵的“乘法”运算,通过其“乘法”运算来求出所有点对的最短距离与对应路径,在得到最短距离的同时也得到对应的路径,结果显示在最终的一般赋权路径矩阵上。该算法易于通过计算机编程实现,对于大规模有向图或无向图,更有优势。     

Solving the Hamiltonian path problem with a light-based computer

In this paper we propose a special computational device which uses light rays for solving the Hamiltonian path problem on a directed graph. The device has a graph-like representation and the light is traversing it by following the routes given by the connections between nodes. In each node the rays are uniquely marked so that they can be easily identified. At the destination node we will search only for particular rays that have passed only once through each node. We show that the proposed device can solve small and medium instances of the problem in reasonable time.     

Using graph coloring in an algebraic compiler

An algebraic compiler allows incremental development of the source program and builds its target image by composing the target images of the program components. In this paper we describe the general structure of an algebraic compiler focusing on compositional code generation. We show that the mathematical model for register management by an algebraic compiler is a graph coloring problem in which an optimally colored graph is obtained by composing optimally colored subgraphs. More precisely, we define the clique-composition of graphs and as the graph obtained by joining all the vertices in a clique in with all the vertices in a clique in and show that optimal register management by an algebraic compiler is achieved by performing clique-composition operations. Thus, an algebraic compiler provides automatically adequate clique separation of the global register management graph. We present a linear-time algorithm that takes as input optimally colored graphs and and constructs an optimal coloring of any clique-composition of and . Motivated by the operation of clique-composition, we define the class of clique-composable graphs as those graphs that can be iteratively built from single vertices using the clique-composition operation. We show that the class of clique-composable graphs coincides with the well-known class of chordal graphs. Received: 11 May 1995 / 30 November 1995     

On-demand chaotic neural network for broadcast scheduling problem

This paper presents a novel approach to optimizing network packet transfer scheme through introducing a new method for on-demand chaotic noise injection strategy for the Broadcast Scheduling Problem (BSP). Packet radio networks have many applications, while finding an optimized scheduling to transmit data is proven to be a NP-hard problem. The objective of the proposed method is to find an optimal time division multiple access (TDMA) frame, based on maximizing the channel utilization. The proposed method benefits from an on-demand noise injection policy, which injects noise based on the status of neuron and its neighborhoods. The method is superior to other Noise Chaotic Neural Networks (NCNN) that suffer from blind injection policy. The experimental result shows that, in most cases, the proposed on-demand noise injection algorithm finds the best solution with minimal average time delay and maximum channel utilization.     

An orthogonal systolic array for the algebraic path problem

This paper is devoted to the design of an orthogonal systolic array ofn(n+1) elementary processors which can solve any instance of the Algebraic Path Problem within only 5n?2 time steps, and is compared with the 7n?2 time steps of the hexagonal systolic array of Rote [8].     

用有向图法解决公式循环依赖问题

用户使用报表系统时,在自定义的公式集合中可能存在公式循环依赖问题,用一种有效的方法发现这一隐藏错误是设计报表系统的一项关键技术。研究了用有向图法解决报表系统中的公式循环依赖问题,提出了报表系统中的公式循环依赖问题;引用有向图和集合论上的关系等概念对公式循环依赖进行了形式定义,证明了公式循环依赖的判定方法;给出了公式依赖关系图的构造算法和用有向图法解决公式循环依赖的算法。     

Construction and algebraic characterizations of a planar four-index transportation problem equivalent to a circularization network flow problem

In this study, a circularization network flow problem with m?+?n?+?2 nodes and (m?+?1)(n?+?1) arcs is described as a planar four-index transportation problem of order 1?×?m?×?n?×?1. Construction and several algebraic characterizations of the planar four-index transportation problem of order 1?×?m?×?n?×?1 are investigated using the generalized inverse and singular value decomposition of its coefficient matrix. The results are compared with some results we obtained on the transportation problem with m sources and n destinations. It is shown that these problems can be solved in terms of eigenvectors of the matrices J _m and J _n , where J _m is a m?×?m matrix whose entries are 1.     

Solving algebraic equations on a microcomputer

Equation-solving programs for microcomputers make the numerical solution of algebraic equations an easy task. It is no longer necessary to learn or to program algorithms for the solution of many different types of equations. A single equation or a set of simultaneous equations may simply be entered into the computer and numerically solved for unknowns without concern as to whether the equations are linear or non-linear. Several examples of possible applications of equation-solving programs are discussed. Solution times for these examples are given for SEQS on the Apple II and Macintosh computers. The example sets of equations, which include chemical equilibrium and enzyme kinetics problems, have been chosen to demonstrate important aspects of the uses and limitations of equation solving. The four examples discussed are: a two-compartment pharmacokinetic model, citric acid ionization in aqueous solution, an enzyme inhibition model, and an example of the application of an equation-solving program in doing a simple non-linear regression problem.     

改进蚁群算法求解最短路径问题

针对蚁群算法在求解最短路径问题时存在容易陷入局部最优解的问题,对经典蚁群算法提出三方面改进。首先,在初始化信息素浓度时加入方向引导,加快初始搜索速度;其次,在局部信息素浓度更新过程中采用信息素重分配思想,避免由路径信息素衰减过程导致的最优路径信息素浓度过分减少;最后,在全局信息素更新过程中引入动态因子,使其自适应地更新较优路径信息素浓度,以提高全局搜索能力。仿真实验结果表明,该改进算法可以保证收敛速度,并提高算法搜索到最优路径的几率。     

Solving the hazmat transport network design problem

In this paper, we consider the problem of network design for hazardous material transportation where the government designates a network, and the carriers choose the routes on the network. We model the problem as a bilevel network flow formulation and analyze the bilevel design problem by comparing it to three other decision scenarios. The bilevel model is difficult to solve and may be ill-posed. We propose a heuristic solution method that always finds a stable solution. The heuristic exploits the network flow structure at both levels to overcome the difficulty and instability of the bilevel integer programming model. Testing on real data shows that the linearization of the bilevel model fails to find stable solutions and that the heuristic finds lower risk networks in less time. Further testing on random instances shows that the heuristically designed networks achieve significant risk reduction over single-level models. The risk is very close to the least risk possible. However, this reduction in risk comes with a significant increase in cost. We extend the bilevel model to account for the cost/risk trade-off by including cost in the first-level objective. The biobjective–bilevel model is a rich decision-support tool that allows for the generation of many good solutions to the design problem.     

Solving bi-objective flow shop problem with hybrid path relinking algorithm

This paper presents and investigates different ways to integrate path relinking techniques into the hypervolume-based multi-objective local search algorithm (HBMOLS). We aim to evaluate the effectiveness of different path relinking strategies, these strategies focus on two main steps: the ways of path generation and the mechanisms of solutions selection. We propose different methods to establish the path relinking algorithms in a multi-objective context. Computational results on a bi-objective flow shop problem (FSP) and a statistical comparison are reported in the paper. In comparison with two versions of HBMOLS, the algorithms selecting a set of solutions located in the middle of the generated path are efficient. The behavior of these algorithms sheds light on ways to further improvements.     

Solving a new bi-objective location-routing-inventory problem in a distribution network by meta-heuristics

This paper presents a novel bi-objective location-routing-inventory (LRI) model that considers a multi-period and multi-product system. The model considers the probabilistic travelling time among customers. This model also considers stochastic demands representing the customers’ requirement. Location and inventory-routing decisions are made in strategic and tactical levels, respectively. The customers’ uncertain demand follows a normal distribution. Each vehicle can carry all kind of products to meet the customer’s demand, and each distribution center holds a certain amount of safety stock. In addition, shortage is not allowed. The considered two objectives aim to minimize the total cost and the maximum mean time for delivering commodities to customers. Because of NP-hardness of the given problem, we apply four multi-objective meta-heuristic algorithms, namely multi-objective imperialist competitive algorithm (MOICA), multi-objective parallel simulated annealing (MOPSA), non-dominated sorting genetic algorithm II (NSGA-II) and Pareto archived evolution strategy (PAES). A comparative study of the forgoing algorithms demonstrates the effectiveness of the proposed MOICA with respect to four existing performance measures for numerous test problems.     

Further results on the algebraic characterizations of a minimum cost network flow problem equivalent to the transportation problem

In this study a minimum cost network flow problem with m+n+2 nodes and mn arcs, which is equivalent to the transportation problem with m sources and n destinations, is described as an axial four-index transportation problem of order 1×m×n×1. Several algebraic characterizations of this problem of order 1×m×n×1 are investigated using the singular value decomposition and generalized inverses of its coefficient matrix. The results are compared with some results on the planar four-index transportation problem. It is shown that these problems have common algebraic characterizations and can be solved in terms of eigenvectors of the matrices J _m and J _n where J _m is an m×m matrix, all of whose entries are 1.     

随机化均匀设计混合遗传算法求解图的二划分问题

图的二划分问题是一个典型的NP—hard组合优化问题,在许多领域都有重要应用．近年来,传统遗传算法等各种智能优化方法被引入到该问题的求解中来,但效果不理想．基于理想浓度模型的机理分析,利用随机化均匀设计抽样的理论和方法,对遗传算法中的交叉操作进行了重新设计,并在分析图的二划分问题特点的基础上,结合局部搜索策略,给出了一个解决图的二划分问题的新的遗传算法．通过将该算法与简单遗传算法和佳点集遗传算法进行求解图的二划分问题的仿真模拟比较,可以看出新的算法提高了求解的质量、速度和精度．     

On open shortest path first related network optimisation problems

The paper deals with flow allocation problems in IP networks using open shortest path first (OSPF) routing. Its main purpose is to discuss and propose methods for finding settlements of OSPF link weight system realising the assumed demand pattern for the given network resources (links capacities). Such settlements can result in a significantly better network performance, as compared with the simplified weight setting heuristics typically used nowadays. Although the configuration of the link weight system is primarily done in the network planning phase, still additional re-optimisations are feasible, and in fact essential, in order to cope with major changes in traffic conditions and with major resources’ failures and rearrangements.

The paper formulates a relevant OSPF routing optimisation problem, proves its NP-completeness, and discusses possible heuristic approaches and related optimisation methods for solving it. Two basic approaches are considered (the direct approach and the two-phase approach) and the resulting optimisation algorithms are presented. The considerations are illustrated with numerical results.     

The matrix partial realization problem: an algebraic approach

This paper introduces a new approach to the multivariable partial realization problem. It formulates the problem in algebraic terminology, which sheds new light on the nature of the problem and our existing knowledge of it. The structure of the state space is analysed in terms of polynomial models. The main idea is analysis of the algebraic structure of the kernels of truncated Hankel maps. The elements of such kernels are directly related to the partial realization problem, in the sense that the columns of the denominator matrix of a partial realization are elements of such kernels. The numerator matrix is determined by an appropriate denominator matrix     

On approximating the longest path in a graph

We consider the problem of approximating the longest path in undirected graphs. In an attempt to pin down the best achievable performance ratio of an approximation algorithm for this problem, we present both positive and negative results. First, a simple greedy algorithm is shown to find long paths in dense graphs. We then consider the problem of finding paths in graphs that are guaranteed to have extremely long paths. We devise an algorithm that finds paths of a logarithmic length in Hamiltonian graphs. This algorithm works for a much larger class of graphs (weakly Hamiltonian), where the result is the best possible. Since the hard case appears to be that of sparse graphs, we also consider sparse random graphs. Here we show that a relatively long path can be obtained, thereby partially answering an open problem of Broderet al. To explain the difficulty of obtaining better approximations, we also prove hardness results. We show that, for any ε<1, the problem of finding a path of lengthn-n ^ε in ann-vertex Hamiltonian graph isNP-hard. We then show that no polynomial-time algorithm can find a constant factor approximation to the longest-path problem unlessP=NP. We conjecture that the result can be strengthened to say that, for some constant δ>0, finding an approximation of ration ^δ is alsoNP-hard. As evidence toward this conjecture, we show that if any polynomial-time algorithm can approximate the longest path to a ratio of , for any ε>0, thenNP has a quasi-polynomial deterministic time simulation. The hardness results apply even to the special case where the input consists of bounded degree graphs. D. Karger was supported by an NSF Graduate Fellowship, NSF Grant CCR-9010517, and grants from the Mitsubishi Corporation and OTL. R. Motwani was supported by an Alfred P. Sloan Research Fellowship, an IBM Faculty Development Award, grants from Mitsubishi and OTL, NSF Grant CCR-9010517, and NSF Young Investigator Award CCR-9357849, with matching funds from IBM, the Schlumberger Foundation, the Shell Foundation, and the Xerox Corporation, G. D. S. Ramkumar was supported by a grant from the Toshiba Corporation. Communicated by M. X. Goemans.     

Solving a furnace loading problem

This paper presents a heuristic solution procedure for the furnace loading problem in metallurgical industry. The problem is decomposed into two stages: ingot order selection and candidate ingot loading. The 2-stage problems are then iteratively solved. It is shown that practical sized problems can be efficiently solved using the proposed approach.