The conjugate gradient technique for certain quadratic network problems

We consider a class of network flow problems with pure quadratic costs and demonstrate that the conjugate gradient technique is highly effective for large-scale versions. It is shown that finding a saddle point for the Lagrangian of an m constraint, n variable network problem requires only the solution of an unconstrained quadratic programming problem with only m variables. It is demonstrated that the number of iterations for the conjugate gradient algorithm is substantially smaller than the number of variables or constraints in the (primal) network problem. Forty quadratic minimum-cost flow problems of various sizes up to 100 nodes are solved. Solution time for the largest problems (4,950 variables and 99 linear constraints) averaged 4 seconds on the CBC Cyber 70 Model 72 computer.     

Time minimizing flows in directed networks

An important class of network flow problems is that class for which the objective is to minimize the cost of the most expensive unit of flow while obtaining a desired total flow through the network. Two special cases of this problem have been solved, namely, the bottleneck assignment problem and time-minimizing transportation problem. This paper addresses the more general case which we shall refer to as the time-minimizing network flow problem. Associated with each arc is an arc capacity (static) and a transferral time. The objective is to find a maximal flow for which the length (in time) of the longest path carrying flow is minimized. The character of the problem is discussed and a solution algorithm is presented.     

Optimal multicommodity network flows with resource allocation

The problem of determining multicommodity flows over a capacitated network subject to resource constraints may be solved by linear programming; however, the number of potential vectors in most applications is such that the standard arc-chain formulation becomes impractical. This paper describes an approach—an extension of the column generation technique used in the multicommodity network flow problem—that simultaneously considers network chain selection and resource allocation, thus making the problem both manageable and optimal. The flow attained is constrained by resource availability and network capacity. A minimum-cost formulation is described and an extension to permit the substitution of resources is developed. Computational experience with the model is discussed.     

Optimization of strategic defenses to provide specified post-attack production capacities

This paper presents a model for choosing a minimum-cost mix of strategic defenses to assure that specified production capacities for several economic sectors survive after a nuclear attack. The defender selects a mix of strategic defenses for each of several geographic regions. The attacker chooses an allocation of attacking weapons to geographic regions, within specified weapon inventories. The attack is optimized against any economic sector. This formulation allows the defense planner the capability to assess the results of the optimal defense structure for a “worst case” attack. The model is a mathematical program with nonlinear programming problems in the constraints; an example of its application is given and is solved using recently developed optimization techniques.     

Multi‐period maintenance scheduling of tree networks with minimum flow disruption

We introduce a multi‐period tree network maintenance scheduling model and investigate the effect of maintenance capacity restrictions on traffic/information flow interruptions. Network maintenance refers to activities that are performed to keep a network operational. For linear networks with uniform flow between every pair of nodes, we devise a polynomial‐time combinatorial algorithm that minimizes flow disruption. The spiral structure of the optimal maintenance schedule sheds insights into general network maintenance scheduling. The maintenance problem on linear networks with a general flow structure is strongly NP‐hard. We formulate this problem as a linear integer program, derive strong valid inequalities, and conduct a polyhedral study of the formulation. Polyhedral analysis shows that the relaxation of our linear network formulation is tight when capacities and flows are uniform. The linear network formulation is then extended to an integer program for solving the tree network maintenance scheduling problem. Preliminary computations indicate that the strengthened formulations can solve reasonably sized problems on tree networks and that the intuitions gained from the uniform flow case continue to hold in general settings. Finally, we extend the approach to directed networks and to maintenance of network nodes. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

一类有增益网络的最大流模型

一般带容量限制的网络图中流出源点与流入汇点的流量相等,但在实际应用中,存在一类流量经过弧发生变化的网络,使得流出源点与流入汇点的流量不相等。针对此类问题,建立了增益网络最大流模型,并通过增设虚弧将增益网络转换成循环网络,利用循环网络中汇点流量瞬间平衡的优点简化了模型。最后,结合实例进行分析,编写程序对实例进行了计算,计算结果验证了该模型的有效性。     

The simplex method for integral multicommodity networks

