【整数规划(十)】二次整数规划

您所在的位置：网站首页 › 0-1规划问题的求解方法 › 【整数规划(十)】二次整数规划

【整数规划(十)】二次整数规划

2023-05-03 19:04| 来源: 网络整理| 查看: 265

在上一节笔记中我们讲解了Benders分解，上一节笔记内容如下所示

王源：【整数规划(九)】Benders 分解（理论分析+Python代码实现）

如需购买本笔记对应的中文版教材可点击下面链接：

1、二次整数规划问题简介

我们在前面的笔记中探讨的主要都是线性整数规划问题，当然也确实是因为线性整数规划问题相对来说求解算法比较成熟，而非线性整数规划问题的求解非常困难。二次整数规划问题是非线性整数规划问题中最简单的一类问题，同时也是应用范围最广的一类非线性整数规划问题。如下所示是一般的二次整数规划问题的形式：

$\underset{x\in Z^n}{\min}x^TQx+c^Tx \;\;\;\;(1.1)$

$s.t.\ Ax\le b\;\;\;\;(1.2)$

在上述问题中 $x \in Z^n$ 属于任意整数，为了我们接下来研究问题的方便，我们将二次整数规划问题（1-2）统一均转化为 0-1 二次整数规划问题来讨论。

转化方法1

若 $x\in Z = \{-1, 2, 5, 10\}$ ，我们可以令

$x=-y_1+2y_2+5y_3+10y_4\;\;\;\;(1.3)$

其中 $y_1,y_2,y_3,y_4 \in \{0,1\}$ 。

通过等式(1.3)的等价替换，我们就可以将属于一般整数集的变量等价转化为4个都属于0-1变量。从这个例子中不难看出只要集合元素是有限个的，式(1.3)的转化方式是非常实用的。

转化方法2

若 $x\in Z=\left\{ 0,1,2,3,...,10 \right\}$ ，我们可以令

x=2^0y_1+2^1y_2+2^2y_3+2^3y_4

其中 $y_1,y_2,y_3,y_4 \in \{0,1\}$ 。

从上面的例子可以看出，如果整数集合是一个包含连续整数的集合，那我们在转化的时候可以采用更少的0-1变量就足以等价转化。

到这里我们知道有转化方法1和2，因此本小节只讨论0-1二次整数规划问题，若不是0-1二次整数规划可以由上面的方式转化得到。如下所示是0-1二次整数规划问题：

$\underset{x\in \{0,1\}^n}{\min}x^TQx+c^Tx \;\;\;\;(1.4)$

$s.t.\ Ax\le b\;\;\;\;(1.5)$

进一步我们知道因为 $x\in\{0,1\}^n$ 所以有 x_i=x_i^2 成立。因此（1.4）中的线性项是可以合并到二次项的对角元素里边去的。不妨令 $\hat{Q}:=Q+\text{diag}(c)$ ，优化问题（1.4-1.5）可以等价改写为：

$\underset{x\in \{0,1\}^n}{\min}x^T\hat{Q}x \;\;\;\;(1.6)$

$s.t.\ Ax\le b\;\;\;\;(1.7)$

在一些实际问题中，我们也经常讨论 $x\in\{-1,1\}^n$ 的二次整数规划问题，如下所示：

$\underset{x\in \{-1,1\}^n}{\min}x^T{Q}x \;\;\;\;(1.8)$

$s.t.\ Ax\le b\;\;\;\;(1.9)$

