2.4.3　计数问题

本节探讨的是计数问题，具体案例如下：

【例2.4】考虑有m（m≥2）个连续类型（或整数类型）决策变量x1，x2，…，xm，要求统计出这些决策变量取值落在实数区间［a，b］的个数。

为了更容易地理清建模思路，我们以x1为例绘制一个示意图，如图2.1所示。x1取值落在区间［a，b］的充分必要条件是：x1≥a且x1≤b。为了标识x1是否同时满足以上两个条件，需要引入额外的辅助变量分别标识x1≥a和x1≤b是否成立。

引入3组0-1变量ui、vi和zi（∀i=1，…，m），其具体作用如下：

最终用于统计次数的变量实际上是zi。为了保证zi的取值符合预期，需要用约束实现下面6个逻辑条件：

（1）若xi≥a，则ui=1。

（2）若xi＜a，则ui=0。

（3）若xi≤b，则vi=1。

（4）若xi＞b，则vi=0。

（5）若ui+vi=2，则zi=1。

（6）若ui+vi≤1，则zi=0。

逻辑条件（1）的建模。将其转换为逆否命题：若ui=0，则xi＜a（转换为xi+ϵ≤a）。将其转换为约束即为xi+ϵ-a-Mui≤0，其中，ϵ为非常小的正数，M为一个足够大的正数，下同。

逻辑条件（2）的建模。将其转换为逆否命题：若ui=1，则xi≥a。将其转换为约束即为a-xi-M（1-ui）≤0。

逻辑条件（3）和（4）的建模类似于前两个逻辑条件，这里直接给出结果。逻辑条件（3）和（4）对应的约束分别为b-xi+ϵ-Mvi≤0和xi-b-M（1-vi）≤0。

逻辑条件（5）的建模。该条件实际上是一个逻辑与运算，参照上文介绍的逻辑与运算的建模方法，该条件可被建模为ui+vi-1≤zi。

逻辑条件（6）的建模。将其转换为逆否命题：若zi=1，则ui+vi＞1（等价于ui+vi≥2）。将其转换为约束即为2-ui-vi-M（1-zi）≤0。由于M是2-ui-vi的上界，因此可取M=2，约束可变为2-ui-vi-2（1-zi）≤0。进一步简化，得到2zi≤ui+vi。

实际上，zi和ui、vi的关系还可以刻画为zi=uivi。该等式虽然是二次表达式，但是由于等式右端是两个0-1变量相乘，因此可以将其进行等价线性化，具体方法见第3章。

综上，本节的计数问题的完整模型如下：

下面以一个简单算例来测试上述模型。给定数字集合X=｛-1，2，5，8，11，14，17，20｝，计算出X中元素落在区间［0，10］内的个数。注意，在实际案例中，数字集合X中的元素的具体取值可能是变量，并不是提前获知的。下面使用Python分别调用COPT和Gurobi求解上述模型。这里仅展示Python调用COPT的完整代码，Gurobi版本的代码见本书配套电子资源2-4。

求解结果为3，这是正确的，也验证了上述模型的正确性。