混合整数规划

阐述

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

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

将问题放松为线性规划问题
如果差于最佳可行解，则剪枝
如果线性规划的解是整数，那么得到了一个可行解
如果线性规划的解不是整数，寻找一个非整数变量，然后求解 $x\le\lfloor f\rfloor$ $x \leq ⌊ f ⌋$ 和 $x\ge\lceil f\rceil$ $x \geq ⌈ f ⌉$ 的两个子问题
1. 这个非整数变量常常是小数部分比较大的

从这个算法可以看出，放松为线性规划的时候必须能比较好地近似问题的最优解。

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

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

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