求解线性双层规划的割平面算法

第十一章 二次规划与割平面法本章主要内容：等式约束二次规划问题的起作用集方法 Wolfe 算法 Lemke 算法 割平面法教学目的及要求：了解等式约束二次规划问题的起作用集方法、Wolfe 算法、Lemke 算法、割平面法。

教学重点：等式约束二次规划问题的起作用集方法． 教学难点：等式约束二次规划问题的起作用集方法． 教学方法：启发式．教学手段：多媒体演示、演讲与板书相结合． 教学时间：2学时． 教学内容：§11.1 等式约束二次规划问题等式约束二次规划问题可表为1min ();2,T Tf x x Qx c x Ax b ⎧=+⎪⎨⎪=⎩s.t. （11.1.1） 其中n n Q R ⨯∈且对称，,,n m m n c R b R A R ⨯∈∈∈且不妨设rank A m n =<．下面介绍求解问题（11.1.1）的两种方法． 一、直接消去法求解问题（11.1.1）最简单又最直接的方法就是利用约束来消去部分变量，从而把问题转化成无约束问题，这一方法称为直接消去法．将A 分解为(,)A B N =，其中B 为基矩阵，相应地，将,,x c Q 作如下分块11122122,,B B N N x c Q Q x c Q x c Q Q ⎛⎫⎛⎫⎛⎫=== ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭，其中11m m Q R ⨯∈．这样，问题（11.1.1）的约束条件变成B N Bx Nx b +=，即得11B N x B b B Nx --=-，代入()f x 中就得到与问题（11.1.1）等价的无约束问题21ˆˆmin ()2T T N N N N N x x Q x c x ϕ=+，（11.1.2） 其中1111222211211ˆ()()T T T T Q Q Q B N N B Q N B Q B N ----=--+， 1112111ˆ()(())T T T T N N B cc N B c Q N B Q B b ---=-+-． 如果2ˆQ 正定，则问题（11.1.1）的最优解显然为12ˆˆN N x Q c -=-，这时，问题（11.1.1）的最优解为1112ˆˆ0B N N x B b B N x Q cx I ---⎛⎫⎛⎫⎛⎫==+ ⎪ ⎪ ⎪-⎝⎭⎝⎭⎝⎭， 记点x 处的Lagrange 乘子为v ，则有()T A v f x Qx c =∇=+，故知11112()()TB NB v B Q xQ x c-=++． 如果2ˆQ 半正定且问题（11.1.2）无下界，或2ˆQ 有负特征值，则不难证明问题（11.1.1）不存在有限解．例1 求解二次规划问题222123123123min ();24,2.f x x x x x x x x x x ⎧=++⎪+-=⎨⎪-+=-⎩s.t. （11.1.3） 解 将约束写成12312324,2.x x x x x x +=+⎧⎨-=--⎩ 用高斯消元法求得132312,233x x x x =-=+， （11.1.4）代入()f x 中可得等价的无约束问题2333148min ()493x x x ϕ=++， 其中228ˆ9Q ⎛⎫= ⎪⎝⎭显然正定，故令3()0x ϕ∇=，求得367x =-，代入（11.1.4）式中得12210,77x x ==．因此，问题（11.1.3）有唯一的最优解1232106(,,)(,,)777T T x x x x ==-．再利用T A v Qx c =+即12112002/72102010/7110026/7v v ⎛⎫⎛⎫⎛⎫⎛⎫ ⎪ ⎪⎪-= ⎪ ⎪ ⎪⎪⎝⎭ ⎪ ⎪⎪--⎝⎭⎝⎭⎝⎭， 可求得1284,77v v ==-．直接消去法思想简单明了，使用方便．不足之处是B 可能接近一个奇异方阵，从而引起最优解x 的数值不稳定． 二、Lagrange 乘子法求解问题（11.1.1）的另一种方法是Lagrange 乘子法．问题（11.1.1）的Lagrange 函数为1(,)()2TT T L x v x Qx c x v Ax b =+--． 令(,)0,(,)0x v L x v L x v ∇=∇=，得到K-T 条件0,0T Qx c A v Ax b +-=-=，写成矩阵形式，有0T x c Q A v b A ⎛⎫-⎛⎫⎛⎫=- ⎪ ⎪ ⎪-⎝⎭⎝⎭⎝⎭， （11.1.5）其系数矩阵称为Lagrange 矩阵，它是对称的但不一定正定． 若上述Lagrange 矩阵可逆，则可表为10T TH R Q A R G A --⎛⎫-⎛⎫= ⎪ ⎪--⎝⎭⎝⎭， （11.1.6） 从而，由（11.1.5）式可得问题（11.1.1）的最优解,.Tx Hc Rb v R c Gb =-+⎧⎨=-⎩（11.1.7） 当1Q -存在时，由（11.1.6）式可得H 、R 、G 的表达式为11111()T T H Q Q A AQ A AQ -----=-，111()T T R Q A AQ A ---=，11()T G AQ A --=-．下面给出x 和v 的另一种表达式．设0x 是问题（11.1.1）的任一可行解，即0Ax b =，在点0x 处目标函数的梯度00()f x Qx c ∇=+，则（11.1.7）式可改写为000(),().Tx x H f x v R f x =-∇⎧⎪⎨=∇⎪⎩（11.1.8） 例2 用Lagrange 乘子法求解问题222123312123123min 22;4,2 2.x x x x x x x x x x x x ⎧+++-⎪++=⎨⎪-+=⎩s.t. （11.1.9） 解 易知22001114240,0,,21120021Q c A b -⎛⎫⎛⎫⎛⎫⎛⎫ ⎪ ⎪=-=== ⎪ ⎪ ⎪ ⎪-⎝⎭⎝⎭ ⎪ ⎪⎝⎭⎝⎭．显然，Q 可逆且111/201/21/20001/2Q -⎛⎫⎪= ⎪ ⎪⎝⎭，因此按上述,,H R G 的表达式可得51/21/43/43/43/4344421/41/83/8,7/41,511111133/43/89/81/41/42H R G ⎛⎫-⎛⎫⎛⎫- ⎪ ⎪ ⎪=-=-=-⎪ ⎪ ⎪ ⎪ ⎪ ⎪--- ⎪⎝⎭⎝⎭⎝⎭， 从而，问题（11.1.9）的最优解为21433(,,)112222Tx Hc Rb =-+=．§11.2 起作用集方法考虑具有不等式约束的二次凸规划问题1min ();2,T T f x x Qx c x Ax b ⎧=+⎪⎨⎪≥⎩s.t. （11.2.1） 其中n n Q R ⨯∈且对称正定，,,n m m n c R b R A R ⨯∈∈∈且不妨设rank A m =．运用起作用集方法的关键是，在每次迭代中，都以已知的可行点为起点，把在该点起作用的约束作为等式约束，而把在该点不起作用的约束暂时去掉不考虑，在新的约束条件下极小化目标函数，求得新的比较好的可行点后，再重复以上步骤．这样，可把问题转化为有限个仅带等式约束的二次凸规划来求解．具体分析如下：设在第k 次迭代中，已知可行点k x ，在该点起作用的约束指标集用k I 表示．这时需要求解等式约束问题min ();,,Ti i k f x a x b i I ⎧⎨=∈⎩s.t. （11.2.2） 其中i a 是矩阵T A 的第i 列元素构成的n 维向量．为方便起见，现将坐标原点移至k x 处，令k k d x x =-，则1()()()()2T T k k k k k k f x d x Q d x c d x =++++ 1122T T T T T k k k k k k k k d Qd d Qx x Qx c d c x =++++ 1()()2T T k k k k k d Qd f x d f x =+∇+． 于是，问题（11.2.2）转化为求校正量k d 的问题1min ();20,,T T k k k k T i k k d Qd f x d a d i I ⎧+∇⎪⎨⎪=∈⎩s.t. （11.2.3） 用11.1节解等式约束的二次规划问题的方法求解问题（11.2.3），其最优解仍记为k d ．根据不同情形，采用下列相应的步骤：（1）若k k x d +是可行点且0k d ≠，则在第1k +次迭代中，取迭代点为1k k k x x d +=+．（2）若k k x d +不是可行点，则取搜索方向为k d ，并令1k k k k x x d λ+=+，其中k λ为步长．按保持可行性的要求，步长k λ的取值应使得对于任意k i I ∉都有()T i k k k i a x d b λ+≥． （11.2.4）由于k x 是可行点，T i k i a x b ≥，因此当0T i k a d ≥时，对任意的非负数k λ，（11.2.4）式总成立；在第1k +次迭代中，取迭代点为1k k k x x d +=+．当0T i k a d <时，只要取正数min ,0TTi i k k k i k T i k b a x i I a d a d λ⎧⎫-⎪⎪≤∉<⎨⎬⎪⎪⎩⎭，则对于每个k i I ∉，（11.2.4）式总成立．为了在第k 次迭代中得到较好的可行点，应进一步取min{1,}k k λλ=，其中k λ为上式的右端项．若存在k p I ∉使得1T p p kk T p kb a x a d λ-=<，则在点1k x +处有1()T T p k p k k k p a x a x d b λ+=+=．这说明，在点1k x +处，T p p a d b ≥为起作用约束．因此，应把指标p 加入点1k x +处的有效约束指标集1k I +中，即令{}1k k I I p += ．（3）若0k d =，则k x 为问题（11.2.2）的最优解．下面，进一步判断k x 是否为问题（11.2.1）的最优解．为此，需用公式（11.1.8）计算出所有起作用约束的Lagrange 乘子(),k i k v i I ∈．若()0,k i k v i I ≥∈，则k x 是问题（11.2.1）的K-T 点，又由于问题（121.2.1）是凸规划，因此k x 就是其最优解；若存在k q I ∈，使得()0k q v <，则k x 不可能是问题（11.2.1）的最优解．因为可以验证，当()0k q v <时，在点k x 处存在可行下降方向．因此，取()()min{|}k k r i k v v i I =∈，并令{}1\k k I I r +=，再解问题（11.2.3）． 算法11-1（起作用集法）Step1 选取初始数据．给定初始可行点1x ，相应的起作用约束指标集为1I ，令1k =．Step2 求解等式约束问题．求解问题（11.2.3），设其最优解为k d ．若0k d =，则转Step4 ；否则，令1min{1,},k k k k k k x x d λλλ+==+，计算1()k f x +∇，转Step3．Step3 修改起作用约束指标集．若1k λ<，则令{}1,:1k k I I p k k +==+ ，返回Step2；若1k λ=，则令:1k k =+，转Step4．Step4 检查是否满足终止准则．用公式（11.1.8）计算出所有起作用约束对应的Lagrange 乘子(),k i k v i I ∈，记()()m in {|}k k r i k v v i I =∈．若()0k rv ≥，则迭代终止，k x 为约束问题（11.2.1）的最优解；否则，从k I 中删除指标r ，返回Step2．§11.3 Wolfe 算法考虑二次凸规划问题1min ();2,0,T Tf x x Qx c x Ax b x ⎧=+⎪⎪=⎨⎪≥⎪⎩s.t. （11.3.1） 其中Q 为n 阶半正定矩阵，,,n m m n c R b R A R ⨯∈∈∈且不妨设rank A m =．易知，问题（11.3.1）的形式并不失一般性．首先研究一下问题（11.3.1）的最优性条件．问题（11.3.1）的最优解x 为K-T 点，即存在,v u 使得,,0,0,0.T TQx A v u c Ax b u x u x ⎧--=-⎪=⎪⎨=⎪⎪≥≥⎩（11.3.2） 若把（11.3.2）式中的非线性部分T u x 作为目标函数，（11.3.2）式中的线性部分作为约束条件，则可得到具有线性约束的非线性最优化问题min ;,,0,0.T T u x Qx A v u c Ax b u x ⎧⎪--=-⎪⎨=⎪⎪≥≥⎩s.t. （11.3.3） 设x y v u ⎛⎫ ⎪= ⎪ ⎪⎝⎭是问题（11.3.3）的最优解，若满足0T u x =，则其中的x 必为问题（11.3.1）的最优解．因此，问题归结为求问题（11.3.3）的最优解．为了使所有变量都具有非负限制，令v v v +-=-，则问题（11.3.3）中的前两个约束条件成为000T Tn x A v b I Q v c AA u +-⎛⎫ ⎪⎛⎫⎛⎫ ⎪= ⎪ ⎪ ⎪---⎝⎭⎝⎭ ⎪⎝⎭， （11.3.4） 后两个约束条件成为0,0,0,0x v v u +-≥≥≥≥． （11.3.5）要求问题（11.3.3）的最优解，我们将先求（11.3.4）满足式（11.3.5）的基本解，为此特引入人工变量y ．具体步骤如下：（1）先用单纯形法的第一阶段法求得满足,0Ax b x =≥的解，记所得解的基变量为B x ，非基变量为0N x =．（2）确定对角阵()j ij E δ=∆，其中j ∆为1或1-，ij δ满足1,,0,.ij i j i j δ=⎧=⎨≠⎩其意义是：在（11.3.4）式中引入人工变量y 后得到0000T Tn x vA b v I Q E c AA u y +-⎛⎫⎪ ⎪⎛⎫⎛⎫⎪= ⎪ ⎪--- ⎪⎝⎭⎝⎭ ⎪ ⎪⎝⎭， （11.3.6）且当x 用（1）中求得的解代入时，若0v v u +-===，则必有0y ≥．记（1）中A 的分解为(,)A B N =，其中B 为可行基．相应地，将Q 分解为(,)B N Q Q Q =，则E 应满足B B Q x Ey c +=-， （11.3.7）且其中的人工变量12(,,,)T n y y y y = 非负．记B Q 中的列向量依次为12,,,m q q q ，则（11.3.7）式等价于(),1,2,,T j j j j B y c q x j n ∆=-+= ． 因此，E 中j ∆的选取规则为1,0,1,0.Tj j B j Tj j B c q x c q x ⎧-+>⎪∆=⎨+≤⎪⎩ （3）在约束（11.3.6）式和约束0,0,0,0,0,0T x v v u y u x +-≥≥≥≥≥= （11.3.8）下极小化线性目标函数1ni i y =∑．对于上述线性规划问题，可采用单纯形法求解．但必须注意，进行旋转变换时，要求0T u x =，即当某个0j x >时，j u 不允许进入基变量．旋转变换直到10nii y==∑时结束，此时得到的x 即为二次凸规划问题（11.3.1）的最优解．例3 用Wolfe 算法求解二次凸规划问题21211231241234min ()2;236,24,,,,0.f x x x x x x x x x x x x x x ⎧=--+⎪++=⎪⎨++=⎪⎪≥⎩s.t. （11.3.9） 解 易知200020000123106,,,000002220400000Q c A b -⎛⎫⎛⎫ ⎪ ⎪-⎛⎫⎛⎫⎪ ⎪==== ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭ ⎪ ⎪⎝⎭⎝⎭． 首先确定满足,0Ax b x =≥的一个解，显然可取(3/2,1,0,0)T x =，确定()j ij E δ=∆．由于22011003/21000100000B B c Q x -⎛⎫⎛⎫⎛⎫ ⎪ ⎪ ⎪--⎡⎤ ⎪⎪ ⎪+=+=⎢⎥ ⎪ ⎪ ⎪⎣⎦ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭， 故12341,1∆=-∆=∆=∆=，因此1000010000100001E -⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦． 下面，要利用单纯形法在约束（11.3.6）和（11.3.8）下极小化目标函数41i i z y ==∑．表11.3.1中给出了初始数据，为了得到初始单纯形表，表11.3.1的最后一行对应于目标函数z 中变量系数的反号．表11.3.1 例3的初始数据表经过初等行变换，得到以121234,,,,,x x y y y y 为基变量的初始单纯形表11.3.2．表11.3.2 例3的第一轮迭代后的初始单纯形表由于1v -对应的检验数2最大，故以1v -为进基变量，显然，3y 为离基变量，进行{5,7}旋转变换，得单纯形表11.3.3．表11.3.3 例3的第二轮迭代后的单纯形表现在是4x 对应的检验数最大，故以4x 进入基变量取代1y ，进行{3,4}旋转变换，得单纯形表11.3.4．表11.3.4 例3的第三轮迭代后的单纯形表在表11.3.4中，按Dantzig 规则（见算法4-1），下一步应让3u 进入基变量取代2y ，由于30x =，不违反约束330T u x u x ==，故可以进基．进行相应的旋转变换后，得单纯形表11.3.5．表11.3.5 例3的第三轮迭代后的单纯形表从表11.3.5右下角的数值知，此时目标函数410i i z y ===∑，因此，所求的二次凸规划问题（11.3.9）的最优解为(2/3,14/9,0,10/9)T x =．定理11.3.1 若问题（11.3.1）中二次目标函数的Hesse 阵Q 是正定的，则用Wolfe 算法必可求得其最优解，即在条件0T u x =下用单纯形法求解问题1min (11.3.6),(11.3.8)n i i y =⎧⎫⎨⎬⎩⎭∑式式时，必能使1ni i y =∑达到零值．一般来说，当Q 是半正定阵时，Wolfe 算法有失败的可能．这时，可将主对角线上的元素作微小扰动，以Q I ε+（0ε>很小）取代Q 后，再利用Wolfe 算法．§11.4 Lemke 算法考虑二次规划问题1min ();2,0,T Tf x x Qx c x Ax b x ⎧=+⎪⎪≥⎨⎪≥⎪⎩s.t. （11.4.1） 其中n n Q R ⨯∈且对称，,,n m m n c R b R A R ⨯∈∈∈，不妨设rank A m =．引入乘子u 和v ，定义Lagrange 函数(,,)()()T T L x u v f x u Ax b v x =---．再引入松弛变量（向量）0y ≥，使Ax y b -=．这样，问题（11.4.1）的K-T 条件为,,0,0,0,0,0,0,T TT Qx A u v c y Ax b v x y u u v x y ⎧--=-⎪-=-⎪⎪=⎨⎪=⎪⎪≥≥≥≥⎩ （11.4.2） 用矩阵形式表为ˆ,0,0,w Mz bw z ⎧-=⎪⎨≥≥⎪⎩ （11.4.3） 及0T w z =， （11.4.4）其中ˆ,,,0T v x c Q A w z M b y u b A⎛⎫-⎛⎫⎛⎫⎛⎫==== ⎪ ⎪ ⎪ ⎪-⎝⎭⎝⎭⎝⎭⎝⎭．,w z 和ˆb均为m n +维向量，M 为m n +阶矩阵．求满足（11.4.3）式和（11.4.4）式的解w z ⎛⎫⎪⎝⎭的问题称为线性互补问题，（11.4.4）式称为互补条件．显然，（11.4.4）式等价于0,1,2,,j j w z j m n ==+ ． （11.4.4a ）设w z ⎛⎫⎪⎝⎭是线性互补问题的一个解，则由（11.4.4a ）式知，其2()m n +个分量中至少有m n +个分量等于0，而且每个互补变量对(,)j j w z 中至少有一个变量取零值．因此，下面给出互补基本可行解的概念．定义 设w z ⎛⎫⎪⎝⎭是问题（11.4.3）的一个基本可行解，且每个互补变量对(,)(1,2,,)j j w z j m n =+ 中只有一个变量是基变量，则称w z ⎛⎫⎪⎝⎭是线性互补问题（11.4.3）和（11.4.4a ）的一个互补基本可行解，简称CBF 解．这样，求二次规划K-T 点的问题就转化为求线性互补问题的CBF 解．下面，介绍求CBF 解的Lemke 算法．分两种情况讨论：（1）若ˆ0b ≥，则ˆ0w b z ⎛⎫⎛⎫= ⎪ ⎪ ⎪⎝⎭⎝⎭就是一个CBF 解； （2）若ˆ0b ≥/，则引入人工变量0z ，使（11.4.3）式变成00ˆ,0,0,0,1,2,,,j j w Mz z e bz w z j m n ⎧--=⎪⎨≥≥≥=+⎪⎩ （11.4.5）其中(1,1,,1)T m n e R +=∈ ．显然，若0w z z ⎛⎫ ⎪⎪ ⎪⎝⎭是线性互补问题（11.4.4a ）和（11.4.5）的可行解且00z =，则w z ⎛⎫⎪⎝⎭就是所求的CBF 解．为叙述方便起见，我们先引入准互补基本可行解的概念．定义 设0w z z ⎛⎫ ⎪⎪ ⎪⎝⎭是线性互补问题（11.4.4a ）和（11.4.5）的可行解且满足：（1）0w z z ⎛⎫ ⎪⎪ ⎪⎝⎭是（11.4.5）的基本可行解；（2）存在{1,2,,}s m n ∈+ ，使得s w 和s z 都不是基变量；（3）每个互补变量对(,)(1,2,,,)j j w z j m n j s =+≠ 中恰有一个变量是基变量且0z 是基变量．则称0w z z ⎛⎫ ⎪⎪ ⎪⎝⎭是线性互补问题（11.4.4a ）和（11.4.5）的准互补基本可行解，简称ACBF解．下面，用单纯形法求ACBF 解． 首先，若令0ˆˆmax{|1,2,,}0j s z b j m n b =-=+=-> ， ˆˆ0,0sz w b b e ==-≥， 则0w z z ⎛⎫⎪⎪ ⎪⎝⎭是一个ACBF 解，其中()j w j s ≠和0z 是基变量，其余变量为非基变量． 以上述0w z z ⎛⎫ ⎪⎪ ⎪⎝⎭为初始解，用单纯形法求新的ACBF 解，力图通过这种方法迫使0z 变成非基变量．为保证可行性，选择主元时要求遵守下面两条规则：（1）按照单纯形法中的Dantzig 规则确定离基变量（见算法4-1）； （2）若j w （或j z ）离基，则j z （或j w ）进基．这样将实现从一个ACBF 解到另一个ACBF 解的转换，直至得到一个CBF 解即0z 变成非基变量，或者得出由约束（11.4.4a ）和（11.4.5）所定义的可行域无界的结论．下面，给出求CBF 解的Lemke 算法的具体步骤． 算法11-2（Lemke 算法）Step1 若ˆ0b ≥，则停止计算，ˆ0w b z ⎛⎫⎛⎫= ⎪ ⎪ ⎪⎝⎭⎝⎭是CBF 解；否则，用表格形式表示出（11.4.5）式中的第一个约束．记ˆˆmax{|1,2,,}s jb b j m n -=-=+ ， 取第s 行为主行，0z 对应的列为主列，将0z 换入基变量取代s w ，对初始表进行旋转变换后得新表，并令s s y z =，转Step2．Step2 设现行表中变量s y 即变量s z 下面的列为s d ，若0s d ≤，则停止计算，得到问题（11.4.5）的可行域的极方向；否则，按Dantzig 规则确定指标r ，使()()()min 0,1,2,,j s r j s s r j p p d j m n d d ⎧⎫⎪⎪=>=+⎨⎬⎪⎪⎩⎭， 其中j p 为当前表格中右端第j 个元素，即第j 个基变量的当前值，()s j d 为向量s d 的第j 个分量．若第r 行对应的基变量为0z ，则转Step4；否则，转Step3．Step3 这时第r 行的基变量为l w 或()l z l s ≠，将该基变量作为离基变量，sy 作为进基变量，进行旋转变换后得新表。

