最小费用最大流问题的一种新算法

现有的最小费用最大流算法都有自身的缺陷,增广链的选取不当会给计算带来不便,同时费用也达不到理想的效果。鉴于对最小费用最大流算法的增广链选取和最小费用的探索,文章通过对费用差的定义给出了一种求最小费用最大流的新算法。新算法的原则是优先选择费用差最小的有向路径进行增广,当费用差相同时就选择修正后的路径。通过对最小费用最大流算法的改进,新算法易理解且便于计算。通过实例说明了新算法的有效性和执行效率。     

网络最大流问题研究进展

网络最大流问题和它的对偶问题——最小截问题,是一对经典组合优化问题,它们在许多工程领域和科学领域有重要的应用,是计算机科学和运筹学重要的内容,最大流问题已经有40多年的研究历史,近年来,随着各种网络的飞速发展,最大流问题的研究也取得了很大的进展,对最大流问题研究做了详细的总结,并对下一步研究趋势进行了预测。     

一种求解最小割集问题的新思路

从本质上来说,最小割集问题与最大流问题是同一个问题。由于后者的实用性更强,人们对它投入的关注与研究也更多,因而实际中是通过最大流问题来求最小割集问题。最大流-最小割集定理给出了一种用最大流算法求最小割集问题的方法,但在实际应用中,这种方法有时显得繁冗并有些迂回。文章首先介绍了最大流、最小割集的相关概念,然后从实际应用出发提出了一种用最大流求流图最小割集的新算法。随后证明了该算法的正确性,并举例说明了这种算法思想在其它方面的应用。     

网络最大流求解算法的研究

近年来,随着各种网络的飞速发展,对最大流问题的研究也取得了很大的进展。文章简述了网络最大流问题的现状,提出了一种求解网络最大流与最小截问题的算法。此算法使得计算网络最大流变得简便,且具有很强的实用性。     

无回路网络中的最小费用流算法

针对无回路网络的特殊性,利用广探法的思想,提出了无回路网络最短路的有效算法,并在此基础之上提出了最小费用流的有效算法.其算法的复杂性分别为o(m)和o(mvo),相比拓扑排序法和最小费用路算法,本文提出的算法更为简练、易懂且复杂性低.     

An exterior simplex type algorithm for the Minimum Cost Network Flow Problem

In this paper a new Network Exterior Point Simplex Algorithm (NEPSA) for the Minimum Cost Network Flow Problem (MCNFP) is analytically presented. NEPSA belongs to a special simplex type category and is a modification of the classical network simplex algorithm. The main idea of the algorithm is to compute two flows. One flow is basic but not always feasible and the other is feasible but not always basic. A complete proof of correctness for the proposed algorithm is also presented. Moreover, the computational behavior of NEPSA is shown by an empirical study carried out for randomly generated sparse instances created by the well-known GRIDGEN network problem generator.     

A Minimum Cut Interference-based Integrated RWA Algorithm for Multi-constrained Optical Transport Networks

Advances in optical technologies have enabled the deployment of wavelength division-multiplexed (WDM) transmission systems capable of providing huge amounts of bandwidth across long distances. In this scenario, dynamic routing for direct provisioning of optical paths at the WDM layer becomes a challenging problem. Any distributed algorithm for routing dynamic traffic demands on optical transport infrastructures should be simple, flexible, efficient and scalable. The contribution of this paper is a novel integrated routing and grooming scheme for setting-up bandwidth guaranteed paths on hybrid wavelength and label switched networks. Our proposal exploits and refines the minimum interference routing idea according to an improved and re-optimized resource and traffic-aware approach, where critical links are detected and weighted according to a low complexity all-pairs minimum cut strategy that substantially reduce the overall number of calculations and hence the computational cost. The valuable results achieved in the comparison against other well-known reference techniques clearly demonstrate that our algorithm is very time-efficient while performing better in terms of blocking probability.

A Divide-and-Conquer Approach to the Minimum k -Way Cut Problem

Abstract. This paper presents algorithms for computing a minimum 3 -way cut and a minimum 4 -way cut of an undirected weighted graph G . Let G=(V, E) be an undirected graph with n vertices, m edges, and positive edge weights. Goldschmidt and Hochbaum presented an algorithm for the minimum k -way cut problem with fixed k , that requires O(n ⁴ ) and O(n ⁶ ) maximum flow computations, respectively, to compute a minimum 3 -way cut and a minimum 4 -way cut of G . In this paper we first show some properties on minimum 3 -way cuts and minimum 4 -way cuts, which indicate a recursive structure of the minimum k -way cut problem when k = 3 and 4 . Then, based on those properties, we give divide-and-conquer algorithms for computing a minimum 3 -way cut and a minimum 4 -way cut of G , which require O(n ³ ) and O(n ⁴ ) maximum flow computations, respectively.     

求解SAT问题的线性半定规划算法

将线性半定规划应用到SAT问题的求解过程中。首先将SAT实例转化为整数规划问题,然后松弛为线性规划模型,最后再转化为一般的线性半定规划模型去求解。用SDPA-M软件求解线性半定规划问题后,规定了如何根据目标函数值去判定SAT实例和当CNF公式可满足时如何根据最优指派的概率X^＊i（i=1,…,n）去进行变元赋值,以期求得该公式的可满足指派。上述算法不仅可以判定SAT问题,而且对于符合算法规定可满足的CNF公式皆可给出一个可满足指派。求解SAT问题的线性半定规划算法在文章中被描述并被给予相应算例。     

一种新的求解度约束最小生成树的遗传算法

