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

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

最优性 - 模型的微小变化可以轻松计算出最优结果，在最小化类型 objective 函数中添加 res 或在最大化函数中添加负数将如果 divVal*res 将变为整数，则将其值缩小到较低的一侧。 Gurobi 不提供小于约束。此外，当变量的值小于最近整数值的 IntFeasTol 时，在 Gurobi 中认为满足了对变量的完整性限制。 IntFeasTol 公差的默认值为 1e-5，并且可以进一步降低至 1e-9 以获得更好的结果。然而，制作 multi-objective 模型，给模型增加了额外的复杂性。我不想推荐它。

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

model.setObjective(res, GRB.MINIMIZE)

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

Integer division in Mixed Integer Linear Programming

linear-programming

gurobi

integer-programming

mixed-integer-programming