整数规划
>整理自《最优化理论与算法》-陈宝林
除目标函数和约束函数是线性函数外，还要求决策变量取整数值，这类问题称为线性整数规划，剪成为整数规划。其中，如果要求所有变量取整数，则称为纯整数规划；如果要求部分变量取整数值，则称为混合整数规划；如果要求变量只取0或1，则称为0-1规划，一般表示为
\[
\begin{aligned}
min &cx
\\s.t. &Ax=b (P_0)\\&
x\geq 0，x_i为整数，\forall j\in IN
\end{aligned}
\] 其中\(IN\)是取整数的变量的下标记集，\(A\)为\(m\times n\)矩阵，\(c\)是\(n\)维行向量，\(b\)是\(m\)维列向量。 在求解整数规划时，容易想到先解相应的线性规划，得到最优解后再四舍五入，作为整数规划的最优解。然而，这种作法一般不可取，经四舍五入得到的解不一定是整数规划的可行解；即使是可行解，也不一定是整数规划的最优解，例如下列整数规划： \[
\begin{aligned}
min &-13x_1-3x_2\\
s.t. &-8x_1+11x_2\leq 82,\\
&9x_1+2x_2\leq 40,\\
&x_1,x_2\geq 0,x_1,x_2取整数值
\end{aligned}
\] 去掉整数限制后，用单纯形方法求得线性规划的最优解为\((x_1,x_2)=(2.4,9.2)^T\),目标函数最优值\(f=-58.8\)。去掉尾数0.4和0.2后，得到的整数点\((x_1,x_2)=(2,9)\)，不满足第1个约束条件，因此不是整数规划的可行点，当然不是整数规划的最优解。事实上，整数规划存在最优解，其最优解就是\(x_1=4,x_2=2\)，目标函数的最优值\(f=-58\)。因此，一般来说，不宜用线性规划最优解的整数部分作为整数规划的最优解。
##分支定界法 分支定界法是求解整数规划广泛使用的一种方法，计算方法过程涉及三个基本概念。
1. 松弛
将整数规划\((P_0)\)去掉整数性约束，得到线性规划
\[ \begin{aligned} min &cx\\ s.t. &Ax=b, (\overline{P}_0)\\ &x\geq0. \end{aligned} \] 称\(\overline{P}_0\)为整数规划\((P_0)\)的松弛问题。
整数规划\((P_0)\)与它的松弛问题\(\overline{P}_0\)之间有下列关系：
（1）若\(\overline{P}_0\)没有可行解，则\({P}_0\)无可行解；
（2）\(\overline{P}_0\)的最小值给出\({P}_0\)的最小值的下界\(F_l\);
（3）若\({\overline{P}_0}\)的最优解是\(P_0\)的可行解，则也是\(\overline{p}_0\)的最优解。
###2.分解
设整数规划问题\((P_0)\)的可行集为\(S(P_0)\)，子问题\((P_1),...,(P_k)\)的可行集分别为\(S(P_1),...,S(P_k)\)，每个子问题与\((P_0)\)有相同的目标函数，满足条件\(\overset{k}{\underset{i=1}{\bigcup}}S(P_i)=S(P_0)\)及\(S(P_i)\bigcap S(P_j)=\emptyset,\forall i\ne j\)，则称\((P_0)\)分解成子问题\((P_1),...,(P_k)\)之和。
下面给出一种分解方法：
设松弛问题\(\overline{P}_0\)的最优解不满足\((P_0)\)中整数性要求，任选一个不满足整数性要求的变量\(x_j\)，设其取值为\(b_j\)，用\([\overline{b}_j]\)表示小于\(\overline{b}_j\)的最大整数，将约束\(x_i\leq [\overline{b}_j]\)和\(x_j\geq [\overline{b}_j]+1\)分别置于问题\((P_0)\)中，则将\((P_0)\)分解成下列两个子问题： \[ \begin{aligned} min &cx\\ s.t. &Ax=b, (P_1)\\ &x_j\leq [\overline{b}_j],\\ &x\geq 0,x_j为整数，\forall j\in IN \end{aligned} \] 和 \[ \begin{aligned} min &cx\\ s.t. &Ax=b, (P_2)\\ &x_j\geq [\overline{b}_j]+1,\\ &x\geq 0,x_j为整数，\forall j\in IN \end{aligned} \]