The simplex method is interpreted as a labeling procedure for certain classes of multicommodity flow problems in a manner similar to that for single commodity networks. As opposed to general multicommodity algorithms, no explicit matrix inversion is required; all simplex operations are performed graph-theoretically.     

Use of dimensionless ratios to determine minimum-cost inventory quantities

The iteration usually necessary for simultaneous determination of minimum-cost order quantity and reorder point in (Q, r) inventory systems may be eliminated by a graphical technique employing dimensionless ratios. This technique is illustrated for three different types of stock-out penalty.     

Single‐commodity stochastic network design under demand and topological uncertainties with insufficient data

Stochastic network design is fundamental to transportation and logistic problems in practice, yet faces new modeling and computational challenges resulted from heterogeneous sources of uncertainties and their unknown distributions given limited data. In this article, we design arcs in a network to optimize the cost of single‐commodity flows under random demand and arc disruptions. We minimize the network design cost plus cost associated with network performance under uncertainty evaluated by two schemes. The first scheme restricts demand and arc capacities in budgeted uncertainty sets and minimizes the worst‐case cost of supply generation and network flows for any possible realizations. The second scheme generates a finite set of samples from statistical information (e.g., moments) of data and minimizes the expected cost of supplies and flows, for which we bound the worst‐case cost using budgeted uncertainty sets. We develop cutting‐plane algorithms for solving the mixed‐integer nonlinear programming reformulations of the problem under the two schemes. We compare the computational efficacy of different approaches and analyze the results by testing diverse instances of random and real‐world networks. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 154–173, 2017     

直流TIG焊接电弧的数值分析

以直流钨极氢弧焊电弧为研究对象,考虑阴极几何形状,建立了轴对称电弧数值计算模型,在电流密度计算中包括了阴极区和弧柱区。采用ＳＩＭＰＬＥ算法求解磁流体动力学方程组。所得电弧弧柱温度分布与实验结果相吻合;电弧速度分布、电磁力分布、电流密度分布、压力分布等电弧参量的计算结果能较全面地反映电弧内部的作用机制。     

A multifacility capacity expansion model with joint expansion set-up costs

This article describes a multifacility capacity expansion model in which the different facility types represent different quality levels. These facility types are used to satisfy a variety of deterministic demands over a finite number of discrete time periods. Applications for the model can be found in cable sizing problems associated with the planning of communication networks. It is assumed that the cost function associated with expanding the capacity of any facility type is concave, and that a joint set-up cost is incurred in any period in which one or more facilities are expanded. The model is formulated as a network flow problem from which properties associated with optimal solutions are derived. Using these properties, we develop a dynamic programming algorithm that finds optimal solutions for problems with a few facilities, and a heuristic algorithm that finds near-optimal solutions for larger problems. Numerical examples for both algorithms are discussed.     

码资源受限系统中的碎片整理算法及定时机制的研究

在分析传统码资源静态分配算法缺陷的基础上,研究了直接合并碎片整理算法和最小分支搜索不完全码碎片整理算法.同时研究了碎片整理算法中的关键问题:碎片整理的时机,即定时机制问题.提出了一种获取定时参数的方法,并利用计算机仿真工具对定时机制进行了仿真,验证了理论结论.     

Optimal interdiction of a supply network

Under certain conditions, the re-supply capability of a combatant force may be limited by the characteristics of the transportation network over which supplies must flow. Interdiction by an opposing force may be used to reduce the capacity of that network. The effects of such efforts vary for differing missions and targets. With only a limited total budget available, the interdictor must decide which targets to hit, and with how much effort. An algorithm is presented for determining the optimum interdiction plan for minimizing network flow capacity when the minimum capacity on an arc is positive and the cost of interdiction is a linear function of arc capacity reduction.     

电弧喷涂技术在防腐工程中的应用及进展

介绍了电弧喷涂技术的原理、特点及进展,特别是电弧喷涂技术在防腐工程领域的应用指出电弧喷涂技术,特别是高速电弧喷涂技术是21世纪表面工程中的重点发展方向。     

化学激光器环形与线形分流管道对比的数值分析

