混合整数线性规划中的整数除法

Question

什么是MILP程序中编码整数除法的求解器友好方式？目前我正在使用以下编码（在Gurobi python中），它可能不完全正确，也不是最优的。

# res is an integer variable in the solver
# val is an integer variable in the solver
# divVal is just a python variable, a constant for solver
offset = 0.999
divRes = val / divVal
model.addConstr(divRes - offset <= res)
model.addConstr(res <= divRes)

上面的编码基本上意味着res应该被分配一个值在divRes-offset和divRes之间，因为offset是0.999，所以在该范围内只应有1个整数，并且求解器被强制将其分配给res。是否有更好（更快）的编码方法？

编辑：通过整数除法，我指的是除法的结果是整数。如果除法后有任何小数部分，我想舍弃它并向下取整结果，该结果将存储在res中。我想做的本质上是将数字向左移动一些x位。在MILP求解器中，这归结为将数字除以(1 << x)，但是在除法后有一些小数部分，我想摆脱它们。

- Samvid Mistry

Answer 1

model.addRange(val - divVal*res, 0, 0.99999, name="Range")

我更倾向于只使用上述提到的范围约束。将更紧密的边界（给定范围中仅有整数，我们需要）直接纳入模型中不仅可以改善数值行为，而且还可以加速优化过程（因为gurobi使用分支定界算法来获得解决方案）https://www.gurobi.com/documentation/9.1/refman/improving_ranges_for_varia.html

< p > 最优性 - 模型的微小变化可以轻松计算出最优结果，将 res 添加到最小化类型的目标函数中，或在最大化函数中添加其负值，如果 divVal * res 变为整数，则会使其值在较低的一侧缩小。Gurobi 不提供小于约束条件。此外，在 Gurobi 中，对变量的整数限制被认为是满足的，当变量的值小于距离最近的整数值的 IntFeasTol。IntFeasTol 容差的默认值为 1e-5，可以进一步降低至 1e-9 以获得更好的结果。然而，创建多目标模型会增加模型的复杂性。我不建议这样做。

model.addRange(val - divVal*res, 0, 1, name="范围")

model.setObjective(res, GRB.MINIMIZE)

- Aaditya Bhardwaj

---

我不理解最优性部分。我的终极目标不是获得res的值，它只是一个更大模型中的变量。我猜这对我的情况不适用？或者你是在说我应该将这个目标作为多目标的一部分添加进去，这样会有助于求解器的性能吗？ - Samvid Mistry

制作多目标模型将使计算变慢。在这种情况下，我更倾向于增加上限值，例如0.999999999。然而，这将提供准确（无法超过Gurobi的公差）的结果。 - Aaditya Bhardwaj