问题标签 [integer-programming]

什么确定性算法适合以下资源分配/调度问题？

考虑一组玩家：P1、P2、P3 和 P4。每个玩家从蜂窝塔接收数据（例如在无线网络中）。塔在 1 秒内传输数据。有5个街区。可以安排每个玩家在任意数量的块中接收数据。

现在，每个块中接收的数据量是一个常数（C）除以同一块中调度的其他玩家的数量（因为必须共享带宽）。贪婪的方法会将每个玩家分配到每个块，但随后每个块接收的数据会减少。

我们如何才能找到玩家对时间块的分配，从而使网络传递的数据量最大化？我已经在这个问题上尝试了许多启发式方法（遗传算法，Sim Anneal）并且它们运行良好。但是，我想解决最佳时间表。

I'm trying to solve the simple example found in https://en.wikipedia.org/wiki/Integer_programming#Example using the CVXOPT library on Python 2.7 ; The optimal answers are either (1,2) or (2,2). I'm getting (0.0 , 0.0). What am I doing wrong in the code below ? Thanks !

在解决具有许多（不断变化的）约束或目标组件的问题时，很难以格式化方程的形式为其创建文档。

有没有一种简单的方法可以从 LP/MPS 文件自动创建格式化方程（LaTeX、PDF、..）？

这对我会有很大的帮助。

提前致谢！

我有一个 FiniteSet 和一个符号，我想将它与一个 Relation 关联，这样该符号就在 FiniteSet 中，sympy 可以吗？symbol in FiniteSet不返回表达式，而是计算它：

编辑：感谢 ohe 告诉我关于Contains. 我更新了我的 sympy 版本，顺便说一下，FinitSet 的语法在更新中也发生了变化。我举了一个我希望在记录中首先工作的小例子：

我正在研究算法，最近发现了一个有趣的挑战。

它会给我们一些行/列，我们的任务是用整数 1~N 填充表格，它只显示一次，并且它们的行和列总和等于给定的行/列。

挑战简单示例：

谢谢

我在 Visual Studio 2015 中从 C# 调用 cplex。

我检查了 Cplex.IntParam.WorkDir 的值（使用 cplex.GetParam(Cplex.IntParam.WorkDir)），它给了我以下值“。\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0"

然后我执行以下代码行，

现在，Cplex.IntParam.WorkDir 的值是“C:\TEMP\cplex\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0 \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\ 0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\ 0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"

当我调用 cplex.Solve() 时，在构建模型之后，即使我将 WorkMem 的值设置为极低的值，节点文件实际上也不会在目录“D:\TEMP\cplex”中创建128 MB。尽管 Cplex.IntParam.NodeFileInd 的值设置为 3，但内存消耗扩展到我的 RAM 容量，然后出错。

我试着写出模型文件，看看它会写在哪里，它在项目的默认目录中。

有谁知道为什么没有创建节点文件？为什么 IntParam.WorkDir 会给出这个值，以及当内存不足时如何强制 cplex 创建节点文件？

这个问题可能很愚蠢，但它确实让我困惑了很长时间。

我阅读了很多关于无线传感器网络的论文。许多研究人员将他们的问题建模为 ILP 的形式。但是，ILP 是 NP 完全的，因此它对于解决问题效率不高。

那么为什么人们将他们的问题写成 ILP 的形式呢？他们这样做是为了让他们的问题清晰易懂吗？还是我在理解 ILP 和 NPC 之间的关系时犯了一些错误？

非常感谢您能帮我解决这个问题。

在 Gurobi 中，是否可以在不实际优化问题的情况下查看一组约束和变量是否可行？似乎如果目标是一个常数，Gurobi 仍然会进行大量繁重的计算来找到我不需要的最佳解决方案！

我的问题总结：
我有一个像这样的Petri网（ILP）的线性方程组：

这些问题可能有更多的变量和约束。方程永远不是不等式。它也可以最大化或最小化。

我检查了一些关于所有整数问题的示例，但它们无法处理变量多于约束或其他方式的系统。

在像lp_solve这样的软件中，我可以处理这些问题，但对于这个解决方案，我必须处理许多 .dll 文件和包装器的东西。

我正在寻找 Java 解决方案或简单的嵌入库。我真的很感谢你的帮助，因为我有点卡住了。

我正在实现一个分支和价格（或列生成）算法。我在优化期间生成的变量（或列）的成本为 offset。例如，如果我想引入一个新变量xi，它既有一个成ci比例的成本系数，xi又有一个常数成本ci'：

总成本 = 所有 i 的总和 (ci * xi + ci')

我的变量xi是连续的。

我该如何处理？

是否有必要重新表述问题以使变量的相关成本没有抵消？例如，为了保证列生成导致最优解。

我的第一个想法是成对生成变量：原始xi变量和关联的二进制变量bi。然后添加附加约束bi = 0ifxi = 0和bi = 1if xi > 0。这是一个合理的方法吗？除了引入二进制变量之外，它还有什么缺点？