mathematical-optimization - 整数组合

Question

我想编写一个模块来查找多变量公式的整数组合。例如

  8x + 9y <= 124

该模块将为 x 和 y 返回所有可能的正整数。例如。x=2，y=12。它不一定是 124，可以是小于或等于 124 的任何数字。如果找不到精确解，则必须尽可能接近 124。

我不想用蛮力解决，因为变量的数量可以是任何...（5,10,100，...n）

有什么算法可以解决这个问题吗？

Answer 1

您可以通过将问题重铸为整数规划问题来解决此问题。

将您的方程式重写为约束。

8x + 9y < = 124 作为

8x + 9y + z = 124

请注意，我们引入了一个 slack 变量z。我们希望z尽可能地小，因此使objective functionto be Minimize zAny 求解器将在递增 z 之前尝试 x 和 y 的所有可能整数值。

您的完整 IP 将是：

最小z
8x + 9y + z = 124
x,y,z >=0 和整数

使用任何商业或开源 LP/IP 求解器求解。（R 的 optim 包是一种可能性，Excel Solver 也可以。）

如果出于任何原因，您想要更大或更小，您也可以x使用yobjective function co-efficients.

更一般地，Min Cx x + Cy y + Cz z控制成本参数 Cx Cy 和 Cz 的权重以满足您的需求。

希望有帮助。