【运筹学】整数规划建模技巧

在整数规划建模中，经常会使用到0-1变量来辅助建模，将模型表述为IP模型或BIP模型，下面是一些常见的整数规划建模技巧

使用辅助0-1变量实现“非此即彼”约束

处理方式如下图，M是一个较大的数，当约束的右边加上M时，无论x1和x2在取在取值范围之内的任意值，式子都是成立的，即该约束无效，没有起到限制变量取值的作用。那么只需要让其中一个约束失效即可，通过在两个约束的右边分别添加M y 1和 My2，并让y 1 + y 2 = 1 来实现

保留N个约束中的K个

函数有N个可能的值

固定收费问题

二进制表示法代替整数变量

当一个模型存在大量0-1变量和少量整数变量时，无法直接使用高效的BIP算法，这时候可以使用二进制表示法将原有的整数变量分解成多个0-1变量。当一个整数x xx的范围为[0，u]时，可以参考下图的方式将其分解为N个0-1变量具体的案例如下图所示

分段函数建模

当一个函数是一个分段分数时，即处于不同区域的x xx，其对应的函数表达式f ( x ) f(x)f(x)是不同的，在处理这种问题的时候，建模的方式如下：

具体的案例如下图所示

分段函数建模

如果无法理解上面的模型处理方式的话，可以仔细理解下面的图片