基于凹性割的线性双层规划全局优化算法赵茂先;宋爱美;王向荣【摘要】A concavity cut is defined by discussing the duality gap of the lower problem of the linear bilevel programming. Based on the feature of the concavity cut, a cutting plane algorithm for solving linear bilevel programming is given. Based on the result that a global optimal solution to linear bilevel programming occurs at an extreme point of its constraint region, the proposed algorithm can obtain a global optimal solution. Finally, a example is given to demonstrate the effectiveness of the algorithm.%通过对线性双层规划下层问题对偶间隙的讨论,定义了一种凹性割,利用该凹性割的性质,给出了一个求解线性双层规划的割平面算法.由于线性双层规划全局最优解可在其约束域的极点上达到,提出的算法能求得问题的全局最优解,并通过一个算例说明了算法的有效性.【期刊名称】《运筹与管理》【年(卷),期】2012(021)001【总页数】5页(P48-52)【关键词】运筹学;割平面算法;凹性割;线性双层规划【作者】赵茂先;宋爱美;王向荣【作者单位】山东科技大学信息科学与工程学院,山东青岛266510;山东科技大学信息科学与工程学院,山东青岛266510;山东科技大学信息科学与工程学院,山东青岛266510【正文语种】中文【中图分类】O221.10 引言在许多系统优化问题中，如城市交通［1］、污染控制［2］和价格制定［3］等实际问题中，系统可能涉及到不止一个决策者，并且不同的决策者具有各自的决策变量和目标函数。

