问题标签 [integer-programming]

给定具有 n 个整数变量和 m 个约束的 ILP（整数线性规划）优化，并实现分支定界树以解决典型问题，

1. 树需要多少层（树的高度）才能达到全整数最优解？
2. 该算法需要多少个分支才能达到全整数最优解？

如何将线性规划 (LP) 问题的凸包表示为积分？是否有任何通用技术来执行此操作？

对于给定的 n 和 m，我迭代所有 n × m 部分循环矩阵，其条目为 0 或 1。我想查找是否存在一个矩阵，使得没有两个列的子集给出相同的总和。在这里，当我们添加列时，我们只是按元素进行。我当前的代码通过o​​rtools使用约束编程。但是它没有我想要的那么快。对于 n = 7 和 m = 12，它需要 3 分钟以上，对于 n = 10，m = 18，即使只有 2^18 = 262144 个不同的矩阵需要考虑，它也不会终止。这是我的代码。

这个问题能否解决得足够快，以至于可以解决 n = 10, m = 18？

对于给定的 n 和 m，我迭代所有 n × m 部分循环矩阵，其条目为 0 或 1。我想查找是否存在一个矩阵，使得不存在具有相同总和的列的两个子集。在这里，当我们添加列时，我们只是按元素进行。我当前的代码通过o​​rtools使用约束编程。这是我的代码。

该行values = [-1,0,1]允许解中有任意数量的零。如何指定解决方案中允许的确切数量的零？

我正在闪烁一块板，我需要使用一种算法来最大化像 s = c1*x1 + c2*x2 + c3*x3 + c4*x4 这样的表达式，但要受到一些约束。

例如最大化 p = x+y 服从 x+y <= 2, 3x+y >= 4 最优解： p = 2; x = 1, y = 1

有免费的代码可以在某处使用吗？

谢谢

I'm trying to solve a MIP using the SCIP command line, with the problem input in CPLEX LP format. However, due to large number of variables, the optimization is taking a lot of time. Is there some way to compute the LP Relaxtion solution of the same MIP in SCIP?

Or any other way to get an approximate, somewhat suboptimal solution?

每个人。我为我的研究制定了一些公式。我想问有没有什么工具可以解决这个问题。我调查了一些工具，例如 GLPK、一些 MATLAB 工具箱……但我的公式似乎是非线性的。我在网上找到了一些资料，它是整数规划的一种特殊情况，称为 0-1 整数规划。

我的疑问是：我可以像下面的公式那样将二进制变量放在指数中吗？解决这个问题时是否可以使用“product(pi)”？我调查了一些例子，但我没有发现这两种用法。

变量是 Xc,n,m,s,i。并且，Lc,n, Tmax, Tm, Pm,s,i, Dc,n,k, Bm 都是已知数。

谁能给我一些关于这个问题的建议？谢谢阅读！

我更新了图片，并尝试将 AMPL 语言用于我的公式。

使用逻辑约束进行修改以从指数中删除变量 X：

假设有一个变量 h 已经与一个正整数值相关联。编写必要的代码来计算值小于 h 的完美正方形的数量，从 1 开始。（一个完美的平方是一个整数，如 9 、 16 、 25 、 36 ，它等于另一个整数的平方（在这种情况下分别为 3*3 、 4*4 、 5*5 、 6*6）。）分配总和你计算一个变量 q 例如，如果 h 是 19 ，你会分配 4 给 q 因为有完美的正方形（从 1 开始）小于 h 是：1 、 4 、 9 、 16 。

这是我到目前为止所拥有的，我无法弄清楚我做错了什么。

q = 0

sqrt = int(h ** 0.5)

如果 sqrt ！= h：

h += 1

对于范围内的 i（1，sqrt）：

q += 1

我有一个整数值有界变量，调用它X。（周围某处0<=X<=100）

我想要一个二进制变量，调用它Y，例如Y=1ifX >= A和X <= B, else Y=0。

到目前为止，我想出的最好的是以下（在哪里T<x>引入了二进制变量，M 是一个很大的数）

（换句话说，如果变量分别满足范围的下限和上限，则引入两个为真的二进制变量，并将结果设置为这些变量的二进制乘法）

这...工作，有点，但有几个主要缺陷。特别是，它没有严格定义-即使超出范围Y也可以。1X

那么：有没有更好的方法来做到这一点？特别是：有没有办法严格定义它，或者如果没有，至少可以防止误报？

编辑：澄清：A并且B是变量，而不是参数。

这是我之前关于使用 SCIP 对 MIP 进行 LP 松弛的问题的跟进。

虽然我可以通过简单地将 MIP（以 CPLEX 格式）传递给 SoPlex 来计算 MIP 的 LP 松弛解，但我观察到 SoPlex 所花费的计算时间比使用 SCIP 本身优化 MIP（测试较小的输入）要长）。由于 SCIP 在求解 MIP 之前在内部使用 SoPlex，这怎么可能？此外，我的 LP 松弛结果实际上是给出整数解，并且与 MIP 具有相同的目标值。我在 LP 放松中犯了错误吗？还是我的问题/公式的某些属性？

我指的是求解器打印的总计算时间（不是我自己计算的）。