整数规划课件

网络优化

Network

Optimization

清华大学课号：40420213（本），70420133（研）

第3章整数规划（IntegerProgramming）

清华大学数学科学系谢金星

整数规划问题的例子

例(续例1.4)指派问题(AssignmentProblem)

一家公司经理准备安排N名员工去完成N项任务，每人一项.由

于各员工的特点不同，不同的员工去完成同一项任务时所获得

的回报是不同的.如何分配工作方案可以使总回报最大？

MAXZI'H%•与线性整数规划（LIP）

s.t.=L/=12…，明非线性整数规划（NIP）

丁纯整数规划（PIP）

_1'2_1,2,・・・，〃，混合整数规划（MIP）

xije{0"，特例：0T规划

许多网络优化问题也可以用整数规划（IP）来建模2

3.1.1整数规划问题的几种描述形式

线性规划(LP：LinearProgramming)问题的标准形式

mincTx

s.t.Ax=b(3.1)

x>0

c/eRLbeRMAeRE,才是行满秩的，且m<n.b>0

纯整数线性规划(PILP,以后简称整数规划(IP))的标准形式

mincTx

s.t.Ax-b(3.2)

x>0

x,GZ

c,xeZn,beZm,AeZmx〃，力是行满秩的，且m<n,b>0

3.1.1整数规划问题的几种描述形式

整数规划的一般形式min/x

T

s.t.Q,x=bj,ieM

a：x>b^ieM(3.3)

xjeZ*,jeN

x.wZ,/wN

JJ

整数规划的规范形式储

mincTx

s.t.Ax>b(3.4)

x>0

XjGZ

整数规划的上述三种形式是等价的：一种形式下的实例,

可以简单地等价变化为另一种形式下的实例.

3.2.2整数规划问题的求解难度

整数规划问题是NP困难的.

为什么不先求解相应的线性规划问题(一般称为整数规划问题

的线性规划松弛问题，或简称LP-Relaxation),然后将

得到的解四舍五入到最接近的整数？

LC

///目标函数下降方向

----1------^巧

IP可行解对应于整点A(2,2)和B(l,1),而最优解为A点.但LP松弛的最|

优解为C(3.5,2.5)5

3.2全么模阵

IP的LP松弛的最优解什么时候一定是整数解呢？

假设在(3.1)式所示的线性规划问题中等式约束个数等于决策

变量个数(旭=〃),则此时的等式约束构成一个线性方程组

det(A

x/—?j-1,2,.

det(/)

如果方阵Z为整数矩阵且b为整数向量,则det(A)和def都是整

数.当然，解工未必是整数向量.

如果det(Z)=1或则解x一定是整数向量.

3.2全么模阵-Hoffman-Kruskal定理(1956)

定理3.1设在(3.1)式所示的线性规划问题中/为整数矩阵，且/满行秩，

则下面三个条件等价：

(1)对每个基矩阵民其行列式det(8)=1或-1.

(2)对任何整数向量其可行域。(6)={x[-=b,xZ0}的每个

极点都是整数向量.

(3)对每个基矩阵8其逆矩阵也是整数矩阵.

o(R。、adj

证明(1)=>(2)：XB=(By'b=^—b

det(5°)

(2)=>(3):设夕为任一基矩阵，如果其逆矩阵不是整数矩阵，任

x

取整数向量y使得z=y+B-ei>0,这里与表示第7个分量为1其余分量为

0的“单位向量”.’

令b=比=5(歹+3一7,)=为十分，则A为整数向量，且向量

z=B-xb20为〃(b)的一个极'点的基向量；因此是整数向量.

因此员Z=z-y为整数向量，即是整数矩阵.

(3)=>(1):设夕为任一基矩阵，由于夕切=/，又知夕和5一都是整数

矩阵，所以det(B)=1或T.

3.2全么模阵-定义

定义3.1如果一个矩阵/的任何子方阵的行列式的值都等于3

1或T,则称Z是全么模的（TU：TotallyUnimodular,又译为

全单位模的），或称/是全么模矩阵.

■模矩阵的元素只能取0,1和

定理3答:1连么模矩阵的性质）下列命题等价：

1）/是全么模矩阵.

2）T是全么模矩阵.

3）AT是全么模矩阵.

4）（《力）是全么模矩阵.

5）（4/）,（儿0）是全么模矩阵.

/为全么模矩阵时的整数规划问题实际上等价于对应的LP&

松弛问题（单纯形算法）.

3.2全么模阵-充分条件

定理3.3设A是由0,1和-1组成的矩阵，如果下面两个条件同时成立，

则A为全么模矩阵.

（1）A的每一列至多含有两个非零元素.

（2）A的行可以分为ALA2两个集合，使得：如果A的一列中有两

个符号不同的元素，则相应的两行在同一集合A1或A2中；如果A的一

列中有两个符号相同的元素，则相应的两行分别位于两个集和A1和A2

中

证明如果矩阵A满足条件（1）和（2）,则力的任意子矩阵仍然满足条件（1）

和（2）.所以，只需证明当/为方阵且满足条件（1）和（2）时，det（A）=

0,1或-1即可.下面用数学归纳法证明

当4为1阶方阵时，显然=0,1或-1.假设结论对任意（几-1）阶方阵均成立，

下面考虑4为〃阶方阵的情形.有且只有以下三种可能：

4的某一列元素全为0,贝lldet（A）=0.

4的某一列元素只有一个不为0，则det（A）=0,1或-1.

4的每一列均含有两个非零元，=Z%，V/=l,2,...，儿

主4ieA29

则det（A）=0.

3.2全么模阵-与网络优化的关系

推论（1）一个有向图的关联矩阵为全么模矩阵.

（2）一个无向图的关联矩阵为全么模矩阵，当且仅当该

图为二部图.

当采用整数规划来描述网络优化问题时，其约束矩阵一般是有

向图的关联矩阵或它的简单变形，一般都是全么模矩阵.因此

可以认为，许多网络优化问题都是一类特殊的整数规划，其LP

松弛与原问题有相同的最优解.

网络优化处于线性规划和整数规划的结合点上，或者说处于连

续优化和离散优化（组合优化）的结合点上.

10

3.3分数割平面法Gomory(1958)

如果给线性规划增加一个约束，则原线性规划问题的可行域集

合可能缩小，即可行域相当于被“割掉”了一块.

基本思想：如果给整数线性规划增加一个线性约束，而没有

“割掉”其任何可行整数解，则新问题与原问题有相同的整数

解.增加的相应约束通常被称为筋^平面(CuttingPlane).

首先用原始单纯形法求解整数线性规划(3.2)的LP松弛

(3.1),得到一个最优基本解.设它对应的基为B,且设对应

的单纯形表中第1个方程(第/行)为：(i=0,1,2,…,m)

、8(力)+ZjeNByijXj~No

记X5(0)=-Z

对约束方程两边取“地板函数”(用L」表示)，即取小于或

等于对应的实数值的最大整数值.由于X为非负整数，所以

/⑴+Z卜/"l_Xo」

乙⑺+ZjcNByijXj~匕0

分数割平面法-L^zO-

两式相减：£六.(为•一必J%/之.Vzo-LZo.

令4=歹「必」，，=0,1,2LM则工jeNBfijXjNfiO.

第i行的Gomory割口^

为了将它加入已经得到的单纯形表并仍然保持一个基本解，将

它进一步变为Zjd)Xj+s=-九(3.10)

其中s为引进的新变量(非负).

引理3.1约束(3.10)加入到LP松弛问题的最优表之后，没有

割掉任何整数可行点；并且当九不是整数时，新表里是一个

对偶基本可行解，但不是原始可行解.

/s与B一起构成新的基变量；基本解中s=一九＜。

12

/单纯形表第0行不变，所以基本解是对偶基本可行解.

分数对偶算法算法(FractionalDualAlgorithm,Gomory,1958)

STEPO.解ILP的LP松弛问题.如果松弛问题无解，则令

feasible=“no”；否则得松弛问题的最优解,令feasible=“yes”,

继续STEPL

STEP1.如果feasible="no”，则原问题无解，结束；如果

feasible="yes”且是整数解，则得到原问题的最优解，结束；

否则继续STEP2.

STEP2.选取某行生成割平面；在单纯形表中加上生成的Gomory

割(3.10)和对应的基变量s.

STEP3.应用对偶单纯形法求解新问题.如果对偶问题无解，令

feasible=“no”；否则设为新的当前最优解.转STEP1.

13

分数对偶算法算法(FractionalDualAlgorithm,Gomory,1958)

例3.1用分数割平面法求解：maxx2

s.t.35+2X2<6

-35+2X2<0

2£Z

将其LP松弛问题化为标准形：maxx2=-min(-x2)

s.t.3/+2X2+%=6

—3xj+2+x—0

%1,x2,x3,x4>0

bX]X4

x2x3

-z=00-100

x3=63210

14

%4=0-3201

分数对偶算法算法(FractionalDualAlgorithm,Gomory,1958)

b%4

%2x3

-z=00-100

二63210

人=0-3201

b%4

x2x3

-z=0-3/2001/2

X3=6601-1

x=0-3/2101/2

b%]

x2x3

XX

-z=3/2001/41/41―3+74—7

巧=1101/6-1/6

X2=3/2011/41/4

分数对偶算法算法(FractionalDualAlgorithm,Gomory,1958)

分数对偶算法算法(FractionalDualAlgorithm,Gomory,1958)

bX.X,%,x4x54

-z=1000010

X]=2/3100-1/32/30

X2=1010010

*3=20011-40

X0,—-2/3000-2/3-2/31

X

bX]%2x35%6

-z=1000010

X]=110001-1/2