§3割平面法割平面法也是求解整数规划问题常用方法之一。

3.1基本思路用割平面法求解整数规划的基本思路是：先不考虑整数约束条件，求松弛问题的最优解，如果获得整数最优解，即为所求，运算停止。

如果所得到最优解不满足整数约束条件，则在此非整数解的基础上增加新的约束条件重新求解。

这个新增加的约束条件的作用就是去切割相应松弛问题的可行域，即割去松弛问题的部分非整数解(包括原已得到的非整数最优解)。

而把所有的整数解都保留下来，故称新增加的约束条件为割平面。

当经过多次切割后，就会使被切割后保留下来的可行域上有一个坐标均为整数的顶点，它恰好就是所求问题的整数最优解。

即切割后所对应的松弛问题，与原整数规划问题具有相同的最优解。

下面以全整数规划问题的割平面法为例，介绍割平面的求解过程。

3.2求解步骤与举例割平面法的具体求解步骤如下：1.对于所求的整数规划问题(4.2)，先不考虑整数约束条件，求解相应的松弛问题（4.6）2.如果该问题无可行解或已取得整数最优解，则运算停止；前者表示原问题也无可行解，后者表示已求得整数最优解。

如果有一个或更多个变量取值不满足整数条件，则选择某个变量建立割平面。

