【整数规划(一)】整数规划问题综述

1 整数规划问题定义

整数规划问题实际上是数学规划问题的一个分支。一般来说在数学规划问题中一部分变量或者全部变量为整数变量的话，该数学规划问题就属于整数规划问题。如下所示是线性整数规划(Integer Linear Programming) 问题：

\underset{x}{\min}\ c^Tx\\ s.t.\ Ax\le b\\ x\ge 0\\ x\in Z^n

整数规划问题的特点在于其决策变量含有整数变量，如上问题中所示的 x\in Z^n 。

设有如下的整数规划问题：

\underset{x}{\min}\ c^Tx\\ s.t.\ x\in P1\\ \\ x\in Z^n

其中 P1 为一个多面体，如果用图像表示出来整数规划的可行域如下所示：

从图中可以看到上述整数规划问题的可行域是 P1 内部和边界上的所有的 整数点 。如果我们去掉整数约束的话该问题就变为线性规划问题，那么其可行域就是 P1 内部和边界上的所有点。

在学习整数规划问题之前自然会产生一个疑问：为何非要采用整数变量呢？整数规划问题在数学规划问题中的地位怎么样？虽然这听起来是一个稍显煞笔的问题，我觉得还是有必要分析一下这个问题。

一般来说，之所以在模型中要引入整数变量主要原因有2点：

1 我们所需要描述的变量来自生活实际，而这些变量都是整数的。例如：要表示 多少架飞机，多少辆汽车，多少个人 等等 这些变量必然只能是整数的，这些实际问题中的变量若取分数则失去了实际意义，因此我们必须用整数变量来进行建模。

2 我们要描述逻辑，Yes 或者 No，乃至于更复杂的逻辑关系。我们经常会用1代表Yes，0代表No，从这里也可以衍生出很多复杂的逻辑关系。值得注意的是区别于前一种情况此时的整数变量看起来貌似还是整数的形式，但实际上准确的来说说 它们已经是 Bool 变量了。Bool 变量满足 Bool 变量的运算法则，例如 与或非这些，而不满足加减乘除的运算规则。明白了这一点对整数规划问题的建模有着很大的帮助。

2 常见整数规划问题举例

1 背包问题：

设有一个背包，其最大承重为 b ，考虑 n 件物品，其中第 j 件重量为 a_j ，其价值为 c_j 。问如何选取物品装入背包中，使得背包内物品的总价值最大？