X2=1010010

x_

Jz—10010-53/2

%4=100011-3/2

得到最优解为（1,1）,是整数解.结束，原问题最

优解为（1,1）,最大值为L

17

对分数割平面算法,我们作以下几点说明

⑴该算法能否保证其有限性，即是否一定在有限步内停止?我们知道,线性

规划的单纯形法可能出现循环，因此不一定在有限步内停止.所以，分数割

平面算法也不一定在有限步内停止.但是，当在(对偶)单纯形法中采用字典

序反循环法则时,可以证明分数割平面算法一定在有限步内停止.

⑵可以看出，该算法在计算过程中不断增加割平面的个数，因此约束越来

越多.为了防止割平面个数任意增加，一般可以作如下处理：如果一个松弛

变量应进入基,则将相应的行和列从单纯形表中去掉，即去掉了对应的割平

面.因此,单纯形表中的约束行数不会多于变量个数.

(3)该算法在计算机上实现过程中会有一点麻烦：由于存在误差，判定

个实数是否为整数是比较困难的.为了克服这一困难,人们提出了全整数算

法.

(4)分数对偶算法采用对偶单纯形法,在达到最优解之前得不到原问题的

可行解，因此如果计算时间过长而不得不中间停机时，结果往往无法使用.

为了解决这一问题,人们提出了原始整数割平面算法.

