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

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)。 , 但我想去掉除法后的小数部分。

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

最优性 - 模型中的微小变化可以轻松计算出最优结果，如果 divVal* res 将变为整数。 Gurobi 不提供小于 约束。此外，当变量的值小于最近整数值的 IntFeasTol 时，在 Gurobi 中认为满足了变量的完整性限制。 IntFeasTol 公差的默认值为 1e-5，可以进一步降低到 1e-9 以获得更好的结果。但是，制作多目标模型会给模型增加额外的复杂性。我不想推荐它。

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

model.setObjective(res, GRB.MINIMIZE)