跳到主要内容

混合整数规划

阐述​

在线性规划的基础上，进一步限制某些变量只能取整数值。这一限制使得问题的难度变大了很多。

max⁡cTx+dTy,s.t. Ax+By≤b,x∈Z+n1,y∈R+n2\max c^Tx+d^Ty,\quad\mathrm{s.t.}~Ax+By\le b,x\in \mathbb Z_+^{n_1},y\in\mathbb R_+^{n_2}

通常，这里的 A,B,b,c,dA, B, b, c, d 等系数也是整数。存在两种特殊情况：

  • 如果 yy 不存在，则也称为整数规划；
  • 如果 xx 都是二值变量，则也称为布尔规划。

建模的注意事项​

MIP 常常使用大量的 0/1 变量，这有的时候看起来非常冗余，但实际上效果不错，而且使得线性的约束比较容易实现。例如

  • 在某个集合里只有一件事情可以发生：∑jxj≤1\sum_j x_j\le 1
  • 某两件事情可以同时发生：xi=xjx_i=x_j
  • 如果 j 发生，那么 i 也必须发生：xj≤xix_j\le x_i
  • 如果 i 不发生，那么 j 为 0，否则无限制：0≤xj≤Mxi0\le x_j\le Mx_i

对于 x≠yx\ne y 的约束，可以引入一个新的二值变量 bb，然后变成

{x≤y−1+bMx≥y+1−(1−b)M\begin{cases} x\le y-1+bM\\ x\ge y+1-(1-b)M \end{cases}

但是它的问题在于，线性规划放松的时候这个约束几乎没有作用了。因此最好还是能重写这个约束。

实例​

性质​

评判建模的优劣​

好的建模应该具有比较好的线性规划放松。定义问题的可行集

T={x:x∈Z+n}∩PT=\{x:x\in Z_+^{n}\}\cap P

考虑 TT 的凸包 CH(T)={x:x=∑iλixi,xi∈T}CH(T)=\{x:x=\sum_i\lambda_ix^i,x^i\in T\}，则这个凸包也是一个多面体，而且这个多面体的极值点就是原始整数规划问题的解。

因此，问题在线性放松之后的多面体应该和这个凸包尽可能接近。

线性放松什么时候是最优的​

考虑 min⁡cTx s.t. Ax=b,x∈Z+n\min c^Tx~\mathrm{s.t.}~Ax=b,x\in\mathbb Z_+^n。如果 A 是完全幺模的（所有子方阵的模都是 ±1\pm 1），那么线性放松之后对应的多面体的极值点一定是整数。此时解线性规划问题就等于解整数规划问题。

切平面法求解​

  1. 将问题放松为线性规划问题并求解
  2. 如果解是整数，那么得到了一个可行解
  3. 如果解不是整数，则增加一个约束，所有整数解应该都满足这个约束，但当前的最优解不满足；然后重新求解线性规划问题。

例如，一个可行的约束是

∑j∈Nxj≥1\sum_{j\in N}x_j\ge1

可行的策略包括 Gomory 切割和分支定界法：

Gomory 切割​

若在线性规划的最优解 x∗x^* 中有 xi∗x^*_i 是非整数，则有

xB+∑j∈Ndjxj=xB∗x_B+\sum_{j\in N}d_jx_j=x_B^* xi+∑j∈Ndijxj=xi∗x_i+\sum_{j\in N}d_{ij}x_j=x_i^*

所以可以引入切割

xi+∑j∈N⌊dij⌋xj≤⌊xi∗⌋x_i+\sum_{j\in N}\lfloor d_{ij}\rfloor x_j\le\lfloor x_i^*\rfloor

分支定界法​

多面体切割​

即新的约束对应于凸包的一个面

覆盖切割​

对应于约束

∑jajxj≤b\sum_ja_jx_j\le b

如果 C⊆{1,⋯ ,n}C\subseteq\{1,\cdots,n\} 满足 ∑j∈C>b\sum_{j\in C}>b，则称它是一个覆盖，那么

∑j∈Cxj≤∣C∣−1\sum_{j\in C}x_j\le|C|-1

是一个合理的切割。其中 CC 也可以扩大到 E(C)=C∪{j∣aj≥ai,∀i∈C}E(C)=C\cup\{j|a_j\ge a_i,\forall i\in C\}。

现在的问题是是否能找到一个这样的切割恰好排除了当前线性放松的最优解。也就是说是否存在 C⊆NC\subseteq N 使得 ∑j∈C(1−xj∗)<1,∑j∈Caj>b\sum_{j\in C}(1-x_j^*)<1,\sum_{j\in C}a_j>b。这就对应于另一个整数规划问题

min⁡∑j∈N(1−xj∗)zj;s.t. ∑j∈Najzj>b,zj∈{0,1}\min\sum_{j\in N}(1-x_j^*)z_j;\quad\mathrm{s.t.}~\sum_{j\in N} a_jz_j>b,z_j\in\{0,1\}

可以用背包方法求解。

相关内容​

参考文献​