优化问题(1.4-1.5)可以通过进行等价代换 $x_i=\frac{1}{2}\left( y_i+1 \right)$ 转化为优化问题 (1.8-1.9）

在上式中由于 $x\in\{-1,1\}^n$ 所以 x_i^2=1 ，因此目标函数(1.8)中二次项的对角元素可以直接去掉，由此可以将目标函数改写为：

$f\left( x \right) =\sum_{1\le ij\le n}{2q_{ij}x_ix_j}+\sum_{i=1}^n{c_ix_i} \;\;\;\;(1.10)$

可以知道大多数的0-1二次整数规划问题是NP-hard的，同时由于0-1二次整数规划是非线性的问题导致问题的难度大大增加。我们一般采用三种常见的思路来解决0-1二次整数规划问题：

思路1：把0-1二次整数规划问题线性化，转化为线性整数规划问题去求解，这样就避开了非线性的问题。

思路2：直接解0-1二次整数规划问题，采用半定规划的方法来把0-1二次整数规划问题进行松弛求解。

思路3：一些极特殊极简单的0-1二次整数规划问题是多项式可解的，因此可以很快的实现求解。

接下来第2-4章就围绕以上提到的三种求解思路来展开。思路1和思路2是比较常用的，思路3只能适用于特别特殊的一些问题。

2、0-1二次整数规划问题线性化方法

首先给出结论：任意一个0-1二次整数规划问题都可以转化为一个线性整数规划问题。

对于 $\forall x_i,x_j\in\{0,1\}$ ，有 $y_{ij}=x_ix_j$ 当且仅当如下表达式成立

$y_{ij}=\max\{x_i+x_j-1,0\}, \;\; y_{ij}\in\{0,1\}$ 或者

$y_{ij}=\min\{x_i, x_j\}, \;\; y_{ij}\in\{0,1\}$

以上条件不难验证，大家可以自行带入不同的 x_i,x_j 值去验证一下，我们这里就不去一一验证了。

考虑如下无约束0-1二次规划问题：

$\underset{x\in \{0,1\}^n}{\min}x^TQx+c^Tx \;\;\;\;(2.1)$

接下来我们采用上面介绍的线性化的方法，将目标函数(2.1)中的二次项都替换为 $y_{ij}$ ，可得等价的目标函数为：

$\underset{\left( x,y \right)}{\min}\sum_{1\le i j\le n}{2q_{ij}y_{ij}}+\sum_{i=1}^n{c_ix_i}\;\;\;\;(2.2)$

并且根据表达式 $y_{ij}=\max\{x_i+x_j-1,0\}, \;\; y_{ij}\in\{0,1\}$ ，我们还需要添加如下约束，构成新的线性化的优化问题：

$\underset{\left( x,y \right)}{\min}\sum_{1\le i j\le n}{2q_{ij}y_{ij}}+\sum_{i=1}^n{c_ix_i}\;\;\;\;(2.3)$

$y_{ij}\le x_i,\ \ y_{ij}\le x_j,\ \ y_{ij}\ge x_i+x_j-1, \;\; (2.4)$

$y_{ij}\in\{0,1\}, \;\; 0\leq ij \leq n \;\; (2.5)$

$x_i\in\{0,1\}, \;\; i = 1,..,n\;\; (2.6)$

优化问题(2.3-2.6)与(2.1)完全等价，观察优化问题(2.3-2.6)可知所有的目标函数和约束都是线性的。至此我们完成了对0-1二次整数规划问题线性化的过程。同理也可以采用 $y_{ij}=\min\{x_i, x_j\}, \;\; y_{ij}\in\{0,1\}$ 这个等价表达式来进行线性化，这个留作课后作业大家可以试着练习一下。

最后一点，可能有人会产生一个疑问：既然都有通用的方法可以把任意一个0-1二次整数规划问题转化为线性整数规划问题了，那我们研究0-1二次整数规划问题岂不是没有什么意义了？直接研究线性整数规划问题就好了啊。反正它们两个可以完全等价转化啊，干嘛不都把0-1二次整数规划问题转化为简单的线性整数规划问题呢？

想回答这个问题我们还是回到转化后得到的线性整数规划问题中去看，我们观察优化问题(2.3-2.6)发现它比没有线性化之前的问题(2.1)的决策变量的维数多了 $n \times n$ 。原始问题的决策变量就是维，而线性化的过程中我们引入了一个新的变量 $y_{ij}$ ，正因为这个新的变量导致了线性化后的问题(2.3-2.6)维数的增加。

也就是说到这里我们知道虽然问题(2.3-2.6)是线性的，但是其决策变量维数增大了一个数量级。那么在实际的求解过程中到底是问题(2.3-2.6)求解速度快还是问题(2.1)快还真不好确定。因此线性化不是万能的，无脑线性化也可能带来很强的副作用。如何去取舍，如何去trade off是我们要根据具体问题具体而定。

3、一类特殊的无约束0-1二次整数规划问题

前面提到了对于一般的无约束0-1二次规划问题是NP-hard的，那是不是存在一些特殊的0-1二次规划问题是可以多项式时间内求解的呢？答案是有的，本节我们就来介绍一种特殊的可见在多项式时间内求解的0-1二次规划问题。还是先考虑无约束0-1二次规划问题（2.1）的等价形式（2.3-2.6）：

$\underset{\left( x,y \right)}{\min}\sum_{1\le i j\le n}{2q_{ij}y_{ij}}+\sum_{i=1}^n{c_ix_i}\;\;\;\;(2.3)$

$y_{ij}\le x_i,\ \ y_{ij}\le x_j,\ \ y_{ij}\ge x_i+x_j-1, \;\; (2.4)$

$y_{ij}\in\{0,1\}, \;\; 0\leq ij \leq n \;\; (2.5)$

$x_i\in\{0,1\}, \;\; i = 1,..,n\;\; (2.6)$

假设若矩阵中所有非主对角元素的值都非正，即 $q_{ij}\le 0, 1\le ij \le n$ ，则可以去掉约束（2.4）中的 $y_{ij} \ge x_i+x_j-1$ ，可得如下问题：

$\underset{\left( x,y \right)}{\min}\sum_{1\le i j\le n}{2q_{ij}y_{ij}}+\sum_{i=1}^n{c_ix_i}\;\;\;\;(2.7)$

$y_{ij}\le x_i,\ \ y_{ij}\le x_j \;\; (2.8)$

$y_{ij}\in\{0,1\}, \;\; 0\leq ij \leq n \;\; (2.9)$

$x_i\in\{0,1\}, \;\; i = 1,..,n\;\; (2.10)$

优化问题（2.7-2.10）和优化问题（2.3-2.6）最优解是一样的。这是因为约束条件 $y_{ij} \ge x_i+x_j-1$ ，是在 x_i=1,x_j=1 时才成立，即 $y_{ij}\ge1$ 。而由于 $y_{ij}$ 的系数 $q_{ij}$ 非正，因此最优解只可能尽量会取到让 $y_{ij}$ 比较大的值，因此在优化问题（2.7-2.10）中最优解 $y_{ij} \ge1$ 必然自动满足，无需添加到约束中。

我们进一步提取出优化问题（2.7-2.10）的约束矩阵的形式为 $\left( \begin{array}{c} C\\ I\\ \end{array} \right)$ ，其中矩阵表示约束（2.8）和（2.9），矩阵为单位阵表示约束（2.9-2.10）。不难发现矩阵的每一行有一个和一个其它的元素必然为0，根据全单模矩阵的充分条件可以证明优化问题（2.7-2.10）的约束矩阵是全单模的。想复习全单模矩阵的同学参考以下文章（结合全单模矩阵的性质和推论2即可证明出来）：

王源：【整数规划(二)】整数规划中的"简单"问题之全单模矩阵(totally unimodular matrix)

至此，由于优化问题（2.7-2.10）的约束矩阵是全单模的，那么求解其线性松弛问题完全等价于求解原始问题。所以该问题就等价转化为线性规划问题如下所示：

$\underset{\left( x,y \right)}{\min}\sum_{1\le i j\le n}{2q_{ij}y_{ij}}+\sum_{i=1}^n{c_ix_i}\;\;\;\;(2.7)$

$y_{ij}\le x_i,\ \ y_{ij}\le x_j \;\; (2.8)$

$y_{ij}\in \left[ 0,1 \right], \;\; 0\leq ij \leq n \;\; (2.9)$

$x_i\in \left[ 0,1 \right], \;\; i = 1,..,n\;\; (2.10)$

4 总结

非线性的整数规划问题目前来说求解难度非常大，在很多情况之下都是考虑把非线性转化为线性去处理，目前在主流求解器中也是将非线性整数规划问题转化为线性整数规划问题来求解。如果根据特殊问题所具备的特性有针对性的设计非线性整数规划的求解算法确实是有可能超过采用求解器的效果的，但这样的情况就是 case by case 的去考虑了。

至此整数规划的理论部分已经完结了，整数规划笔记系列即将迎来尾声（下一期笔记也就是最后一期笔记我会讲一下关于整数规划求解器的内容，以及如何使用整数规划求解器来求解整数规划问题）。有很多内容是我一开始想写的，但是由于时间精力有限最终删掉了，例如 branch and price，代理拉格朗日松弛算法，各种非光滑优化的方法，TSP问题的列生成求解算法，基于半定规划松弛的二次整数规划问题等等。不过总体来说基本上达到了我一开始的目标，这些高级一点的内容后续有时间再慢慢补充。

【本文地址】

【整数规划(十)】二次整数规划

【整数规划(十)】二次整数规划

今日新闻

推荐新闻