18

3.4分枝定界法（Branchand

Bound）

基本思想：隐式地枚举一切可行解（组合优化）

所谓分枝，就是逐次对解空间进行划分；而所谓定界，是指对于

每个划分后的解空间（即每个分枝），要计算原问题的最优解的

下界（对极小化问题）.这些下界用来在求解过程中判定是否

需要对目前的解空间（即分枝）进一步划分，也就是尽可能去掉

一些明显的非最优点，从而避免完全枚举.

定界方法中经常采用的有Lagrange松弛方法和线性规划松弛方法等

•T

若在某一时刻，得到mmcxmincTx

一个全整数解的费用力Ax-bAx-b

为小,则马,为原问题x>

x>00

的一个上界；/0

Xj>X：+1X<X

否则得该分枝的一个

19

下界，继续分枝.

分枝定界算法

STEPO.令activeset={0}（原问题）；〃二°°；currentbest=0.

STEP1.如果activeset=0,则已经得到原问题的最优解,结束;否

则从活跃分枝点集合activeset中选择一个分枝点％将左从

activeset中去掉,继续STEP2.

STEP2.生成左的各分枝i=1,2,…,%及其对应的下界孙

STEP3.对分枝％=12…,%:如果分枝，得到的是全整数解且召＜4

则令我为且current