Loading [MathJax]/jax/output/CommonHTML/fonts/TeX/fontdata.js

logo

整数规划

Integer Programming

wangzf / 2024-08-28

目录

整数规划简介

通常，决策变量的取值是大于或等于 0 的自然数，然而在许多实际问题中， 都要求决策变量的取值为正整数，如机器台数、商品数量、工人数量、装载货物的汽车数量等， 这类要求变量为整数的问题称为 整数规划(Integer Progamming, IP) 问题。

整数线性规划

Integer Linear Programming, ILP

maxZ=3x1+2x2

s.t.{2x1+3x2≤144x1+2x2≤18x1,x2≥0且为整数

混合整数规划

Mix Integer Programming, MIP

0-1 整数规划

Binray Integer Programming, MIP

整数规划求解

求解整数规划的常用方法有 分支定界法 和 割平面法， 这两种方法的共同特点是：在线性规划的基础上，通过增加附加约束条件， 使整数最优解成为线性规划的一个极点（可行域的一个顶点），于是就可以用单纯形法等方法找到这个最优解， 它们的区别在于约束条件的选取规划和方式不同。

分支定界法

分支定界法（Branch and Bound Algorithm, B&B）， 其基本思想是对有整数约束条件问题的可行域进行系统搜索， 通常是把全部解空间反复地切割为越来越小的子集，称为分支， 然后在每个子集内计算出一个目标下界，称为定界。

问题介绍

以最大化目标函数的整数规划（MP）问题 A 为例，最优解为 Z∗A，如果去掉整数约束， 对应的松弛问题 B 为普通的线性规划问题（LP）。

假设 B 的最优解是 ZB，假设某一符合整数约束的 A 问题解（不一定是最优解）为 ZA，则有：

ZA≤ZB

对松弛问题 B 一个或多个变量添加整数约束（分支），相当于对可行域进行切割，每个可行域空间对应一个线性松弛问题， 设为 Bi，这些松弛问题 Bi 的解的最大值（设为 Z′B）一定会小于 ZB， 即 Z′B≤ZB，因此 Z′B 是 A 问题的一个上界，即：

ZA≤Z′B≤ZB

同理，这些松弛问题 Bi 的解的最小值（设为 Z″B）可能会小于 ZA， 即 ZA 是 A 问题的一个下界：

ZA≤Z″B≤Z′B≤ZB Z″B≤ZA≤Z′B≤ZB ZA≤Z∗A

如果这些最松弛问题 Bi 的某个解（设为 ˙ZB）符合整数约束， 且 ˙ZB>ZA，则 ˙ZB 是 A 问题的一个新的下界。

ZA<˙ZB≤Z∗A

分支定界法就是将 B 的可行解空间分成子空间再求最大值的方法，逐步减小上界和下界，最终求得 Z∗A。 当 LP 问题满足全部整数约束条件时，即为 MP 问题的解。

求解步骤

对于上面的整数规划问题 A，求解步骤如下：

  1. 去掉整数约束条件，得到原问题 A 的松弛问题 B，使用单纯形法或内点法等求解 B 得到 B 的最优解，即：

X(0)=(x1,x2)T=(3.25,2.5)T Z(0)=14.75

  1. 由于此时 x1 和 x2 都不是整数，因此需要选择一个分支变量，如选择 x1 作为分支变量， 分成左支（x1≤3）和右支（x1≥4），对应的分支子问题如下：

    LP1 maxZ=3x1+2x2

    s.t.{2x1+3x2≤144x1+2x2≤18x1≤3x1,x2≥0

    LP2 maxZ=3x1+2x2

    s.t.{2x1+3x2≤144x1+2x2≤18x1≥4x1,x2≥0

    求解两个子问题的最优解（单纯形法、内点法）如下：

    X(1)=(3.0,2.66)T,Z(1)=14.33 X(2)=(4.0,1.0)T,Z(2)=14.0

    此时原整数规划 A 的新的下界为 14.0，新的上界为 14.33，即 14.0≤Z∗≤14.33。

  2. 此时 LP2 的最优解是 14.0，如果继续 LP2 分支，那么其分支后的最优解一定小于 14.0。 因为分支代表更多的约束，使线性规划更逼近整数规划，其最优解小于没有分支的最优解 Z(2)=14.0， 所以没有必要对 LP2 这个分支继续搜索，从优化的角度，不可能从这个点以后的分支中找到比目前 14.0 更优的解， 可以直接删除，只需要搜索 LP1 分支即可，这样就大大减少了搜索空间，提高求解的效率。

  3. 对 LP1 选择 x2 作为分支变量，分成左支（x2≤2）和右支（x2≥3）， 对应的分支子问题如下：

    LP3 maxZ=3x1+2x2

    s.t.{2x1+3x2≤144x1+2x2≤18x1≤3x2≤2x1,x2≥0

    LP4 maxZ=3x1+2x2

    s.t.{2x1+3x2≤144x1+2x2≤18x1≤3x2≥3x1,x2≥0

    求解两个子问题的最优解（单纯形法、内点法）如下：

    X(3)=(3.0,2.0)T,Z(1)=13.0 X(4)=(2.5,3.0)T,Z(2)=13.5

  4. 此时可以看到，在第一次分支后的最优解为 14.0≤Z∗≤14.33，而在第二次分支后最优解反而小于 14.0， 虽然可以继续在 LP4 分支下继续搜索，但是搜索结果肯定不会大于 Z(2)=14.0，只会更差， 而且 LP2 的解恰好满足变量为整数的约束条件，因此该整数规划问题 A 的最优解的 LP2 对应的解为：

    X∗=X(2)=(4.0,1.0)T,Z∗=Z(2)=14.0

用图形展示搜索过程如下图：

img

总结

从分支定界的搜索过程来看，该方法非常简洁清晰，相当于增加约束条件后继续求解普通线性规划问题。 但是也要注意到，在变量很多的情况下，该搜索过程是很复杂的，如对于 0-1 整数规划问题， 每个变量的取值只可能是 0 或 1，分支也只是简单的左右两支，形成简单二叉树。 如果变量个数为 10，那么最小分支数是 1024；如果变量数为 20，那么最小分支数是 1048576，呈指数级增长。

因此，分支定界法一般不考虑直接求解该问题的精确解，而是求解近似解或局部最优解，如可以设定当上界和下界非常接近时（如 0.001）， 分支定界结束或者使用相对差值，即分支定界法中的 GAP：

GAP=ˉZ−ZˉZ

当 GAP≤0.001 时，可以认为当前的上界或下界时问题的最优解，分支定界法结束迭代。

割平面法

问题介绍

分支定界法的思路是对原问题对应的松弛问题的可行域进行切割，切割方法是对非整数变量取相邻整数作为附加约束。 从几何的角度来说，这些约束相当于切割可行域的超平面，这些超平面与坐标轴平行。

分支定界法的缺点是子问题由于分支的增加呈指数增长，为克服该缺点，学者提出了割平面法（Cutting Planes Method）， 割平面法也是通过增加切割超平面切割掉松弛问题的非整数解部分，但是并没有对问题进行分支。

割平面法通过增加切割超平面切割掉部分的解空间，该超平面应该满足两个条件：

  1. 刚好切割掉松弛问题的非整数解部分
  2. 保留所有整数解

求解步骤

那如何找到这个切割超平面呢？

假设有如下整数规划问题及其对应的松弛问题：

IP:maxZ=cTx s.t.{Ax=bx≥0x为整数

LP:maxZ=cTx s.t.{Ax=bx≥0

假设 LP 的最优解不是整数解，否则 LP 的最优解就是问题 IP 的最优解。设 LP 的最优解为：

X(0)=(b1,⋯,bi,⋯,bm,0,⋯,0)T

其中，bi 是分数（不是整数），X(0) 表示 x1,⋯,xi,⋯,xm 是基变量， xm+1,⋯,xn 是非基变量，在单纯形法中说过，在标准型线性规划方程中，非基变量为 0 时， 基变量的值等于常数项，所有基变量组成一个单位阵。

变量 x1 ⋯ xi ⋯ xm xm+1 ⋯ xn b
x1 1
⋯ 1
xi 1 aim+1 ⋯ ain bi
⋯ 1
xm 1

bi 所在行的方程是：

xi+aim+1xm+1+⋯+aim+jxm+j+⋯+ainxn=bi

⇒xi+n−m∑j=1aim+jxm+j=bi

把 aim+j 和 bi 分解成整数 N 和小数 f 两部分（如 2.3=2+0.3），即：

aim+j=Nim+j+fim+j bi=Nbi+fbi

因此，bi 所在的方程可以写成：

xi+n−m∑j=1(Nim+j+fim+j)xm+j=Nbi+fbi

xi+n−m∑j=1Nim+jxm+j+n−m∑j=1fim+jxm+j=Nbi+fbi

xi−Nbi+n−m∑j=1Nim+jxm+j=fbi−n−m∑j=1fim+jxm+j

因为 −∑n−mj=1fim+jxm+j≤0，fbi≤0，所以：

fbi−n−m∑j=1fim+jxm+j≤1

若要决策变量都取整数，则：

fbi−n−m∑j=1fim+jxm+j≤0

这样就得到第 i 行对应的割平面法方程：

fbi−n−m∑j=1fim+jxm+j≤0

引入松弛变量 yi，将割平面法方程标准化，即：

−n−m∑j=1fim+jxm+j+yi=−fbi

将新的约束加入到原来的问题约束中，继续求解，直到求出整数最优解为顶点时才停止计算。

求解步骤示例

maxZ=7x1+9x2

s.t.{−13x1+x2≤2.0x1+17x2≤5.0x1,x2≥0且为整数

对应的松弛问题为：

maxZ=7x1+9x2

s.t.{−13x1+x2+x3=2.0x1+17x2+x4=5.0x1,x2,x3,x4≥0

使用单纯形法求解，最优单纯形法如下表：

目标和基变量 b x1 x2 x3 x4
Z -63 0 0 -2811 -1511
x1 92 1 -122 322
x2 72 1 722 122

在选择行 i 时，一般选择最大的 fbi 所在的行 i。 如果 fbi 相同，那么选择 ∑n−mj=1fim+j 小的所在行 i 构造割平面， 因此选择 x2 所在行构造割平面，即：

fbi−n−m∑j=1fim+jxm+j≤0

12≤722x3+122x4

加入松弛变量，并调整后得到：

−722x3−122x4+y1=12

将新的约束加入到前面得到的最优单纯形表的最后一列中，如下表：

目标和基变量 b x1 x2 x3 x4 y1
Z -63 0 0 -2811 -1511 0
x1 92 1 -122 322 0
x2 72 1 722 122 0
y1 -12 0 0 -722 -122 1

使用对偶单纯形法求解，得到最终的最优单纯形表，如下表：

目标和基变量 b x1 x2 x3 x4 y1
Z -59 0 0 0 -1 -8
x1 327 1 0 0 17 -17
x2 3 0 1 0 0 1
x3 117 0 0 1 17 -227

选择 x1 所在的行构造割平面，得到割平面方程：

74≤17x4+67y1

加入松弛变量，并调整后得到：

−17x4−67y1+y2≤74

将新的割平面方程加入到上一步得到的最优单纯形表中，得到如下结果：

目标和基变量 b x1 x2 x3 x4 y1 y2
Z -59 0 0 0 -1 -8 0
x1 327 1 0 0 17 -17 0
x2 3 0 1 0 0 1 0
x3 117 0 0 1 17 -227 0
y2 -47 0 0 0 -17 -67 1

迭代求解得到满足整数规划的解，结果如下表：

目标和基变量 b x1 x2 x3 x4 y1 y2
Z -55 0 0 0 0 -2 -7
x1 4 1 0 0 0 -1 1
x2 3 0 1 0 0 1 0
x3 1 0 0 1 0 -4 1
x4 4 0 0 0 1 6 -7

即得到的满足整数规划的解为：

X∗=(x1,x2)=(4,3) Z∗=55

Gurobi 求解整数规划

使用 Gurobi 求解以下整数规划模型：

maxZ=3x1+2x2

s.t.{2x1+3x2≤144x1+2x2≤18x1,x2≥0且为整数

import gurobipy as grb

# 定义模型
model = grb.Model()

# 定义整数变量
x1 = model.addVars(vtype = grb.GRB.INTEGER, name = "x1")
x2 = model.addVars(vtype = grb.GRB.INTEGER, name = "x2")

# 添加约束
model.addConstrs(2 * x1 + 3 * x2 <= 14)
model.addConstrs(4 * x1 + 2 * x2 <= 18)
model.addConstrs(x1 >= 0)
model.addConstrs(x2 >= 0)

# 定义目标函数
model.setObjective(3 * x1 + 2 * x2, sense = grb.GRB.MAXIMIZE)

# 模型求解
model.optimize()

# 模型结果打印 
print(f"目标函数值：{model.objVal}")
for v in model.getVars():
    print(f"参数 {v.varName} = {v.x}")

# 目标函数值：14.0
# 参数 x1 = 4.0
# 参数 x2 = 1.0

上面的代码很简单，基本与线性规划的代码一样，不同之处在于， 定义变量时线性规划不限定变量的类型，而整数规划中限定变量类型为整数。