整数规划_整数线性规划（Integer Linear Programming）

符号说明：

LP(Linear Programming):线性规划

ILP(Integer LP):整数线性规划

relax LP:LP最优解

不同类型的优化模型

优化模型的变量常可以分为三类

1. 离散类型的变量

2. 连续类型的变量

3. 混合类型的变量

问题方程

A是一个m×n的矩阵

b是一个m行的列矩阵

c是一个n行的列矩阵

x是含有n个变量的列矩阵(值为离散类型)

如图所示，此时LP的最优解(称为relaxed LP)为小数，最接近relaxed LP的整数解在可行域的外面，而ILP的最优解在relaxed LP的左边。

如果我们将最接近relaxed LP的所有整数解都考虑在内，是不是就能够找到ILP的最优解了呢？

答案是否定的。一般来说，我们将relaxed LP周围的整数解都考虑在内，可能会出现两种情况，一是不在可行域，二是非ILP最优解。

如图所示，此时我们可以看到ILP的最优解与relaxed LP周围的整数解并不在一起。

由此我们可以分析一下ILP问题

1. ILP最优解很少是可行域的各个顶点，如上图所示，它在可行域的内部。

2. 如果relaxed LP(也就是LP的最优解)恰好是整数，那么它同时也是ILP的最优解，但是这种情况很少出现，一般来说relaxed LP代表的ILP最优解的上限或下限，这点在之后的算法中会用到。

3. relaxed LP周围的整数解并不一定是ILP的最优解，甚至常常不在可行域内。

4. 可行域可以不为空，但ILP可以无解。

5. 目前来说，没有已知的算法能够快速地求解ILP问题(但是有快速求解LP问题的算法)。

6. 处理器可以很容易求解有10000个变量的LP问题，但只能处理几十个变量的ILP问题。(主要是因为如果我们采用暴力搜索算法，处理器运行的时间增加非常迅速)

7. 尽管有很多问题，但不可置否的是ILP模型仍然是一个很有用的建模方法。

解决ILP的主要方法

在这里主要讲解Branch-and-bound methods方法 分支定界方法

分支定界方法主要包含两个步骤

1. 将该问题看作LP问题，求出最优解，如果最优解为整数，那么结束，否则继续第二步

2. 通过增加限制条件来创建两个分支

分支定界算法描述

举例

以S₀进行分割为例

此时分出两个蓝色的区域，一个是点(0，3)一个是下面的蓝色梯形区域

再根据目标函数Z = 4x₁+3x₂  可以知道在蓝色梯形区域内的relax LP(即LP最优解)为(5/4,2)，然后仍然继续分割，重复之间的步骤，可以得到下图。

注意：在如上构建的树中

1. 我们选择两个变量中最接近整数(已经为整数的不用考虑)的变量作为首先分割条件，

因此在S₀中我们选择第二个变量x₂作为分隔条件，进行分割区域，我们只需要考虑x₂≤2与x₂≥3的部分。此时不需要考虑当x₂在2到3之间的区域，因为x₂在这个区间内为小数，是不会存在最优整数解的。

2. 如果在第一步中，S₁的最优值<=9，此时我们已经可以结束分割了，除非要求出所有的最优整数解。

如上当我们面对只有两个变量时候我们可以通过画图进行求解，但是当我们面对三个及以上变量时

比如：

如果使用暴力搜索算法我们最多需要测试6x6x8x4=1152个候选整数点。

所以在这种情况下，需要借助计算机帮助我们求解。

使用python的scipy.optimize导入linprog库

官方文档

这里我们使用jupyter进行编程

选择x₁进行分支

最后可以得到如下树

最后的结果为

x=[0 7 0 0]

z=21

英语词汇：

可行域 feasible region

算法 algorithm

分支定界方法 Branch-and-bound methods

线性规划：LP(Linear Programming)

整数线性规划：ILP(Integer LP)

LP最优解：relax LP

扫码关注 探索数据