（计算机软件与理论专业论文）网络优化中的整数规划算法研究.pdf

摘要 v 5 7 8 9 88 网络优化就是研究如何有效地计划、管理和控制整个网络系统，使之产生最大的 社会和经济效益，它是计算机科学和运筹学中的一个经典和重要分支。随着现代社会 网络规模的迅速增大和日趋复杂，如何在各种有着巨大规模的网络问题中以最小的时 间代价找一个最优解或近似最优解具有十分重要的意义。网络优化涉及到的大量实际 问题是极富挑战性的，其中的绝大多数问题属于n p h a r d 问题。本文主要研究求解网 络优化中的整数规划、背包、线性规划等问题的新算法及其高效并行算法。 针对求解线性规划松弛算法在选取松弛变量时存在的不足，提出了线性规划问题 有最优解的一个必要条件，将本必要条件应用于线性规划松弛算法中松弛变量的选取 上，对松弛算法进行了改进。在此基础上，提出了一种基于c l u s t e r 结构的并行松弛 算法，与线性规划同类并行算法对比，本算法具有更好的并行性和求解效率。 最近，有学者提出了一种算法，它适于求解约束个数很多但变量个数较少的线性 规划问题。本文根据其在数据和操作上各个步骤的相关性，将该算法在主从式消息传 递接口环境下并行化，设计了一个求解该类问题的并行算法，理论分析和实验结果表 明本算法具有良好的并行性和可扩展性。 整数规划是离散算法和n p 问题研究中的核心问题之一，如何提高实际应用中大 规模整数规划问题的求解效率具有十分重要的理论和实际意义。利用二分网格作为几 何工具，将传统二分搜索推广应用到整数规划问题的可行域中，提出一种求解整数规 划的新算法。本算法不仅能够克服分枝限界算法和割平面算法求解系数呈指数增长的 整数规划实例时存在的实质性困难，而且其高可并行性可望为一般大规模整数规划的 精确求解提供新的可选方案。将本算法的设计思想用于求解与整数规划有密切关系的 无界背包问题，得到一种求解该问题的新算法。新算法对于固定物品数背包实例的求 解时间仅为问题输入规模上的线性函数，这一结果表明新算法明显改进了动态规划和 分枝限界算法的相关性能。 等式背包问题是背包问题类中一种无目标函数的问题，其求解时间和空间都随物 品个数的增多呈指数形式增长。由于它在数论研究和信息密码学领域中具有极重要的 应用，寻找该问题的高效算法一直是该领域的研究热点。将求解背包问题著名的二表 算法和动态二表算法通过一个大小可变的数据结构统一起来，提出一种改进算法，算 法的最大优点是它的自适应性，即算法中的参数可据问题规模和可用计算资源的大小 i 索努僻当导师弼意 匆垒文公布 加以调整。实验结果证明改进算法将可破解的背包密钥的维数较此前扩大了数倍。 并行计算是解决等式背包问题的有效方法之一。本文深入研究了背包问题并行算 法的研究现状，在指出相关文献一个主要结论错误的基础上，利用分治方法，首次提 出了背包问题基于c r e w 模型的成本最优并行算法。然后，分析了基于c r e w 最优 算法中可能存在的共享冲突，借鉴无存取冲突最优并行归并算法，进步提出了背包 问题基于e r e w 模型的成本最优并行算法，解决了算法中各处理机对共享存储器的 存取冲突。 关键词：网络优化整数规划背包问题并行算法存取冲突高性能计算 i i a b s t r a c t n e t w o r ko p t i m i z a t i o ni sad i s c i p l i n ew h i c hr e s e a r c h e so nh o wt o p l a n ，m a n a g ea n d c o n t r o lt h ew h o l en e t w o r ks y s t e m ，s oa st og e n e r a t et h em a x i m u m s o c i e t ya n de c o n o m i c p r o f i t s i ti sac l a s s i ca n di m p o r t a n tb r a n c ho fc o m p u t e rs c i e n c ea n do p e r a t i o nr e s e a r c h a s t h en e t w o r ki sb e c o m i n gm o r ea n dm o r e h u g ea n dc o m p l e x ，h o wt of i n da no p t i m a ls o l u t i o n o rn e a r - o p t i m a ls o l u t i o no ft h el a r g e s c a l en e t w o r k p r o b l e mi nal e a s tt i m eb e c o m e sm o r e a n dm o r es i g n i f i c a n t m a n yp r a c t i c a lp r o b l e m si nn e t w o r ko p t i m i z a t i o na r ec h a l l e n g e a b l e ， m o s to fw h i c ha r en p h a r d t h i st h e s i si sc o n c e m e dw i t ha n dr e s e a r c h e so nt h ee f f i c i e n t s e q u t i a l a n d p a r a l l e la l g o r i t h m s f o r i n t e g e rp r o g r a m m i n g ，l i n e a rp r o g r a m m i n g ，a n d k n a p s a c kp r o b l e m t oo v e r c o m et h e d e f i c i e n c y o ft h er e l a x e dm e t h o df o rt h el i n e a r p r o g r a m m i n g ，a n e c e s s a r yc o n d i t i o no fl i n e a rp r o g r a m m i n gi sp r e s e n t e d t h i sc o n d i t i o ni sa p p l i e dt ot h e s e l e c t i o no fr e l a x e dv a r i a b l e s ，a n dt h er e l a x e da l g o r i t h mi sr e v i s e d t h e r e a f t e r , b a s e do nt h e c l u s t e rs t r u c t u r e ，ap a r a l l e lr e l a x e da l g o r i t h mi sp r e s e n t e d b o t ht h et h e o r e t i ca n a l y s i sa n d c o m p u t a t i o n a le x p e r i m e n t a lr e s u l t ss h o wt h a t ，a sc o m p a r e dw i t ht h es i m i l a rk i n do fp a r a l l e l a l g o r i t h m s ，t h ep r o p o s e dp a r a l l e la l g o r i t t u nh a sb e t t e rp a r a l l i s ma n dh i g h e re f f i c i e n c y r e c e n t l y , s o m es c h o l a r sp r e s e n t e d an e w a l g o r i t b a n f o rl i n e a r p r o g r a m m i n g t h i s a l g o r i t h m i ss u i tf o r s o l v i n ga s y m m e t r i c l i n e a r p r o g r a m m i n gw h e r e t h en u m b e ro f c o n s t r a i n t si sm u c h g r e a t ，b u tt h en m n b e r o fv a r i a b l e si sl i t t l e a c c o r d i n gt ot h er e l e v a n c eo f t h ed a t aa n d o p e r a t i o n s i nt h a t a l g o r i t h m ，ap a r a l l e la l g o r i t h m t h a ti sb a s e do na m a s t e r - s l a v ea n d m e s s a g ep a s s a g ei n t e r f a c ee n v i r o n m e n t si sp r e s e n t e d b e c a u s eo f i t si d e a l l i n e a rs p e e d u p ，i ti ss c a l a b l e t h u si ti so b v i o u st h a to u rp r o p o s e da l g o r i t h mo u t p e r f o r m s i m i l a ra l g o r i t h m si nt h eo v e r a l lp e r f o r m a n c e i n t e g e rp r o g r a m m i n gp l a y sak e yr o l ei nr e s e a r c ho nd i s c r e t ea l g o r i t h m sa n dn p p r o b l e m s h o wt oi m p r o v et h ee f f i c i e n c yo ft h es o l u t i o na l g o r i t h m sf o ri n t e g e rp r o g r a m m i n gi s v e r y i m p o r t a n ti nt h e o r ya n dp r a c t i c e b yt h eu s eo fg e o m e t r i ct o o l o fd i m i d i a t el a t t i c e ，w e p r o p o s ean e wa l g o r i t h mf o ri n t e g e rp r o g r a m m i n g i tc a no v e r c o m et h eh a r d n e s sw h i c h a p p e a r s w h e nu s eo t h e rc l a s s i c a l a l g o r i t h m s t os o l v et h e l a r g e - s c a l e i n s t a n c e sw i t h e x p o n e n t i a l l yg r o w i n gc o e f f i c i e n t s m o r ei m p o r t a n t l y , b e c a u s eo fi t sh i g hp a r a l l i s m ，i ti s e x p e c t e d t o p r o v i d e an e wc h o i c ef o rt h e s o l u t i o no f g e n e r a ll a r g e s c a l ei n t e g e r p r o g r a m m i n gi n s t a n c e s t h ei d e ao ft h ea b o v ea l g o r i t h mi se x t e n d e dt ot h eu n b o u n d e d k n a p s a c kp r o b l e mw h i c h c a nb ev i e w e da sas p e c i a lf o r mo fi n t e g e rp r o g r a m m i n g ，a n dan e wa l g o r i t h mf o rt h e u n b o u n d e dk n a p s a c kp r o b l e mi sp r o p o s e d w h e nt h en u m b e ro ft h ei t e m si sf i x e d ，t h et i m e c o m p l e x i t yo f t h ep r o p o s e da l g o r i t h m i sl i n e a rt ot h el e n g t ho f t h e i n p u td a t a ，w h i c h i sl o w e r t h a nt h e c o m p l e x i t yo ft h e c l a s s i cd y n a m i c p r o g r a m m i n ga n d t h eb r a n c ha n db o u n d a l g o r i t h m t h ee q u a l i t yk n a p s a c kp r o b l e mi so n eo ft h eh a r d e s tp r o b l e m si n k n a p s a c k s ，b o t ht h e s o l u t i o nt i m ea n ds p a c eo fw h i c ha r ei n c r e a s i n ge x p o n e n t i a l l yw i t ht h en u m b e ro f i t e m so f t h ep r o b l e m m u c he f f o r th a s p a i do n t h er e s e a r c h e so ni t ss e q u e n t i a la n d p a r a l l e la l g o r i t h m s f o ri t s i m p o r t a n ta p p l i c a t i o ni nn u m b e rt h e o r ya n dc r y p t o g r a m i nt h i sp a p e r , b yad a t a s t r u c t u r ew h i c hi sc a l l e dl i s ta n dh a sa na l t e r a b l el e n g t h ，a n i m p r o v e da l g o r i t h mt h a tu n i f i e s t h ef a m o u st w o l i s ta l g o r i t h ma n dt w o l i s tf o u r - t a b l ea l g o r i t l u ni sp r e s e n t e d t h em a i nm e r i t o ft h ei m p r o v e da l g o r i t b a ni st h a ti ti s a d a p t i v e i ta l l o w sa d j u s t i n gt h ep a r a m e t e ri nt h e a l g o r i t h ma c c o r d i n gt ot h es c a l eo ft h ei n s t a n c e sa n dt h ea v a i l a b l ec o m p u t a t i o ns o u r c ef o r t h eo b j e c t i v i t yo fs o l u t i o no fh a r di n s t a n c e s t h ec o m p u t a t i o n a le x p e r i m e n ta l s os h o w st h a t t h eh a r dc r y p t o g r a m st h a tc a n n o tb es o l v e db e f o r ec a nb ee a s i l yb r o k e nb yt h eu s eo fo u r i m p r o v e da l g o r i t h m p a r a l l e l c o m p u t a t i o ni s a ne f f i c i e n t w a yt o t h es e t t l e m e n to ft h e e q u a l i t yk n a p s a c k p r o b l e m t h ee x i s t i n gp a r a l l e la l g o r i t h m sa r ea n a l y s i st h o r o u g h l yi nt h i sp a p e r a f t e ra n e r r o ri nt h em a i nc o n c l u s i o n so fr e l e v a n tl i t e r a t u r e si sp o i n t e do u t ，f o rt h ef i r s tt i m e ，a n o p t i m a lp a r a l l e la l g o r i t h mb a s e do nc r e w i sp r e s e n t e di nw h i c ht h em e t h o do fd i v i d ea n d c o n q u e r i s a p p l i e d t h e r e a f t e r , e n l i g h t e n e db yt h eo p t i m a lm e r g i n g w i t h o u t m e m o r y c o n f l i c t s ，w ep r o p o s ea ne r e wo p t i m a lp a r a l l e la l g o r i t h mf o rt h ek n a p s a c kp r o b l e mw h e r e t h em e m o r yc o n f l i c t si nt h es h a r e dm e m o r ya r ea v o i d e d c o m p l e t e l y k e y w o r d s ： n e t w o r k o p t i m i z a t i o n ；i n t e g e rp r o g r a m m i n g ；k n a p s a c kp r o b l e m ；p a r a l l e la l g o r i t h m ； m e m o r yc o n f l i c t s ；h i g hp e r f o r m a n c ec o m p u t i n g 1 1 本文的研究目的 1 绪论 本文的研究目的在于： ( 1 ) 整数规划是许多实际网络优化( n e t w o r ko p t i m i z a t i o n ) i 口的数学模型，本文试 图研究整数规划及与之密切相关的线性规划、背包问题在通常或某种条件下新的高效 算法。 ( 2 ) 基于c l u s t e r 结构或p r a m 模型，研究上述问题的并行算法，为解决大规模线 性规划、整数规划、背包等网络优化问题奠定坚实基础，从而给实际应用中众多网络 的优化设计提供决策支持。 1 , 2 选题的背景与依据 我们生活在一个网络社会中，从某种意义上说，现代社会是一个由计算机网络、 电话通讯网络、运输服务网络、能源和物质分派网络等多种网络所组成的复杂的网络 系统。网络优化( n e t w o r ko p t i m i z a t i o n ) 就是研究如何有效地计划、管理和控制整个网 络系统，使之产生最大的社会和经济效益。网络优化涉及到的如何设计和管理整个网 络等实际问题是极富挑战性的，这些问题包括“设计具有最小成本的可靠性网络；设 计集成电路板；设计能支持大规模在线应用的通讯网；设计能实时处理复杂问题( 如 雷达信号处理、天气信息处理等) 的高性能多处理器系统；在给定网络中寻求最优线 路( 如基于q o s 的路由器设计) 等。 网络优化是计算机科学和运筹学中的一个经典和重要的分支。随着现代社会网络 规模的迅速增大和日趋复杂，如何在各种有着巨大规模的网络问题中以最小的时间代 价找一个最优解或近似最优解具有十分重要理论和实际意义 1 。“。 许多网络可以视为一个由众多元件组成的系统，其中某些元件以某种方式和另外 的元件相互作用，例如：一个通讯网是一系列终端的集合，其中的某些终端彼此直接 通讯：印制电路板是一些通讯导线联接的终端的集合。这些系统可以十分方便地用一 个图来表示：图的结点表示组成网络的元部件，边表示元部件之间的相互联系。通常 既来，影响网络设计的因素包括：消息延迟时间；输入( 出) 量、信息通讯密度和设备 容量( 终端速度，中继比率等) ，这些因素可以通过给图的边分配适当的权的方式表示 到图的理论模型中。这样，最后得到的图通常是带权有向图或无向图。通常情况下许 多实际应用巾产生的问题是在满足某魑要求下如何寻找和设计根据某些标准f 如成 本、输出或性能等) 最优的网络，而网络所必须满足的某些要求一般能以适当方式， 如图的某些常数界等表示到图的理论特性中，因此，所谓的这类网络优化问题最终就 变成能以整数规划( i n t e g e r p r o g r a m m i n g ，r p ) 建模的图的最优化问题f 5 l 。 网络优化问题属于组合最优化问题的范畴【6 】，因为只要用网络为通讯、运输及分 配等问题建立模型，就会产生组合优化问题。即从有限的但却非常多的构形中选择一 种最优的构形。这些问题可能包括网络综合、现存网络中服务设施的最优选址、以及 为通过网络的信息流选择一种最优的力式等。虽然应用是多种多样的，但某些典型的 组合优化问题却反复出现，它们或者是网络问题的模型，或者是作为更为复杂模型的 子问题出现。这些基本问题可以分为两类，在第一类中，基于对问题结构的深刻理解， 已经为它们找到了有效的解算方法，最短路径、最大流和最小生成树等问题均属于此 类。对第二类问题，尚未找到最坏情况下确实比探试搜索更好的算法。这就是d d 述的 能以整数规划或混合整数规戈l j ( m i x e di n t e g e rp r o g r a m m i n g ) 建模的网络优化问题。因 此，这类问题，包括整数规划、线性规划、背包问题，将是本文研究的主要目标，并 日，如无特别指出，在以后的叙述中，所谓的网络优化问题就特指此类较难解决的问 题。 由于多数网络优化问题能以混合整数规划建模，而线性规划则是整数规划的基础， 阅此，对线性规划的简单介绍是必要的。 线性规划曾被列为2 1 世纪的第九大数学问题【5 。它是现代军事行动、现代商业和 金融活动、现代政务管理和现代工农业生产的组成部分，其应用范围十分广泛。美国国 家研究委员会1 9 9 0 年在著名的振兴美国数学一9 0 年代的计划的报告中称，“前些 年发现的线性规划的各种内点算法及其发展是算法方面的一个惊人的新进展” 7 。美 国物理学会和国际电气与电子工程计算机协会i e e e 于2 0 0 0 年联合筛选出的2 0 世纪 最成功的十大算法中就列出了求解线性规划的单纯形算法 8 】。虽然人们现在已知道线 性规划可在多项式时间内求解，但作为汁算机理论科学的一个基本问题之一，线性规 划属于p 类、还是n p 类问题却曾经引起了计算机和数学科学界十几年的争论。 作为网络优化问题数学模型的整数规划只不过是对线性规划的变量加以非线性的 整数限制而得到，并且线性规划存在以椭球法和内点法为代表的多项式算法，但是， 混合整数规划( m 口) 或整数规划( i p ) 则属二于二典型的n p - h a r d 问题【5 l 。线性规划是整数规 划的基础，而背包问题与整数规划紧密相关，因此，整数规划、线性规划、背包等网 络优化问题是研究实际应用中大规模刚络优化设计的理论基础。而对它们有效求解算 法的研究，自然引起了广大科学工作者巨大的研究兴趣 4 8 】。 1 3 网络优化算法研究的国内外现状、水平与发展趋势 对整数规划、线性规划、背包等网络优化问题算法的研究，一直以来是沿着两个 方向发展| 5 f ， + 平十方向是为这些网络优化问题寻找精确算法( e x a c ta l g o r i t h m ，或称最 优算法) ，即为这些问题找到全局最优解，例如分支限界法、动态规划、割平面算法以 及枚举法等算法就是精确算法。精确算法在解决小规模问题时，其求解时间是可以容 忍的，但是随着问题规模的增大，由于解的数目以指数方式增长，准确求出问题的最 优解有时变成了非常困难的事情；另一个方向是所谓的启发式算法f h e u r i s t i c a l g o r i t h m ) ，是指那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的 方法口j 。当然，将求解整数规划、背包等网络优化问题的算法分成两类也不是绝对的， 事实e ，实际应用中的很多精确算法就使用了启发式规则。除了这两个方向以外，随 着现代并行处理技术乃至网格计算技术的发展，对网络优化并行算法的研究也日益受 到重视。 i 精确算法( e x a c ta l g o r i t h m ) 网络优化问题精确算法或最优算法的研究是随着网络优化问题的出现便开始进行 的，至今仍是该领域研究的一个核心课题。求解整数规划、线性规划、背包等网络优 化最优算法主要有：分枝限界法( b r a n c ha n db o u n da l g o r i t h m ) 、动态规划、割平面法 ( c u t t i n g p l a n e a l g o r i t h m ) 及分枝割平面算法( b r a n c ha n dc u t t i n g p l a n e a l g o r i t h m ) 等。 1 9 5 0 年，a h l a n d 和a g d o i g 首先对货郎担问题提出了一个分解算法【6 】，紧接 着e b a l a s 等人将其发展为求解一般整数规划问题的分枝限界法【5 1 。分枝限界法的基 本思想是隐式地枚举一切可行解，当然，这种枚举不是简单的完全枚举，而是一种以 比较聪明的方式进行的，即依次对解空间进行划分。分枝指的就是指这个不断进行的 划分过程，而所谓限界，是指对于每个划分后的解空r m ( & p 每个分枝) 计算原问题最优 解的下界，利用这些下界在求解过程中判定是否需要对目前解空间进一步划分，从而 避免完全枚举。从算法的思想容易看出，算法的实际计算效果取决于具体的分枝策略 和限界方法。限界中常采用的方法是线性规划松弛方法和l a g r a n g e 松弛方法f 5 j 。对于 线性规划方法，在求解每个松弛的问题时，可以采用较简单的单纯形法和较繁难的内 点法 1 】，单纯形法虽简单易行，且多数情况下，可以很快求得问题的一个下界，但它 本身不是一个多项式时间算法，在不少实际化问题中容易出现因退化而导致循环迭代 “。内，j n 厶虽然最例在小型问题和某些大规模问题。p 不如单纯形法有效，绎过人毓科 学家的努力完善，现已发展成为口j 与甲纯彤法媲美f i 稳定性更为出色的方法。n i 。典 际应用中可酌情选用单纯形法和内i 法办或使用将两者牛h 结合的混合式算法。限 界常1 1 j 的，卜利t 方法是l a g r a n g e 松弛法【ij 。该方法的基本思想是：将网络优化问题i i i 较难的约束吸收到目标函数中，并保词 日标函数的线性性，由此使得问题容易求解。 此外，坯r , j - 进步利用拉格朗同松弛的基本原理筛选出基于托格朗松弛的启发，算 法，、j 然，侄使用分枝限界法的同叫，可以利用某些启发式方法米加快球解过程。如 m 出现多个分支时，选界较低的个笥。但足，这些启发式舰则有时足从直删感觉得 山的，这“望枷则既尢理论卜严格的证明，也非对丁任坩隋况都有用。正如l aw o l s e y ”o 所说：使用启发式算法对某些| 史例= j ：j 能会加速其求解过程，但刈另外些实例印使 求解小得不面对更多的分枝进行，进i 使求解过程延长。应该指山的足：虽然分枝限 界法理沦卜是一种指数时问算法( e x p o n e n t i a lt i m e a l g o r i t h m ) ，但其实际效果却小蔗， 因为实际i u 题中许多分枝会冈超过下男而被删除。因此：分枝限界法仍然是熬数规划、 1 ： l 包问题等网络优化问题的首选方法之，当然，针对彳i 同的实际问题，可能会采川 些不同处理技巧，如h o f f m a n 和p a d b e r g 提出的覆盖不等式( c o v e ri n e q u a l i t i c s ) i 、 s a v e l s b e r g h 提出的预处理和穿刺技术f p r e p o c e s s i n ga n dp r o b i n gt e c h n i q u e s ) j i l l 以及 c l a e s s c n s i 等在处理丹麦通讯线路的塌优布局- 斗j 采用的冗余和主变量技巧等。 割平算法最甲是g o m o r y 于1 9 5 8 年提m 的所峭分数割平面法( f r a c t i o n a ld u a l a l g o r i t h m ) 1 5 l 。其基本思想是：给所求解的整数规划增加个线性约束，但小致“割掉” 原来问题的任何可行整数解，口保持新问题与原问题有相同的整数解。从o o m o r y 算 法可以看卅，该算法在计算过程巾不断增加割平面的个数，因而会出现约束个数越米 越多的情况；其次，该算法在计算机卜的实现过程会有一点麻烦，因为计算机执i j ：算 法时的累积误差，要判断个实数是否为一个整数绝非易事，为克服这缺点，有 学析提出了令整数算法【| j ；最后：分数对偶算法采用对偶单纯形法，存达到最优解之 f j u 将得小到原问题的最优解，甚至连原油题的个r j 行解都难以得到。而实际应川中 例络优化问题f 内规模义| 分庞大，要在任何情况下都得到问题的最优斛是不现实的。 此，血u 果闪计算时间过长而不得彳ir r 间停机时，结果往往无法使用。为此。义确人 提fj5 了原始整数割平面算法”i 。但不管采用何种补救办法，现在人们普遍认为：钏甲 硼算法般不会比分枝限界算法吏有效。i “。 实际h 近年柬广泛使用的求解整数规划、背包问题等网络优化问题的钾：法之 魁将分枝限界算法和割平面算法结合起来的所谓分枝割、r 丽算法【l 。其摹本思想足： 采用分枝限界法的分枝方法求最优解，但限界时不用传统方法求解线性规划松弛0 u 题 或拉格朗h 松弛问题的界，而是对每一个分枝子问题用割平面方法求得一个更好的下 界，如何求得一个更好的下界取决于添加一个怎样的割平面，若选择一个能产生好下 界的紧约束平面，将使得待搜索树的分枝数大为减少，从而提高算法的求解效率。经 过许多学者在实现技巧上的改进，现在人们对分枝割平面算法的基本认识如下： a 通过在分枝限界时使用前面计算下界中使用过的切平面约束，可以节省大量 的计算时间和存储空间。因为这样做可使约束或迭代不必从存储器中静态产生。 b 对在前面汁算下界中使用过的约束的重用可使本次求下界的工作不必从零丌 始，同时可在同时刻对各分枝结点的解空间多胞体描述作进一步改进“。 c 对于某些大型网络优化问题，l p 松弛变量的个数将十分庞大，这将使得相j 、t l p 问题的求解时间不可接受，从而影响分枝割平面算法的求解效果，这时可采用预 处理办法和g r o t o s e h e l 等| 13 ) 提出的稀疏图技术来减少0 - 1 变量的个数，缩短计算时间。 通过对分枝割平面算法的不断改进，现在，能用该算法求最优解的网络优化问题 规模越来越大，以著名的旅行商问题( t r a v e l i n gs a l e s p e r s o n p r o b l e m ，t s p ，一种特殊的 整数规划) 为例，1 9 5 4 年，d a n t z i g 等最初只能求解4 9 个城市的t s p ，1 9 7 7 年能够精 确求解1 2 0 个城市的t s p 1 4 】，后来，a p p l e g e t 等【】5 】可求解7 3 9 7 个城市t s p ，最近的 报道则可求城市数多达1 3 5 0 9 的t s p 的精确解【1 6 1 。这些算法中使用较多的技巧是“梳 子不等式( c o m bi n e q u a l i t i e s ) ”和“斜树不等式( c l i q u e t r e e i n e q u a l i t i e s ) ” j ”。 启发式算法是相对于最优算法提出的，一个问题的最优算法求得该问题每个实例 的最优解，而启发式算法则是一个基于直观或经验构造的方法，它能在可接受的时间 和空间花费内给出待解决问题的一个可行解，该可行解与最优解的偏离程度不一定事 先可以预计【1 。目前，整数规划、线性规划、背包等网络优化问题中广为使用的启发 式算法有禁忌搜索( t a b us e a r c h ) 、模拟退火( s i m u l a t e da n n e a l i n g ) 、遗传算法( g e n e t i c a l g o r i t h m ) 与人工神经网络( a r t i f i c i a l n e u r a ln e t w o r k s ) 等。虽然在某些情况下，特别是 实际问题中，当最优算法的串行计算时间使人无法忍受时，采用启发式算法是可选方 案之一，但由于它们并不能导致有时是必须的最优解，本文不拟研究这种算法，有关 启发式算法在这些网络优化问题中的详细应用，可见于文献【1 7 - 3 5 。 ( 2 ) 并行网络优化算法( p a r a l l e la l g o r i t h m f o rn e t w o r k o p t i m i z a t i o n ) 由于信息技术在最近几十年的迅猛发展，使得构成现代社会的各种网络r 趋复杂， 网络的规模也呈爆炸方式增长。在各种网络优化问题中，有些问题不但规模庞大，而 且对最优解的精度要求很高。例如集成电路板的电路布线、航空公司的航线设计、基 于背包密钥的有效破解等网络优化问题就是如此。这时传统的最优算法和现代启发式 算法对解决这些问题显然都无能为力，于是，人们对那种能在合理的时问界限内求出 精确最优解的算法提出了迫切要求，这就是并行算法。另一方向，近年来，并行叫算 技术在并行计臂机及其千应软件曲个巾自f 的发展f f 趋成熟，这也为人规模整数规划、 背包问题等刚络优化问题的精确求解提供了i i j - 能。 史际l 二，整数规划j 背包m 题并i ，：算法的研究十要集中为对它们的精确算法椰们 发式算法存各种并行汁算模型p 的并j ，。化。而且，由丁+ 大多数启发式算法的洲算i i , j 币ij 总足问题规模的一个阶数较低的多项式，因此，相应并行算法f t j t ：究主要表现为研究 j 确算法的，f ： j ：化及其实现技术，如并行分枝限界法、并行割平面算法、并行动态规 划算栏：等。当然，凶为割甲而算法1 i 及分枝限界算法有效，近二：1 年术，这领域的 成果大多集- 扣i 并行分枝限界算法或并行动态规划算法上。分枝限界算法的并行化 般有两个层次：第个层次实质上是对棵每个接点表示i p 一个解空问的树的外行搜 索。这涉及到搜索方式足采用深度优先还屉宽度优先、树的节点如f i , 1 分配到备- j j ：处 j ；| i 。机单元等符种具体策略弦”】。如何列每个节点并行求解，则是分枝限界算法并行 1 u o t ：究的第二：层次，即如何并行求解个线性规划的刚题。线性舰j j l j j j ：行算法的研究 涉及剑刈它的两类算法( 单纯形法和内点法) 的升：行化，尽管内l l 法的并行化存丈现时 较繁琐，但多数研究者赞同对内点法使用并行求解，原凶在于：首先，内点法较传统 f i j 单纯形法更能处理约束矩阵中非零个数较多的情况；其次，侮次迭代巾，荆恻：r 计 算代价i 叮吉的通讯代价在内点法中比重更低。当线性舰划问题的约柬矩阵为稠密矩阵 h 满足定结构特性时，其并行算法的研究是较为成功的，但现实问题- j 约束m 阵多 为稀疏舛r 阼，冈此现阶段对约束矩阵为稀疏矩阵的线性舰划的并行算法研究是 个怍 常活跃的领域【j ”j 。 自从网络优化问题诞生以来，令世界刈这一问题丌展了广泛的研究，六r 水， 随彳午个个从史际应用领域产生的网络优化问题的不断解决和新的问题不断产 二，例 络优化问题不断地。卜富，到今天，能够称为删络优化的问题己十分庞大。堪管嘲络优 化某些问题的大量研究成果极大地推动了人类社会的发展和繁荣，为各个科学页域特 川足计钾机科学、数学、智能控制等学科走向小断成熟奠定了r * 实基础。仉是，这“b 【。j 墩得的成就远谈不上对这问题的全面解决，尤其是对那u b 能以整数舰划建模的网 络优化lu 题，i i 于其难角犁性，在解决这螳问题上还存在许多挑战性l 作。 虽然启i 发式算法具有简单易行、快速及在某种情况下得到的解比用精确算法求得 的解更接近实际情况等优点，但它仍存缸目前无法解决的f 述缺点p 】：不能保证求得 最优解；表现小稳定，以致在实际应用i + ，由丁这种不稳定性造成计算结果小可信； 算法的好坏依赖于实际问题、设计者的经验和技术，使得算泫设计难于总结规律：行 非所有的网络优化问题都可用启发式算；去来解决，如经典的网络优化问题一等式背包 问题( e q u a l i t yk n a p s a c kp r o b l e m ) 和t s p 问题就无法用启发式算法求得问题的近似最 优解，对等式背包问题问题和t s p 甚至不存在时f i j 复杂度为o ( n 3 ) 的启发式算法。 许多网络优化问题能用已有算法在合理的时间界限内精确求解，这主要是因为可 以设计出求解这些问题的强多项式算法或弱多项式算法，如无界背包问题，就可用时 阳j 复杂性为o ( n c ) 的动态规划方法求解，但这样的问题毕竟只占全部网络优化问题的一 部分，对于更多的问题，甚至不存在比枚举法更有效的精确算法 3 9 - 4 1 】，如等式背包问 题、一般整数规划等。因此，对于这些时间应用极重要的网络优化问题，设训和研究 时削和空间复杂性相对较低的算法显得更加紧迫。 在网络优化的并行算法方面，剥于整数规划、背包等网络优化问题的精确算法， 如切平面法和分枝限界法，其并行化不易实现，或者说算法并行后，其并行效率和效 果难以令人满意，这主要因为：1 ) 切平面算法和分枝限界法都要求求解大量线性规划 松弛问题，若采用单纯形法，则其并行效率通常低于3 0 口，虽然采用内点法求解时 其并行效率能有小辐提高，但求解过程却不如单纯形法简便【3 ”。分枝限界法的串行效 果虽比切平面法好，但涉及到对一棵二：元树的搜索和比较问题，如果采用深度优先搜 索( d e p t h f i r s ts e a r c h l ，则它本质上是不可并行的【3 ”，若采用宽度优先搜索( b r e a d t hf i r s t s e a r c h ) ，其并行算法的效果会因为频繁的通讯和同步而大为逊色。另一方面，这些并 行算法中的各个进程如何在各种具体的并行结构上有效调度 4 2 - 4 7 】，现在也没有统一的 认识。而对于在信息密码学领域和数论研究中有着重要地位的等式背包问题，虽然已 设计出多种并行算法，但这些算法大多是基于理想的p r a m 并行计算模型，而且至今 为止，尚未见有基于c r e w 或e r e w 的成本最优算法出现。 本文正是基于上述背景，针对整数规划、线性规划和背包问题现有精确算法求解 这些网络优化问题时间和空间复杂性过高、算法在并行化后效率较低、可扩展性不好 等缺点，根据这些问题的本质，研究求解这些网络优化问题的新算法，以及具有更高 性能( 如更高的并行加速比、较好的可扩展性、成本最优等) 的并行算法。 1 4 研究目标与研究意义 博士论文的研究目标主要集中在以下二个方面，一是针对整数规划、线性规划和 背包等网络优化问题的某些精确算法复杂性过高、不易并行的缺点，研究求解这些问 题整体上或某种条件下性能更好的新算法。二是根据问题的实际需要，设计这些问题 基于各种并行计算模型的并行算法，并将其中的部分算法在基于m p p 结构的实际系统 卜进行实验分析。相信这些研究工作能够推动网络优化相应领域的研究，为更好地解 7 决实j 轫咄v t _ j f 一泛存在的网络优化问题奠定定的耻! 论基础。 从前述沦述可以看i 【 ，本文的研究j i 作具有如下重要意义： ( 1 ) 网络优化是计算机科学的一个罩要分支，这领域的仟何突破都将导致整个 f l ：机学科的发腥。 ( 2 ) 蔡数规划、线性规划、背包等网络优化问题是实际应用巾各种决策刚题的j + 骊“，