有理系数整数线性规划的模式化算法

D0I:10.13374/i.issn1001-053x.1991.01.035 第13卷第4(1)期 北京科技大学学报 Vol.13No.4(1) 1991年7月 Journal of University of Science and Technology Beijing July 1991 有理系数整数线性规划的模式化算法 龚金双·李宗元· 摘要：给出了有理系数整数线性规划的新的改进算法，称为模式化算法。其特点是： 首先将此类规划变换（模式化）为一种特殊类型，然后利用其特殊结构建立改进算法。其 综合了分枝定界法与割平面法，减少了分枝次数，简化了割平面的技巧。 关键词：整数线性规划，模式化，自然割平面 The Modelling Algorithm of Solving Integer Linear Programming of the Rational Coefficients Gong Jinshuang Li Zongyuan.. ABSTRACT:A new algorithm of solving integer linear programming is intro- duced in which the coefficients of the objective function are rational.This algorithm is called the modelling algorithm.In this algorithm,first of all, it can transform (ILP)into a special programming,then solve the special programming using a kind of special algorithm.The basic ideas of the algo- rithm is due to concentrating of the brance-bound and the cutting-plane,but it decreases the number of the branch and simplifies the technique of the cutting-plane. KEY WORDS:integer linear programming,modelling algorithm,natural cut- ting-plane 1990-05-04收稿 ·北京石油管现学院 ··数力系(Deprment of Mathematics and Mechanics) 393

第 卷第 ‘ 嘲 北 京 科 技 大 学 学 报 叭 。 。 年 月 五 。 。 有理系数整数线性规划的模式化算法 龚金 双 ， 李 宗元 ‘ 幸 摘 要 给出 了有 理 系数 整数线 性规划 的新的改进算法 ， 称为模式化 算法 。 其特点是 首先 将 此 类规划 变换 模式 化 为一种特殊 类型 ， 然后利 用 其特殊结构建立 改 进 算 法 。 其 综合 了分枝定 界法与割 平面法 ， 减少 了分枝次数 ， 简化了割平面 的技 巧 。 关键词 整数线 性规划 ， 模 式化 ， 自然割 平面 夕 ” 夕 夕夕 二 。 ， ， 扭 ， 。 一 一 ， 一 ， ， 一 一 一 魂收稿 北京石油管理学 院 数 力系 旧 爪 皿 DOI ：10．13374／j ．issn1001－053x．1991．04．035

