问题标签 [operations-research]

我在 C++ 中使用 CPLEX 来解决集线器位置问题，即 MIP，并且我最近发现了一组非常精确的输入，CPLEX 认为这些输入是不可行的（即 CPXMIP_INFEASIBLE），即使该问题肯定是可行的。在 MIP Presolve 期间，CPLEX 中的问题似乎出现了分歧；通常在这一点上问题被简化为空问题，但不是在不可行的输入集中。

我发现对输入数据进行几乎任何轻微调整都可以切换 CPLEX 找到解决方案的能力。例如，将 250.242566 更改为 250.242567，或者甚至只是将每个输入值四舍五入到最接近的整数，都会给我一个完全有效的解决方案。

软化我拥有的两个松弛约束也将允许一个解决方案，但考虑到输入数据，这些约束不应该被打破。求解后这些约束变量的值近似为 0，但略为负，例如 -0.7e-10。（这是可疑的，因为值应该大于 0。）

到底是怎么回事？我一无所知。我尝试调整一些与精度相关的 CPLEX 变量（即 CPX_PARAM_NUMERICALEMPHASIS、CPX_PARAM_EPOPT、CPX_PARAM_EPMRK、CPX_PARAM_EPRHS），但没有任何帮助。输入数据本身对精度的要求并不高——输入中的最小值为 1.412，最大值为 1520.984907。

我将不胜感激任何意见或建议！

更新：

我注意到在 MIP 的 Presolve 期间，不可行问题与可行问题有所不同。

检查 CPXgetprestat 是否存在这两个问题，我可以看到这两个问题之间的一个显着区别是在 pcstat 向量中，一个变量不能在不可行集中聚合出来（即，在不可行问题中的值为 0，而在可行问题中为 -4） .

此外，CPXgetprestat 的 ocstat 和 orstat 向量在不可行问题中各有一个非零值（可行问题没有，因为它已被简化为空问题），但我不确定如何处理这两个值。如果 orstat[0] == 7 和 ocstat[0] == 1，这是否意味着在 Presolve 之前的第 7 行和问题的第一个变量中有一些值得注意的地方？我将如何检查这个？

我已经比较了两个问题中 CPXwriteprob 的输出，除了我将输入值更改了 0.0001 以使问题不可行之外，没有什么不同。

我正在使用 AMPL，需要输入具有非负偏差变量 (s+ - s-) 的模型。

一个示例约束是：(x - 5) = (s+ - s-)

我正在比较两个保护区设计工具，即Marxan和ConsNet，它们都使用元启发式算法来解决最小集覆盖问题的一个版本。Marxan 使用模拟退火，ConsNet 使用禁忌搜索。虽然我的背景是生物学，但我认为我能够通过元启发式掌握一些优化的概念。

但是，关于禁忌搜索，我还没有弄清楚两件事。首先是它如何逃避局部最优。我知道它不能逆转它的动作，这会阻止它循环，但我不知道是什么让它在找到它后留下局部最优值。我可以理解模拟退火是如何做到的——它有一定的概率接受一个更糟糕的解决方案，随着时间的推移它会减少，直到它不再接受一个更糟糕的解决方案——但我不知道 TS 是如何做到的。

第二个问题是，在ConsNet手册中，找到如下语句

搜索是完全确定性的，但它可以根据解决方案存档的当前状态或目标的当前状态来决定如何进行

TS 总是确定性的吗？通过阅读一些资料，我了解到移动可能是随机的，就像在 SA 中一样。但是后来有一些论文谈论“确定性禁忌搜索”。确定性禁忌搜索如何知道采取哪些行动以及如何摆脱局部最优？它有时必须接受更糟糕的解决方案，对吧？

提前谢谢了

I've been set the assignment of producing a solution for the capacitated vehicle routing problem using any algorithm that learns. From my brief search of the literature, tabu search variants seem to be the most successful. Can they be classed as learning algorithms though or are they just variants on local search?

我在 cplex 模型（在 Java 中）中定义了一些变量。这些变量有界[0,1]。作为： Model.numVar(0, 1, IloNumVarType.Float, "X(" + i+ ")");

但在最终解决方案中，这些变量的值超出了这个范围。（如-1.7、1.3、...）。请帮助我。

我需要你的帮助来解决这个问题。我有一组任务，每个任务都有其执行时间。我有两种类型的约束。第一种是任务之间的优先关系。第二种约束类型是允许一组任务同时执行。例如：我有一个包含 6 个任务和以下边 (T1,T2)、(T2,T3)、(T4,T3)、(T4,T5) 和 (T6,T5) 的图 G。假设 T1,T4 能够一起执行，T1,T6 也可以执行，但 T4,T6 不能。考虑到每个任务的执行时间。考虑到某些任务的并行执行，如何找到满足任务之间优先关系的调度，同时最小化调度的长度。

我不擅长使用 java 并试图从中获得实现。我正在运行这段代码，但我遇到了很多错误。主要错误

StdOut 无法解析

我正在尝试使用 eclipse 运行 java 代码。我正在运行此代码： http : //algs4.cs.princeton.edu/65reductions/Simplex.java.html 我在第 317/319/322 行出现错误，因为“StdRandom 无法解析”

我正在尝试使用从源节点 s 到目标节点 t 的最大流量来查找k（给定 k）路径，并在图 G =（V，E）中具有一些约束。给定 V 的不同子集 A_i，一个子集可以有一个或多个节点。问题是我只能在一个路径中使用一个子集。我正在使用此代码查找最大流量

如何添加每个子集只能在此代码中使用一个路径（我的意思是，如果我在路径 1 中使用子集 A_1，那么我不能再将 A_1 用于其他路径？我是 java 新手。我试图上传我的问题图片，但我不能，因为我是这方面的新手。谢谢

我正在设计和实现一个 SAT 求解器。如果所有条款都具有以下形式，那就特别好

在文献中，他们使用 CNF 形式，我认为这在实践中对原始现实世界问题的表示效率较低。他们这样做是因为现有的 SAT 求解器可以更好地处理 CNF。然而，这不适用于我的 SAT 求解器，这会给我带来不公平的劣势。有人知道上述形式的任何现实世界实例吗？