问题标签 [integer-programming]

我有一个看起来像这样的整数编程问题，但有更多的变量和约束

它等于 3SAT 问题。没有目标函数，所以任何整数解都是最优的。

现在我可以使用 cplex 找到一个非整数解决方案，并且我想手动添加切割平面。我现在的问题是我不知道第一次放松后如何产生削减。我发现了许多关于 clique cut 等的论文，但它们都是理论上的，并没有展示如何做到这一点的算法。我希望有人能给我一个提示，如何生成这些削减并解决这个问题。

因此，我正在尝试创建具有最佳解决方案的 IP，其中所有变量都是整数，并且都是数字的倍数，例如 3。（因此解决方案中的变量必须是 0、3、6 ,9,12 等）

我在 R 中编码，并且很容易设置解决方案必须为整数的约束（all.int = TRUE），但我不确定如何将其设置为数字的倍数。我必须在 Ax <= b 公式中进行哪些更改？您的帮助将不胜感激！截至目前，我对如何实际做到这一点相当迷茫

我注意到 R 并没有使用我所有的 CPU，我想极大地增加它（高达 100%）。我不希望它只是并行化几个函数；我希望 R 使用更多的 CPU 资源。我正在尝试使用 lp() 函数运行纯 IP 集打包程序。目前，我运行 Windows，我的计算机上有 4 个内核。

我尝试过使用 snow、doParallel 和 foreach（虽然我不知道我真的在用它们做什么）。

在我的代码中，我有这个......

R 卡住并运行 lp() 很长时间。我的 CPU 大约是 25%，但我该如何提高呢？

对于这个问题，区域是Z ^d的子集，由具有整数系数的有限多个线性不等式定义，其中Z ^d是整数的 d 元组的集合。例如，(x, y)非负整数对的集合2x+3y >= 10构成一个区域d=2（非负性只是强加了额外的不等式x>=0和y>=0）。

问题：有没有一种好方法，使用整数编程（或其他东西？）来检查一个区域是否包含在有限多个其他区域的联合中？

我知道一种检查收容的方法，我将在下面描述，但我希望有人能够提供一些改进，因为它不是太有效。

这是我知道的检查收容措施的方法。首先，整数编程库可以直接检查区域是否为空：在整数编程术语中（据我理解），区域的空性对应于模型的不可行性。我使用 gurobi 库编写了一些代码来检查空虚，它在实践中似乎对我关心的那种区域运行良好。

现在假设我们要检查一个区域X是否包含在另一个区域中Y（问题的一个特例）。让Z是X与 的补码的交集Y。thenX包含在Y当且仅当Z为空时。现在，Z它本身不是我所说的区域，而是区域的联合Z_1, ..., Z_n，其中n是用于定义的不等式的数量Y。我们可以Z通过检查 each 是否为空来检查是否Z_1, ..., Z_n为空，我们可以如上所述进行。

一般情况可以用完全相同的方式处理：如果Y是区域的有限联合，Y_1, ..., Y_k那么Z仍然是区域的有限联合Z_1, ..., Z_n，因此我们只需检查每个区域Z_i是否为空。IfY_i由m_i不等式定义 then n = m_1 * m_2 * ... * m_k。

所以总而言之，我们可以将包含问题简化为空性问题，图书馆可以直接解决这个问题。问题是我们可能必须解决非常大量的空性问题来解决包含问题（例如，如果每个Y_i不等式仅由两个不等式定义，则n = 2^k随着 指数增长k），因此这可能需要很多时间。

我希望使用整数规划来枚举帕累托最优解。我想实现一个算法，使用 gurobi 或类似的单目标整数规划求解器来做到这一点，但我不知道任何这样的算法。有人可以提出一个枚举有效边界的算法吗？

我正在尝试解决可能有多个答案的 MILP（所有答案都为目标函数提供相同的值）。基于分支定界的算法是否能够找到所有解决方案？

是否可以使用 MATLAB（例如使用 intlinprog）找到此类 MILP 的所有解决方案。

谢谢你。

我正在尝试使用 gurobi 和 networkx 将其编码到 python 中，

S >= quicksum(uij for j in N) 对于 N 中的每个 i

我的代码是

问题是我得到关键错误（1,1），这是有道理的，因为我没有优势（1,1）

但我确实想为节点中的每个 i 求和，即连接到特定节点 i 的所有 j 的所有 uij 的总和。

这不是度数问题，它实际上是对连通分量求和，因此如果 i 和 j 之间存在路径，则 uij 为 1。我已将此编码为关键节点检测问题。

请帮忙！谢谢！

问题：

最小化x1+x2+...+xn

已知k1*x1+k2*x2+...kn*xn = T

k1,k2,...,kn并且T是已知整数并且 > 0

k1 > k2 > k3 > ... > kn

所有的 x 也是整数并且 >= 0

找到所有的 x

我试图使用 Rglpk 和 Glpk。但我找不到只有一行矩阵的例子。这是整数编程吗？它可以解决吗？非常感谢。

我写的一些 Ruby 代码：

我建立了一个混合整数规划模型，我想定义一个决策变量的最小值和 mzximum。

例如，假设 C={19, 20, 30}

我想将 C_early 定义为 19，将 C_late 定义为 30。然后我想最小化差异。C_late 部分是使用辅助约束成功定义的，但是，我认为我在 min 部分缺少一些东西。

这是我的代码：

最后三个约束与我的问题有关。

数据集示例：

我知道我必须对 min 约束使用 big m 方法，但是，我不确定如何谢谢，

我有一张图片，我想找到面积最小的作物，同时保留一定比例的边缘能量。

我对此的看法是将其表述为一个优化问题，并让 scipy 的约束优化器解决它[代码见下文]。这显然是有问题的，因为它是一个整数问题（裁剪将左上角和右下角的整数坐标作为参数）。并且确实fmin_cobyla在大约 20 秒的运行时间后未能找到解决方案，而fmin_slsqp在一次迭代后失败，“ LSQ 子问题中的奇异矩阵 C（退出模式 6） ”。

关于我如何解决这个问题的任何想法？是否有一个处理图像优化问题的库？