（系统分析与集成专业论文）多约束非线性背包问题的替代对偶方法.pdf

2 0 0 6 年上海大学硕士学位论文 摘要 非线性背包问题是一类特殊而重要的非线性整数规划问题，它可以定 义为在有限整数集上极大化一个可分离非线性函数的约束( 可分离) 最优化 同题由于这类问题在经济管理，金融投资，资源分配，工业生产及计算机 网络的最优化模型中有着十分广泛的应用，因此研究非线性背包问题的算 法具有重要的现实意义本文所讨论的多约束非线性背包问题可以描述如 下： n m a xf ( x ) = ：( x j ) j = 1 t l s t 9 i ( x ) = ：g o ( x j ) 曼b i ，i = 1 ， ，m ， j = l z x = 码! 巧曼u j ，x j 为整数，j = 1 ，一，n ) ， 其中疗，蛐为定义在u j 】上的单调递增函数，0 和呦为整数，分别表示 整数变量z ，的下界和上界，b l 是常数，这里i = l ，仉j = 1 ，n 本文根据背包问题的结构特点，提出了一种替代对偶( s u r r o g a t ed u a l ) 方法和区域分割方法来解这类多约束非线性背包问题我们用替代松弛方 法把多约束问题化为单约束问题，并利用0 一i 线性化方法求解替代松弛问 题为得到更紧的上界，消除对偶间隙以保证算法的收敛性，我们利用割 平面方法求解替代对偶问题，利用区域割技术丢掉某些整数箱子，并把剩 下的区域划分为一些整数箱子的并集，以便使替代松弛问题能有效求解， 使算法在有限步内收敛到最优解算法的特色和创新之处是把替代松弛方 法用于求解对偶问题并与区域分割有效结合起来解决多约束非线性背包问 题数值结果表明本文提出的方法可以较有效地求解大规模多约束非线性 背包问题此外，我们还对来自实际应用中的多约束非线性背包问题进行 了大量的数值试验 本文总共分为五章，第一章简单介绍了非线性背包问题的背景和应用， 整数规划问题算法的研究现状和研究进展，并介绍了本文的主要内容第 二章简单介绍了求解非线性背包问题( 单约束) 的现有的算法，如：分枝定 界算法，动态规划与分枝定界的混合算法，0 1 线性化方法，以及拉格朗 日对偶与区域割算法等第三章介绍替代对偶理论，包括替代松弛理论以 2 0 0 6 年上海大学硕士学位论文 i i 及替代对偶搜索的几种经典算法第四章介绍我们的非线性背包问题的替 代对偶和区域割算法，并给出了数值试验结果第五章是结论部分，是对本 文结果的总结以及对未来研究的展望 关键词：非线性背包问题，替代对偶，区域割，割平面法，次梯度法 2 0 0 6 年上海大学硕士学位论文i i i a b s t r a c t n o n l i n e a rk n a p s a c kp r o b l e mi sa l li m p o r t a n tc l a s so fn o n l i n e a ri n t e g e rp r o - g r a m m i n gp r o b l e m sw h i c hc a nb ed e f i n e da st i l em a x i m i z a t i o no fas e p a r a b l e f u n c t i o ns u b j e c tt os e p a r a b l ec o n s t r a i n t sa n db o u n d e di n t e g e rv a r i a b l e sb e c a u s e o fi t sw i d ea p p l i c a t i o n si nm a n a g e m e n t ，e c o n o m i c s ，r e s o u r c ea l l o c a t i o n ，i n d u s t r i a lp l a n n i n ga n dc o m p u t e rn e t w o r k ，i ti so fg r e a ti n t e r e s tt os t u d yt h en o n l i n e a r k n a p s a c kp r o b l e m s ag e n e r a ln o n l i n e a rk n a p s a c kp r o b l e mc a l lb ee x p r e s s e da s f o l l o w s ： m 一，( z ) = f j ( 3 2 j ) j = l n s t 吼( 。) = ( 印) 曼b i ，i = 1 ，m j = l 3 2 x = l j z ) u j ，z j i si n t e g e r ，j = 1 ，n ) w h e r e ，ja n dg i ja r ec o n t i n u o u sn o n d e c r e a s i n gf u n c t i o n so n 1 j ，脚】，l ja n du ja r e t h el o w e rb o u n da n dt h eu p p e rb o u n do ft h ea r g u m e n tx jo nt h ei n t e g e rv a r i a b l e s r e s p e c t i v e l y , b li snc o n s t a n t f o ri = 1 t h em a i np u r p o s eo ft h i st h e s i si st op r o p o s eas u r r o g a t ed u a la n dd o m a i nc u t m e t h o df o rs o l v i n gt h em u l t i d i m e n s i o n a ln o n l i n e a rk n a p s a c kp r o b l e m sm u l t i p l y c o n s t r a i n e dp r o b l e mi sr e l a x e dt oas i n g l yc o n s t r a i n e dp r o b l e mb ys u r r o g a t et e c h n i q u et oc o m p u t et i g h t e rb o u n d so ft h ep r i m a lp r o b l e m ，c u t t i n gp l a n em e t h o di s u s e dt os o l v et h es u r r o g a t ed u a lp r o b l e m ，w h e r et i l es u r r o g a t er e l a x a t i o np r o b l e m i ss o l v e db yt h e0 1l i n e a r i z a t i o nm e t h o d d o m a i nc u tt e c h n i q u ei se m p l o y e dt o e l i m i n a t et h ed u a l i g rg a pa n dt h u st og u a r a n t e et h ec o n v e r g e n c eo ft h ea l g o r i t h m f i n a l l y , n u m e r i c a lr e s u l t sr e v e a lt h a tt h es u r r o g a t em e t h o di sc a p a b l eo fs o l v i n g l a r g e - s c a l em u l t i - d i m e n s i o n a ln o n l i n e a rk n a p s a c kp r o b l e m s t h i st h e s i si so r g a n i z e da sf o l l o w si nc h a p t e r1 ，w eg i v es o m eb r i e fi n t r o d u c t i o no fn o n l i n e a rk n a p s a c kp r o b l e m sa n ds o m ee x a m p l e so fi t sa p p l i c a t i o n s r e c e n tr e s e a r c hp r o g r e s so nn o n l i n e a rk n a p s a c kp r o b l e m si sa l s oi n t r o d u c e di n c h a p t e r2w ed i s c u s ss o m eo ft h ee x i s t i n gm e t h o d sf o rs o l v i n gn o n l i n e a rk n a p s a c k p r o b l e m s ) s u c ha sb r a n c h - a n d b o u n dm e t h o d ，h y b r i dm e t h o db a s e do nd y n a m i c p r o g r a m m i n ga n db r a n c h a n d b o u n d ，0 1l i n e a r i z a t i o nm e t h o d ，a n dl a g r a n g i a n 2 0 0 6 年上海大学硕士学位论文i v d u ma n dd o m a i nc u tm e t h o di nc h a p t e r3 ，w eg i v eab r i e f s u r v e y0 1 2s u r r o g a t e d u a lm e t h o di n c l u d i n gs u r r o g a t er e l a x a t i o na n ds e v e r a lc l a s s i c a ls u r r o g a t ed u a l m u l t i p l i e rs e a x c bp r o c e d m e san e ws u r r o g a t ed u ma n dd o m a i nc u tm e t h o d a n di t sc o m p u t a t i o n a lr e s u l t sa r ep r e s e n t e di nc h a p t e r4f o rs o l v i n gt h em u l t i d i m e n s i o n a ln o n l i n e a rk n a p s a c kp r o b l e m s f i n a l l y , c h a p t e r5c o n t a i n s8 0 m ec o n c l u d i n gr e m a r k s w es u m m a r i z et h em a i nr e s u l t so ft h et h e s i sa n ds u g g e s ts o m e f u t u r er e s e a r c hd i r e c t i o n s k e yw o r d s ：n o n l i n e a rk n a p s a c kp r o b l e m ，s u r r o g a t ed u a l ld o m a i nc u t ，c u t r i n gp l a n em e t h o d ，s u b g r a d i e n tm e t h o d 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均己在论文中作了明确的说明并表示了谢意。 签名獬日期：蚴 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名她衅师躲雄! ：出垆 第一章前言 1 1非线性背包问题的背景和应用 非线性背包问题是非线性整数规划中一类特殊而且重要的问题，它可表示为 n ( n k p ) n l a x ，( z ) = f j ( x j ) j = 1 其中疗，毋为定义在u j 上的单调连续实函数，b 和为整数，分别表示整数 变量嘶的下界和上界，这里j = 1 ，nb 是常数 经典的非线性背包问题只有一个约束条件，如果上述问题有多个约束条件，则 被称作多约束非线性背包问题( m u l t i - d i m e n s i o n a ln o r f l i a e a rk n a p s a c kp r o b l e m s ) 它 的一般形式可表示为： ( m n k p ) m a x ，( z ) = f j ( q ) j = l st 仇( z ) = 蜘( ) h i , i = l ，m ， j = l z x = z z “，c j 曼z j u j ，j = 1 ，n ) 其中矗( 吩) ，g i j ( x j ) 为定义在u j 上的单调连续实函数，f j 和为整数，分别表 示整数变量的下界和上界，“是常数，这里j = 1 ，7 , ，i = 1 ，m 1 1 1 非线性背包问题的研究背景 线性背包问题是整数规划和组合优化中的一个经典问题，问题可描述如下：一 个徒步旅行者带了一个背包，他要用背包装入尽可能多的物品而不能超过这个背 包的容量如果有几种不同的物品可以装进背包，且每种物品都有一定的价值和体 积下面的问题就产生了：如何从这几种物品中选择才能使得放入背包的物品的价 值最大这就是著名的背包问题( k n a p s a c kp r o b l e m ) 令b 表示背包的最大容量，整数1 ，2 ，n 表示n 种可以选择的物品，功，q 分 吣 叶叻 虬 l j 。，：p 如果( 1 ) 0 时，z ，( a ) ，町( a ) ，叻( a ) 满足除( 2 1 1 ) 一( 2 14 ) 之外的( c p ) 的所有 的k k t 条件寻找最优的乘子a 使得q ( ) ，啦( a ) ，屿( ) 满足剩余的两个k k t 条件 是当前的主要任务求解非线性方程a ，j a 吻一a 勘o x ；= 0 ，如果而( ) 可以表示 成 的显式形式，则把其代入上面的三个式子，得到( c p ) 的最优解否则，要多 次寻找非线性方程的根，增加了算法的难度令”表示最优的拉格朗f t 乘子，如 果”= 0 ，则很容易得到( c p ) 的最优解，否则，单一的不等式约束就变为等式约 束，即翟，野( ) = b 且忽略掉变量的上下界，相应的松弛问题比( c p ) 更容易求 2 0 0 6 年上海大学硕士学位论文 9 解由此形成了变量固定p e g g i n g 算法阱每一次迭代过程中都会将不满足上下界 约束的变量固定为其上( 下) 界，如此就可以减少下面需要解决的问题的规模当 所有没被固定的变量都满足其上下界时，算法在有限步内终止令z ；，。：表示 松弛问题( c p ) 的最优解很容易知道如果变量x ；= k 或者z ；= 。，则变量z ；被固 定记驴为到第k 次迭代时被固定为下界的所有变量的下标的集合，u 为到第k 次迭代时被固定为上界的所有变量的下标的集合，p 为到第k 次迭代时未被固定 的所有变量的下标的集合则第k 次迭代时要求解的松弛子问题( r p “) 为： ( 胛) m “ ( 戤) + f i ( l i ) + ( 蛳) i e i i e l ki e u k s t 吼( 叫= b 一g i ( l i ) 一吼( u t ) i e l t 二i e u k 我们假设子问题( c p ) 有最优解并记： z i ，一，z ：为子问题的最优解； z ，z 为p e g g i n g 程序第k 次迭代时子问题( r p ) 的最优解； a 。为子问题( c p ) 非线性约束的最优乘子； ”为子p e g g i n g 程序第k 次迭代时子问题( 兄p ) 的最优乘子； q ( ) = 竺1 仇( ( ) ) ； 碴= z f ：吒k 叫) ； 玮= p 一( 碹一磕) ； s l = t ( g i ( 1 i ) 一玑( g ) ) ； s i = 吲j ( 9 i ( x i ) 一甄( 。k ) ) 我们将考虑如下四种情况： ( 1 ) 对任何i ，吼( z 。) 关于x i 单调减，2 ；( a ) 关于 单调增这意味着对任何i ，矾( a ) 关于 非减，q ( a ) 关于 非增 ( 2 ) 对任何i ，9 i ( 趴) 关于吼单调增，娩( ) 关于a 单调减这意味着对任何i ，x i ( ) 关于a 非减，q ( a ) 关于a 非增 ( 3 ) 对任何i ，g t ( x 1 ) 关于她单调减，黾( a ) 关于a 单调减这意味着对任何i ，x i ( a ) 关于a 非增，q ( a ) 关于 非减 ( 4 ) 对任何i ，吼( z 。) 关于毛单调增，毛( ) 关于a 单调增这意味着对任何i ，x i ( a ) 关于a 非减，q ( a ) 关于a 非减 不失一般陛，这里我们假设y ( x i ) 在l i u ；上关于黝单调增减考察凹函数 2 0 0 6 年上海大学硕士学位论文 1 0 ( z 。) ，此函数从开始单调增接着从x 。= z p “处开始单调减 对于第( 1 ) 种情况下求解松弛问题( c p ) 的p e g g i n g 算法描述如下 程序2 1 1 ( 求解问题( c p ) 的p e g g i n g 算法) 司 s t e p1 ( 决定 。 o 或a 。= o ) 令 = 0 如果墨l 吼( 黝( a ) ) b ，则”= 0 ，得到 ( c p ) 的最优解z i ，z ；，停止否则，a 。= 0 ，转向第2 步 s t e p 2 ( 初始化) k = 1 ，1 2 = 1 ，2 ，n ) ，l = 0 ，u = 0 s t e p3 ( 求解子问题( r p ) ) 求解当前的子问题( r p 。) ，并记z ；为对于i ，的最 优解 s t e p4 ( 辨别未到达边界值的变量) s = 0 ，硝= 0 ，聩= 0 ，碴= 0 对每个i j ，如果z ? l i ，则硝= 璐+ g i ( 1 i ) 一m ( z ? ) ，碹= 瑶u 0 ) ；如果。； ， 则破= 破+ g ( x i ) 一乳( 嗡k ) ，破= 磕u 0 如果破u 瑶= o ，转第6 步 s t e p5 ( p e g g i n g ) 如果醴殴，则有i m = i 一破，u = u u 破，驴+ 1 = l ；否 则，有j o + 1 = j “一j ，l “+ 1 = l “u 碹，u o + 1 = u o k = k + 1 ，转第3 步 s t e p6 ( 问题( c p ) 的最优解的还原) 对于i l 2 ，z ；= “，对于i u 2 ，。；= 地，对于 i f ，。；= x i 对于第2 种情况，只需要将第5 步做如下修改： s t e p5 ( p e g g i n g ) 如果铝s l ，则有j + 1 = i 一碹，l + 1 = l u 畦，u 2 + 1 = u ；否 则，有，。+ 1 = 。一破，u + 1 = u u 破，l + 1 = l k = k + 1 ，转第3 步 2 2单约束非线性背包问题的0 - 1 线性化算法 根据背包问题的单调性和凸性，h o c h b a u m 提出了0 - 1 线性化方法2 4 1 求解问 题( n k p ) 这个方法是m a t h u r 3 8 1 解二次背包问题方法的一个推广，在【3 7 1 中有此 方法的详细介绍，但是没有给出数值结果文2 6 1 提出了解凹背包问题的动态规划 和0 - 1 线性化方法：当 为凹函数时，此凸背包问题可以直接转化成个等价的 0 - 1 线性背包问题，然后通过隐枚举法或动态规划方法解这个0 - 1 线性背包问题就 可以得到原凸背包问题的最优解； 当 为凸函数时，对于此凹背包问题，首先用 一个线性函数逼近目标函数，约束条件不变，由此得到一个目标函数是缌陛函数的 凸背包问题，接下来就可以把得到的这个凸背包问题转化成一个等价的0 - 1 线性背 包问题，利用上述方法可以得到此凸背包问题的最优值和最优解，且此时得到的最 优解是原凹背包问题的一个上界，把得到的这个最有解代入原凹背包问题的目标函 2 0 0 6 年上海大学硕士学位论文 数中，就可阱得到一个下界，考虑到函数的单调性，结合分枝定界方法和区域割技 巧即可保证算法的收敛性，得到原问题的最优值和最优解 2 2 1 0 - 1 线性化 本节介绍把凸背包问题转化成一个等价的0 - 1 线性背包问题的方法令z j k = 9 j ( ) ，其中j jsk 曼u j 定义一个逐段线性函数h j ( z j ) ，其断点为b ，f j ( k ) 、k = b ，f j + 1 ，- ，“j 定义集合乃= 矾，= z ，l j + 1 ，u j ) = g j ( 1 j ) ，g i ( z j + 1 ) ， ，毋( u ，) ) ，j = 1 ，2 ，n 则凸背包问题可以写成下面的等价形式： n ( e p )m a x b ( 勺) j = l 勺巧，j = 1 ，。，” 引理2 2 1 凸函数的差分是非减的即若g ( z ) 是皿上的凸函数，o 0 j u 缸= 1 ，k 口 f 2 2 1 0 ) ( 22 1 1 ) ( 22 1 2 ) ( 22 1 3 ) 由于( = ，) 是凹函数，则由( 2 2 1 0 ) ( 2 2 1 2 ) 组成的( l p ) 的松弛问题的最优解必然 满足式子( 2 2 1 3 ) 也就是说，式( 2 2 1 3 ) 从( l p ) 中去掉之后，问题( _ l p ) 依然与原 问题等价( l p ) 的松弛问题是一个典型的o _ 1 线性背包问题，则原问题可以通过 解一个等价的0 4 线性背包问题获得最优解假设是松弛问题的最优解，原问题 的最优解为。+ ，则我们有下面的关系：z ；= 蓦 十】u 荔+ b ，= 1 ，n 原问题的 最优值等于松弛问题的最优值下面的问题是求解0 - 1 线性背包问题 2 2 2 0 - 1 线性背包问题的主要解法 。一l 线性背包问题是一种最简单的整数规划问题，其一般形式为 其中，q 是决策变量不失一般性，p j ，a j ，b 都足大于等于零的数 任何求解线性整数规划问题的算法都可以用来求解0 - 1 线性背包问题( o - 1 k p ) ， 一般地分有： ( 1 ) ，隐枚举法( i m p l i c i te n u m e r a t i o n ) ；( 2 ) ，动态规划方法( d y n a m i c x ，则令s = i 一1 ，z = x p s n 。如果厶m 【z j + ， 转到第5 步 旭弛 q 。赳 2 0 0 6 年上海大学硕士学位论文 1 4 s t e p2 ( 可行解) 如果吼x ，i n ，令x ：= x o 。，f ：= f - i - m 粕= 1 ，i ：= i + 1 ，转 第3 步；否则，如果i n ，令戥= o ，i ：= i + 1 如果i n ，转第4 步 s t e p3 ( 更新) 如果，耐 f ，令f o p f f ，。f ，i = n 如果。”= 1 ，令x ：= x + 。n ， f ：= f p 。，口”= 0 s t e p4 ( 回溯) 找到最大的k i 使得z = 1 如果不存在这样的k ，停止，当前解 。就是最优解否则，令x ：= x + ，f ：= ，一p k ，= o ，诘k 十1 ，转第2 步 ( b ) 动态规划方法 动态规划方法可以用来求解( 0 1 k p ) 问题，但是要满足一定的系数为整数的 条件这里我们设系数a j , j = 1 ，n 都为正整数上述转化来的( 0 1 k p ) 问题 满足此条件对每个m = 1 ，一，n ，。= 1 ，b ，我们定义 m m ( z ) = m “ p j 唧i a j x j z ，x l ，z m ) o ，l ”) j = lj = i 在第m 步的递归方程为： 驰，= 竺“巩m 以蓑； 其中起始条件为： p l ( ：) ：po “。1 lp l ，8 l z b a j ，j = 1 ，n 满足为正整数的条件，由动态规划算法我们得到一个n ( b + 1 ) 维 的矩阵，并依据深度优先原则计算输入值岛( z ) ，( m = 1 ，- ，n ，z = 0 ，b ) 如果得 到最优值r ( b ) 即可得到最优解 2 2 3 凹背包问题的线性逼近 当问题( n k p ) 中的厶，g j 都是非减的凸函数，则原问题是凹背包问题此类问 题首先要线性逼近目标函数，构造一个目标函数是线性函数的凸背包问题下面我 们介绍此问题的线性逼近 2 0 0 6 年上海大学硕士学位论文 1 5 令n ，卢z ”0 蔓! 岛u j ，其中a = ( l ，n 。) ，卢= ( 卢l ，风) 考虑原 问题的子问题： ( s p ) m “m ) = f a j ) j = l s t 9 ( 。) = g j ( x j ) b ， j = l 哟茎z ，曼岛，x i 为整数，j = 1 ，- ，n 则在区间h ，岛】上厶( 叼) 的上逼近凹函数为过两点( 哟，疗( n ) ) ，( 岛，疗( n ，) ) 的一条直 线： 0 ( q ) = f j ( 。j ) 十勺( q 一口，) 其中 勺= 篡 因此，( z ) = 譬，j ( q ) 在箱子b 明的上逼近函数可以写为 nnn l ( z ) = l j ( x j ) = ( 如( q ) 一s j ( ) ) + s j x j 令s o = - ( 矗( ) 一s ，( 哟) ) ，则可以得到子问题( s p ) 的线性上逼近问题 ( l s p ) m a x 工( z ) = s 0 + s j q j = l st 9 ( 。) = 野( 码) sb j = a q q 口j ，x j 为整数，j = 1 ，n 其中s j 是l ( z ) 中z ，的系数，8 0 是l ( x ) 的常数项由于，是非减的函数，所以 s j 0 ，0 = 1 ，) ，又因为l i ( x ，) 是线性函数即凹函数，从而我们知道( l s p ) 是 一个带有线性目标函数的凸背包问题下面就要把( l s p ) 转化成一个等价的o - 1 线 性背包问题来求解事实上，如果矿是( l s p ) 的一个最优解，+ 是原问题的最优 值，则有，( 矿) s ，4 蔓l ( x + ) 即由线j 陛逼近得到的问题的最优值是原问题的一个上 界，将此最优解带入原问题得到原问题的一个下界再利用分枝定界方法逐步缩小 上下界距离，直到找到原问题的最优值 2 0 0 6 年上海大学硕士学位论文 1 6 2 3非线性凸整数规划的分枝定界算法 分枝定界基本思想是根据某种规则将原整数模型的可行域分解为越来越小的子 区域，并检查某个子区域内整数解的情况，直到找到最优的整数解或探明整数解不 存在一般地，一个非线性混合整数规划( n l m i p ) 问题如下形式： ( n l m i p ) m i n ，知) s t g i ( x ) 0 ，i = h k ( x ) = 0 ，k q 为整数，j 1 ， 1 ，e ( 23 1 6 ) 这里f ，g 。是凸函数，h 是线性函数 分枝定界通过松弛整性的条件变成连续最优化问题，从而求得连续问题的一个 全局最优解若这个解为整数，则它为( n l m i p ) 的一个整数解，若不是整数，则至 少有一个变量。，是连续的，可以将z ，的值分为整数部分陋，】和分数部分z ；，即： z j = 扛， + z ；，其中扛，】为整数，0 x ： 1 ，于是形成了两个子问题，每个子问题中 分别增加一个上界约束x ，b 】和下界约束z f f x ， + l ，我们称原问题为父问题， 这种由父问题产生子问题的过程就称作分枝，变量。，为分枝变量，因此求解父问 题的连续松弛转化为求解这两个子问题的连续松弛问题一般地，每个结点的迭代 都给目标函数值提供一个上界和下界，且原问题的下界就是所有子问题中下界最小 的一个，继续进行上面的分枝及求解连续问题的算法，直到我们找到某个连续问题 的一个可行的整数解，则它所对应的目标函数值为问题( n l m i p ) 的目标函数的上 界为防止子问题数目增加太快，我们必须把已经解过出现下列情形之一的子问题 从问题集中删去( 剪枝) ( i ) 子问题不可行；( n ) 子问题的下界比原始问题最优值 的上界要大；( i i i ) 子问题的连续松弛问题的解是整数解这样剪枝以后，原始问题 的最优值的下界就是所有子问题下界中最小的那个另外，分枝定界算法解非线性 凸背包问题( p ) 关键在于求出连续松驰问题的全局最优解下面这些因素也将影响 分枝定界算法的效率：连续松弛问题的求解方法；分枝变量的选取方法；分枝结点 的选取方法 2 3 1 求解连续松弛问题的方法选择 因为连续松弛问题产生的子问题很多，所以提高算法的效率的关键是找到一种 有效的算法来求解松弛子问题对一般的非线性整数规划问题研究表明广义既约梯 2 0 0 6 年上海大学硕士学位论文 1 7 度方法( g r g ) 求解子问题是比较有效的，该方法实现细节可参考 1 7 】 2 3 2 分枝变量的选取 1 选下标最大或最小的变量：若给定的模型中决策变量在实际应用中对应着不同 的重要性，则我们可以根据它们的重要性排序，比如可以假设越重要的变量它 的下标越小，则选下标最小的变量为分枝变量 2 选取离整数最远的变量：选取离整数最远的变量为分枝变量，目的在于使新产 生的子问题能尽早地被剪枝比如可以选分数部分最大或最小的变量为分枝变 量 3 伪成本方法：伪成本方法即建立变量问的某种优先次序，以便于决定哪一个变 量为分枝变量建立变量间的这种次序，就必须考察分枝变量的单位变化所引 起的两个子问题最优值的下降量其中假设是第k 个子问题，z ，为所选择的分 枝变量，。；为变量z j 对应的分数部分，a 为第k 个子问题所对应的目标值， ，凡分别为两个子问题( 连续松弛加上约束条件码b ，】或巧画】+ 1 ) 所 得目标函数值，则x j 的伪成本下界( p c l j ) 及上界嘶) 计算如下： 删，2 警一2 旨 在所有的p c l j 及p c u j 计算出来之前，我们可以一直选取离整数最远的变量为分 枝变量如果考察第s 个结点时，p c l j 及p c u j 都已计算出来，则我们定义q 的 伪成本为： v j = m i n p 吗z ；，p c u j ( 1 一z ；) ) ， j = 1 ，n ( 2 3 1 7 ) 若= 。m a x 。v j 成立，则选x j 。为分枝变量 2 3 3 分枝结点的选取 如果得到了当前子问题( 结点) 的连续松弛问题的最优解，则下一步要考虑的 是应选哪一个结点作为父问题来产生新的子问题，即分枝结点的选取我们知道算 法产生的子问题和分枝树上的结点是一一对应的，每一个子问题都对应着分枝树上 的一个结点选取分枝结点的方法很多，其中主要有： 1 深度优先搜索的方法；也叫后进先出的方法如果当前考虑的子问题没有被剪 枝，则接下来总是选它两个子问题中的一个来产生新的子问题被剪枝时， 我们将沿着从该结点到根结点的路径往回找，直到找一个还未被求解的结点为 2 0 0 6 年上海大学硕士学位论文 1 8 止这种方法一方面可以减少子问题的存储个数，另一方面能较快地找到一个 好的可行解 2 广度优先搜索的方法t 如果定义一个结点的层次为连接该结点与根结点的唯一 路径所含边的数目，则广度优先搜索的方法在考虑下一层次的结点之前，总是 先考虑同一层次上的结点该方法所要存储的子问题个数往往比较多，如果把 它和好的启发式算法相结合也能取到很好的效果 3 最好下界方法；如果当前子问题被剪枝，则下一个要考虑的子问题是子问题集 中下界最小的那个子问题，因为这种结点存在原问题最优解的可能性较大 4 估计法：若v j ( j = 1 ，2 ，- - ，n ) 表示变量的伪成本，p o 表示问题集中未被考察的 子问题个数，表示第m 个子问题的连续松弛问题的最优解，令 n e k = + f y j ，k = 1 ，p o ，( 2 3 1 8 ) j = l 当e b = m a x e ，成立时，则选第k o 个子问题为分枝结点产生新的子问题 在实际问题中，上述方法也可以混合使用例如，把深度优先搜索和最好下界 相结合的方法就有很好的效果这种方法首先选下界最小的子问题进行考虑，如果 该问题没有被剪枝，则接下来总是考虑它的左( 或者右) 子问题当左子问题被剪 枝以后，则再考虑问题集中下界最小的子问题 2 4一般整数规划问题的分枝定界和动态规划混合算法 考虑下面的整数规划问题： ( 6 ) = i n d e x 方( q ) i = 1 m ，n ， ( 24 1 9 ) 其中岛= ( o ，1 ，吩 ，局是正整数，如( ) 是定义在岛上的非降函数，j 1 一佗 这里我们假设下列非负条件成立： b i 0 ，1 i m ， f j ( x j ) 20 ，1 茎j n ，x j 岛， 9 玎( z j ) 0 ，1 i m ，1 j n ，x j 毋 f 242 0 1 ( 242 1 ) ( 2 42 2 ) 魄 1 一 | 1 ) ， j 知 9 。同q cs 2 0 0 6 年上海大学硕士学位论文 1 9 令 k f k ( b ) = m a x 矗( 町) ( 242 3 ) j = 1 m 1 ，一，n ， 表示问题( 2 4 2 3 ) 所有可行解组成的集合的子集如果存在。1 x f 和。2 使得 成立，且至少有一个严格不等式成立，则称。2 被z 1 占优 如果z x f ，且z 不被任何x f 中的可行解占优，则称。为x f 的有效可行 解若把问题( 2 4 2 3 ) 的所有有效可行解记为雄，问题( 2 4 1 9 ) 的所有有效可行解 记为j 焉，则j 皤可以通过下面的递归关系来计算： 础= ( z h，z k _ l z ) t ( z 1 ，z 2 ， ，g k 一1 ) t x - l ，z 女甄) k = ( 础i ( q ) s6 。，i = l ， ，m ) ， j = l 群一 z x lz 是x f 的有效可行解) 由有效可行解的定义可知，如果i 群，且对任意的i = 1 ，2 扁( 声= b ) 成立，则2 就是问题( 2 41 9 )