3.增加为割平面的新约束条件，用前面介绍的灵敏分析的方法继续求解，返回1。

下面介绍割平面的建立方法及其求解过程。

例1 求解下列整数规划问题（4.7）解引入松弛变量，写成标准形式：(4.8)对上述模型不考虑整数条件，用单纯形法求解相应松弛问题的最终单纯形表为（表4-2）表4-215/38/3-13/3显然，为非整数解。

为求得整数解，我们想办法在原约束条件的基础下引入一个新的约束条件，以保证一个或几个变量取值为整数。

为此，在表4-2中任选一个取值非整数的变量，如，写出用基变量表示基变量的表达式：(4.9)将上式的所有变量的系数及右端常数均改写成一个整数与一个非负真分数之和的形式。

据此，(4.9)式可以改写成若将带有整数系数的变量整数项留在方程的左边，其余移到方程的右边，则有， (4.10) 由于要求变量取值为正整数，方程(4.10)的左边必为整数。

割平面法的基本思想割平面法主要用于求解整数规划问题的方法。

1958年由美国格莫理提出。

基本思路是：先不考虑整数性约束，求解相应的线性规划问题。

若线性规划问题的最优解恰好是整数解，则此解即为整数规划问题的最优解。

否则，就增加一个新的约束条件,称为割平面。