设决策变量 x_j=\left\{ \begin{array}{l} 1,\ \text{若选第}j\text{件物品}\\ 0,\ \text{若不选}\\ \end{array} \right.

则背包问题可以表示为下列整数规划：

\underset{x}{\max}\sum_{j=1}^n{c_jx_j} \\ s.t.\ \ \sum_{j=1}^n{a_jx_j}\le b\\ x\in \left\{ 0,1 \right\} ^n

2 广义指派问题：

设有 m 台机器， n 个工件，第 i 台机器的可用工时数为 b_i ，第 i 台机器完成第 j 件工件需要的工时数为 a_{ij} ，费用为 c_{ij} 。问如何最优指派机器生产。

设决策变量 x_{ij}=\left\{ \begin{array}{l} 1,\ \ \text{若第}i\text{机器加工第}j\text{件工件}\\ 0,\ \ \text{其他}\\ \end{array} \right.

则广义指派问题可以表示为下列整数规划：

\underset{x}{\min}\sum_{i=1}^m{\sum_{j=1}^n{c_{ij}x_{ij}}}\\ s.t.\ \ \sum_{j=1}^n{a_{ij}x_{ij}}\le b_i,\ \forall i=1,\cdots ,m \\ \sum_{i=1}^m{x_{ij}}=1,\ \ \forall j=1,\cdots ,n\\ x_{ij}\in \left\{ 0,1 \right\}

3 集合覆盖问题：

设某地区划分为若干个区域，需要建立若干个应急服务中心（如消防站，急救中心等），每个中心的建立都需要一笔建站费用，设候选中心的位置已知，每个中心可以服务的区域预先知道，问如何选取中心使得应急服务能覆盖整个地区且使得建站费用最小。

记 M=\left\{ 1,\cdots ,m \right\} 为该地区中的区域， N=\left\{ 1,\cdots ,n \right\} 是可选的中心，设 S_j\subseteq M 为中心 j\in N 可以服务的区域集合， c_j 是中心建站费用，定义0-1关联矩阵 A=\left( a_{ij} \right) ，其中，若 i\in S ，则 a_{ij}=1 ，否则 a_{ij}=0

设 x_{j}=\left\{ \begin{array}{l} 1,\ \ \text{选中心}j\\ 0,\ \ \text{不选}\\ \end{array} \right.

则问题可以表示为：

\underset{x}{\min}\sum_{j=1}^n{c_jx_j} \\ s.t.\ \ \sum_{j=1}^n{a_{ij}x_j}\ge 1,\ \ \forall i=1,\cdots ,m\\ x\in \left\{ 0,1 \right\} ^n

3 组合优化和整数规划的联系

稍微熟悉整数规划的同学应该也听说过组合优化。下面给出组合优化问题的定义

集合 N=\left\{ 1,\cdots ,n \right\} ， c=\left( c_1,\cdots ,c_n \right) ，给定一个子集 M\subseteq N ，组合优化表示为：

\min \sum_{j\in F}{c_j}\\ s.t.\ F\subseteq M

那么什么条件之下组合优化问题和整数规划问题可以一一对应呢？

答：集合 N 是有限的(Finite)的话，组合优化问题都可以被等价转化为整数规划问题。

从上面的结论来看，我们在实际中大多数的问题都满足集合 N 是有限的条件。 粗略的来说 在绝大多数场合之下 我们并不会严格去区分 组合优化 (Combinatorial Optimization) 和 整数规划 (Integer Programming) 这两个概念，而可以把它们不作区别的混用。

关于组合优化和整数规划的关系进一步详细的讨论可参考文献【4】。

4 整数规划问题分类

Integer Linear Programming （线性整数规划）：目标函数为线性，约束为线性，决策变量只含有整数变量的整数规划问题。线性整数规划问题目前是整数规划问题中研究最多，也是算法相对比较成熟一点的领域。

Binary Linear Programming （0-1线性规划）：目标函数为线性，约束为线性，决策变量只含有0-1变量的整数规划问题。线性整数规划都可以转化为0-1线性规划问题。

Mixed-integer Linear Programming （混合整数线性规划）：目标函数为线性，约束为线性，决策变量既含有整数变量也含有连续变量的整数规划问题。

Nonlinear Integer Programming （非线性整数规划）：目标函数和约束中至少有一个是非线性的，决策变量只含有整数变量的整数规划问题。非线性整数规划的难度要比线性整数规划问题难很多。

Nonlinear Binary Programming （0-1非线性规划）：目标函数和约束中至少有一个是非线性的，决策变量只含有0-1变量的整数规划问题。

Mixed-integer Nonlinear Programming （0-1非线性混合整数规划）：目标函数和约束中至少有一个是非线性的，决策变量既含有整数变量也含有连续变量的整数规划问题。

Polynomial Binary Programming （0-1多项式规划）：目标函数和约束中都是多项式函数，决策变量只含有0-1变量的整数规划问题。

5 整数规划问题的挑战性

5.1 计算复杂度

很多整数规划问题往往看上去很简单，其数学模型也不复杂，如背包问题，但求解这类问题往往非常困难。绝大部分的整数规划问题的可行域包含有限多个可行点，一个最简单直观的想法就是穷举所有的可行点。设 X=\left\{ 0,1 \right\}^n 是某个问题的可行域。假设有一台超级计算机，每秒钟可以计算该问题的目标函数 10^8 （1亿次）。

当 n=30 时，我们需要计算时间为 2^{30}/10^8\approx10 秒

当 n=40 时，我们需要计算时间为 2^{40}/10^8\approx10000 秒，约折合3个小时。

当 n=50 时，我们需要计算时间为 2^{50}/10^8\approx1125899906842624 秒，约折合8年半。

当 n=100 时，我们需要计算时间为 2^{100}/10^8 秒，约折合 4\times10^{14} 年。这是什么概念呢？地球诞生到现在大约45亿年左右，而这个计算时间大约是地球诞生到现在的十万倍。

学过一点计算复杂度的童鞋应该知道穷举法在这里实际上是一个具有指数复杂度的算法。要知道即使是 O\left( n^4 \right) 已经是比较恐怖的了，更何况是指数复杂度的算法，从上面的例子中也充分反映出了指数增长的恐怖力量。 因此想要依靠穷举法来求解整数规划对于规模稍微大一点点的问题都无异于是痴人说梦 。

对比整数规划问题和连续优化问题，我们会发现整数规划问题的可行域大多数情况下包含有限多个可行点，而连续优化问题正常情况下可行域包含的可行点是无穷多个。按照常规直观思路来说，从有限个点找出最优点应该比从无限多个点中找出最优点要简单啊。那对比整数规划问题和连续优化，是什么导致了整数规划问题求解的困难呢？

答案是：虽然连续优化问题的可行解有无数多个，但是我们处理连续（可微）的问题有比较成熟和强大的工具即微积分。通过微积分的原理我们往往可以建立出针对连续优化问题的最优性条件，比如KKT条件就是典型的代表。如果说运气好一点我们刚好处理的还是可微的凸优化问题的话，那我们是可以给出全局最优的充要条件的。而在整数规划问题中，问题天生就不可微分就导致了我们无法使用微积分的工具，自然也很难得到最优性条件，同时由于天生是离散的 就注定了肯定也无法满足凸性。

5.2 一些其它方法(Rounding, Heuristic method)

除了上面所述穷举法以外，还有2大类方法容易被想到。1是Round取整，先求解相对应的连续优化问题（舍弃整数约束），然后对所求得的解进行舍入（可能是四舍五入，也可能是其它的舍入方法），得到一个整数解。这个方法有2个问题：1是很难通过舍入得到一个满足约束的可行解；2即使能得到一个可行解，其质量可能往往很差。2是启发式方法(Heuristic method)，其典型代表为贪婪法，例如在求解背包问题中，每次总是先放入价值最大的问题，直到放不进物品为止。启发式方法一般来说计算复杂度很低，可以快速的获得一个可行解。启发式方法很多时候也比较难以保证解的质量。当然在实际问题中 Rounding 和 Heuristic method 的方法也经常和其他的一些方法结合起来使用。当然本笔记的主要内容不是这两种方法，故在此不过多做介绍。

参考文献：

【1】孙小玲，李端，整数规划，科学出版社，2010

【2】Laurence A. Wolsey, Integer Programming, Wily, 2021

【3】Li D, Sun X. Nonlinear integer programming[M]. Springer Science & Business Media, 2006.

【4】Ibaraki T. Integer programming formulation of combinatorial optimization problems[J]. Discrete Mathematics, 1976, 16(1): 39-52.

下一篇笔记快速访问：