染色体编码是遗传算法的关键内容,编码的优劣并直接影响算法的性能.提出了基于过程控制的生成树编码方法--PC编码.PC码为定长的整数向量,使用PC编码求解特定生成树问题时,首先选定的一个有效算法,并将修改为可控算法,然后用编码向量控制算法的运行过程,从面得到唯一生成树.为了求解度约束最小生成树(DCMST)问题,在D-Prim算法的基础上,设计r过程可控的度约束生成树构造PC-Prim算法.给出了以PC-Prim算法作为译码器的求解DC-MST问题的遗传算法.仿真结果表明遗传算法求解精度和运行时间均优于参与其他算法.     

A Network Flow Algorithm for Reconstructing Binary Images from Continuous X-rays

Tomography is a powerful technique to obtain accurate images of the interior of an object in a nondestructive way. Conventional reconstruction algorithms, such as filtered backprojection, require many projections to obtain high quality reconstructions. If the object of interest is known in advance to consist of only a few different materials, corresponding to known image intensities, the use of this prior knowledge in the reconstruction procedure can dramatically reduce the number of required projections. In previous work we proposed a network flow algorithm for reconstructing a binary image defined on a lattice from its projections. In this paper we propose a new algorithm for the reconstruction of binary images that do not have an intrinsic lattice structure and are defined on a continuous domain, from a small number of their projections. Our algorithm relies on the fact that the problem of reconstructing an image from only two projections can be formulated as a network flow problem in a graph. We derive this formulation for parallel beam and fan beam tomography and show how it can be used to compute binary reconstructions from more than two projections. Our algorithm is capable of computing high quality reconstructions from very few projections. We evaluate its performance on both simulated and real experimental projection data and compare it to other reconstruction algorithms.

求解度约束最小生成树的新的遗传算法

针对度约束最小生成树问题的特征,设计了一种新的编码方式,并在此基础上提出了一个新遗传算法来求解该问题。该算法采用新的启发式杂交算子、变异算子和局部搜索算子,以概率1收敛到全局最优解。数值实验表明该算法优于文中提出的其他4种算法。     

带有时间和费用双重限制的网络容量扩充问题

该文将网络容量定义为最大s-t流的流量,建立了带有时间和费用双重限制下的网络容量扩充问题的一般模型。通过网络变换,将带有时间限制的容量扩充问题转化为线性最小费用流问题,并给出了具体证明和求解容量扩充问题的算法。该模型和算法不仅适用于各种情形的容量扩充问题,而且还可应用于网络流规划。最后通过具体例子的求解,说明了模型和算法的正确性和有效性。     

网络最大流问题的改进算法

网络最大流问题是图论中的经典问题之一,对于最大流问题有很多经典的算法,但这些经典算法皆有不足之处。针对其不足,文中通过引入容量差的概念,对算法进行了一些改进。改进算法的原则是优先选择路径最短且容量差最大的路径进行增广,若当路径长度一样并且容量差也一样时就要对其修正,然后选择修正后的路径,这样每次增广至少使一条弧达到饱和。通过实例说明了改进算法的可行性,整个运算过程可以在一个图上完成,直观性强并且方便计算,较传统算法更为有效。     

A Neural Network for Solving Nonlinear Programming Problems

A neural network for solving convex nonlinear programming problems is proposed in this paper. The distinguishing features of the proposed network are that the primal and dual problems can be solved simultaneously, all necessary and sufficient optimality conditions are incorporated, and no penalty parameter is involved. Based on Lyapunov, LaSalle and set stability theories, we prove strictly an important theoretical result that, for an arbitrary initial point, the trajectory of the proposed network does converge to the set of its equilibrium points, regardless of whether a convex nonlinear programming problem has unique or infinitely many optimal solutions. Numerical simulation results also show that the proposed network is feasible and efficient. In addition, a general method for transforming non-linear programming problems into unconstrained problems is also proposed. ID="A1" Correspondence and offprint requests to: Dr Z Chen, Department of Electronic Engineering, Brunel University, Uxbridge, Middle-sex, UK     

最小生成树的高效异步并行算法

在ＭＩＭＤ－ＳＭ并行计算模型上，本文给出了时间复杂性为Ｏ（ｎ（ｎ／ｐ＋ｌｏｇｐ））的最小生成树的异步并行算法，其中ｎ，ｐ（１≤ｐ≤ｎ）分别表示图的顶点数和处理机的个数。     

一类非线性整数规划问题的计算机求解

文章针对一类具有特殊性质的非线性整数规划问题,提出了一种具有剔除选择的计算机求解的方法。该求解方法的提出,对解决现实生活中这一类非线性整数规划问题,提供了一种切实可行的途径,这为此类问题的决策提供了有效的手段。     

一种优化非线性目标的QoS路由算法

基于多条件约束的QoS路由选择是当前通信网络中的一个重要问题，其基本目的是求解多约束条件下的参数优化问题．文献[3]通过引入系统丢失率及平均时延的性能指标，建立了一个在满足一定系统丢失率要求下求系统最小平均时延的QoS路由选择算法．本文研究在满足一定的系统平均时延要求下求系统最小丢失率的QoS路由选择，建立了一种整数规划模型，并根据模型特点给出了用线性整数规划逐次迭代逼近求精确解的算法．实例表明所提出的模型和算法是有效的．     

非线性整数规划的粒子群优化算法

提出了一种新的粒子群优化算法来求解无约束的整数规划问题，粒子在[0，1]空间内运动，并与整数空间对应。对粒子群优化算法参数的合理选取进行了实验分析，给出了算法参数选取的基本原则。数值试验计算结果表明该方法比较有效，并具有通用性。