割平面必须具有两条性质：（1)从线性规划问题的可行域中至少割掉目前的非整数最优解；（2)不割掉任何整数可行域，然后在缩小的可行域上继续解线性规划问题。

重复以上做法，经有限次切割后，必可在缩小的可行域的一个整数极点上达到整数规划问题的最优解。

混合整数线性规划（MILP）的割平面法通过将整数问题线性松弛为非整数线性问题，并对其进行求解，来求解MILP 问题。

线性规划理论说明，在温和的假定下（如果线性规划存在最优解，并且可行域不包含一条线），总存在一个极值点或顶点是最优的。

检验所获的最优解是否为整数解。

如否，则必然存在一线性不等式将最优点和真可行集的凸包分离。

找到这样的不等式是分离问题，而这样的不等式就是切割。

切割可以被加入到被松弛的线性规划中，使得当前的非整数解对松弛不再可行。

该过程不断重复，直到找到最优整数解。

用于普遍的凸连续优化和变体的割平面法有不同的名称：Kelley 法，Kelley-Cheney-Goldstein 法和捆绑法。

它们常用于不可微的凸最小化问题。

对于这类问题，通常的可微优化的梯度法无法使用，而使用这些方法可以高效地得到凸目标函数及其次梯度。

这种情况最常出现在双拉格朗日函数的凹优化中。

