我应该在具有完全单模约束矩阵的整数线性程序中包含积分约束吗?

计算科学 优化 线性规划 混合整数规划
2021-11-27 15:21:00

我制定了一个整数线性规划(ILP)。ILP 的约束矩阵是完全单模的。

我应该将它作为没有积分约束的 LP 求解,还是应该保留积分约束并让优化工具箱 (MOSEK) 的混合整数求解器处理这种特殊情况?

1个回答

如果您保留或省略积分约束,只要您的约束矩阵真正完全是单模的,那么对于任何有价值的混合整数线性规划 (MILP,也称为 MIP) 求解器都没有关系。

为了安全起见,请保留积分约束并调用您的 MILP 求解器。任何使用分支定界或分支切割框架的求解器都应该从求解 ILP 的线性规划 (LP) 松弛开始,在这种情况下,它将忽略积分约束。由于您的约束矩阵是完全单模的,因此 LP 松弛的最优解应该满足积分约束,因为这些约束定义的多面体由具有整数坐标的顶点组成。由于松弛的解满足积分约束,MILP 解算器将停止并返回从 LP 松弛获得的解,除了调用 LP 解算器之外几乎没有额外开销(如果您刚刚解决了 LP松弛)。