（运筹学与控制论专业论文）混合二次规划的几种定界方法.pdf

v 18 5 0 5 混合二次规划的几种定界方法 摘要 带有01 变量的混合_ 次规划有着十分广泛的应刖前景，但实践中遇到的这 类问题大多是n ph a r d 的。目前，这类问题的求解一股采用的是分支定界方法。 现有的文献中，有关分支定界方法的研究大多致力于0l 二次规划问题。本文把 一些对j 0 1 二：次规划问题有效的定界方法，例如：线性化方法、下界对偶方法 及l a g r a n g e 松弛三种定界方法加以推广到混合规划上去，并提出了利用次梯度 方法训算的次梯度法等方法。本文最后对这些方法的计算结果做了一些泔论。 关键词：混合一：次规划，h a g r a n g e 松弛，线性化方法，下界剥偶方法 分类号：0 2 2 s o m eb o u n d i n ga l g o r i t h mo fm i x e dq u a d r a t i cp r o g r a 删i n g t h em i x e dq u a d r a t i cp r o g r a n h n i n gw i t hz e r o o n ev a r i a b l e s jsw i d e l y a p p i e di np r a c t i c e b u ti t isa l w a y sf o u n dv e r yd i f f i c u l tt ob es o l v e d b e c a u s et h ec o m p i e x i t yo fitisn p h a r d n o ww eu s et h eb r a n c ha n db o u n d i n g a l g o r i t h mt os o lv ei t int h em o s to c c a s i o n s ，a n di nt h e p a s ta r t ic 1e s ， t h e r ea r eal o to fr e s e a r c h e so fo - 1 q u a d r a t i cp r o g r a m m in g i nt h i st h e s i s ，w es t u d i e dt h e b o u n d i n ga l g o r it h m s f o r0 1 q u a d r a t i cp r o g r a m m i n g ，i i n e a r i z a t i o n ，f l o o r d u a la n dl a g r a n g em e lh o d a n de x t e n d e dt h e mt nm i x e dq u a d r a t icp r o g r a m m i n g a tl a s tw ed is c u s s e d t h ee f f e clo ft h e s ea l g o r i t h m s k e yw o r d s ：m i x e dq u a d r a t i cp r o g r a m m in g ，l a g r a n g er e l a x a t i o n ， l i n e a r iz a t io n f 1o o rd u a l i n d e x ：0 2 2 iiiii1 i liiilili【0l 1 引言 0 1 规划问题及o l 混合规划问题是运筹学中一个基本的问题，从以往的各 类文献中可以知道，大量的组合问题可以用含有o 1 变量的二次规划形式来表 示，例如最大割问题( m a x c u t ) ，简单选址问题( s i m p l ep l a n tl o c a t i o n ) ，二次 分配问题( q u a d r a t i ca s s i g n m e n t ) ，集合划分问题( s e t p a r t i t i o n ) 等都可以自然 的用o 一1 二次规划问题解决【2 3 1 。o - 1 二次规划在工业生产中与经济生活中也有 着广泛的应用。 本文研究这类问题，主要出于以下几个动因： 首先，从应用角度来说，许多实际问题可以归结成0 1 二次规划的模型， 例如下文中所示的两个例子：最大割问题和带基数约束的投资组合有效集问 题。它的解决直接影响了生产效益，速度等重要因素。 其次，0 1 规划的有效解决是更广泛的整数规划问题的基础。例如十分常见 的t s p 问题在神经网络算法中就被写成如下的o l 二次规划问题的形式。 再次，由于o 1 二次规划问题一个n p h a r d 的问题，至今为止一直是运筹 学中一个挑战性的问题，许多的研究致力于此以期对算法加以改进。 1 1 关于0 - 1 二次规划的一些例子 1 1 】最大割问题 设g 是一个无向图，其点集为v = 1 ，2 ，3 ，n ) ，边集e 中的每条边赋权 为 c c i e e ( g ) ，从而该图的关联矩阵为a = ( 8 0 ) ，其中a i j = c 。，e e ( g ) ，否则a i j = 0 。 最大割问题要求把点集v 分成两部分s 和v s ，并最大化该分割的割集边 上的权数之和，即： m a x a n( 1 1 ) l ，j j s v ( 1 2 ) i s ，j g s( i 3 ) 若将一种分割用一个向量x 一1 ，+ 1 ) “来表示，其中x i = 1 表示点i 属于s ， x = 1 表示点i 属于v s ，记l = d i a g ( a e ) a 4 ，e = ( 1 ，1 ，l - 一，1 ) 7 ，从而可以将以 上的最大割问题化成如下的o 1 二次规划问题： m a x x s t l x s( 1 4 ) s t x 。 一1 ，+ 1 ”( 1 5 ) 这罩的每个x 。就对应了一种分割( s ，v s ) 。 注意到这里的变量取值为1 和+ 1 ，而非0 和1 ，本文将在下文给出0 - 1 二 次规划与 + 1 ，1 ) 二次规划之间的转换形式，说明它与二次o l 规划是等价的。 更广泛的结论是任何的二次布尔规划都可以等价的化成0 - ! 二次规划的形式 。 1 1 2 旅行售货员问题的0 - 1 二次规划表示 一个旅行售货员从某个城市出发，去其他各个城市推销商品，然后返回其 出发城市。若已知各城市问往来所经历的路程长度，旅行售货员问题就是要求 一条路线，使得每个城市都恰好访问一次，并且总共走过的路程最短。我们用 y i j = 1 表示第i 步售货员所在的是第j 个城市( 这里假设，第n + l 步所到的城市 就是第一步所到的城市) ，a j k 表示第j 个城市和第k 个城市间的距离。并加以 约束式保证每一步经过且只经过一个城市和每一个城市经过且只经过一次。从 而得到以下的0 1 二次规划问题： n nn r a i n ( y o 。y ”1 ) k a j k ) i ：l j = tk = l s t y # = 1 y a = 1 y “= 0o r 1 ( 1 6 ) ( 1 7 ) ( 1 8 ) ( 】9 ) 由于上式是一个带约束的离散的规划问题，那么在神经网络算法中通过如 下加入惩罚函数的方法将它变成一个无约束的连续函数规划问题： min艺芝(y。y(。ajk)+p(yi一1)2+(yii)2n n n ) nn n n 1 2 1 j 2 1 。2 1j 2 1 1 2 2 1 2 l f 1 1 0 1 + q ( y 。y 。+ y 。yk j ) s t y 。0i ，j = 1 , 2 ， n ( 11 1 ) 上式中，第一项即为原先的目标函数。第二项表示每一行和每一列中的各 个数之和为1 ，第三项表示每一行和每一列中至多只有一个非。项。两个惩罚 数p ，q 取值应尽量大，以保证求出的最优解中原函数的后两项取值为o 。取 利用神经网络算法尽管对这类问题可以求解到上千个点，然而由于在其实 际求解过程中往往是通过下降叠代算法求得一个极小解，而不是求出全局最优 解，而且从上式可以看出，上述0 - l 二次规划( 1 6 ) - ( 1 9 ) 中的任何一个可行解都 是无约束连续规划问题( 11 0 ) ( 1 1 1 ) 的极小解。所以说能否有效的解决o 一1 二次 规划成为这类问题计算过程中的关键。 1 1 3 带基数约束的投资组合问题( c a r d i n a t i o n a l - c o n s t r a i n e dq u a d r a t i c p r o g r a m m i n g ) 通常的投资组合问题要求在给定的一组投资项目中选择一些进行投资，并 在满足一定的收益要求的前提下使总体风险最小。但在普通的投资组合问题有 效集算法中求出的答案中往往有很多的非。项，这就要求投资者同时管理和关 心很多的项目，耗费大量的人力和物力。但其实很多情况中有些项目并不十分 重要，由此，提出带基数约束的投资组合问题，即要求被投资的项目数不得超 过一个即定的范围k ，那么问题可以写成如下的形式： r a i n x o x s t t x ，= 1 ( 1 1 2 ) ( 1 1 3 ) 曩r 1 1 4 x y ( i 1 5 ) 善y = k ，y = o 训 (116)-i -”， 这里通过0 - 1 变量y 。保证了非0 的投资分量x i 不超过k 个，从而达到减少投资 项目的目的。 1 2 历史文献介绍 1 2 10 - 1 二次规划的复杂性 尽管二次规划问题被k o z l o v ，t a r a s o v 和h a c i j a n 证明为是多项式时间内可 解的简单f q 题 1 5 l ，但是对于非连续取值的二次规划问题却并非如此，g a r e y a n d j o h n s o n ( 1 9 7 9 ) 首先证明了o l 二次规划问题是一个n p c 的问题【1 7 】。 因为o 1 二次规划是一个难问题，所以为它找到一个有效的算法几乎是不 可能的，那么实际应用中我们会常常会考虑寻找一个近似解代替，然而不幸的 是，即使只是很弱的要求，m i h i r b e l l a r e ，p h i l l i p r o g a w a y ( 1 9 9 5 ) 证明了对于 凸胞体内离散变量的多项式最大化问题，不存在有效的算法可以保证求出的近 似解与最优解之间的比值在所要求的比例之内，即使这里的多项式仅仅是二次 的，除非所有n p 问题都可以在准多项式的时间内求解。即一般不会找到一个 0 1 二次规划或混合二次规划问题近似解的有效算法【1 4 1 。 1 2 2 关于0 - 1 二次规划问题的近似解 c a r r a r e s i ，p 、m a l u c e l l i ，f 和p a p p a l a r d o ，m ( 1 9 9 5 ) 证明，如果原问题是n p h a r d 的，那么要检验其某个解是否为最优解也决不会比解决原问题更为简单，即检 验一个n p h a r d 问题的可行解是否为最优解也是n p h a r d 问题【2 j 。进而，根据 h i r r i a r t u r r u t y , j b 对凸集上凸二次规划最大化问题的最优解的研究结果t s , 9 】， c a r r a r e s i ，p 、m a l u c e l l i ，f 和p a p p a l a r d o ，m 给出了检验某可行解是否为e 最优解 4 的充分和必要条件1 4 i 。所谓e 一最优解是其目标函数值与最优值之间至多相差 的解。并且在他们的文章中给出估计某个可行解与最优解之间近似程度的方 法。 尽管如此，寻找一些特殊的n p h a r d 问题的计算速度较快的近似算法仍然 是有意义的。g o e m a n sa n d w i l l i a m s o n 和f r i e z ea n dj e r r u m 就边代价非负的最大 割问题提出一个近似算法，并证明其结果与最优解之间的近似比小于 1 - 08 7 8 5 6 1 5 , 7 1 。这里的近似比定义为：近似解目标函数值和最优值之差与最优 值和最劣值之差的比值。 1 2 3 0 - 1 二次规划问题的一些其他形式 y i n y u y e 证明，对于如下的二次规划问题 m a x 卅( x ) = x 7 0 x n “。；= b 。， i = l ，2 ，聊 j = l e x e ( 1 1 7 ) ( 1 1 8 ) ( 1 1 9 ) 可以找到一个近似比为4 7 的多项式算法。当m = n ，a i j = 6u ，b f l 时，上述规 划等价于一个无约束的o 一1 二次规划问题。 对于o l 二次规划问题的另一种推广，如下式： m i n q o ( x ) s t 一q ，( x ) s 0i = 1 , 2 ，m ( 1 2 0 ) ( 1 2 1 ) q ( x ) = i 1 + - - i - 1 ，2 ，m ( 1 2 2 ) 其中，a o 为一个n 阶的对称方阵，a i 为n 阶的对称正定阵，i = l ，2 ，m ，r 。 为一个小于0 的实数。x , b i 属于全空间。在l et h ih o a ia n 的文章中给出了两 中解法，一是凸函数差分算法( d i f f e r e n c eo f c o n v e xf u n c t i o n sa l g o r i t h m ) 算法， 其主要工具是凸规划中的投影梯度法和近似点算法。另一种是使用l a g 砌g e 对偶定界法的分支定界算法。d c a 方法被p h a md i n h 于1 9 8 6 年首先提出【2 0 】。 另外，可将无约束0 - 1 二次规划推广，为如下的形式： r a i n x 1 q x( 1 2 3 ) s t x 2 f ( 1 2 4 ) 其中，x 2 = ( x ；，。2 ，x ：) 7 。 ( 1 2 5 ) 当f = ( 1 ，l ，1 ) 7 时，这等价于无约束的o - 1 二次规划问题。s h u z h o n g z h a n g 在他的文章中利用半定松弛对这类问题进行了讨论，指出这其中一类特 殊的问题，利用半定松弛可以得到一个多项式时间的算法。并且利用半定松弛 可以将g o e m a n sa n dw i l l i a m s o n 的结果推广，指出对于一类n p h a r d 问题，利 用半定松弛的方法可以得到一个近似比小于( 1 - 0 8 7 8 5 6 ) 的近似算法，这一数 值与g o e m a n sa n dw i l l i a m s o n 的文章中相同【2 5 1 。 最后，对于二次o - 1 规划问题，若其二次导数矩阵q 中的所有元素都非负， 则这类问题可以在多项式时间内解决。i 1 1 关于半定松弛的方法今年来是一个十分热门的话题，我们可在 1 9 】，【2 8 】 中大致了解，并可由v a n d e n b e r g h e l 的文章看到其对半定规划应用的一个全面 的介绍1 2 9 】。 1 3 本文思路 在实际的生产、生活中混合规划有着十分广泛的应用前景，例如前文所述 的带基数约束的投资组合问题，对这类问题的解决将带来十分显著的效益和效 率。在过去的文献中，大多数的学者致力于0 1 二次规划问题的研究，而对于 混合规划问题却少有见诸文献。本文把一些曾对于o 1 二次规划问题有效的定 界方法推广到混合规划求解上去，并对这些计算方法效果做了一些讨论。 在本文中，首先阐述了计算0 i 二次规划问题所用到的一类基本的计算精 确解的方法分支定界法，以及常用的定界算法l a g m g e 乘子法。 其次本文将在0 - l 规划中起定界作用的线性化方法，下界对偶法及l a g r a n g e 乘子法三种方法推广到混合规划上去，提出了次梯度方法计算的下界对偶法。 2 求解0 1 规划问题的基本方法分支定界方法 由于0 - 1 二次规划问题一般是n p h 的，不可能找到好的有效的算法，所以 只能采用枚举法来解决这类问题，然而枚举法所产生的巨大的计算量成为实际 处理过程中无法克服的困难。为了尽量提高计算的效率，如何减少枚举的次数 是一个很关键的问题，现在一般在编程中采用分支定界方法求解0 一l 二次混合 规划问题，该方法由b a l a s 和d a k i n 提出【l 5 i ，通过对某些子问题的定界的手 段删除一些没有必要进行枚举的分支，从而达到有效提高计算效率的目的。有 关分支定界算法的思想在c a t e r 的文章中有详细的介绍1 1 8 j 。 2 1 分支定界方法的原理 以下是关于分支定界方法原理的一个简单的介绍： 对于最优化问题 m i n f ( x )( 2 1 ) s t g ( x ) 0( 2 2 ) x 。= 0o r l ( 2 3 ) i = 1 , 2 ，- - ，p n 为了避免枚举法所带来的计算量的指数增长的困难，将整个可行集f 分成 f = f iu f 2 ，f l = x l = 0 ) 7 1 f , f 2 = x i = i ) n f 。显然f ( x ) 在f 中的最优解不是在f l 中 就是在f 2 中。 假设已找到f 2 中的最优解x + ，其函数值为z ( x + ) ，这时还剩下f l 中的解未 被考虑。 通过下文中所提到的几种算法对f l 中的子问题进行定界，可能发生如下的 几种情况： ( 1 ) 无解 ( 2 ) 其下界大于z ( x + ) ( 3 ) 定界过程中正好得到了f l 的最优解 ( 4 ) 其下界小于z ( x + ) 对于第一种情况，整个f l 中都不存在可行解，所以可将之删除，从而问题 得到解决。对于第二种情况，f i 中f ( x ) 的下界大于f 2 中已经得到的目标函数值， 所以最优解不可能出现在f i 中，也可以将该分支删除。对于第三种情况，则正 好得到了f 。中f ( x ) 的最优解，那么只须将之与f 2 中已经得到的最优解加以比 较就可得到原问题的解。总之，对于前三种情况，问题都已经被解决，只有当 发生第四种情况时，才须要对f t 进行继续计算。这种做法大大的减小了计算量， 提高了计算效率，在实际应用中取得了很好的效果。 但是由于分支定界实际上仍是一种枚举法，在应用中我们经常要决定如何 进行分支以得到可比较容易计算的子集。 同时，定界的方法也十分重要，如果定得好，离真实的最优值充分靠近， 算法将删去很多不必要的计算分支，具有很高的计算效率。二则可以借此知道 某一个可行解离最优解还差多少，是否是可以接受的近似解。本文以下的部分 将对定界方法加以详细的讨论。 2 2 定界的基本方法l a g r a n g e 松弛及l a g r a n g e 乘子问题3 2 为了描述l a g r a n g e 松弛方法的过程，考察以下的最优化问题： m i n f ( x ) ( p )s t g ( x ) 0 x x 该模型的决策变量x 被限制在一个可行集x 内。 ( 2 4 ) ( 2 5 ) ( 2 6 ) l a g r a n g e 松弛方法将放松一些约束条件，对刚才的问题( p ) ，我们松弛掉 困难约束g ( x ) ，并将之乘以系数u 加入到原问题的目标函数上去，所得到的新问 题是： ( l p ) r a i n f ( x ) + u t g ( x ) s t x x 将( l p ) 称之为l a g r a n g e 子问题。并设 l ( u ) = m i n f ( x + u t g ( x ) l x e x ( 2 7 ) ( 2 8 ) ( 2 9 ) 9 为l a g r a n g e 函数。由于去除了一些约束条件，所以l a g r a n g e 子问题的解未必 是原问题的可行解。 引理2 1 ：对任意的乘子u - 0 ，x x - 0 ，x x 证毕。 ( 2 1 0 ) ( 2 1 1 ) 性质2 2 ( 弱对偶) ：由刚才的引理可知l a g r a n g e 子问题的值l ( u ) 是原问题最优 值z + 的一个下界，从而有下式成立： l ( u ) z + f ( x )( 2 1 2 ) 该性质体现了l a g r a n g e 方法的一个优点：它可以确认一个可行解x 是否是最优 解，并且可在l ( u ) 0 ，并在 该方向上迈出足够小的一步0 ，即将x 变成x + 0d ，这样将使目标函数上升， 这类方法在非线性问题中称为梯度法。 在这里0 为步长，表示u 在该梯度方向上移动的长度。根据次梯度的定义， u 的变化与g ( x ) 有如下的关系： g 。( x ) = o 则固定u 的第i 个分量 g i ( x ) o 则增加u 的第i 个分量 若取u o 为初始点，根据u k + i = u 。+ 0g ( x 。) 这一递推公式，依次决定各u 。，x 。 为u - u 。时的l a g r a n g e 子问题的最优解，0 。是第k 步时迈出的步长。 为了保证解决l a g r a n g e 乘子问题，最终求出其最优解，步长应具有以下的 一些性质：， l 、0 。一o ，以保证最后的收敛性 2 、0 。一。以保证能走到最优解 例如0 = 1 k 如前所述，当对不等式约束问题使用l a g r a n g e 方法时，l a g r a n g e 乘子u 被限制为非负，但是递推式u k + l = u 。+ og ( x 。) 有时会使得u 的若干分量取负值， 为了避免这种情况的发生，我们重新定义递推式如下： u k + 1 = u k + 0g + ( x 。) ( 2 2 0 ) g + ( x ) 表示只取g ( x ) 的正分量，负分量用0 来代替而所得的向量。即在递推 公式得到负分量时简单的用0 代替。 2 4 牛顿法解l a g r a n g e 乘子问题 在非线性规划中有一种称之为牛顿法的叠代求解方法，其原理大致如下： 设在第k 步叠代中，若x 。是l ( u 。) 的解，在这一方法下，如果希望最好的 情况发生，即只通过一次叠代，算法就得到了l a g r a n g e 乘子问题的最优解l ， 可以写成下式： f ( x 。) + u 。+ 1 9 ( x 。) = l + ( 2 2 1 ) 又由叠代公式u k + l = u 。+ 0 。g ( x 。) ，推导出： f ( x 。) + u 。+ o 。g ( x 。) g ( x 。) = l + ( 2 2 2 ) 从而解得： 扎群i 。( x k 亿2 3 ， j) r 但是由于其实事先并不知道l ，所以计算中常用一个l + 的上界u b 来近 似代替它，即： 扎i g ( x 斧 2 4 ， 1w 在该表达式中，u b 为l 的上界， 。一般取为0 到2 之间的一个比例。 有时我们取u b 为( p ) 的一个可行解对应的目标函数值，在问题处理的过 程中，若产生了另一个更接近l 的上界，则进一步替代之。通常一开始取 。= 2 ，并依次减小。实际工作中一般不论是否找到最优解，而是运行一确 定步数后终止了该项处理。 2 5 l a g r a n g e 松弛与混合规划 如前所述，l a g r a n g e 松弛可以用于求出最优化问题的一个下界。如果将这 种想法应用于混合规划中，松弛掉整数约束，得到一个连续性的规划问题，这 可能是另一种得到问题下界的方法。这其实是给出了求解整数规划问题的另一 条途径，我们可以松弛一部分整数约束，利用次梯度方法解一系列松弛后的连 续性规划问题，大多数情况下原问题比松弛后的问题要难许多。 、 3 求解0 1 二次混合规划的几种定界算法 在实际的生产、生活中混合规划有着十分广泛的应用前景，例如前文所述 的带基数约束的投资组合问题，对这类问题的解决将带来十分显著的效益和效 率。d o n gs h a w 就曾与美国著名的证券研究机构合作研究了有关基数约束下的 投资组合问题的近似解方法。 过去的文献，较多致力于o 1 二次规划问题的研究，而对于混合规划问题 却没有许多研究。本文把一些对于o 一1 二次规划问题有效的定界方法加以推广 到混合规划上去，并对其计算结果做了一些讨论。 对于变量约束为为f 0 ，l 的混合二次规划问题，设其形式为： m i n f ( x 、= x 7 q x + c 7 x s t a x b x ， 0 ，1 1 ，i = 1 , 2 ，p n ( 3 、1 ) ( 3 2 ) ( 3 3 ) 其中：q 为一任意的n 阶方阵，c ，b 为n 维空间中的向量，a 为m x n 的 约束矩阵。变量中有若干为0 一l 变量。 对于上述o - l 二次规划，通过变量代换y = 2 x e ，e = ( 1 ，1 ，1 ) 7 ，可以得 到如下的( 一l ，+ 1 ) 规划： r a i n f ( x ) = y 7 百y + 6 7 y + a s t 五y 5 y 。 一1 ，+ 1 ) ，i = 1 , 2 ，p n ( 34 ) ( 3 5 ) ( 3 6 ) 其中： 毛= ；g 。，万= 圭爿，石= 三1 ( 8 7 q + c ) ，孑= 百1 ( e 7 q e + 2 e r c ) ，百= 6 一；4 e ( 3 7 ) 显然，通过上述的代换，可以发现这两者是等价的。 下面本文将直接对 0 ，1 ) 规划和 1 ，+ 1 1 规划加以讨论，而不再赘述其两者 之间的差别。 3 1 混合规划最优解的模上界估计 本节中要处理的是如下的混合二次规划问题， 4 m i nx 1 0 x + c t x ( 3 8 ) ( m q p ) s t a x b ( 3 9 ) x o ，1 ) i = 1 , 2 ，p 蔓n ( 3 1 0 ) 其中，定义b = i l i ：l ，2 ，3 ，p ) 为0 - 1 变量的下标集，l 2 i | i p + l ，p + 2 ，n ) 为线性变量的下标集。并按照b 和l 的定义将q 、a 和c 也相应地进行划分： q 橇黜 。1 1 a = ( a 。，a 。) ， ( 3 1 2 ) 桃2 ( 3 1 3 ) 在下面的文章中始终假定q l l 是半正定的，且q 为上半三角阵。 由于下文中需要对规划( 3 7 ) ，( 3 8 ) ，( 3 9 ) 中的线性变量进行处理，这要求所有 的线性变量都处于【o ，1 】区间内，所以本文首先对上述混合规划问题做如下的 转换。 下面的引理3 1 将说明，对于给定的问题( m q p ) ，其最优解的模长具有一个 已。知的匕界。 引理3 1 ：对于任何一个给定的二次规划问题( q p ) 如下，其输入长度为s 则其最优解的模长至多不会超过2 2 8 。 其中， s = s 。+ s ：= 砉l o g ：c la 。f + ，+ 喜l o g ：c | c 。i + ， c 。1 4 ) = 。+ s ：= i ：( 1q “f + 1 ) + ：( | c 。i + 1 ) i ( 3 il ，j = lj = 1j + 芝窆l o g ：( hi + 1 ) + 芝l o g ：( ib ，i + i ) + l o g ：n m + 1 ( 3 1 5 )+ i ：( i a b + 1 ) + ：( i j i z ( 3 1 5 l l _ 1j = l l = 1 j n 为x 的维数，m 为约束个数。 而对于任何一个给定的o - 1 混合规划问题( m q p ) ，在其一组确定的0 1 变量的取值下，对应的其线性变量的二次规划问题的输入长度也不会超过s ， 从而由上述引理可知，对于混合规划的最优解的模长至多不会超过2 2 8 + p 。 由上面的分析知道，一个给定的混合二次规划问题，其解的任何一个分量 x 。，都满足2 2 s + p x 2 2 8 + p ，那么我们就可以通过一组变量代换： 叉。= x ，k + ；，i l ( 3 - 1 6 ) k _ ( 2 2 5 + 1 + 2 p ) ( 3 1 7 ) 使所有的线性变量的取值都处在 o ，1 】内，且对问题的最优解不产生任何影响。 其相应的系数为： 可l l = k 2 q l l ，百b l = k q b l ，可b b = q b b ( 3 1 8 ) 五。= k a 。，五。= a 。 ( 3 1 9 ) i 。= c 。一圭k 4 q 。，- l = k c 。一- ；k 4 q 。( 3 2 0 ) 6 b + ；k a e 。t ( 3 2 1 ) 并在目标函数中另加常数项二k2 e ：q l l e 。一k c 。t 。 f322)4 一一 - 由此，我们将混合二次规划问题转化为如下的标准形式 r a i n x 1 q x + c t x c 呻， 8 。冀u 1 1 b x ， ，廿 x i “0 ，1 】，i l 下面我们就这一标准形式进行讨论。 ( 3 2 3 ) ( 3 2 4 ) ( 3 2 5 ) ( 3 2 6 ) 3 2 将含0 - 1 变量二次交叉项线性化的定界方法 对于一个n p h a r d 的二次规划问题的定界，最容易想到的就是利用已有的 线性问题的处理办法，将0 - 1 二次问题转化为o 1 线性规划问题进行解决。本 文根据h a m m e r 的文章中对0 - 1 二次规划问题所用的方法推广到混合规划中来， 将每一个含0 1 变量的交叉二次项都用一个等价的线性函数来替代，通过松弛 其o l 约束得到一个容易求解的规划，并由此得到一个下界。 具体做法如下： 3 2 1 线性化方法与割平面： 原问题 写成如下形式： m i n x 1 q x + c t x s t a x b x o ，1 ) ，i b x 【o ，1 ，i l m i n q ，x x ，+ q 。x ，x ，+ c 。x ( 1 ，j m l o l( i ，j ) e l o l 卜l s t a x b ( 3 2 7 ) ( 3 2 8 ) ( 3 2 9 ) ( 3 3 0 ) ( 3 3 1 ) f 3 3 2 ) ( 3 3 3 ) f 3 3 4 ) 其中，l o l 表示l 与l 的笛卡儿积。 接下来为了问题处理的方便，对含有0 1 变量的二次交叉项做如下的等价 代换： fq i j x xj = q “x ，xj当q i 0 ，i 0 ，i ( j ，( i ，j ) 硭l o l ( 3 3 6 ) 为了方便起见，定义如下的集合p 和n ， p = ( i ，j ) i 0 ) ( 3 3 7 ) n = ( i ，j ) i i j ，( i ，j ) g l p l q 0 ( 3 3 8 ) 那么原问题目标函数变为： f ( x ) = q i x j x ，+ 【q o x ， ( i j ) e l q( 1 ，j ) e p + ( q ，+ c i ) x + q o x ，x ，+ c x 。 ( 3 3 9 ) i e b ( 1 ，j ) e l o l i e l 由于所有的变量线性x i 都在 0 ，1 x e i n 内，所以我们可以引入一个新的变 量y o 用以代替交叉项x i x j ，从而得到以下的0 - 1 二次规划问题： m i nf ( x ) = q o y + q o x 。一q “y 。】 ( 1 j k n( 1 ，j ) e p + z q “+ c ，) x ，十z q o x ，x ，+ z c x ， ( 3 4 0 ) l e bf 1 t ) e l o li e l s t a x b r 3 4 1 ) b l o o ( x x 雕yo 一 b ，得到如下的l a g r a n g e 乘子问题： m a x ( “) = r a i n 7 q 4 - c7 z + “7 ( a t - 一b )( 3 ，4 8 ) ( l m p ) s t x ， 0 ，1 ) ，i b( 3 4 9 ) 5 f y 蔓0 f 3 5 0 ) 由于上述规划问题中的l a g r a n g e 子问题是一个无约束的二次混合规划问 题，它的求解可以直接化为一个0 1 二次规划问题。虽然这仍是一个n p 难的 问题，但我们可以将l ( u ) 化为o 1 二次规划后用定界的方法求个松弛解x ， 再代入次梯度法的v u = ( a x - b ) 以期求出更好的下界。显然，这样做也得到是原 问题的一个下界。 显然上述做法可以有很多值得改进的地方。m a n n e dp a d b e r g 在他的文章 中研究和讨论了松弛掉0 一l 约束后的线性规划可行域q p l p 与原问题中所有可行 0 1 点的凸包q p “间的关系。文章对一个有1 1 个变量的无约束0 1 二次规划问 题所得的线性规划n ( n + 1 ) 2 维可行点的凸包q p “进行研究，指出q p “共有三类 面存在，而对于松弛掉 o ，1 ) 约束后的线性规划可行域q p l p ，其所有极点的任 何一个分量都取值为 0 ，0 5 ，1 ) 之一，并且通过增加上述三类o ( n 3 ) 次割平面 约束可以将其所有的含有分数分量的极点都排除在可行域外【1 3 】。 3 3 下界对偶方法( f l o o r - d u a l ) e l h a m m e ra n dr h a n s e n 在其文章中讨论了0 - 1 二次规划的r o o fd u a l i t y ， c o m p e m e n t a t i o n 和线性化方法三种定界方法【2 2 】，证明了对于无约束的o 1 二次 规划问题，上面三种定界方法所得到的界相同。另外由下界对偶方法可以得到 关于o l 二次规划的p e r s i s t e n c y 性质，该性质可以被用来事先决定0 1 二次规 划中若干变量的值，减少问题计算量。该文被以后的文章多次引用。 本文下面将其无约束二次0 1 规划的定界方法一下界对偶方法推广至o l 混合规划中去。 3 3 1 线性约束仅含连续变量的情况 设混合规划问题如下： m i n x q x + c q x s t a l x l b x e 0 ，1 ) ，i b x 。【o ，l 】，i l ( 3 5 1 ) f 3 5 2 ) r 3 5 3 ) ( 3 5 4 ) 这里我们首先假设所有的线性约束a 。x 。b 只与线性变量部分有关。 对每个含有o - l 变量的交叉项q i j x i x j ，都用一个其下界线性函数来代替它， 在这里，本文只对o l 变量的二次交叉项进行分析，对于线性变量与o - l 变量 的二