近年来，在传统的分枝定界法与割平面法〔1)的基础上，陆续产生了许多改进算法。 本文对如下的有理系数整数线性规划(RIP)提出了一种新的改进算法，称之为模式化算 法： MinCrx (Ax≤b (RIP) (x,取整数 (1) j=1.2……n 其中Cr=(C:,C2…C)C,为有理数 j=1,2…n x=(x1,x2,.)T,b=(61,b26)T A为m×n矩阵 此算法的基本构思是：通过变换将(RIP)化为一种特殊形式的整数线性规划(MIP) MinC,y (MIP) JBy≤b (2) y,为整数 j=1,2…n 其中，C,为C的某一分量，不失一般性，可假定C,>0,B为m×n矩阵，B与A的关系 见定理1多y=(y1,y2…y.)「。 然后，建立求解具有特殊结构的(MIP)的算法。值得注意的是，由于在计算机上求解一 般整数线性规划时，如遇到无理数，均用有理数来近似。所以，本文的方法实际使用范围相 当广泛。 1(RIP)到(MIR)的模式化变换 定理1：任何目标函数系数为有理数的纯整数线性规划都可以化为(2)形式的整数线性 规划。 证明：在(1)形式的(RIP)中，由于C,都是有理数(j=1,2,…n),所以存在整数 w>0,使得Cr=品(C1,C,…C),其中C;(=1,2,…m)均为整数，因而 可设C,均为整数。 (1)如果存在，1≤i≤n,使得C:lC,j=1,2,…n,则作变换： y,=×;j≠i 1 y=C-CIx (3) 即y=Bx (4) 10 0 0 1 0 …0 B=C1C2 C3 C. i行 5) C.C . 0 00 0 394

近年来 ， 在传统的分 枝定界法与割平面法 〔 ” 的基础上 ， 陆续产生 了许多改 进算法 。 本文 对如下的有理系数整数线性规划 提出了 一种新的改进算法 ， 称之为模式 化算 法 ‘ 劣 成 ‘ ， 取整数 其 中 ， ” 一 ， 为有理数 二 。 二 。 二 。 打 ， 。 。 种 二 二 ， ， 义 ， “ 心 。 二 ， ·，一 、 ‘ 为 二 矩阵 此算法 的基本构思是 通过变换将 化为一种特殊形式 的整数线性规划 。 ‘ ， 为整数 ， “ 。 。 “ 月 其 中 ， ‘ 为 的某一分 量 ， 不失 一般性 ， 可假 定 。 ， 为 矩阵 ， 与 的关系 见定理 ， ， … 。 然 后 ， 建立求解具有特殊结构的 的算法 。 值得注意的是 ， 由于在计算机 上求解一 般整数线性规划时 ， 如遇到无理数 ， 均用有理数来近似 。 所以 ， 本文 的方法实际使用 范围相 当广泛 。 到 的模式化变换 定理 任何 目标函数系数为有理数 的纯整数线性规划都可以化 为 形式的整数线性 规划 。 证明 在 形式的 中 ， 由于 ， 都 是 有 理 数 ， ， 一川 ， 。 。 ， 使得 。 一 告 ， ‘ ， “ … ， 其 中 ， ， 一 所 以 存 在 整 数 均 为整数 ， 因 而 可设 ， 均 为整数 。 如 果存在 ， ， 使得 ‘ ， 二 ， ， “ … ， 则作 变换 厂 ， ， 笋 ， ‘ 万一 七 ‘ “ 即 二 二 二 一 ‘ 行 、一 八八… ，’一州﹄卜八 丛认 凡 斌一… 移

易知，B满秩，其逆变换为： x,=y, j≠i *y- A8,· (6) 或 x=B-iy (7) 这里 1 0 0 0 0 1 0 0 B-i= C C2 C3 C. 一i行 (8) C. . C. …1…- C. 0 0 0 1 列 由(3)，(6)可知：x是整向量←→y是整向量，将(7)代入(1)得(MIP): MinCy, (MIP) By≤b y,是整数 j=1,2…n 这里，B=AB-1 (2)如果不存在i,1≤≤n,使得C:iC,j=1,2,…n,则假设|C,l=minC,l}, C中0 令整数9；及r,满足 C,=9C,+r,0≤r,≤|C,j≠i (9) 将(9)代入(1)，可得： Min∑(9，C,+r)x;+C,x: 了Ax≤& (10) (×,为整数 nj=1,2…n 作变换： ￥=， j≠i (I qx;十n 其逆变换为： (xj=x j≠i (12) x,=x!-∑91x{ jxi 由(11)，(12)知：×；是整数←→×；是整数，j=1,2…n,将(12)代入(10)，可得： 395

易知 ， 满秩 ， 其逆变换为 “ 一 夕 ’ ‘ ‘ 一 笋 ‘ 气、 ， 自 一亡几为 或 ‘ 二 一 ‘ 这里 ‘ 卫‘ 公一… 一 一… 一 ·· 一仇… ︸ 口一已… 、 一 一 生 二 行 列 由 ， 可 知 是整向量幸净 是整向 量 ， ‘ ， 簇 了 是整数 将 代入 得 夕 二 ， 。 “ 了气 少、 这里 ， 一 ’ 如果不存在 ， 簇 ‘簇 ， 使得 ‘ ， ， ， … ， 令整数 ， 及 ， 满足 ， 二 ， ‘ ， 簇 ，簇 ‘ 关 将 代入 ， 可得 、 艺 。 ， ‘ 二 ， 、 ‘ ‘ 则 假设 ‘ 卜 ， ， 了今 簇互 “ ， 为整数 。 了 ， “ 。 ” 。 作 变换 盆劣 、、尸 其逆 变换 为 护 一 矛，， 劣 一︸ 劣 ︺、、厂 由 ， 幻 知 ， 是整数“ 净‘ 了 ， 是整数 ， ， 一 ” ， 将 代人 ， 可得

MiaC.+ Ax'≤b (13) (x}为整数， j=1,2n 这里， 1 0 0 海象 0 0 1 0 0 A=AB] B1= 一i行 -q1 -q2 -93 ”14◆ -9。 0 0 0 4中0。 1) i列 此时lr<|C,lj≠i 故每进行一次这样的变换，目标函数中，非零的绝对值最小的系数至少下降1，故经若千次 这样的变换，必能化为情况(1)，定理证华。 2模式化算法 模式化算法，下面以2·表示 step1求解(2)的松弛问题 MinC:y. (14) By≤b 如果(14)无解，则(2)无解，停： 如果(14)有最优解y°=(yi,y,…y)r 若y(j=1,2…n)皆为整数，则y·为(2)的最优解，停； 若y·不为整数，则给定目标函数的初始上界M:=+∞，下界m: Ciy? y”为整数 m:= C:(Cy)+1)y非整数 转step2 step2分枝 (1)若y?是整数，且存在j≠：y?不是整数，则将相应的整数规划分枝，在两个分 枝规划上分别加上约束y1≤〔y)；y,≥〔y)+1； (2)若y:不是整数，且存在j≠，y不是整数，则在两个分枝规划上分别加上约束 y,≤Cy门，y:≥〔y门+1；y≥〔y)+1,y:≥〔y)+1； (3)若y不是整数，y?j≠i均为整数，则在相应整数规划上加上约束y,≥〔y)+1, 仅得一个分枝规划。 step3求解分枝整数规则的松弛问题 如果无解，则进行step4 396

‘ 习 ， 了 劣 产 镇 了为整数 ， ， ， 这里 一 丁 丁 一 一 “ “ 。 “ 。 此时 ， 。 笋 故每进行一次这样的变换 ， 目标 函数 中 ， 非零的绝对值最小 的系数 至少 下降 ， 故经 若干次 这样的变换 ， 必能化为情况 ， 定 理证华 。 模式化算法 模 式化算法 ， 下面以 ’ 表示 求解 的松 弛 问厄 ‘ ‘ 簇 如果 无解 ， 则 无解 ， 停多 如果 有最优解 贯 ， 穿 ， … 忿 若 少 ， “ 皆为整数 ， 则 为 的最优解 ， 停 若 不为格数 ， 则给定 目标 函数 的初始上界 ， 下 界 。 ‘ 〔 乍〕 ，为整数 兮非整 数 转 分技 若 甲是整数 ， 且存在 笋 ‘ 萝不是整数 ， 则 将相应 的整数规翅分枝 ， 在 两 个 分 枝规划 上分别加上约束 二簇 〔 ，〕 ， 〔 ，〕 若 不是整数 ， 且存 在 笋 ， 夕，不是整数 ， 则在两个分 枝规翅上分别加 上 约 束 夕 ，簇 〔少 ， 〕 ， 夕 ‘ 〔夕，〕 夕 ， 〔夕亨〕 ， 夕 ‘ 〔夕兮〕 若 了不是整数 ， 萝 笋 均 为整数 ， 则在相应整数规划上加上约 束 ， 〔 匀 十 ， 仅得一个分 枝 规划 。 求解分技整橄规 划的松 弛 问 皿 如果无解 ， 则进行

如果得到非整数解y·=〔y,…y)T y·是整数 若{C,(Cy)+1)>My不是 则进行step4否则，转step2 如果得到整数解y·=(y?…y·)T 若C,y:>M,则进行step4 若C:≤M,记录此解y",且令M:xCy? 当M>m时，进行step4 当M=m时，进行step5 step4检查是否存在尚未考虑的分枝，若存在，则转step3;否则，进行ste?5, step5终止步 如果M=+∞，则(2)无解 如果M<+∞，则M为(2)的最优值，其对应的整数解为(2)的最优解。 3自然割平面法 与传统的分枝定界法相比，算法2·在某些分枝规划中增加了约束y,≥〔y)。本文将它 称为自然割平面，因为它类似于作了一次切割。但它比Gomory的割平面简单可靠，并且 无需高的技巧性。本节定理将表明，由于引入自然割平面，一般说来将减少分枝次数。 为讨论及叙述的方便，引入下列记号： (MIP。)一表示求解(2)时的某个分枝整数线性规划（也可以是(MIP); (MIP:)、(MIP)-分别表示(MIP。)增加y:≥〔y)+1,y,≤〔3所得的分枝整数 线性规划。 (MIP()一(MIP,)的前一级分枝整数线性规划（但(MIP。)为(MIP)的情祝除外）。 定理2如果整数线性规划(MIP)有最优解，且所有最优解为其松弛问题(3)的可行域的内 点，则用传统的分枝定界法求解时，必须进行一次y:≥〔y】+1:y,≤〔y)的分枝过程，即 必须求解(MIP,)、(MIP2)型的两个分枝规划。 证明：反证法。假设不经过y,>〔y)+1,y,≤〔y)的分枝过程，即不求解(MIP:), (MIPz)便可得到(MIP)的最优解。即存在(MIP'),它是(MIP)增加一些关于y:(i≠)的约 束得出的，且其松弛问题的最优解y=(y1,…y)是(MIP)的最优解。 从而，由假设条件知，存在e>0,使得y=(y1,…y,-e,…y)是(MIP)的松弛 问题的可行解。又注意到y,(j≠)满足(MIP')中关于y,(j≠)的分枝不等式约束，但 (MIP)中没有关于y:的分枝不等式约束，所以，y是(MIP')的松弛问题的可行解。但 C:(y:-e)<C,y,这与y是(MIP')的松弛问题的最优解矛盾，定理证华。 定义：(C,缓慢下降)。若(MIP)与(MIP:)对应的两个松弛问题最优值之差小于 C:时，称为C:缓慢下降。 定理3：用算法2·求解(MIP)时，不存在C:缓慢下降的(MIP,),(MIP,)。 证明：由算法2及(MIP),(MIP。),(MIP:)的意义知，产生(MIPa)与产生(MIP:) 397

如 果得到非整数解 夕 · 二 〔少 兮 ， … 钓 若 心 井 ， 、 蕊裴羹 数 则 进行 否则 ， 转 如果得到整数解 卜二 份 丁 若 、 少 宁 ， 则进行 若 少 于毛 ， 记录此解 ， 且令 二 ‘ ， 当 。 时 ， 进行 当 ， 时 ， 进行 检查是否存在尚未考虑 的分枝 ， 若存在 ， 则转 否 则 ， 进行 终止步 如 果 ， 则 无解 如 果 十 ， 则 为 的 最优值 ， 其对应的整数解为 的 最优 解 。 自然割平面法 与传统 的分 枝定界法相 比 ， 算法 在某些分 枝 规划 中增加 了约 束 ‘ 浮 〔 匀 。 本文 将 它 称 为 自然 割平面 ， 因 为它 类似于作 了一次切割 。 但它 比 的 割平面简单 可 靠 ， 并 且 无需高的技巧性 。 本节定理将表明 ， 由于 引人 自然 割 平面 ， 一般说来 将减少分 枝次数 。 为讨论及叙述的方便 ， 引人下列记号 。 － 表示求解 时 的某个分枝整 数 线 性 规划 也可 以是 、 － 分别 表示 。 增加 夕 ‘ 〔少 宁〕 ， 夕 ‘ 气 〔 宁〕所 得 的分 枝整 数 线性规划 。 否－ 。 的前一级分枝整数线性规划 但 。 为 的情况 除 外 。 定理 如果整数线性规划 有最优解 ，且所有最优解为其松弛问题 的可 行域 的内 点 ， 则用 传统 的分 枝定界法 求解时 ， 必须进行一次 ‘ 〔 份〕 〔 份〕的分枝过程 ， 即 必 须 求解 、 型 的两个分 枝规 划 。 证呱 反证法 。 假设不经过 ‘ 〔 ，〕 ‘ 毛〔 幻 的分枝 过程 ， 即不求解 ， 便可得到 的最优解 。 即存在 ‘ ， 它是 增加一些关于 夕 ， 护 的约 束得 出的 ， 且其松弛问题 的最优解 二 ， ， 夕 。 是 的最优解 。 从而 ， 由假设 条件知 ， 存在 。 ， 使得犷 ， … ‘ 一 。 ， 一 是 ， 的 松 弛 问题的可行解 。 又注意到 ， 笋 ’ 满足 ‘ 中 关 于 ， 并 的 分 枝 不 等 式 约 束 ， 但 ， 中没有 关于 的分枝不 等式约 束 ， 所以 ， ’ 是 ， 的松弛 问 题 的 可 行 解 。 但 ‘ ‘ 一 。 ‘ ‘ ， 这 与 是 ’ 的 松弛问题 的最优 解矛盾 ， 定 理证华 。 定义 ‘ 缓慢下降 。 若 ‘ 与 对应 的两个松 弛问题 最优值 之差 小 于 ‘ 时 ， 称 为 ‘ 缓慢下降 。 定 理 用 算法 求 解 时 ， 不存在 ‘ 缓慢下降 的 。 ， ， 。 证 明 由算法 ， 及 ‘ ， 。 ， ， 的意 义 知 ， 产 生 。 与 产 生