环柱型化学激光器中使用的分流管道的总管为环形弯曲管道,支管分布在内侧圆弧或外侧圆弧上,结构与线形分流管道有较大差别。应用计算流体力学方法,对上述各分流管道进行了三维的数值模拟及对比分析。结果表明,线形分流管道总管内的总压高于支管分布在外侧圆弧上的环形管道,但低于支管分布在内侧圆弧上的环形管道;无论是支管分流,抑或环形管道内的二次流现象都会使总管截面上产生径向速度,使得流体流动呈现明显的三维特征;分流管道各支管流量沿主流流动方向基本上是上升的,这与总管的总压分布趋势相反,而与总管的静压分布趋势相似;比较而言,支管分布在外侧圆弧上的环形分流管道的支管流量波动幅度最小,在均匀分配气流方面最具优势,线形分流管道居中,支管分布在内侧圆弧上的环形分流管道最差。     

Modeling and simulation of muzzle flow field of railgun with metal vapor and arc

During the electromagnetic railgun launching process, there will be a complex flow field with high temperature in the muzzle area because of the high-speed friction, transition and secondary arc-ignition. This paper models the muzzle area of railgun when the projectile is far away from the muzzle, and the dynamic simulation of the flow field with secondary arc in the muzzle area is carried out based on the magneto hydrodynamic equations. Meanwhile, a multi-component plasma transport model is used to analyze the muzzle arc plasma flow process of the mixed gas of Al vapor and the air. Furthermore, the pressure boundary conditions are fitted by the dynamic mesh simulation results. The current and voltage of the muzzle are obtained through the emission experiment of the railgun experimental prototype. We load the current data into the simulation model and the voltage of experiments and simulations are compared, which proves the accuracy of the simulation. Then the plasma temperature and the composition of Al vapor in the muzzle flow process are analyzed in-depth.     

Algorithm to solve a chance‐constrained network capacity design problem with stochastic demands and finite support

We consider the problem of determining the capacity to assign to each arc in a given network, subject to uncertainty in the supply and/or demand of each node. This design problem underlies many real‐world applications, such as the design of power transmission and telecommunications networks. We first consider the case where a set of supply/demand scenarios are provided, and we must determine the minimum‐cost set of arc capacities such that a feasible flow exists for each scenario. We briefly review existing theoretical approaches to solving this problem and explore implementation strategies to reduce run times. With this as a foundation, our primary focus is on a chance‐constrained version of the problem in which α% of the scenarios must be feasible under the chosen capacity, where α is a user‐defined parameter and the specific scenarios to be satisfied are not predetermined. We describe an algorithm which utilizes a separation routine for identifying violated cut‐sets which can solve the problem to optimality, and we present computational results. We also present a novel greedy algorithm, our primary contribution, which can be used to solve for a high quality heuristic solution. We present computational analysis to evaluate the performance of our proposed approaches. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 236–246, 2016     

基于自由边控制流图的路径覆盖分析实现方法

针对路径覆盖测试,给出了一般循环结构的一种简化处理方案及把按此方案得到的控制流图转化为自由边控制流图方法,并探讨了基于自由边控制流图进行路径覆盖分析的实现方法和优点。     

基于复杂网络的作战描述模型研究*

针对传统作战模型重点关注兵力的毁伤,不能充分地反映信息时代作战的特点,提出了一个基于复杂网络的作战描述模型,把作战单元抽象成节点,把各单元之间的相互作用抽象成有向边,将战场描述为一个由传感器、决策器、影响器、目标四类节点组成的有向网络图。定义了网络模型的若干特征参数,把作战环看成是反映作战能力的指标,并区别分析了标准作战环和广义作战环,能更好地反映信息时代作战的特点。最后实例研究了传统作战条件下决策器连通程度的变化给作战能力带来的影响。     

Min/max bounds for dynamic network flows

This paper presents an algorithm for determining the upper and lower bounds for arc flows in a maximal dynamic flow solution. The procedure is basically an extended application of the Ford-Fulkerson dynamic flow algorithm which also solves the minimal cost flow problem. A simple example is included. The presence of bounded optimal are flows entertains the notion that one can pick a particular solution which is preferable by secondary criteria.