02. 整数规划

定义

规划中的变量 (部分或全部) 限制为整数时，称为整数规划。

若在线性规划模型中变量限制为整数，则称为整数线性规划。

分类：

变量全限制为整数时，称纯 (完全) 整数规划；
变量部分限制为整数时，称混合整数规划。

求解方法

分枝定界法

思路：将可行解空间分割为越来越小的子集，对每个子集内的解集计算目标下界，超出已知可行解集目标值的子集不再进一步分枝。

步骤

分枝：在问题中任选一个不符合整数条件的变量，取小于的最大整数和大于的最小整数，构造新的约束条件将约束条件加入原问题，构造两个新问题；
定界：对于新问题的解，从符合整数条件的分枝中，找出目标函数值最大作为新的下界；
比较与剪枝：若分枝的解小于下界，则去除该分枝；若分枝的解大于下界且不符合整数条件，重复步骤 1，直到解等于下界。

例子

1. 求解与定界

记问题，首先不考虑整数限制，得

而时，则为的下界，记。

即

2. 分枝再求解

对任选一个进行分枝，设选分枝，有：

对于，构成新的约束条件，记问题：解得对于，构成新的约束条件，记问题：解得

3. 再定界

的解均不满足整数条件，下界不变，即

两个问题的解均不等于下界，继续分枝。

4. 再分枝再求解

对问题再分枝，由于满足整数条件，选：分别构成问题。

最优解分别为：

同样对问题再分枝，有：

无可行解

5. 再定界

中，满足整数条件，作为下界，即其余分枝解均小于下界，被剪枝，保留。

而满足整数条件，无需继续分枝，作为最终解，即

过滤隐枚举法

思路：排除掉不可能的变量取值集合，只检查变量取值组合的一部分，就能求到问题的最优解。

过滤隐枚举法是解 0-1 型整数规划的一种解法。

步骤

试探求一个可行解，代入得；
增加约束条件；
继续试探求解并更新约束条件，从而抬高过滤门槛，减少计算量。

蒙特卡洛法

对可行解集进行随机取样，选取部分解集代入计算。

Python 代码

利用 cvxpy 包可以直接进行整数规划的求解。

对于问题：

代码如下：

# %%

import numpy as np
import cvxpy as cp

# %%

# 目标函数形如 min c^T·x
c = np.array([40, 90])

# 约束形如 a·x <= b
a = np.array([[9, 7],
              [-7, -20]])
b = np.array([56, -70])

# 两个整数决策变量
x = cp.Variable(2, integer=True)

# 目标函数
z = cp.Minimize(c * x)

# 约束条件
cons = [a * x <= b,
        x >= 0]

# 问题模型
prob = cp.Problem(z, cons)
prob.solve(solver='GLPK_MI', verbose=True)

# %%

print('best z =', prob.value)
print('best x =', x.value)

输出：

1 2	best z = 350.0 best x = [2. 3.]

因此有最优解时，取得最小值 350.

吴世涵的博客

【数学建模笔记 02】数学建模的整数规划