另一种常见情形是Dantzig-Wolfe分解应用于结构优化问题中，这类问题通常有含有指数级变量的表达式。

通过延迟列生成法按需生成这些变量等同于在对应的对偶问题上切割平面。

图1.割平面法例，如上图1，单位立方体与切割平面。

在三节点的旅行推销员问题中，该（弱）不等式表明每次旅行必须连接至少两个点。

2Gomory 切割切割平面法由Ralph Gomory 在19 世纪50 年代提出，用于解决整数规划和混合整数规划问题。

割平面法在纯整数规划中的应用1、摘要：割平面法是整数规划问题中常用的一种重要方法。

割平面法解整数规划问题的基本思路是：首先根据单纯形法，画出单纯形表格,利用迭代法求出不考虑整数约束条件时的松弛问题的最优解，如果得到的解是整数则即为问题的整数解，运算停止。

但是在大多数情况下得到的解不完全是整数，其中会出现非整数的形式，也就是这个松弛问题的最优解中存在某个或者某几个基变量为非整数的形式，这就需要进一步的运算：从最优表格中提取出关于非整数基变量的约束等式，再从这个约束等式出发构造出一个割平面方程添加到原来的约束条件中去，再进行单纯形表格的迭代运算，求出最优解，如果得到的最优解是整数则即为所要求的问题的最优解，运算停止。

如果得到的解仍然不完全是整数，就需要继续进行运算，重复以上步骤，一直求解出满足条件的最优解则运算停止。

这就是割平面法的整数求解的一般步骤。

Cutting plane method which is used in an integer programming problem is a kind of important method. Cutting plane method solution in integer programming problem is the basic train of thought: first according to the simplex method, draw the simplex form, using iterative algorithm to find the integer constraint conditions do not consider the relaxation of the optimal solution of the problem, given the solution is for the problem that is the integer solutions, stop operations. But in most cases thesolution doesn't get completely integer, which could not be the integer form, also is the relaxation of the optimum solution of the existence of a or certain base the variable is not the integer form, this needs further operation: the optimal form from the extract about the base variables the constraint equation integer variables, and again from the constraint equation is constructed on a cutting plane equation added to the original conditions to, and then to simplex form iterative operation, to work out the optimal solution, if we get the optimal solution is required for the integer is the problem of optimal solution, stop operations. If the solution have still not quite integer, it needs to continue operations, repeat the above steps, has been worked out to meet the conditions of the optimal solution is to stop operations. This is cutting plane method of solving the integral general steps.1、整数规划的简要介绍整数规划是指在一类问题中要求其解的全部或者一部分变量为整数的数学规划。